| /* |
| * Copyright (c) 2002-2005 Lev Walkin <vlm@lionet.info>. All rights reserved. |
| * Copyright (c) 2001-2004 Netli, Inc. All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND |
| * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE |
| * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
| * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
| * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
| * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
| * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
| * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
| * SUCH DAMAGE. |
| * |
| * $Id: genhash.c 447 2005-06-07 06:51:10Z vlm $ |
| */ |
| /* |
| * Implementation of a hash data structure. |
| * This particular implementation is supposed to be space-efficient |
| * particularly in the case of tiny number of hash elements. |
| * It also has an aggressive hash buckets expanding technique, which allows |
| * to deal with increasing number of elements without a loss of search speed. |
| * |
| * Generally, one structure of type genhash_t is allocated per hash set. |
| * This structure is supposed to hold all information related to the current |
| * set, and also holds a tiny number of hash elements, when hash hasn't yet |
| * grown up. When the number of elements reaches some point, part of the |
| * genhash_t structure is reused to contain the pointers to the actual |
| * hash buckets and LRU (Least Recently Used) list's head and tail. |
| * Elements which were held inside genhash_t will be moved to the hash buckets. |
| * |
| * Said above effectively means two modes of operation: TINY and NORMAL. |
| * They can be distinguished by examining the h->numbuckets value, which |
| * is 0 for TINY and greater for NORMAL mode. |
| * |
| * In the TINY mode we use a lower part of the genhash_t structure |
| * (lower 32 bytes from 64 bytes of genhash_t) to hold up to IH_VALUE (4) |
| * key/value pairs. |
| * |
| * In the NORMAL mode we use the lower part of the genhash_t structure |
| * to hold a set of pointers, including a pointer to the hash buckets. |
| * We agressively expand hash buckets size when adding new elements |
| * to lower the number of key comparisons. |
| */ |
| |
| #include <sys/types.h> |
| #include <stdlib.h> |
| #include <string.h> |
| #include <assert.h> |
| #include <stddef.h> |
| #include <errno.h> |
| #include "genhash.h" |
| |
| /* 1M entries, 4M RAM */ |
| #define DEFAULT_MAXIMUM_HASH_BUCKETS_NUMBER (1024 * 1024) |
| static int maximum_hash_buckets_number = DEFAULT_MAXIMUM_HASH_BUCKETS_NUMBER; |
| |
| /* |
| * A single hash element structure which binds a value to its key. |
| */ |
| typedef struct genhash_el_s { |
| unsigned int key_hash; /* Saved hash of the key */ |
| void *key; |
| void *value; |
| struct genhash_el_s *hash_next; /* Collision list inside the bucket */ |
| struct genhash_el_s *hash_prev; |
| struct genhash_el_s *lru_prev; /* Per-hash LRU list */ |
| struct genhash_el_s *lru_next; |
| } genhash_el; |
| |
| /* |
| * A hash structure with buckets etc. |
| */ |
| struct genhash_s { |
| int (*keycmpf) (const void *lkey1, const void *rkey2); |
| unsigned int (*keyhashf) (const void *key); /* hash function */ |
| void (*keydestroyf) (void *key); /* key destructor */ |
| void (*valuedestroyf) (void *value); /* value destructor */ |
| |
| int numelements; /* Total number of hash elements */ |
| int numbuckets; /* 0 means "use _TINY" */ |
| int lru_limit; /* Must be initialized explicitly */ |
| genhash_iter_t *iters; /* Active iterators */ |
| |
| /* 32-byte boundary here */ |
| |
| union { |
| #define IH_VALUES 4 /* Internally held key/value pairs for TINY mode */ |
| struct _internal_tiny_s { |
| void *keys[IH_VALUES]; |
| void *values[IH_VALUES]; |
| } _TINY; /* 32-byte structure */ |
| struct _internal_normal_s { |
| genhash_el *lru_head; /* LRU list head */ |
| genhash_el *lru_tail; /* LRU list tail */ |
| genhash_el **buckets; /* Hash buckets */ |
| /* void *unused; */ |
| } _NORMAL; |
| } un; |
| #define tiny_keys un._TINY.keys |
| #define tiny_values un._TINY.values |
| #define lru_head un._NORMAL.lru_head |
| #define lru_tail un._NORMAL.lru_tail |
| #define buckets un._NORMAL.buckets |
| }; |
| |
| |
| static int |
| _genhash_normal_add(genhash_t *h, genhash_el *el, void *key, void *value); |
| |
| |
| genhash_t * |
| genhash_new( |
| int (*keycmpf) (const void *key1, const void *key2), |
| unsigned int (*keyhashf) (const void *key), |
| void (*keydestroyf) (void *key), |
| void (*valuedestroyf) (void *value) |
| ) { |
| genhash_t *h; |
| |
| h = (genhash_t *)malloc(sizeof(genhash_t)); |
| if (!h) |
| return NULL; |
| |
| memset(h, 0, sizeof(genhash_t)); |
| |
| genhash_reinit(h, keycmpf, keyhashf, keydestroyf, valuedestroyf); |
| |
| return h; |
| } |
| |
| int |
| genhash_reinit( |
| genhash_t *h, |
| int (*keycmpf) (const void *key1, const void *key2), |
| unsigned int (*keyhashf) (const void *key), |
| void (*keydestroyf) (void *key), |
| void (*valuedestroyf) (void *value) |
| ) { |
| |
| assert(keycmpf && keyhashf); |
| |
| h->keycmpf = keycmpf; |
| h->keyhashf = keyhashf; |
| h->keydestroyf = keydestroyf; |
| h->valuedestroyf = valuedestroyf; |
| |
| return 0; |
| } |
| |
| int |
| genhash_count(genhash_t *h) { |
| if(h) { |
| return h->numelements; |
| } else { |
| return 0; |
| } |
| } |
| |
| |
| static void |
| _remove_normal_hash_el(genhash_t *h, genhash_el *el) { |
| genhash_iter_t *iter; |
| void *kd_arg; |
| void *vd_arg; |
| |
| /* Remove from the collision list */ |
| if (el->hash_prev) { |
| if((el->hash_prev->hash_next = el->hash_next)) |
| el->hash_next->hash_prev = el->hash_prev; |
| |
| } else { |
| if((h->buckets[el->key_hash % h->numbuckets] = el->hash_next)) |
| el->hash_next->hash_prev = NULL; |
| } |
| |
| /* Remove from LRU list */ |
| if(el->lru_prev) { |
| if((el->lru_prev->lru_next = el->lru_next)) |
| el->lru_next->lru_prev = el->lru_prev; |
| else |
| h->lru_tail = el->lru_prev; |
| } else { |
| if(h->lru_head == el) { |
| if((h->lru_head = el->lru_next) == NULL) |
| h->lru_tail = NULL; |
| else |
| h->lru_head->lru_prev = NULL; |
| } |
| } |
| |
| /* Remember key and value */ |
| kd_arg = el->key; |
| vd_arg = el->value; |
| |
| /* Move iterators off the element being deleted */ |
| for(iter = h->iters; iter; iter = iter->iter_next) { |
| assert(iter->hash_ptr == h); |
| if(iter->un.location == el) { |
| iter->un.location = iter->order_lru_first |
| ? el->lru_prev : el->lru_next; |
| } |
| } |
| |
| free(el); |
| h->numelements--; |
| |
| /* Remove key and value */ |
| if (h->keydestroyf) h->keydestroyf(kd_arg); |
| if (h->valuedestroyf) h->valuedestroyf(vd_arg); |
| } |
| |
| static inline void |
| _genhash_normal_el_move2top(genhash_t *h, genhash_el *el) { |
| |
| /* Disable sorting if iterators are running */ |
| if(h->iters) return; |
| |
| /* Move to the top of the hash bucket */ |
| if(el->hash_prev) { |
| int bucket = el->key_hash % h->numbuckets; |
| |
| /* Remove from the current location */ |
| if((el->hash_prev->hash_next = el->hash_next)) |
| el->hash_next->hash_prev = el->hash_prev; |
| |
| /* Move to the top of the hash bucket */ |
| if((el->hash_next = h->buckets[bucket])) |
| el->hash_next->hash_prev = el; |
| h->buckets[bucket] = el; |
| el->hash_prev = NULL; |
| } |
| |
| /* Move to the top of LRU list */ |
| if(h->lru_limit && el->lru_prev) { |
| |
| /* Remove from current location */ |
| if((el->lru_prev->lru_next = el->lru_next)) |
| el->lru_next->lru_prev = el->lru_prev; |
| else |
| h->lru_tail = el->lru_prev; |
| |
| /* Append to the head */ |
| el->lru_prev = NULL; |
| h->lru_head->lru_prev = el; |
| el->lru_next = h->lru_head; |
| h->lru_head = el; |
| } |
| } |
| |
| static int |
| _expand_hash(genhash_t *h) { |
| int newbuckets_count; |
| genhash_el **newbuckets; |
| |
| /* |
| * Compute a new number of buckets value. |
| */ |
| if(h->numbuckets) { |
| newbuckets_count = h->numbuckets << 2; |
| /* Too big hash table */ |
| if(newbuckets_count > maximum_hash_buckets_number) { |
| if(h->numbuckets < maximum_hash_buckets_number) { |
| newbuckets_count = maximum_hash_buckets_number; |
| } else { |
| /* No need to set errno here. */ |
| return -1; |
| } |
| } |
| } else { |
| /* 8 buckets -> 32 bytes of memory */ |
| newbuckets_count = IH_VALUES << 1; |
| if(newbuckets_count > maximum_hash_buckets_number) { |
| if(maximum_hash_buckets_number) { |
| newbuckets_count = maximum_hash_buckets_number; |
| } else { |
| /* Allowed to store only IH_VALUES elements */ |
| errno = EPERM; |
| return -1; |
| } |
| } |
| } |
| |
| /* |
| * Allocate a new storage for buckets. |
| */ |
| newbuckets = malloc(newbuckets_count * sizeof(*newbuckets)); |
| if(newbuckets) { |
| memset(newbuckets, 0, newbuckets_count * sizeof(*newbuckets)); |
| } else { |
| return -1; |
| } |
| |
| if(h->numbuckets) { |
| genhash_el *el; |
| int bucket; |
| |
| /* |
| * Rehash elements from old h->buckets to newbuckets. |
| * No need to touch LRU pointers and other stuff - it is okay. |
| */ |
| for(el = h->lru_tail; el; el = el->lru_prev) { |
| bucket = el->key_hash % newbuckets_count; |
| el->hash_prev = NULL; |
| if((el->hash_next = newbuckets[bucket])) |
| el->hash_next->hash_prev = el; |
| newbuckets[bucket] = el; |
| } |
| |
| free(h->buckets); |
| h->buckets = newbuckets; |
| h->numbuckets = newbuckets_count; |
| } else { |
| /* |
| * Moving from inline tiny storage into buckets. |
| */ |
| genhash_el *els[IH_VALUES] = { NULL }; |
| struct _internal_tiny_s tiny_substruct; |
| int i; |
| int saved_numelements; |
| int saved_lru_limit; |
| genhash_iter_t *iter; |
| |
| /* Pre-allocate hash elements (for "undo") */ |
| for(i = 0; i < h->numelements; i++) { |
| els[i] = (genhash_el *)malloc(sizeof(genhash_el)); |
| if(els[i] == NULL) { |
| for(i = 0; i < h->numelements; i++) |
| if(els[i]) |
| free(els[i]); |
| free(newbuckets); |
| return -1; |
| } |
| } |
| |
| /* Save part of the union */ |
| tiny_substruct = h->un._TINY; |
| /* Re-initialize this part in NORMAL model */ |
| memset(&h->un._NORMAL, 0, sizeof(h->un._NORMAL)); |
| |
| /* There was no allocated buckets, when in tiny hash mode. */ |
| h->buckets = newbuckets; |
| h->numbuckets = newbuckets_count; |
| |
| saved_numelements = h->numelements; |
| saved_lru_limit = h->lru_limit; |
| h->numelements = 0; |
| h->lru_limit = 0; /* Disable LRU expiration for a while */ |
| |
| for(i = saved_numelements - 1; i >= 0; --i) { |
| /* |
| * genhash_normal_add won't fail, if we supply |
| * an already allocated genhash_el *. |
| */ |
| (void)_genhash_normal_add(h, els[i], |
| tiny_substruct.keys[i], |
| tiny_substruct.values[i]); |
| } |
| |
| /* Now, scan through iterators and convert them TINY->NORMAL */ |
| for(iter = h->iters; iter; iter = iter->iter_next) { |
| assert(iter->hash_ptr == h); |
| if(iter->un.item_number < 0 |
| || iter->un.item_number >= saved_numelements) { |
| iter->un.location = 0; |
| } else { |
| iter->un.location = els[iter->un.item_number]; |
| } |
| } |
| |
| h->lru_limit = saved_lru_limit; |
| } |
| |
| return 0; |
| } |
| |
| /* |
| * Won't return with error if el is provided. |
| */ |
| static int |
| _genhash_normal_add(genhash_t *h, genhash_el *el, void *key, void *value) { |
| genhash_el **bucket; |
| |
| if(el == NULL) { |
| el = malloc(sizeof (*el)); |
| if(el == NULL) { |
| /* Errno will be set by malloc() */ |
| return -1; |
| } |
| } |
| |
| /* Maintain maximum number of entries */ |
| if(h->lru_limit) { |
| while(h->numelements >= h->lru_limit) |
| _remove_normal_hash_el(h, h->lru_tail); |
| } |
| |
| memset(el, 0, sizeof(genhash_el)); |
| |
| /* Compute the index of the collision list */ |
| el->key_hash = h->keyhashf(key); |
| bucket = &h->buckets[el->key_hash % h->numbuckets]; |
| |
| el->key = key; |
| el->value = value; |
| |
| /* |
| * Add to the collision list |
| */ |
| el->hash_prev = NULL; |
| if((el->hash_next = *bucket)) |
| (*bucket)->hash_prev = el; |
| *bucket = el; |
| |
| /* |
| * Add to the LRU list. |
| */ |
| if(h->lru_head) { |
| el->lru_next = h->lru_head; |
| el->lru_next->lru_prev = el; |
| h->lru_head = el; |
| } else { |
| h->lru_head = el; |
| h->lru_tail = el; |
| } |
| |
| h->numelements++; |
| |
| return 0; |
| } |
| |
| |
| int |
| genhash_add(genhash_t *h, void *key, void *value) { |
| |
| if(key == NULL) { |
| errno = EINVAL; |
| return -1; |
| } |
| |
| if(h->numbuckets == 0) { |
| |
| /* We have a tiny internally-held set of elements */ |
| if(h->numelements < IH_VALUES) { |
| h->tiny_keys[h->numelements] = key; |
| h->tiny_values[h->numelements] = value; |
| h->numelements++; |
| return 0; |
| } |
| |
| if(_expand_hash(h) == -1) |
| return -1; |
| |
| } else { |
| |
| if((h->numelements / h->numbuckets) > 2) |
| (void)_expand_hash(h); |
| } |
| |
| return _genhash_normal_add(h, NULL, key, value); |
| } |
| |
| int |
| genhash_addunique(genhash_t *h, void *key, void *value) { |
| if(genhash_get(h, key)) { |
| errno = EEXIST; |
| return -1; |
| } |
| return genhash_add(h, key, value); |
| } |
| |
| void * |
| genhash_get(genhash_t *h, const void *key) { |
| |
| if(h->numbuckets) { |
| |
| genhash_el *walk; |
| int bucket = h->keyhashf(key) % h->numbuckets; |
| |
| for(walk = h->buckets[bucket]; |
| walk; walk = walk->hash_next) { |
| |
| if (h->keycmpf(walk->key, key) == 0) { |
| _genhash_normal_el_move2top(h, walk); |
| return walk->value; |
| } |
| } |
| |
| } else { |
| /* TINY mode */ |
| int i; |
| |
| assert(h->numelements <= IH_VALUES); |
| for(i = 0; i < h->numelements; i++) { |
| if(h->keycmpf(h->tiny_keys[i], key) == 0) |
| /* Don't reorder in TINY mode */ |
| return h->tiny_values[i]; |
| } |
| |
| } |
| |
| errno = ESRCH; |
| return NULL; |
| } |
| |
| int |
| genhash_del(genhash_t *h, void *key) { |
| |
| if(h->numbuckets) { |
| /* NORMAL mode */ |
| genhash_el *walk; |
| int bucket; |
| |
| if(h->numelements == 0) { |
| errno = ESRCH; |
| return -1; /* not found */ |
| } |
| |
| bucket = h->keyhashf(key) % h->numbuckets; |
| |
| for(walk = h->buckets[bucket]; walk; walk = walk->hash_next) |
| if(h->keycmpf(walk->key, key) == 0) |
| break; |
| |
| if(walk) { |
| _remove_normal_hash_el(h, walk); |
| return 0; |
| } |
| } else { |
| /* TINY mode */ |
| int i; |
| |
| /* Look for matching key */ |
| for(i = 0; i < h->numelements; i++) |
| if(h->keycmpf(h->tiny_keys[i], key) == 0) |
| break; |
| |
| if(i < h->numelements) { |
| /* Remember values */ |
| void *kd_arg = h->tiny_keys[i]; |
| void *vd_arg = h->tiny_values[i]; |
| |
| h->numelements--; |
| |
| if(h->iters) { |
| /* If iterators are involved, we have to |
| * shift elements to maintain iteration order |
| * and avoid duplications */ |
| genhash_iter_t *iter; |
| memmove(&h->tiny_keys[i], |
| &h->tiny_keys[i+1], |
| (h->numelements - i) |
| * sizeof(h->tiny_keys[0])); |
| memmove(&h->tiny_values[i], |
| &h->tiny_values[i+1], |
| (h->numelements - i) |
| * sizeof(h->tiny_values[0])); |
| /* Shift the iterator's indexes */ |
| for(iter = h->iters; iter; |
| iter = iter->iter_next) { |
| int in = iter->un.item_number; |
| if(iter->order_lru_first) { |
| if(in > i) |
| iter->un.item_number--; |
| } else { |
| if(in >= i) |
| iter->un.item_number--; |
| } |
| } |
| } else { |
| /* Substitute it with the last one */ |
| /* No harm if overwriting itself */ |
| h->tiny_keys[i] = h->tiny_keys[h->numelements]; |
| h->tiny_values[i] = h->tiny_values[h->numelements]; |
| } |
| h->tiny_keys[h->numelements] = 0; |
| h->tiny_values[h->numelements] = 0; |
| /* Delete for real */ |
| if(h->keydestroyf) h->keydestroyf(kd_arg); |
| if(h->valuedestroyf) h->valuedestroyf(vd_arg); |
| return 0; |
| } |
| } |
| |
| errno = ESRCH; |
| return -1; |
| } |
| |
| /* |
| * Initialize a hash iterator. |
| */ |
| int |
| genhash_iter_init(genhash_iter_t *iter, genhash_t *h, int reverse_order) { |
| |
| iter->hash_ptr = h; |
| iter->iter_prev = 0; /* Add itself to the iterators list */ |
| iter->iter_next = h->iters; |
| h->iters = iter; |
| iter->order_lru_first = reverse_order; |
| |
| if(h->numbuckets) { |
| /* NORMAL mode */ |
| if(reverse_order) { |
| /* Least recent first order */ |
| iter->un.location = h->lru_tail; |
| } else { |
| /* Most recent first order */ |
| iter->un.location = h->lru_head; |
| } |
| } else { |
| /* TINY mode */ |
| if(reverse_order) { |
| iter->un.item_number = 0; |
| } else { |
| iter->un.item_number = h->numelements - 1; |
| } |
| } |
| |
| return h->numelements; |
| } |
| |
| int |
| genhash_iter(genhash_iter_t *iter, void *key_p, void *val_p) { |
| void **key = key_p; |
| void **val = val_p; |
| genhash_t *h = iter->hash_ptr; |
| |
| if(h->numbuckets) { |
| /* NORMAL mode */ |
| genhash_el *cur_el = iter->un.location; |
| if(!cur_el) |
| /* Already finished */ |
| return 0; |
| |
| if(key) *key = cur_el->key; |
| if(val) *val = cur_el->value; |
| |
| /* Move pointer to the next hash element */ |
| iter->un.location = iter->order_lru_first |
| ? cur_el->lru_prev : cur_el->lru_next; |
| } else { |
| /* TINY mode */ |
| if(iter->un.item_number < 0 |
| || iter->un.item_number >= h->numelements |
| || h->tiny_keys[iter->un.item_number] == 0) |
| return 0; |
| |
| if(key) *key = h->tiny_keys[iter->un.item_number]; |
| if(val) *val = h->tiny_values[iter->un.item_number]; |
| |
| /* Advance to the next element */ |
| if(iter->order_lru_first) |
| iter->un.item_number++; |
| else |
| iter->un.item_number--; |
| } |
| |
| |
| return 1; |
| } |
| |
| void |
| genhash_iter_done(genhash_iter_t *iter) { |
| assert(iter->hash_ptr->iters); |
| /* Remove itself from the iterators list */ |
| if(iter->iter_next) |
| iter->iter_next->iter_prev = iter->iter_prev; |
| if(iter->iter_prev) |
| iter->iter_prev->iter_next = iter->iter_next; |
| else |
| iter->hash_ptr->iters = iter->iter_next; /* Shift the head */ |
| iter->hash_ptr = (void *)0xdeadbeef; |
| } |
| |
| int |
| genhash_set_lru_limit(genhash_t *h, int value) { |
| if(h) { |
| int prev_limit = h->lru_limit; |
| if(value >= 0) |
| h->lru_limit = value; |
| return prev_limit; |
| } else { |
| errno = EINVAL; |
| return -1; |
| } |
| } |
| |
| int |
| genhash_set_buckets_limit(int value) { |
| int prev_limit = maximum_hash_buckets_number; |
| if(value > 0) { |
| maximum_hash_buckets_number = value; |
| } |
| return prev_limit; |
| } |
| |
| void |
| genhash_destroy(genhash_t *h) { |
| if(h) { |
| assert(h->iters == 0); /* All iterators MUST be _done(). */ |
| genhash_empty(h, 1, 1); |
| free(h); |
| } |
| } |
| |
| void |
| genhash_empty(genhash_t *h, int freekeys, int freevalues) { |
| genhash_iter_t *iter; |
| |
| if(h == NULL) return; |
| |
| /* |
| * Don't free what could not be freed. |
| */ |
| if(h->keydestroyf == NULL) freekeys = 0; |
| if(h->valuedestroyf == NULL) freevalues = 0; |
| |
| if(h->numbuckets == 0) { |
| while(h->numelements > 0) { |
| int n = --h->numelements; |
| void *kd_arg = h->tiny_keys[n]; |
| void *vd_arg = h->tiny_values[n]; |
| |
| if (freekeys) h->keydestroyf(kd_arg); |
| if (freevalues) h->valuedestroyf(vd_arg); |
| } |
| } else { |
| genhash_el *el, *el_next; |
| |
| for(el = h->lru_head; el; el = el_next) { |
| void *kd_arg = el->key; |
| void *vd_arg = el->value; |
| el_next = el->lru_next; |
| free(el); |
| |
| h->numelements --; |
| |
| if (freekeys) h->keydestroyf(kd_arg); |
| if (freevalues) h->valuedestroyf(vd_arg); |
| } |
| free(h->buckets); |
| h->numbuckets = 0; /* Move back to TINY model */ |
| } |
| memset(&h->un, 0, sizeof(h->un)); |
| |
| /* Invalidate iterators in TINY model */ |
| for(iter = h->iters; iter; iter = iter->iter_next) { |
| assert(iter->hash_ptr == h); |
| iter->un.item_number = -1; |
| } |
| |
| assert(h->numelements == 0); |
| } |
| |
| |
| /*----- Simple hash and compare functions for common data types ------*/ |
| |
| unsigned int |
| hashf_int (const void *key) { |
| return (*(const ptrdiff_t *)key ^ (*(const ptrdiff_t *)key >> 16)); |
| } |
| |
| int |
| cmpf_int (const void *key1, const void *key2) { |
| return (*(const int *)key1 != *(const int *)key2); |
| } |
| |
| unsigned int |
| hashf_void (const void *key) { |
| return ((ptrdiff_t)key ^ ((ptrdiff_t)key >> 16)); |
| } |
| |
| int |
| cmpf_void (const void *key1, const void *key2) { |
| return (key1 != key2); |
| } |
| |
| |
| /* |
| * Phong's linear congruential hash |
| */ |
| #define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c)) |
| |
| unsigned int |
| hashf_string(const void *keyarg) { |
| register const unsigned char *key; |
| register unsigned int h; |
| register unsigned char c; |
| |
| key = keyarg; |
| for (h = 0; (c = *key++);) |
| dcharhash(h, c); |
| |
| return (h); |
| } |
| |
| int |
| cmpf_string(const void *key1, const void *key2) { |
| return strcmp((const char *)key1, (const char *)key2); |
| } |
| |