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
13 typedef struct jsw_node {
14 void *key; /* Key used for searching */
15 void *item; /* Actual content of a node */
16 struct jsw_node *next; /* Next link in the chain */
19 typedef struct jsw_head {
20 jsw_node_t *first; /* First link in the chain */
21 size_t size; /* Length of the chain */
25 jsw_head_t **table; /* Dynamic chained hash table */
26 size_t size; /* Current item count */
27 size_t capacity; /* Current table size */
28 size_t curri; /* Current index for traversal */
29 jsw_node_t *currl; /* Current link for traversal */
30 hash_f hash; /* User defined key hash function */
31 cmp_f cmp; /* User defined key comparison function */
32 keydup_f keydup; /* User defined key copy function */
33 itemdup_f itemdup; /* User defined item copy function */
34 keyrel_f keyrel; /* User defined key delete function */
35 itemrel_f itemrel; /* User defined item delete function */
38 static jsw_node_t *new_node ( void *key, void *item, jsw_node_t *next )
40 jsw_node_t *node = malloc ( sizeof *node );
52 static jsw_head_t *new_chain ( void )
54 jsw_head_t *chain = malloc ( sizeof *chain );
66 Create a new hash table with a capacity of size, and
67 user defined functions for handling keys and items.
69 Returns: An empty hash table, or NULL on failure.
71 jsw_hash_t *jsw_hnew ( size_t size, hash_f hash, cmp_f cmp,
72 keydup_f keydup, itemdup_f itemdup,
73 keyrel_f keyrel, itemrel_f itemrel )
75 jsw_hash_t *htab = malloc ( sizeof *htab );
81 htab->table = malloc ( size * sizeof *htab->table );
83 if ( htab->table == NULL ) {
88 /* Empty chains have no head */
89 for ( i = 0; i < size; i++ )
90 htab->table[i] = NULL;
93 htab->capacity = size;
98 htab->keydup = keydup;
99 htab->itemdup = itemdup;
100 htab->keyrel = keyrel;
101 htab->itemrel = itemrel;
106 /* Release all memory used by the hash table */
107 void jsw_hdelete ( jsw_hash_t *htab )
111 /* Release each chain individually */
112 for ( i = 0; i < htab->capacity; i++ ) {
113 jsw_node_t *save, *it;
115 if ( htab->table[i] == NULL )
118 it = htab->table[i]->first;
120 for ( ; it != NULL; it = save ) {
122 htab->keyrel ( it->key );
123 htab->itemrel ( it->item );
127 free ( htab->table[i] );
130 /* Release the hash table */
131 free ( htab->table );
136 Find an item with the selected key
138 Returns: The item, or NULL if not found
140 void *jsw_hfind ( jsw_hash_t *htab, void *key )
142 unsigned h = htab->hash ( key ) % htab->capacity;
144 /* Search the chain only if it exists */
145 if ( htab->table[h] != NULL ) {
146 jsw_node_t *it = htab->table[h]->first;
148 for ( ; it != NULL; it = it->next ) {
149 if ( htab->cmp ( key, it->key ) == 0 )
158 Insert an item with the selected key
160 Returns: non-zero for success, zero for failure
162 int jsw_hinsert ( jsw_hash_t *htab, void *key, void *item )
164 unsigned h = htab->hash ( key ) % htab->capacity;
165 void *dupkey, *dupitem;
166 jsw_node_t *new_item;
168 /* Disallow duplicate keys */
169 if ( jsw_hfind ( htab, key ) != NULL )
172 /* Attempt to create a new item */
173 dupkey = htab->keydup ( key );
174 dupitem = htab->itemdup ( item );
176 new_item = new_node ( dupkey, dupitem, NULL );
178 if ( new_item == NULL )
181 /* Create a chain if the bucket is empty */
182 if ( htab->table[h] == NULL ) {
183 htab->table[h] = new_chain();
185 if ( htab->table[h] == NULL ) {
186 htab->keyrel ( new_item->key );
187 htab->itemrel ( new_item->item );
193 /* Insert at the front of the chain */
194 new_item->next = htab->table[h]->first;
195 htab->table[h]->first = new_item;
197 ++htab->table[h]->size;
204 Remove an item with the selected key
206 Returns: non-zero for success, zero for failure
208 int jsw_herase ( jsw_hash_t *htab, void *key )
210 unsigned h = htab->hash ( key ) % htab->capacity;
211 jsw_node_t *save, *it;
213 if ( htab->table[h] == NULL )
216 it = htab->table[h]->first;
218 /* Remove the first node in the chain? */
219 if ( htab->cmp ( key, it->key ) == 0 ) {
220 htab->table[h]->first = it->next;
222 /* Release the node's memory */
223 htab->keyrel ( it->key );
224 htab->itemrel ( it->item );
227 /* Remove the chain if it's empty */
228 if ( htab->table[h]->first == NULL ) {
229 free ( htab->table[h] );
230 htab->table[h] = NULL;
233 --htab->table[h]->size;
236 /* Search for the node */
237 while ( it->next != NULL ) {
238 if ( htab->cmp ( key, it->next->key ) == 0 )
245 if ( it->next == NULL )
249 it->next = it->next->next;
251 /* Release the node's memory */
252 htab->keyrel ( save->key );
253 htab->itemrel ( save->item );
256 --htab->table[h]->size;
259 /* Erasure invalidates traversal markers */
268 Grow or shrink the table, this is a slow operation
270 Returns: non-zero for success, zero for failure
272 int jsw_hresize ( jsw_hash_t *htab, size_t new_size )
274 jsw_hash_t *new_htab;
278 /* Build a new hash table, then assign it to the old one */
279 new_htab = jsw_hnew ( new_size, htab->hash, htab->cmp,
280 htab->keydup, htab->itemdup, htab->keyrel, htab->itemrel );
282 if ( new_htab == NULL )
285 for ( i = 0; i < htab->capacity; i++ ) {
286 if ( htab->table[i] == NULL )
289 for ( it = htab->table[i]->first; it != NULL; it = it->next )
290 jsw_hinsert ( new_htab, it->key, it->item );
293 /* A hash table holds copies, so release the old table */
294 jsw_hdelete ( htab );
300 /* Reset the traversal markers to the beginning */
301 void jsw_hreset ( jsw_hash_t *htab )
308 /* Find the first non-empty bucket */
309 for ( i = 0; i < htab->capacity; i++ ) {
310 if ( htab->table[i] != NULL )
316 /* Set the link marker if the table was not empty */
317 if ( i != htab->capacity )
318 htab->currl = htab->table[i]->first;
321 /* Traverse forward by one key */
322 int jsw_hnext ( jsw_hash_t *htab )
324 if ( htab->currl != NULL ) {
325 htab->currl = htab->currl->next;
327 /* At the end of the chain? */
328 if ( htab->currl == NULL ) {
329 /* Find the next chain */
330 while ( ++htab->curri < htab->capacity ) {
331 if ( htab->table[htab->curri] != NULL )
335 /* No more chains? */
336 if ( htab->curri == htab->capacity )
339 htab->currl = htab->table[htab->curri]->first;
346 /* Get the current key */
347 const void *jsw_hkey ( jsw_hash_t *htab )
349 return htab->currl != NULL ? htab->currl->key : NULL;
352 /* Get the current item */
353 void *jsw_hitem ( jsw_hash_t *htab )
355 return htab->currl != NULL ? htab->currl->item : NULL;
358 /* Current number of items in the table */
359 size_t jsw_hsize ( jsw_hash_t *htab )
364 /* Total allowable number of items without resizing */
365 size_t jsw_hcapacity ( jsw_hash_t *htab )
367 return htab->capacity;
370 /* Get statistics for the hash table */
371 jsw_hstat_t *jsw_hstat ( jsw_hash_t *htab )
374 double sum = 0, used = 0;
377 /* No stats for an empty table */
378 if ( htab->size == 0 )
381 stat = malloc ( sizeof *stat );
387 stat->schain = (size_t)-1;
389 for ( i = 0; i < htab->capacity; i++ ) {
390 if ( htab->table[i] != NULL ) {
391 sum += htab->table[i]->size;
393 ++used; /* Non-empty buckets */
395 if ( htab->table[i]->size > stat->lchain )
396 stat->lchain = htab->table[i]->size;
398 if ( htab->table[i]->size < stat->schain )
399 stat->schain = htab->table[i]->size;
403 stat->load = used / htab->capacity;
404 stat->achain = sum / used;