darling-objc4/runtime/maptable.h

/*
 * Copyright (c) 1999-2003, 2006-2007 Apple Inc.  All Rights Reserved.
 * 
 * @APPLE_LICENSE_HEADER_START@
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */
/*	maptable.h
	Scalable hash table of mappings.
	Bertrand, August 1990
	Copyright 1990-1996 NeXT Software, Inc.
*/

#ifndef _OBJC_MAPTABLE_H_
#define _OBJC_MAPTABLE_H_

#ifndef _OBJC_PRIVATE_H_
#   define OBJC_MAP_AVAILABILITY \
    OBJC_OSX_DEPRECATED_OTHERS_UNAVAILABLE(10.0, 10.1, "NXMapTable is deprecated")
#else
#   define OBJC_MAP_AVAILABILITY
#endif

#include <objc/objc.h>

__BEGIN_DECLS

/***************	Definitions		***************/

    /* This module allows hashing of arbitrary associations [key -> value].  Keys and values must be pointers or integers, and client is responsible for allocating/deallocating this data.  A deallocation call-back is provided.
    NX_MAPNOTAKEY (-1) is used internally as a marker, and therefore keys must always be different from -1.
    As well-behaved scalable data structures, hash tables double in size when they start becoming full, thus guaranteeing both average constant time access and linear size. */

typedef struct _NXMapTable {
    /* private data structure; may change */
    const struct _NXMapTablePrototype	* _Nonnull prototype;
    unsigned	count;
    unsigned	nbBucketsMinusOne;
    void	* _Nullable buckets;
} NXMapTable OBJC_MAP_AVAILABILITY;

typedef struct _NXMapTablePrototype {
    unsigned	(* _Nonnull hash)(NXMapTable * _Nonnull,
                                  const void * _Nullable key);
    int		(* _Nonnull isEqual)(NXMapTable * _Nonnull,
                                     const void * _Nullable key1,
                                     const void * _Nullable key2);
    void	(* _Nonnull free)(NXMapTable * _Nonnull,
                                  void * _Nullable key,
                                  void * _Nullable value);
    int		style; /* reserved for future expansion; currently 0 */
} NXMapTablePrototype OBJC_MAP_AVAILABILITY;
    
    /* invariants assumed by the implementation: 
	A - key != -1
	B - key1 == key2 => hash(key1) == hash(key2)
	    when key varies over time, hash(key) must remain invariant
	    e.g. if string key, the string must not be changed
	C - isEqual(key1, key2) => key1 == key2
    */

#define NX_MAPNOTAKEY	((void * _Nonnull)(-1))

/***************	Functions		***************/

OBJC_EXPORT NXMapTable * _Nonnull
NXCreateMapTableFromZone(NXMapTablePrototype prototype,
                         unsigned capacity, void * _Nullable z)
    OBJC_MAP_AVAILABILITY;

OBJC_EXPORT NXMapTable * _Nonnull
NXCreateMapTable(NXMapTablePrototype prototype, unsigned capacity)
    OBJC_MAP_AVAILABILITY;
    /* capacity is only a hint; 0 creates a small table */

OBJC_EXPORT void
NXFreeMapTable(NXMapTable * _Nonnull table)
    OBJC_MAP_AVAILABILITY;
    /* call free for each pair, and recovers table */
	
OBJC_EXPORT void
NXResetMapTable(NXMapTable * _Nonnull table)
    OBJC_MAP_AVAILABILITY;
    /* free each pair; keep current capacity */

OBJC_EXPORT BOOL
NXCompareMapTables(NXMapTable * _Nonnull table1, NXMapTable * _Nonnull table2)
    OBJC_MAP_AVAILABILITY;
    /* Returns YES if the two sets are equal (each member of table1 in table2, and table have same size) */

OBJC_EXPORT unsigned
NXCountMapTable(NXMapTable * _Nonnull table)
    OBJC_MAP_AVAILABILITY;
    /* current number of data in table */
	
OBJC_EXPORT void * _Nullable
NXMapMember(NXMapTable * _Nonnull table, const void * _Nullable key,
            void * _Nullable * _Nonnull value) OBJC_MAP_AVAILABILITY;
    /* return original table key or NX_MAPNOTAKEY.  If key is found, value is set */
	
OBJC_EXPORT void * _Nullable
NXMapGet(NXMapTable * _Nonnull table, const void * _Nullable key)
    OBJC_MAP_AVAILABILITY;
    /* return original corresponding value or NULL.  When NULL need be stored as value, NXMapMember can be used to test for presence */
	
OBJC_EXPORT void * _Nullable
NXMapInsert(NXMapTable * _Nonnull table, const void * _Nullable key,
            const void * _Nullable value)
    OBJC_MAP_AVAILABILITY;
    /* override preexisting pair; Return previous value or NULL. */
	
OBJC_EXPORT void * _Nullable
NXMapRemove(NXMapTable * _Nonnull table, const void * _Nullable key)
    OBJC_MAP_AVAILABILITY;
    /* previous value or NULL is returned */
	
/* Iteration over all elements of a table consists in setting up an iteration state and then to progress until all entries have been visited.  An example of use for counting elements in a table is:
    unsigned	count = 0;
    const MyKey	*key;
    const MyValue	*value;
    NXMapState	state = NXInitMapState(table);
    while(NXNextMapState(table, &state, &key, &value)) {
	count++;
    }
*/

typedef struct {int index;} NXMapState OBJC_MAP_AVAILABILITY;
    /* callers should not rely on actual contents of the struct */

OBJC_EXPORT NXMapState
NXInitMapState(NXMapTable * _Nonnull table)
    OBJC_MAP_AVAILABILITY;

OBJC_EXPORT int
NXNextMapState(NXMapTable * _Nonnull table, NXMapState * _Nonnull state,
               const void * _Nullable * _Nonnull key,
               const void * _Nullable * _Nonnull value)
    OBJC_MAP_AVAILABILITY;
    /* returns 0 when all elements have been visited */

/***************	Conveniences		***************/

OBJC_EXPORT const NXMapTablePrototype NXPtrValueMapPrototype
    OBJC_MAP_AVAILABILITY;
    /* hashing is pointer/integer hashing;
      isEqual is identity;
      free is no-op. */
OBJC_EXPORT const NXMapTablePrototype NXStrValueMapPrototype
    OBJC_MAP_AVAILABILITY;
    /* hashing is string hashing;
      isEqual is strcmp;
      free is no-op. */
OBJC_EXPORT const NXMapTablePrototype NXObjectMapPrototype
    OBJC2_UNAVAILABLE;
    /* for objects; uses methods: hash, isEqual:, free, all for key. */

__END_DECLS

#endif /* _OBJC_MAPTABLE_H_ */