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     ! 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.