2 Hash table library using separate chaining
4 > Created (Julienne Walker): August 7, 2005
5 > Modified (Julienne Walker): August 11, 2005
6 Added a cast for malloc to enable clean
15 typedef struct jsw_node {
16 void *key; /* Key used for searching */
17 void *item; /* Actual content of a node */
18 struct jsw_node *next; /* Next link in the chain */
21 typedef struct jsw_head {
22 jsw_node_t *first; /* First link in the chain */
23 size_t size; /* Length of the chain */
27 jsw_head_t **table; /* Dynamic chained hash table */
28 size_t size; /* Current item count */
29 size_t capacity; /* Current table size */
30 size_t curri; /* Current index for traversal */
31 jsw_node_t *currl; /* Current link for traversal */
32 hash_f hash; /* User defined key hash function */
33 cmp_f cmp; /* User defined key comparison function */
34 keydup_f keydup; /* User defined key copy function */
35 itemdup_f itemdup; /* User defined item copy function */
36 keyrel_f keyrel; /* User defined key delete function */
37 itemrel_f itemrel; /* User defined item delete function */
40 static unsigned int default_hash(const void *key) {
41 const unsigned char *p = key;
44 int len = strlen((char *)p);
46 for (i = 0; i < len; i++) {
59 static jsw_node_t *new_node ( void *key, void *item, jsw_node_t *next )
61 jsw_node_t *node = malloc ( sizeof *node );
73 static jsw_head_t *new_chain ( void )
75 jsw_head_t *chain = malloc ( sizeof *chain );
87 Create a new hash table with a capacity of size, and
88 user defined functions for handling keys and items.
90 Returns: An empty hash table, or NULL on failure.
92 jsw_hash_t *jsw_hnew ( size_t size, hash_f hash, cmp_f cmp,
93 keydup_f keydup, itemdup_f itemdup,
94 keyrel_f keyrel, itemrel_f itemrel )
96 jsw_hash_t *htab = malloc ( sizeof *htab );
102 htab->table = malloc ( size * sizeof *htab->table );
104 if ( htab->table == NULL ) {
109 /* Empty chains have no head */
110 for ( i = 0; i < size; i++ )
111 htab->table[i] = NULL;
114 htab->capacity = size;
117 htab->hash = hash ? hash : default_hash;
119 htab->keydup = keydup;
120 htab->itemdup = itemdup;
121 htab->keyrel = keyrel;
122 htab->itemrel = itemrel;
127 /* Release all memory used by the hash table */
128 void jsw_hdelete ( jsw_hash_t *htab )
132 /* Release each chain individually */
133 for ( i = 0; i < htab->capacity; i++ ) {
134 jsw_node_t *save, *it;
136 if ( htab->table[i] == NULL )
139 it = htab->table[i]->first;
141 for ( ; it != NULL; it = save ) {
143 htab->keyrel ( it->key );
144 htab->itemrel ( it->item );
148 free ( htab->table[i] );
151 /* Release the hash table */
152 free ( htab->table );
157 Find an item with the selected key
159 Returns: The item, or NULL if not found
161 void *jsw_hfind ( jsw_hash_t *htab, void *key )
163 unsigned h = htab->hash ( key ) % htab->capacity;
165 /* Search the chain only if it exists */
166 if ( htab->table[h] != NULL ) {
167 jsw_node_t *it = htab->table[h]->first;
169 for ( ; it != NULL; it = it->next ) {
170 if ( htab->cmp ( key, it->key ) == 0 )
178 static int insert_item(jsw_head_t **table, jsw_node_t *item, unsigned int chain) {
179 /* Create a chain if the bucket is empty */
180 if ( table[chain] == NULL ) {
181 table[chain] = new_chain();
184 if ( table[chain] == NULL ) {
188 /* Insert at the front of the chain */
189 item->next = table[chain]->first;
190 table[chain]->first = item;
192 ++table[chain]->size;
198 Insert an item with the selected key
200 Returns: non-zero for success, zero for failure
202 int jsw_hinsert ( jsw_hash_t *htab, void *key, void *item )
204 unsigned h = htab->hash ( key ) % htab->capacity;
205 void *dupkey, *dupitem;
206 jsw_node_t *new_item;
208 /* Disallow duplicate keys */
209 if ( jsw_hfind ( htab, key ) != NULL )
212 /* Attempt to create a new item */
213 dupkey = htab->keydup ( key );
214 dupitem = htab->itemdup ( item );
216 new_item = new_node ( dupkey, dupitem, NULL );
218 if ( new_item == NULL )
221 /* Create a chain if the bucket is empty */
222 if ( htab->table[h] == NULL ) {
223 htab->table[h] = new_chain();
225 if ( htab->table[h] == NULL ) {
226 htab->keyrel ( new_item->key );
227 htab->itemrel ( new_item->item );
233 /* Insert at the front of the chain */
234 new_item->next = htab->table[h]->first;
235 htab->table[h]->first = new_item;
237 ++htab->table[h]->size;
244 Remove an item with the selected key
246 Returns: non-zero for success, zero for failure
248 int jsw_herase ( jsw_hash_t *htab, void *key )
250 unsigned h = htab->hash ( key ) % htab->capacity;
251 jsw_node_t *save, *it;
253 if ( htab->table[h] == NULL )
256 it = htab->table[h]->first;
258 /* Remove the first node in the chain? */
259 if ( htab->cmp ( key, it->key ) == 0 ) {
260 htab->table[h]->first = it->next;
262 /* Release the node's memory */
263 htab->keyrel ( it->key );
264 htab->itemrel ( it->item );
267 /* Remove the chain if it's empty */
268 if ( htab->table[h]->first == NULL ) {
269 free ( htab->table[h] );
270 htab->table[h] = NULL;
273 --htab->table[h]->size;
276 /* Search for the node */
277 while ( it->next != NULL ) {
278 if ( htab->cmp ( key, it->next->key ) == 0 )
285 if ( it->next == NULL )
289 it->next = it->next->next;
291 /* Release the node's memory */
292 htab->keyrel ( save->key );
293 htab->itemrel ( save->item );
296 --htab->table[h]->size;
299 /* Erasure invalidates traversal markers */
308 Grow or shrink the table, this is a slow operation
310 Returns: non-zero for success, zero for failure
312 int jsw_hresize ( jsw_hash_t *htab, size_t new_size )
315 jsw_head_t **newtable;
319 if (new_size == htab->capacity) {
323 newtable = malloc(new_size * sizeof *htab->table);
329 for(i=0; i < new_size; i++) {
333 for ( i = 0; i < htab->capacity; i++ ) {
334 if ( htab->table[i] == NULL ) continue;
336 for ( it = htab->table[i]->first; it != NULL; it = it->next ) {
337 bucket = htab->hash(it->key) % new_size;
338 insert_item(newtable, it, bucket);
342 htab->capacity = new_size;
343 htab->table = newtable;
348 /* Reset the traversal markers to the beginning */
349 void jsw_hreset ( jsw_hash_t *htab )
356 /* Find the first non-empty bucket */
357 for ( i = 0; i < htab->capacity; i++ ) {
358 if ( htab->table[i] != NULL )
364 /* Set the link marker if the table was not empty */
365 if ( i != htab->capacity )
366 htab->currl = htab->table[i]->first;
369 /* Traverse forward by one key */
370 int jsw_hnext ( jsw_hash_t *htab )
372 if ( htab->currl != NULL ) {
373 htab->currl = htab->currl->next;
375 /* At the end of the chain? */
376 if ( htab->currl == NULL ) {
377 /* Find the next chain */
378 while ( ++htab->curri < htab->capacity ) {
379 if ( htab->table[htab->curri] != NULL )
383 /* No more chains? */
384 if ( htab->curri == htab->capacity )
387 htab->currl = htab->table[htab->curri]->first;
394 /* Get the current key */
395 const void *jsw_hkey ( jsw_hash_t *htab )
397 return htab->currl != NULL ? htab->currl->key : NULL;
400 /* Get the current item */
401 void *jsw_hitem ( jsw_hash_t *htab )
403 return htab->currl != NULL ? htab->currl->item : NULL;
406 /* Current number of items in the table */
407 size_t jsw_hsize ( jsw_hash_t *htab )
412 /* Total allowable number of items without resizing */
413 size_t jsw_hcapacity ( jsw_hash_t *htab )
415 return htab->capacity;
418 /* Get statistics for the hash table */
419 jsw_hstat_t *jsw_hstat ( jsw_hash_t *htab )
422 double sum = 0, used = 0;
425 /* No stats for an empty table */
426 if ( htab->size == 0 )
429 stat = malloc ( sizeof *stat );
435 stat->schain = (size_t)-1;
437 for ( i = 0; i < htab->capacity; i++ ) {
438 if ( htab->table[i] != NULL ) {
439 sum += htab->table[i]->size;
441 ++used; /* Non-empty buckets */
443 if ( htab->table[i]->size > stat->lchain )
444 stat->lchain = htab->table[i]->size;
446 if ( htab->table[i]->size < stat->schain )
447 stat->schain = htab->table[i]->size;
451 stat->load = used / htab->capacity;
452 stat->achain = sum / used;