6
/****************************************************************************
10
****************************************************************************/
12
#define HASH_MINSIZE 8
13
#define SLOW_DOWN 50000 /* stop increasing the hash table so quickly to
17
* Return values for h_set
21
HASH_KEY_DOES_NOT_EXIST = 0,
27
* struct used internally to store values in the HashTable
37
* As the hash table is filled and entries are deleted, Dummy HashEntries are
38
* put in place. We therefor keep two counts. +size+ is the number active
39
* elements and +fill+ is the number of active elements together with the
40
* number of dummy elements. +fill+ is basically just kept around so that we
41
* know when to resize. The HashTable is resized when more than two thirds of
42
* the HashTable is Filled.
44
typedef struct HashTable
46
int fill; /* num Active + num Dummy */
47
int size; /* num Active ie, num keys set */
48
int mask; /* capacity_of_table - 1 */
51
/* table points to smalltable initially. If the table grows beyond 2/3 of
52
* HASH_MINSIZE it will point to newly malloced memory as it grows. */
55
/* When a HashTable is created it needs an initial table to start if off.
56
* All HashTables will start with smalltable and then malloc a larger
57
* table as the HashTable grows */
58
HashEntry smalltable[HASH_MINSIZE];
60
/* the following function pointers are used internally and should not be
61
* used outside of the HashTable methods */
62
HashEntry *(*lookup_i)(struct HashTable *self, register const void *key);
63
unsigned long (*hash_i)(const void *key);
64
int (*eq_i)(const void *key1, const void *key2);
65
void (*free_key_i)(void *p);
66
void (*free_value_i)(void *p);
70
* Hashing function type used by HashTable. A function of this type must be
71
* passed to create a new HashTable.
73
* @param key object to hash
74
* @return an unsigned 32-bit integer hash value
76
typedef unsigned long (*hash_ft)(const void *key);
79
* Equals function type used by HashTable. A function of this type must be
80
* passed to create a new HashTable.
82
typedef int (*eq_ft)(const void *key1, const void *key2);
85
* Determine a hash value for a string. The string must be null terminated
87
* @param str string to hash
88
* @return an unsigned long integer hash value
90
extern unsigned long str_hash(const char *const str);
93
* Determine a hash value for a pointer. Just cast the pointer to an unsigned
96
* @param ptr pointer to hash
97
* @return an unsigned long integer hash value
99
extern unsigned long ptr_hash(const void *const ptr);
102
* Determine if two pointers point to the same point in memory.
104
* @param q1 first pointer
105
* @param q2 second pointer
106
* @return true if the pointers are equal
108
extern int ptr_eq(const void *q1, const void *q2);
111
* Create a new HashTable that uses any type of object as it's key. The
112
* HashTable will store all keys and values so if you want to destroy those
113
* values when the HashTable is destroyed then you should pass free functions.
114
* NULL will suffice otherwise.
116
* @param hash function to determine the hash value of a key in the HashTable
117
* @param eq function to determine the equality of to keys in the HashTable
118
* @param free_key function to free the key stored in the HashTable when an
119
* entry is deleted, replaced or when the HashTable is destroyed. If you
120
* pass NULL in place of this parameter the key will not be destroyed.
121
* @param free_value function to free the value stored in the HashTable when
122
* an entry is deleted, replaced or when the HashTable is destroyed. If you
123
* pass NULL in place of this parameter the value will not be destroyed.
124
* @return A newly allocated HashTable
126
extern HashTable *h_new(hash_ft hash, eq_ft eq, free_ft free_key,
130
* Create a new HashTable that uses null-terminated strings as it's keys. The
131
* HashTable will store all keys and values so if you want to destroy those
132
* values when the HashTable is destroyed then you should pass free functions.
133
* NULL will suffice otherwise.
135
* @param free_key function to free the key stored in the HashTable when an
136
* entry is deleted, replaced or when the HashTable is destroyed. If you
137
* pass NULL in place of this parameter the key will not be destroyed.
138
* @param free_value function to free the value stored in the HashTable when
139
* an entry is deleted, replaced or when the HashTable is destroyed. If you
140
* pass NULL in place of this parameter the value will not be destroyed.
141
* @return A newly allocated HashTable
143
extern HashTable *h_new_str(free_ft free_key, free_ft free_value);
146
* Create a new HashTable that uses integers as it's keys. The
147
* HashTable will store all values so if you want to destroy those
148
* values when the HashTable is destroyed then you should pass a free function.
149
* NULL will suffice otherwise.
151
* @param free_value function to free the value stored in the HashTable when
152
* an entry is deleted, replaced or when the HashTable is destroyed. If you
153
* pass NULL in place of this parameter the value will not be destroyed.
154
* @return A newly allocated HashTable
156
extern HashTable *h_new_int(free_ft free_value);
159
* Destroy the HashTable. This function will also destroy all keys and values
160
* in the HashTable depending on how the free_key and free_value were set.
162
* @param self the HashTable to destroy
164
extern void h_destroy(HashTable *self);
167
* Clear the HashTable. This function will delete all keys and values from the
168
* hash table, also destroying all keys and values in the HashTable depending
169
* on how the free_key and free_value were set.
171
* @param self the HashTable to clear
173
extern void h_clear(HashTable *self);
176
* Get the value in the HashTable referenced by the key +key+.
178
* @param self the HashTable to reference
179
* @param key the key to lookup
180
* @return the value referenced by the key +key+. If there is no value
181
* referenced by that key, NULL is returned.
183
extern void *h_get(HashTable *self, const void *key);
186
* Delete the value in HashTable referenced by the key +key+. When the value
187
* is deleted it is also destroyed along with the key depending on how
188
* free_key and free_value where set when the HashTable was created. If you
189
* don't want to destroy the value use h_rem.
191
* This functions returns +true+ if the value was deleted successfully or
192
* false if the key was not found.
196
* @param self the HashTable to reference
197
* @param key the key to lookup
198
* @return true if the object was successfully deleted or false if the key was
201
extern int h_del(HashTable *self, const void *key);
204
* Remove the value in HashTable referenced by the key +key+. When the value
205
* is removed it is returned rather than destroyed. The key however is
206
* destroyed using the free_key functions passed when the HashTable is created
207
* if del_key is true.
209
* If you want the value to be destroyed, use the h_del function.
213
* @param self the HashTable to reference
214
* @param key the key to lookup
215
* @param del_key set to true if you want the key to be deleted when the value
216
* is removed from the HashTable
217
* @return the value referenced by +key+ if it can be found or NULL otherwise
219
extern void *h_rem(HashTable *self, const void *key, bool del_key);
222
* WARNING: this function may destroy an old value or key if the key already
223
* exists in the HashTable, depending on how free_value and free_key were set
224
* for this HashTable.
226
* Add the value +value+ to the HashTable referencing it with key +key+.
228
* When a value is added to the HashTable it replaces any value that
229
* might already be stored under that key. If free_value is already set then
230
* the old value will be freed using that function.
232
* Similarly the old key might replace be replaced by the new key if they are
233
* are equal (according to the HashTable's eq function) but seperately
236
* @param self the HashTable to add the value to
237
* @param key the key to use to reference the value
238
* @param value the value to add to the HashTable
239
* @return one of three values;
241
* HASH_KEY_DOES_NOT_EXIST there was no value stored with that key
242
* HASH_KEY_EQUAL the key existed and was seperately allocated.
243
* In this situation the old key will have been
244
* destroyed if free_key was set
245
* HASH_KEY_SAME the key was identical (same memory pointer) to
246
* the existing key so no key was freed
249
extern int h_set(HashTable *self, const void *key, void *value);
252
* Add the value +value+ to the HashTable referencing it with key +key+. If
253
* the key already exists in the HashTable, the value won't be added and the
254
* function will return false. Otherwise it will return true.
256
* @param self the HashTable to add the value to
257
* @param key the key to use to reference the value
258
* @param value the value to add to the HashTable
259
* @return true if the value was successfully added or false otherwise
261
extern int h_set_safe(HashTable *self, const void *key, void *value);
264
* Return a hash entry object so you can handle the insert yourself. This can
265
* be used for performance reasons or for more control over how a value is
266
* added. Say, for example, you wanted to append a value to an array, or add a
267
* new array if non-existed, you could use this method by checking the value
268
* of the HashEntry returned.
270
* @param self the HashTable to add the value to
271
* @param key the key to use to reference the value
272
* @return HashEntry a pointer to the hash entry object now reserved for this
273
* value. Be sure to set both the *key* and the *value*
275
extern HashEntry *h_set_ext(HashTable *ht, const void *key);
278
* Check whether key +key+ exists in the HashTable.
280
* @param self the HashTable to check in
281
* @param key the key to check for in the HashTable
282
* @return true if the key exists in the HashTable, false otherwise.
284
extern int h_has_key(HashTable *self, const void *key);
287
* Get the value in the HashTable referenced by an integer key +key+.
289
* @param self the HashTable to reference
290
* @param key the integer key to lookup
291
* @return the value referenced by the key +key+. If there is no value
292
* referenced by that key, NULL is returned.
294
extern void *h_get_int(HashTable *self, const unsigned long key);
297
* Delete the value in HashTable referenced by the integer key +key+. When the
298
* value is deleted it is also destroyed using the free_value function. If you
299
* don't want to destroy the value use h_rem.
301
* This functions returns +true+ if the value was deleted successfully or
302
* false if the key was not found.
306
* @param self the HashTable to reference
307
* @param key the integer key to lookup
308
* @return true if the object was successfully deleted or false if the key was
311
extern int h_del_int(HashTable *self, const unsigned long key);
314
* Remove the value in HashTable referenced by the integer key +key+. When the
315
* value is removed it is returned rather than destroyed.
317
* If you want the value to be destroyed, use the h_del function.
321
* @param self the HashTable to reference
322
* @param key the integer key to lookup
323
* @return the value referenced by +key+ if it can be found or NULL otherwise
325
extern void *h_rem_int(HashTable *self, const unsigned long key);
328
* WARNING: this function may destroy an old value if the key already exists
329
* in the HashTable, depending on how free_value was set for this HashTable.
331
* Add the value +value+ to the HashTable referencing it with an integer key
334
* When a value is added to the HashTable it replaces any value that
335
* might already be stored under that key. If free_value is already set then
336
* the old value will be freed using that function.
338
* Similarly the old key might replace be replaced by the new key if they are
339
* are equal (according to the HashTable's eq function) but seperately
342
* @param self the HashTable to add the value to
343
* @param key the integer key to use to reference the value
344
* @param value the value to add to the HashTable
345
* @return one of three values;
347
* HASH_KEY_DOES_NOT_EXIST there was no value stored with that key
348
* HASH_KEY_EQUAL the key existed and was seperately allocated.
349
* In this situation the old key will have been
350
* destroyed if free_key was set
351
* HASH_KEY_SAME the key was identical (same memory pointer) to
352
* the existing key so no key was freed
355
extern int h_set_int(HashTable *self, const unsigned long key, void *value);
358
* Add the value +value+ to the HashTable referencing it with integer key
359
* +key+. If the key already exists in the HashTable, the value won't be added
360
* and the function will return false. Otherwise it will return true.
362
* @param self the HashTable to add the value to
363
* @param key the integer key to use to reference the value
364
* @param value the value to add to the HashTable
365
* @return true if the value was successfully added or false otherwise
367
extern int h_set_safe_int(HashTable *self, const unsigned long key, void *value);
369
* Check whether integer key +key+ exists in the HashTable.
371
* @param self the HashTable to check in
372
* @param key the integer key to check for in the HashTable
373
* @return true if the key exists in the HashTable, false otherwise.
375
extern int h_has_key_int(HashTable *self, const unsigned long key);
377
typedef void (*h_each_key_val_ft)(void *key, void *value, void *arg);
380
* Run function +each_key_val+ on each key and value in the HashTable. The third
381
* argument +arg+ will also be passed to +each_key_val+. If you need to pass
382
* more than one argument to the function you should pass a struct.
386
* // Lets say we have stored strings in a HashTable and we want to put them
387
* // all into an array. First we need to create a struct to store the
390
* struct StringArray {
396
* static void add_string_ekv(void *key, void *value,
397
* struct StringArray *str_arr)
399
* str_arr->strings[str_arr->cnt] = (char *)value;
403
* struct StringArray *h_extract_strings(HashTable *ht)
405
* struct StringArray *str_arr = ALLOC(struct StringArray);
407
* str_arr->strings = ALLOC_N(char *, ht->size);
409
* str_arr->size = ht->size;
411
* h_each(ht, (h_each_key_val_ft)add_string_ekv, str_arr);
416
* @param self the HashTable to run the function on
417
* @param each_key_val function to run on on each key and value in the
419
* @param arg an extra argument to pass to each_key_val each time it is called
421
extern void h_each(HashTable *self,
422
void (*each_key_val)(void *key, void *value, void *arg),
425
typedef void *(*h_clone_func_t)(void *val);
427
* Clone the HashTable as well as cloning each of the keys and values if you
428
* want to do a deep clone. To do a deep clone you will need to pass a
429
* clone_key function and/or a clone_value function.
431
* @param self the HashTable to clone
432
* @param clone_key the function to clone the key with
433
* @param clone_value the function to clone the value with
434
* @return a clone of the original HashTable
436
extern HashTable *h_clone(HashTable *self,
437
h_clone_func_t clone_key,
438
h_clone_func_t clone_value);
441
* The following functions should only be used in static HashTable
445
* This is the lookup function for a hash table keyed with strings. Since it
446
* is so common for hash tables to be keyed with strings it gets it's own
447
* lookup function. This method will always return a HashEntry. If there is no
448
* entry with the given key then an empty entry will be returned with the key
449
* set to the key that was passed.
451
* @param ht the hash table to look in
452
* @param key the key to lookup
453
* @return the HashEntry that was found
455
extern HashEntry *h_lookup_str(HashTable *ht, register const char *key);
458
* This is the lookup function for a hash table with non-string keys. The
459
* hash() and eq() methods used are stored in the hash table. This method will
460
* always return a HashEntry. If there is no entry with the given key then an
461
* empty entry will be returned with the key set to the key that was passed.
463
* @param ht the hash table to look in
464
* @param key the key to lookup
465
* @return the HashEntry that was found
467
extern HashEntry *h_lookup(HashTable *ht, register const void *key);
469
typedef HashEntry *(*h_lookup_ft)(HashTable *ht, register const void *key);
471
extern void h_str_print_keys(HashTable *ht);
added
removed
ext/hash.h
