4
/*****************************************************************************/
5
/******************************** Documentation ******************************/
6
/*****************************************************************************/
10
Dynamic hash table implementation based on article in CACM April 1988 pp.
11
446-457, by Per-Ake Larson.
13
This implementation was based on a 3/7/1989 submission to comp.sources.misc by
14
Esmond Pitt (ejp@ausmelb.oz.AU) that emulated the hsearch(3) interface. The interface
15
was reworked to be much more flexible and significant new functionality was
16
added by John Dennis (jdennis@sharpeye.com).
18
A hash table maintains a set of <key,value> pairs. Lookups are performed by
19
locating the key in the table and returning its value.
21
A dynamic hash table keeps the number of hash collisions constant
22
independent of the number of entries in the hash table.
24
Both keys and values may be of different types. Two different key types are
25
supported, strings and unsigned longs. If the key type is a string the hash
26
library will automatically allocate memory to hold the hash key string and
27
will automatically free the memory for the key string when the hash entry
28
is destroyed. Items in the hash table only match when their key types match
29
AND the keys themselves match. For example if there were two hash entries,
30
one whose key type was an unsigned long equal to 1 and one whose key type was
31
a string equal to "1" they would not match, these are considered two
34
The value of the key may be a undefined, pointer, an int, an unsigned int, a
35
long, an unsigned long, a float, or a double. The hash library does nothing
36
with user pointers (value.type == HASH_VALUE_PTR). Its the user responsibility
37
to free items pointed to by these pointers when a hash entry is deleted or the
38
hash table is destroyed (see hash_delete_callback and/or hash_destroy).
40
See dhash_example.c for an illustration of how one might use the API. It does not
41
represent complete API coverage nor the optimal way to do things in all cases,
42
it is just a general example.
46
/*****************************************************************************/
47
/******************************* Include Files *******************************/
48
/*****************************************************************************/
52
/*****************************************************************************/
53
/*********************************** Defines *********************************/
54
/*****************************************************************************/
57
#define HASH_STATISTICS
60
#define HASH_DEFAULT_DIRECTORY_BITS 5
61
#define HASH_DEFAULT_SEGMENT_BITS 5
62
#define HASH_DEFAULT_MIN_LOAD_FACTOR 1
63
#define HASH_DEFAULT_MAX_LOAD_FACTOR 5
65
#define HASH_ERROR_BASE -2000
66
#define HASH_ERROR_LIMIT (HASH_ERROR_BASE+20)
67
#define IS_HASH_ERROR(error) (((error) >= HASH_ERROR_BASE) && ((error) < HASH_ERROR_LIMIT))
69
#define HASH_SUCCESS 0
70
#define HASH_ERROR_BAD_KEY_TYPE (HASH_ERROR_BASE + 1)
71
#define HASH_ERROR_BAD_VALUE_TYPE (HASH_ERROR_BASE + 2)
72
#define HASH_ERROR_NO_MEMORY (HASH_ERROR_BASE + 3)
73
#define HASH_ERROR_KEY_NOT_FOUND (HASH_ERROR_BASE + 4)
74
#define HASH_ERROR_BAD_TABLE (HASH_ERROR_BASE + 5)
76
/*****************************************************************************/
77
/******************************* Type Definitions ****************************/
78
/*****************************************************************************/
80
struct hash_table_str;
81
typedef struct hash_table_str hash_table_t;
106
typedef struct hash_key_t {
114
typedef struct hash_value_t {
115
hash_value_enum type;
127
typedef struct hash_entry_t {
132
#ifdef HASH_STATISTICS
133
typedef struct hash_statistics_t {
134
unsigned long hash_accesses;
135
unsigned long hash_collisions;
136
unsigned long table_expansions;
137
unsigned long table_contractions;
142
/* typedef's for callback based iteration */
143
typedef bool(*hash_iterate_callback)(hash_entry_t *item, void *user_data);
144
typedef void (hash_delete_callback)(hash_entry_t *item,
145
hash_destroy_enum type, void *pvt);
147
/* typedef's for iteration object based iteration */
148
struct hash_iter_context_t;
149
typedef hash_entry_t *(*hash_iter_next_t)(struct hash_iter_context_t *iter);
150
struct hash_iter_context_t {
151
hash_iter_next_t next;
154
/* typedef for hash_create_ex() */
155
typedef void *(hash_alloc_func)(size_t size, void *pvt);
156
typedef void (hash_free_func)(void *ptr, void *pvt);
158
/*****************************************************************************/
159
/************************* External Global Variables ***********************/
160
/*****************************************************************************/
162
/*****************************************************************************/
163
/**************************** Exported Functions ***************************/
164
/*****************************************************************************/
167
* Given an error code returned by a hash function, map it to a error string.
168
* Returns NULL if the error code is unrecognized.
170
const char* hash_error_string(int error);
173
* Create a new hash table with room for n initial entries. hash_create returns
174
* an opaque pointer to the new hash table in the table parameter. Functions
175
* operating on the hash table pass in this hash table pointer. This means you
176
* may have as many concurrent hash tables as you want. The delete_callback
177
* parameter is a pointer to a function which will be called just prior to a
178
* hash entry being deleted. This is useful when the hash value has items which
179
* may need to be disposed of. The delete_callback may be NULL.
180
* The delete_private_data is data passed to the delete_callback, this way
181
* custom callbacks can have a private context to reach data they need to use
182
* before performning their operations. delete_private_data may be NULL.
184
int hash_create(unsigned long count, hash_table_t **tbl,
185
hash_delete_callback *delete_callback,
186
void *delete_private_data);
189
* Create a new hash table and fine tune it's configurable parameters.
190
* Refer to CACM article for explanation of parameters.
192
* directory_bits: number of address bits allocated to top level directory array.
193
* segment_bits: number of address bits allocated to segment array.
194
* min_load_factor: table contracted when the ratio of entry count to bucket count
195
* is less than the min_load_factor the table is contracted.
196
* max_load_factor: table expanded when the ratio of entry count to bucket count
197
* is greater than the max_load_factor the table is expanded.
198
* alloc_func: function pointer for allocation
199
* free_func: funciton pointer for freeing memory allocated with alloc_func
200
* alloc_private data: data passed to the alloc and free functions so that
201
* custom functions can refernce other private data they may
202
* need during their execution without having to use global
205
* Note directory_bits + segment_bits must be <= number of bits in unsigned long
207
int hash_create_ex(unsigned long count, hash_table_t **tbl,
208
unsigned int directory_bits,
209
unsigned int segment_bits,
210
unsigned long min_load_factor,
211
unsigned long max_load_factor,
212
hash_alloc_func *alloc_func,
213
hash_free_func *free_func,
214
void *alloc_private_data,
215
hash_delete_callback *delete_callback,
216
void *delete_private_data);
218
#ifdef HASH_STATISTICS
220
* Return statistics for the table.
222
int hash_get_statistics(hash_table_t *table, hash_statistics_t *statistics);
226
* hash_destroy deletes all entries in the hash table, freeing all memory used
227
* in implementing the hash table. Some hash entries may have values which are
228
* pointers to user data structures. User pointers are not free by hash_destroy,
229
* they must be free by the caller. This may be done by iterating over all the
230
* entries in the table using hash_iterate() and freeing the values or by
231
* registering a delete callback when the table is created with
232
* hash_create(). Note, hash keys which are strings will be automatically freed
233
* by hash_destroy, the caller does not need to free the key strings.
235
int hash_destroy(hash_table_t *table);
238
* Enter or update an item in the table referenced by key. If the key does not
239
* exist yet the item will be created and inserted into the table with the
240
* value, otherwise the value for the existing key is updated. The return value
241
* may be HASH_ERROR_BAD_KEY_TYPE or HASH_ERROR_BAD_VALUE_TYPE if the key or
242
* value type respectively is invalid. This function might also return
243
* HASH_ERROR_NO_MEMORY.
245
int hash_enter(hash_table_t *table, hash_key_t *key, hash_value_t *value);
248
* Using the key lookup the value associated with it in the table. If the key is
249
* not in the table HASH_ERROR_KEY_NOT_FOUND is returned. If the type of key is
250
* invalid HASH_ERROR_BAD_KEY_TYPE is returned. Otherwise HASH_SUCCESS is
251
* returned. If the result is anything other than HASH_SUCCESS the value pointer
254
int hash_lookup(hash_table_t *table, hash_key_t *key, hash_value_t *value);
257
* Like hash_lookup() except if the key is not in the table then it is entered
258
* into the table and assigned the default_value. Thus it is not possible for
259
* hash_get_default() to return HASH_ERROR_KEY_NOT_FOUND.
261
int hash_get_default(hash_table_t *table, hash_key_t *key, hash_value_t *value, hash_value_t *default_value);
264
* Delete the item from the table. The key and its type are specified in the key
265
* parameter which are passed by reference. If the key was in the table
266
* HASH_SUCCESS is returned otherwise HASH_ERROR_KEY_NOT_FOUND is
267
* returned. Memory allocated to hold the key if it was a string is free by the
268
* hash library, but values which are pointers to user data must be freed by the
269
* caller (see delete_callback).
271
int hash_delete(hash_table_t *table, hash_key_t *key);
274
* Often it is useful to operate on every key and/or value in the hash
275
* table. The hash_iterate function will invoke the users callback on every item
276
* in the table as long as the callback returns a non-zero value. Returning a
277
* zero from the callback can be used to halt the iteration prematurely if some
278
* condition is met. The user_data parameter is passed to the callback
279
* function. It can be used for any purpose the caller wants. The callback
282
* bool callback(hash_entry_t *item, hash_table_t *user_data);
284
* WARNING: Do not modify the contents of the table during an iteration it will
285
* produce undefined results. If you need to visit each item in the table and
286
* potentially delete or insert some entries the proper way to do this is to
287
* obtain a list of keys or items using hash_keys() or hash_items() which
288
* returns a copy of the keys or items. You may then loop on the list returned
289
* and safely update the table (don't forget to free the list when done).
291
int hash_iterate(hash_table_t *table, hash_iterate_callback callback, void *user_data);
294
* This is another method to iterate on every key/value in the hash table.
295
* However, unlike hash_iterate which requires a callback this function returns
296
* an iterator object which contains a next() function pointer. Each time
297
* next() is invoked it returns a pointer to the next hash entry in the table,
298
* then NULL when all entries have been visited. In some circumstances it's more
299
* convenient than having to define a callback. Like hash_iterate() one must
300
* never modify the table contents during iteration. If you intend to modify the
301
* table during iteration use the functions which return an indepent list of
302
* keys, values, or items instead and iterate on the list. The iterator object
303
* must be free'ed when you're done iterating by calling free() on it.
307
* struct hash_iter_context_t *iter;
308
* hash_entry_t *entry;
310
* iter = new_hash_iter_context(table);
311
* while ((entry = iter->next(iter)) != NULL) {
312
* do_something(entry);
316
struct hash_iter_context_t *new_hash_iter_context(hash_table_t *table);
319
* Return a count of how many items are currently in the table.
321
unsigned long hash_count(hash_table_t *table);
324
* Get an array of all the keys in the table returned through the keys
325
* parameter. The number of elements in the array is returned in the count
326
* parameter. Each key in the array is a copy of the key in the table. Any
327
* pointers in the key will be shared with the table entry thus both the item in
328
* the array and the item in the table point to the same object. The array
329
* should be freed by calling free(). The function may return
330
* HASH_ERROR_NO_MEMORY, otherwise HASH_SUCCESS.
332
int hash_keys(hash_table_t *table, unsigned long *count, hash_key_t **keys);
335
* Get an array of all the values in the table returned through the values
336
* parameter. The number of elements in the array is returned in the count
337
* parameter. Each value in the array is a copy of the value in the table. Any
338
* pointers in the value will be shared with the table entry thus both the item in
339
* the array and the item in the table point to the same object. The array
340
* should be freed by calling free(). The function may return
341
* HASH_ERROR_NO_MEMORY, otherwise HASH_SUCCESS.
343
int hash_values(hash_table_t *table, unsigned long *count, hash_value_t **values);
347
* Get an array of all the entries in the table returned through the entries
348
* parameter. The number of elements in the array is returned in the count
349
* parameter. Each entry in the array is a copy of the entry in the table. Any
350
* pointers in the entry will be shared with the table entry thus both the item in
351
* the array and the item in the table point to the same object. The array
352
* should be freed by calling free(). The function may return
353
* HASH_ERROR_NO_MEMORY, otherwise HASH_SUCCESS.
355
int hash_entries(hash_table_t *table, unsigned long *count, hash_entry_t **entries);
358
* Return boolean if the key is in the table.
360
bool hash_has_key(hash_table_t *table, hash_key_t *key);
added
removed
common/dhash/dhash.h
