Lines Matching refs:hash
17 * $Id: hash.c,v 1.4 2009-11-19 10:37:43 franklahm Exp $
26 #include "hash.h"
29 static const char rcsid[] = "$Id: hash.c,v 1.4 2009-11-19 10:37:43 franklahm Exp $";
121 static void clear_table(hash_t *hash)
125 for (i = 0; i < hash->nchains; i++)
126 hash->table[i] = NULL;
136 * the hash table will continue to function exactly as before without having to
150 * chains based on the value of each node's newly exposed hash bit.
154 * the various bookeeping fields of the hash structure.
157 static void grow_table(hash_t *hash)
161 assert (2 * hash->nchains > hash->nchains); /* 1 */
163 newtable = realloc(hash->table,
164 sizeof *newtable * hash->nchains * 2); /* 4 */
167 hash_val_t mask = (hash->mask << 1) | 1; /* 3 */
168 hash_val_t exposed_bit = mask ^ hash->mask; /* 6 */
171 assert (mask != hash->mask);
173 for (chain = 0; chain < hash->nchains; chain++) { /* 7 */
189 newtable[chain + hash->nchains] = high_chain;
192 hash->table = newtable; /* 9 */
193 hash->mask = mask;
194 hash->nchains *= 2;
195 hash->lowmark *= 2;
196 hash->highmark *= 2;
198 assert (hash_verify(hash));
207 * 1. It is illegal to have a hash table with one slot. This would mean that
208 * hash->shift is equal to hash_val_t_bit, an illegal shift value.
209 * Also, other things could go wrong, such as hash->lowmark becoming zero.
231 static void shrink_table(hash_t *hash)
236 assert (hash->nchains >= 2); /* 1 */
237 nchains = hash->nchains / 2;
240 low_chain = hash->table[chain]; /* 2 */
241 high_chain = hash->table[chain + nchains];
247 hash->table[chain] = high_chain;
249 assert (hash->table[chain] == NULL); /* 6 */
251 newtable = realloc(hash->table,
254 hash->table = newtable;
255 hash->mask >>= 1; /* 9 */
256 hash->nchains = nchains;
257 hash->lowmark /= 2;
258 hash->highmark /= 2;
259 assert (hash_verify(hash));
264 * Create a dynamic hash table. Both the hash table structure and the table
272 * 2. Allocate a hash table control structure.
273 * 3. If a hash table control structure is successfully allocated, we
275 * 4. We try to allocate the table of hash chains.
276 * 5. If we were able to allocate the hash chain table, we can finish
277 * initializing the hash structure and the table. Otherwise, we must
278 * backtrack by freeing the hash structure.
295 hash_t *hash;
300 hash = malloc(sizeof *hash); /* 2 */
302 if (hash) { /* 3 */
303 hash->table = malloc(sizeof *hash->table * INIT_SIZE); /* 4 */
304 if (hash->table) { /* 5 */
305 hash->nchains = INIT_SIZE; /* 6 */
306 hash->highmark = INIT_SIZE * 2;
307 hash->lowmark = INIT_SIZE / 2;
308 hash->nodecount = 0;
309 hash->maxcount = maxcount;
310 hash->compare = compfun ? compfun : hash_comp_default;
311 hash->function = hashfun ? hashfun : hash_fun_default;
312 hash->allocnode = hnode_alloc;
313 hash->freenode = hnode_free;
314 hash->context = NULL;
315 hash->mask = INIT_MASK;
316 hash->dynamic = 1; /* 7 */
317 clear_table(hash); /* 8 */
318 assert (hash_verify(hash));
319 return hash;
321 free(hash);
331 void hash_set_allocator(hash_t *hash, hnode_alloc_t al,
334 assert (hash_count(hash) == 0);
337 hash->allocnode = al ? al : hnode_alloc;
338 hash->freenode = fr ? fr : hnode_free;
339 hash->context = context;
343 * Free every node in the hash using the hash->freenode() function pointer, and
344 * cause the hash to become empty.
347 void hash_free_nodes(hash_t *hash)
351 hash_scan_begin(&hs, hash);
353 hash_scan_delete(hash, node);
354 hash->freenode(node, hash->context);
356 hash->nodecount = 0;
357 clear_table(hash);
365 void hash_free(hash_t *hash)
370 hash_free_nodes(hash);
371 hash_destroy(hash);
375 * Free a dynamic hash table structure.
378 void hash_destroy(hash_t *hash)
381 assert (hash_isempty(hash));
382 free(hash->table);
383 free(hash);
387 * Initialize a user supplied hash structure. The user also supplies a table of
388 * chains which is assigned to the hash structure. The table is static---it
399 hash_t *hash_init(hash_t *hash, hashcount_t maxcount,
408 hash->table = table; /* 2 */
409 hash->nchains = nchains;
410 hash->nodecount = 0;
411 hash->maxcount = maxcount;
412 hash->compare = compfun ? compfun : hash_comp_default;
413 hash->function = hashfun ? hashfun : hash_fun_default;
414 hash->dynamic = 0; /* 3 */
415 hash->mask = compute_mask(nchains); /* 4 */
416 clear_table(hash); /* 5 */
418 assert (hash_verify(hash));
420 return hash;
424 * Reset the hash scanner so that the next element retrieved by
434 void hash_scan_begin(hscan_t *scan, hash_t *hash)
436 hash_val_t nchains = hash->nchains;
439 scan->table = hash;
443 for (chain = 0; chain < nchains && hash->table[chain] == NULL; chain++)
448 scan->next = hash->table[chain];
455 * Retrieve the next node from the hash table, and update the pointer
483 hash_t *hash = scan->table;
485 hash_val_t nchains = hash->nchains;
493 while (chain < nchains && hash->table[chain] == NULL) /* 5 */
497 scan->next = hash->table[chain];
507 * Insert a node into the hash table.
510 * should verify that the hash table is not full before attempting an
515 * 4. We take the bottom N bits of the hash value to derive the chain index,
516 * where N is the base 2 logarithm of the size of the hash table.
519 void hash_insert(hash_t *hash, hnode_t *node, const void *key)
525 assert (hash->nodecount < hash->maxcount); /* 1 */
526 assert (hash_lookup(hash, key) == NULL); /* 2 */
528 if (hash->dynamic && hash->nodecount >= hash->highmark) /* 3 */
529 grow_table(hash);
531 hkey = hash->function(key);
532 chain = hkey & hash->mask; /* 4 */
536 node->next = hash->table[chain];
537 hash->table[chain] = node;
538 hash->nodecount++;
540 assert (hash_verify(hash));
544 * Find a node in the hash table and return a pointer to it.
546 * 1. We hash the key and keep the entire hash value. As an optimization, when
547 * we descend down the chain, we can compare hash values first and only if
548 * hash values match do we perform a full key comparison.
550 * the hash value by anding them with the current mask.
551 * 3. Looping through the chain, we compare the stored hash value inside each
552 * node against our computed hash. If they match, then we do a full
557 hnode_t *hash_lookup(hash_t *hash, const void *key)
562 hkey = hash->function(key); /* 1 */
563 chain = hkey & hash->mask; /* 2 */
565 for (nptr = hash->table[chain]; nptr; nptr = nptr->next) { /* 3 */
566 if (nptr->hkey == hkey && hash->compare(nptr->key, key) == 0)
574 * Delete the given node from the hash table. Since the chains
578 * 1. The node must belong to this hash table, and its key must not have
588 * 6. Indicate that the node is no longer in a hash table.
591 hnode_t *hash_delete(hash_t *hash, hnode_t *node)
596 assert (hash_lookup(hash, node->key) == node); /* 1 */
599 if (hash->dynamic && hash->nodecount <= hash->lowmark
600 && hash->nodecount > INIT_SIZE)
601 shrink_table(hash); /* 2 */
603 chain = node->hkey & hash->mask; /* 3 */
604 hptr = hash->table[chain];
607 hash->table[chain] = node->next;
617 hash->nodecount--;
618 assert (hash_verify(hash));
624 int hash_alloc_insert(hash_t *hash, const void *key, void *data)
626 hnode_t *node = hash->allocnode(hash->context);
630 hash_insert(hash, node, key);
636 void hash_delete_free(hash_t *hash, hnode_t *node)
638 hash_delete(hash, node);
639 hash->freenode(node, hash->context);
644 * used from within a hash table scan operation. See notes for hash_delete.
647 hnode_t *hash_scan_delete(hash_t *hash, hnode_t *node)
652 assert (hash_lookup(hash, node->key) == node);
655 chain = node->hkey & hash->mask;
656 hptr = hash->table[chain];
659 hash->table[chain] = node->next;
666 hash->nodecount--;
667 assert (hash_verify(hash));
677 void hash_scan_delfree(hash_t *hash, hnode_t *node)
679 hash_scan_delete(hash, node);
680 hash->freenode(node, hash->context);
684 * Verify whether the given object is a valid hash table. This means
686 * 1. If the hash table is dynamic, verify whether the high and
688 * 2. Count all nodes in the table, and test each hash value
692 int hash_verify(hash_t *hash)
698 if (hash->dynamic) { /* 1 */
699 if (hash->lowmark >= hash->highmark)
701 if (!is_power_of_two(hash->highmark))
703 if (!is_power_of_two(hash->lowmark))
707 for (chain = 0; chain < hash->nchains; chain++) { /* 2 */
708 for (hptr = hash->table[chain]; hptr != NULL; hptr = hptr->next) {
709 if ((hptr->hkey & hash->mask) != chain)
715 if (count != hash->nodecount)
722 * Test whether the hash table is full and return 1 if this is true,
727 int hash_isfull(hash_t *hash)
729 return hash->nodecount == hash->maxcount;
733 * Test whether the hash table is empty and return 1 if this is true,
738 int hash_isempty(hash_t *hash)
740 return hash->nodecount == 0;
755 * Create a hash table node dynamically and assign it the given data.
807 hashcount_t hash_count(hash_t *hash)
809 return hash->nodecount;
813 hashcount_t hash_size(hash_t *hash)
815 return hash->nchains;
841 /* From http://www.azillionmonkeys.com/qed/hash.html */
857 hash_val_t hash = 0, tmp = 0;
866 hash += get16bits (data);
867 tmp = (get16bits (data+2) << 11) ^ hash;
868 hash = (hash << 16) ^ tmp;
870 hash += hash >> 11;
875 case 3: hash += get16bits (data);
876 hash ^= hash << 16;
877 hash ^= data[sizeof (uint16_t)] << 18;
878 hash += hash >> 11;
880 case 2: hash += get16bits (data);
881 hash ^= hash << 11;
882 hash += hash >> 17;
884 case 1: hash += *data;
885 hash ^= hash << 10;
886 hash += hash >> 1;
890 hash ^= hash << 3;
891 hash += hash >> 5;
892 hash ^= hash << 4;
893 hash += hash >> 17;
894 hash ^= hash << 25;
895 hash += hash >> 6;
897 return hash;
975 "a <key> <val> add value to hash table\n"
976 "d <key> delete value from hash table\n"
977 "l <key> lookup value in hash table\n"
978 "n show size of hash table\n"
980 "t dump whole hash table\n"
981 "+ increase hash table (private func)\n"
982 "- decrease hash table (private func)\n"