This is haptable.h in view mode; [Download] [Up]

/*	haptable.h
	Scalable hash table of happings.
	Bertrand, August 1990
	Copyright 1990 NeXT, Inc.


#import <objc/objc.h>
#import <objc/zone.h>

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

    /* This module allows hashing of arbitrary associations [key -> key].  Keys must be pointers or integers, and client is responsible for allocating/deallocating this data.  A deallocation call-back is provided.
    NX_HAPNOTAKEY (-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 _NXHapTable {
    /* private data structure; may change */
    const struct _NXHapTablePrototype	*prototype;
    unsigned	count;
    unsigned	nbBuckets;
    void	*buckets;
} NXHapTable;

typedef struct _NXHapTablePrototype {
    unsigned	(*hash)(NXHapTable *, const void *key);
    int		(*isEqual)(NXHapTable *, const void *key1, const void *key2);
    void	(*free)(NXHapTable *, void *key);
    int		style; /* reserved for future expansion; currently 0 */
} NXHapTablePrototype;
    /* 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_HAPNOTAKEY	((void *)(-1))

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

extern NXHapTable *NXCreateHapTableFromZone(NXHapTablePrototype prototype, unsigned capacity, NXZone *zone);
extern NXHapTable *NXCreateHapTable(NXHapTablePrototype prototype, unsigned capacity);
    /* capacity is only a hint; 0 creates a small table */

extern void NXFreeHapTable(NXHapTable *table);
    /* call free for each pair, and recovers table */
extern void NXResetHapTable(NXHapTable *table);
    /* free each pair; keep current capacity */

extern BOOL NXCompareHapTables(NXHapTable *table1, NXHapTable *table2);
    /* Returns YES if the two sets are equal (each member of table1 in table2, and table have same size) */

extern unsigned NXCountHapTable(NXHapTable *table);
    /* current number of data in table */
extern void *NXHapMember(NXHapTable *table, const void *key);
    /* return original table key or NX_HAPNOTAKEY.  */
extern void *NXHapGet(NXHapTable *table, const void *key);

extern void *NXHapInsert(NXHapTable *table, const void *key);
    /* override preexisting pair; Return previous key or NULL. */
extern void *NXHapRemove(NXHapTable *table, const void *key);
    /* previous key 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;
    NXHapState	state = NXInitHapState(table);
    while(NXNextHapState(table, &state, &key)) {

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

extern NXHapState NXInitHapState(NXHapTable *table);

extern int NXNextHapState(NXHapTable *table, NXHapState *state, const void **key);
    /* returns 0 when all elements have been visited */

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

extern const NXHapTablePrototype NXPtrValueHapPrototype;
    /* hashing is pointer/integer hashing;
      isEqual is identity;
      free is no-op. */
extern const NXHapTablePrototype NXStrValueHapPrototype;
    /* hashing is string hashing;
      isEqual is strcmp;
      free is no-op. */
extern const NXHapTablePrototype NXObjectHapPrototype;
    /* for objects; uses methods: hash, isEqual:, free, all for key. */

#endif /* _OBJC_HAPTABLE_H_ */

These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.