home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.0 / NeXTSTEP3.0.iso / NextDeveloper / Headers / objc / hashtable.h < prev    next >
Encoding:
C/C++ Source or Header  |  1992-02-08  |  8.4 KB  |  189 lines
  1. /*
  2.     hashtable.h
  3.     Scalable hash table.
  4.     Copyright 1989 NeXT, Inc.
  5. */
  6.  
  7. #ifndef _OBJC_LITTLE_HASHTABLE_H_
  8. #define _OBJC_LITTLE_HASHTABLE_H_
  9.  
  10. #import <objc/objc.h>
  11. #import <objc/zone.h>
  12.  
  13. /*************************************************************************
  14.  *    Hash tables of arbitrary data
  15.  *************************************************************************/
  16.  
  17. /* This module allows hashing of arbitrary data.  Such data must be pointers or integers, and client is responsible for allocating/deallocating this data.  A deallocation call-back is provided.
  18. The objective C class HashTable is prefered when dealing with (key, values) associations because it is easier to use in that situation.
  19. 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. */
  20.  
  21. typedef struct {
  22.     unsigned    (*hash)(const void *info, const void *data);
  23.     int        (*isEqual)(const void *info, const void *data1, const void *data2);
  24.     void    (*free)(const void *info, void *data);
  25.     int        style; /* reserved for future expansion; currently 0 */
  26.     } NXHashTablePrototype;
  27.     
  28. /* the info argument allows a certain generality, such as freeing according to some owner information */
  29. /* invariants assumed by the implementation: 
  30.     1 - data1 = data2 => hash(data1) = hash(data2)
  31.         when data varies over time, hash(data) must remain invariant
  32.             e.g. if data hashes over a string key, the string must not be changed
  33.     2- isEqual (data1, data2) => data1= data2
  34.  */
  35.  
  36. typedef struct {
  37.     const NXHashTablePrototype    *prototype;
  38.     unsigned            count;
  39.     unsigned            nbBuckets;
  40.     void            *buckets;
  41.     const void            *info;
  42.    } NXHashTable;
  43.     /* private data structure; may change */
  44.     
  45. extern NXHashTable *NXCreateHashTableFromZone (NXHashTablePrototE'tprototype, unsigned capacity, const void *info, NXZone *zone);
  46. extern NXHashTable *NXCreateHashTable (NXHashTablePrototype prototype, unsigned capacity, const void *info);
  47.     /* if hash is 0, pointer hash is assumed */
  48.     /* if isEqual is 0, pointer equality is assumed */
  49.     /* if free is 0, elements are not freed */
  50.     /* capacity is only a hint; 0 creates a small table */
  51.     /* info allows call backs to be very general */
  52.  
  53. extern void NXFreeHashTable (NXHashTable *table);
  54.     /* calls free for each data, and recovers table */
  55.     
  56. extern void NXEmptyHashTable (NXHashTable *table);
  57.     /* does not deallocate table nor data; keeps current capacity */
  58.  
  59. extern void NXResetHashTable (NXHashTable *table);
  60.     /* frees each entry; keeps current capacity */
  61.  
  62. extern BOOL NXCompareHashTables (NXHashTable *table1, NXHashTable *table2);
  63.     /* Returns YES if the two sets are equal (each member of table1 in table2, and table have same size) */
  64.  
  65. extern NXHashTable *NXCopyHashTable (NXHashTable *table);
  66.     /* makes a fresh table, copying data pointers, not data itself.  */
  67.     
  68. extern unsigned NXCountHashTable (NXHashTable *table);
  69.     /* current number of data in table */
  70.     
  71. extern int NXHashMember (NXHashTable *table, const void *data);
  72.     /* returns non-0 iff data is present in table.
  73.     Example of use when the hashed data is a struct containing the key,
  74.     and when the callee only has a key:
  75.     MyStruct    pseudo;
  76.     pseudo.key = myKey;
  77.     return NXHashMember (myTable, &pseudo)
  78.     */
  79.     
  80. extern void *NXHashGet (NXHashTable *table, const void *data);
  81.     /* return original table data or NULL.
  82.     Example of use when the hashed data is a struct containing the key,
  83.     and when the callee only has a key:
  84.     MyStruct    pseudo;
  85.     MyStruct    *original;
  86.     pseudo.key = myKey;
  87.     original = NXHashGet (myTable, &pseudo)
  88.     */
  89.     
  90. extern void *NXHashInsert (NXHashTable *table, const void *data);
  91.     /* previous data or NULL is returned. */
  92.     
  93. extern void *NXHashInsertIfAbsent (NXHashTable *table, const void *data);
  94.     /* If data already in table, returns the one in table
  95.     else adds argument to table and returns argument. */
  96.  
  97. extern void *NXHashRemove (NXHashTable *table, const void *data);
  98.     /* previous data or NULL is returned */
  99.     
  100. /* Iteration over all elements of a table consists in setting up an iteration state and then to progress untiE(l entries have been visited.  An example of use for counting elements in a table is:
  101.     unsigned    count = 0;
  102.     MyData    *data;
  103.     NXHashState    state = NXInitHashState(table);
  104.     while (NXNextHashState(table, &state, &data)) {
  105.     count++;
  106.     }
  107. */
  108.  
  109. typedef struct {int i; int j;} NXHashState;
  110.     /* callers should not rely on actual contents of the struct */
  111.  
  112. extern NXHashState NXInitHashState(NXHashTable *table);
  113.  
  114. extern int NXNextHashState(NXHashTable *table, NXHashState *state, void **data);
  115.     /* returns 0 when all elements have been visited */
  116.  
  117. /*************************************************************************
  118.  *    Conveniences for writing hash, isEqual and free functions
  119.  *    and common prototypes
  120.  *************************************************************************/
  121.  
  122. extern unsigned NXPtrHash(const void *info, const void *data);
  123.     /* scrambles the address bits; info unused */
  124. extern unsigned NXStrHash(const void *info, const void *data);
  125.     /* string hashing; info unused */
  126. extern int NXPtrIsEqual(const void *info, const void *data1, const void *data2);
  127.     /* pointer comparison; info unused */
  128. extern int NXStrIsEqual(const void *info, const void *data1, const void *data2);
  129.     /* string comparison; NULL ok; info unused */
  130. extern void NXNoEffectFree(const void *info, void *data);
  131.     /* no effect; info unused */
  132. extern void NXReallyFree(const void *info, void *data);
  133.     /* frees it; info unused */
  134.  
  135. /* The two following prototypes are useful for manipulating set of pointers or set of strings; For them free is defined as NXNoEffectFree */
  136. extern const NXHashTablePrototype NXPtrPrototype;
  137.     /* prototype when data is a pointer (void *) */
  138. extern const NXHashTablePrototype NXStrPrototype;
  139.     /* prototype when data is a string (char *) */
  140.  
  141. /* following prototypes help describe mappings where the key is the first element of a struct and is either a pointer or a string.
  142. For example NXStrStructKeyPrototype can be used to hash pointers to Example, where Example is:
  143.     typedef struct {
  144.         char    *key;
  145.         int        data1;
  146.         ...
  147.         } Example
  148.     
  149. For the following prototypes, free is defined as NXReallyFree.
  150.  */
  151. extern const NXHashTablePrototype NXPtrStructKeyPrototype;
  152. extern const NXHashTablePrototype NXStrStructKeyPrototype;
  153.  
  154. /**********************************************************************E( *    Unique strings and buffers
  155.  *************************************************************************/
  156.  
  157. /* Unique strings allows C users to enjoy the benefits of Lisp's atoms:
  158. A unique string is a string that is allocated once for all (never de-allocated) and that has only one representant (thus allowing comparison with == instead of strcmp).  A unique string should never be modified (and in fact some memory protection is done to ensure that).  In order to more explicitly insist on the fact that the string has been uniqued, a synonym of (const char *) has been added, NXAtom. */
  159.  
  160. typedef const char *NXAtom;
  161.  
  162. extern NXAtom NXUniqueString(const char *buffer);
  163.     /* assumes that buffer is \0 terminated, and returns
  164.      a previously created string or a new string that is a copy of buffer.
  165.     If NULL is passed returns NULL.
  166.     Returned string should never be modified.  To ensure this invariant,
  167.     allocations are made in a special read only zone. */
  168.     
  169. extern NXAtom NXUniqueStringWithLength(const char *buffer, int length);
  170.     /* assumes that buffer is a non NULL buffer of at least 
  171.     length characters.  Returns a previously created string or 
  172.     a new string that is a copy of buffer. 
  173.     If buffer contains \0, string will be truncated.
  174.     As for NXUniqueString, returned string should never be modified.  */
  175.     
  176. extern NXAtom NXUniqueStringNoCopy(const char *string);
  177.     /* If there is already a unique string equal to string, returns the original.  
  178.     Otherwise, string is entered in the table, without making a copy.  Argument should then never be modified.  */
  179.     
  180. extern char *NXCopyStringBuffer(const char *buffer);
  181.     /* given a buffer, allocates a new string copy of buffer.  
  182.     Buffer should be \0 terminated; returned string is \0 terminated. */
  183.  
  184. extern char *NXCopyStringBufferFromZone(const char *buffer, NXZone *zone);
  185.     /* given a buffer, allocates a new string copy of buffer.  
  186.     Buffer should be \0 terminated; returned string is \0 terminated. */
  187.  
  188. #endif /* _OBJC_LITTLE_HASHTABLE_H_ */
  189.