Return to maptable.h CVS log

Up to [Apple XNU] / GNUtools / debug / Common / objc

Annotation of GNUtools/debug/Common/objc/maptable.h, revision 1.1.1.1

1.1       root        1: /*     maptable.h
                      2:        Scalable hash table of mappings.
                      3:        Bertrand, August 1990
                      4:        Copyright 1990 NeXT, Inc.
                      5: */
                      6: 
                      7: #ifndef _OBJC_MAPTABLE_H_
                      8: #define _OBJC_MAPTABLE_H_
                      9: 
                     10: #import <objc/objc.h>
                     11: #import <objc/zone.h>
                     12: 
                     13: /***************       Definitions             ***************/
                     14: 
                     15:     /* 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.
                     16:     NX_MAPNOTAKEY (-1) is used internally as a marker, and therefore keys must always be different from -1.
                     17:     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. */
                     18: 
                     19: typedef struct _NXMapTable {
                     20:     /* private data structure; may change */
                     21:     const struct _NXMapTablePrototype  *prototype;
                     22:     unsigned   count;
                     23:     unsigned   nbBuckets;
                     24:     void       *buckets;
                     25: } NXMapTable;
                     26: 
                     27: typedef struct _NXMapTablePrototype {
                     28:     unsigned   (*hash)(NXMapTable *, const void *key);
                     29:     int                (*isEqual)(NXMapTable *, const void *key1, const void *key2);
                     30:     void       (*free)(NXMapTable *, void *key, void *value);
                     31:     int                style; /* reserved for future expansion; currently 0 */
                     32: } NXMapTablePrototype;
                     33:     
                     34:     /* invariants assumed by the implementation: 
                     35:        A - key != -1
                     36:        B - key1 == key2 => hash(key1) == hash(key2)
                     37:            when key varies over time, hash(key) must remain invariant
                     38:            e.g. if string key, the string must not be changed
                     39:        C - isEqual(key1, key2) => key1 == key2
                     40:     */
                     41: 
                     42: #define NX_MAPNOTAKEY  ((void *)(-1))
                     43: 
                     44: /***************       Functions               ***************/
                     45: 
                     46: extern NXMapTable *NXCreateMapTableFromZone(NXMapTablePrototype prototype, unsigned capacity, NXZone *zone);
                     47: extern NXMapTable *NXCreateMapTable(NXMapTablePrototype prototype, unsigned capacity);
                     48:     /* capacity is only a hint; 0 creates a small table */
                     49: 
                     50: extern void NXFreeMapTable(NXMapTable *table);
                     51:     /* call free for each pair, and recovers table */
                     52:        
                     53: extern void NXResetMapTable(NXMapTable *table);
                     54:     /* free each pair; keep current capacity */
                     55: 
                     56: extern BOOL NXCompareMapTables(NXMapTable *table1, NXMapTable *table2);
                     57:     /* Returns YES if the two sets are equal (each member of table1 in table2, and table have same size) */
                     58: 
                     59: extern unsigned NXCountMapTable(NXMapTable *table);
                     60:     /* current number of data in table */
                     61:        
                     62: extern void *NXMapMember(NXMapTable *table, const void *key, void **value);
                     63:     /* return original table key or NX_MAPNOTAKEY.  If key is found, value is set */
                     64:        
                     65: extern void *NXMapGet(NXMapTable *table, const void *key);
                     66:     /* return original corresponding value or NULL.  When NULL need be stored as value, NXMapMember can be used to test for presence */
                     67:        
                     68: extern void *NXMapInsert(NXMapTable *table, const void *key, const void *value);
                     69:     /* override preexisting pair; Return previous value or NULL. */
                     70:        
                     71: extern void *NXMapRemove(NXMapTable *table, const void *key);
                     72:     /* previous value or NULL is returned */
                     73:        
                     74: /* 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:
                     75:     unsigned   count = 0;
                     76:     const MyKey        *key;
                     77:     const MyValue      *value;
                     78:     NXMapState state = NXInitMapState(table);
                     79:     while(NXNextMapState(table, &state, &key, &value)) {
                     80:        count++;
                     81:     }
                     82: */
                     83: 
                     84: typedef struct {int index;} NXMapState;
                     85:     /* callers should not rely on actual contents of the struct */
                     86: 
                     87: extern NXMapState NXInitMapState(NXMapTable *table);
                     88: 
                     89: extern int NXNextMapState(NXMapTable *table, NXMapState *state, const void **key, const void **value);
                     90:     /* returns 0 when all elements have been visited */
                     91: 
                     92: /***************       Conveniences            ***************/
                     93: 
                     94: extern const NXMapTablePrototype NXPtrValueMapPrototype;
                     95:     /* hashing is pointer/integer hashing;
                     96:       isEqual is identity;
                     97:       free is no-op. */
                     98: extern const NXMapTablePrototype NXStrValueMapPrototype;
                     99:     /* hashing is string hashing;
                    100:       isEqual is strcmp;
                    101:       free is no-op. */
                    102: extern const NXMapTablePrototype NXObjectMapPrototype;
                    103:     /* for objects; uses methods: hash, isEqual:, free, all for key. */
                    104: 
                    105: #endif /* _OBJC_MAPTABLE_H_ */

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.