Lines Matching refs:hash
27 * mod_hash: flexible hash table implementation.
29 * This is a reasonably fast, reasonably flexible hash table implementation
30 * which features pluggable hash algorithms to support storing arbitrary keys
32 * data. The hash uses chaining to resolve collisions, and does not feature a
33 * mechanism to grow the hash. Care must be taken to pick nchains to be large
35 * hash chains.
37 * The client of the hash is required to supply a number of items to support
38 * the various hash functions:
41 * A destructor is responsible for freeing an object when the hash
47 * - A hashing algorithm which returns a uint_t representing a hash index
53 * constants associated with the hash table.
59 * This is used when searching the hash chain. The key comparator
66 * examples of how to create a customized hash table.
68 * Basic hash operations:
71 * create a hash using strings as keys.
72 * NOTE: This create a hash which automatically cleans up the string
76 * create a hash using pointers as keys.
81 * create a customized hash table.
83 * mod_hash_destroy_hash(hash):
84 * destroy the given hash table, calling the key and value destructors
85 * on each key-value pair stored in the hash.
87 * mod_hash_insert(hash, key, val):
88 * place a key, value pair into the given hash.
91 * mod_hash_insert_reserve(hash, key, val, handle):
92 * place a key, value pair into the given hash, using handle to indicate
96 * mod_hash_reserve(hash, *handle):
98 * policy of 'hash', returning the storage handle in 'handle'.
100 * mod_hash_reserve_nosleep(hash, *handle): reserve storage for a key-value
101 * pair ignoring the memory allocation policy of 'hash' and always without
104 * mod_hash_remove(hash, key, *val):
105 * remove a key-value pair with key 'key' from 'hash', destroying the
108 * mod_hash_replace(hash, key, val)
109 * atomically remove an existing key-value pair from a hash, and replace
113 * mod_hash_destroy(hash, key):
114 * remove a key-value pair with key 'key' from 'hash', destroying both
117 * mod_hash_find(hash, key, val):
118 * find a value in the hash table corresponding to the given key.
120 * mod_hash_find_cb(hash, key, val, found_callback)
121 * find a value in the hash table corresponding to the given key.
123 * The callback is called with the hash lock held.
127 * mod_hash_walk(hash, callback(key, elem, arg), arg)
135 * mod_hash_clear(hash):
136 * clears the given hash table of entries, calling the key and value
137 * destructors for every element in the hash.
151 #define MH_KEY_DESTROY(hash, key) ((hash->mh_kdtor)(key))
157 #define MH_VAL_DESTROY(hash, val) ((hash->mh_vdtor)(val))
161 * Call the key comparator for the given hash keys.
163 #define MH_KEYCMP(hash, key1, key2) ((hash->mh_keycmp)(key1, key2))
197 * Create a hash using strings as keys
207 uint_t hash = 0;
213 hash = (hash << 4) + *p;
214 if ((g = (hash & 0xf0000000)) != 0) {
215 hash ^= (g >> 24);
216 hash ^= g;
219 return (hash);
265 * Create a hash that uses pointers as keys. This hash algorithm
266 * picks an appropriate set of middle bits in the address to hash on
267 * based on the size of the hash table and a hint about the size of
299 * We want to hash on the bits in the middle of the address word
317 mod_hash_destroy_ptrhash(mod_hash_t *hash)
319 ASSERT(hash);
320 mod_hash_destroy_hash(hash);
331 * Create a hash that uses numeric keys.
333 * The hash algorithm is documented in "Introduction to Algorithms"
334 * (Cormen, Leiserson, Rivest); when the hash table is created, it
335 * attempts to find the next largest prime above the number of hash
336 * slots. The hash index is then this number times the key modulo
337 * the hash size, or (key * prime) % nchains.
393 mod_hash_destroy_idhash(mod_hash_t *hash)
395 ASSERT(hash);
396 mod_hash_destroy_hash(hash);
414 * The full-blown hash creation function.
417 * nchains - how many hash slots to create. More hash slots will
418 * result in shorter hash chains, but will consume
427 char *hname, /* descriptive name for hash */
428 size_t nchains, /* number of hash slots */
431 uint_t (*hash_alg)(void *, mod_hash_key_t), /* hash algorithm */
460 * Link the hash up on the list of hashes
472 * destroy a hash table, destroying all of its stored keys and values
476 mod_hash_destroy_hash(mod_hash_t *hash)
482 * Remove the hash from the hash list
484 if (hash == mh_head) { /* removing 1st list elem */
493 if (mhp == hash) {
505 mod_hash_clear(hash);
507 rw_destroy(&hash->mh_contents);
509 kmem_free(hash->mh_name, strlen(hash->mh_name) + 1);
510 kmem_free(hash, MH_SIZE(hash->mh_nchains));
515 * Call the hashing algorithm for this hash table, with the given key.
518 i_mod_hash(mod_hash_t *hash, mod_hash_key_t key)
523 * Also a nice shortcut when using a hash as a list
525 if (hash->mh_nchains == 1)
528 h = (hash->mh_hashalg)(hash->mh_hashalg_data, key);
529 return (h % (hash->mh_nchains - 1));
536 * insert 'val' into the hash table, using 'key' as its key. If 'key' is
537 * already a key in the hash, an error will be returned, and the key-val
539 * handle abstraction, allowing hash entry allocation to be separated from
540 * the hash insertion. this abstraction allows simple use of the mod_hash
545 i_mod_hash_insert_nosync(mod_hash_t *hash, mod_hash_key_t key,
551 ASSERT(hash);
555 * using the hash's allocation policy.
558 entry = kmem_cache_alloc(mh_e_cache, hash->mh_sleep);
560 hash->mh_stat.mhs_nomem++;
567 hashidx = i_mod_hash(hash, key);
570 entry->mhe_next = hash->mh_entries[hashidx];
572 hash->mh_entries[hashidx] = entry;
573 hash->mh_stat.mhs_nelems++;
579 mod_hash_insert(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t val)
584 rw_enter(&hash->mh_contents, RW_WRITER);
587 * Disallow duplicate keys in the hash
589 if (i_mod_hash_find_nosync(hash, key, &v) == 0) {
590 rw_exit(&hash->mh_contents);
591 hash->mh_stat.mhs_coll++;
595 res = i_mod_hash_insert_nosync(hash, key, val, (mod_hash_hndl_t)0);
596 rw_exit(&hash->mh_contents);
602 mod_hash_insert_reserve(mod_hash_t *hash, mod_hash_key_t key,
608 rw_enter(&hash->mh_contents, RW_WRITER);
611 * Disallow duplicate keys in the hash
613 if (i_mod_hash_find_nosync(hash, key, &v) == 0) {
614 rw_exit(&hash->mh_contents);
615 hash->mh_stat.mhs_coll++;
618 res = i_mod_hash_insert_nosync(hash, key, val, handle);
619 rw_exit(&hash->mh_contents);
632 mod_hash_reserve(mod_hash_t *hash, mod_hash_hndl_t *handlep)
634 *handlep = kmem_cache_alloc(mh_e_cache, hash->mh_sleep);
636 hash->mh_stat.mhs_nomem++;
644 mod_hash_reserve_nosleep(mod_hash_t *hash, mod_hash_hndl_t *handlep)
648 hash->mh_stat.mhs_nomem++;
658 mod_hash_cancel(mod_hash_t *hash, mod_hash_hndl_t *handlep)
667 * Remove an element from the hash table.
670 i_mod_hash_remove_nosync(mod_hash_t *hash, mod_hash_key_t key,
676 hashidx = i_mod_hash(hash, key);
679 for (e = hash->mh_entries[hashidx]; e != NULL; e = e->mhe_next) {
680 if (MH_KEYCMP(hash, e->mhe_key, key) == 0)
690 hash->mh_entries[hashidx] = e->mhe_next;
697 MH_KEY_DESTROY(hash, e->mhe_key);
701 hash->mh_stat.mhs_nelems--;
707 mod_hash_remove(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val)
711 rw_enter(&hash->mh_contents, RW_WRITER);
712 res = i_mod_hash_remove_nosync(hash, key, val);
713 rw_exit(&hash->mh_contents);
720 * atomically remove an existing key-value pair from a hash, and replace
725 mod_hash_replace(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t val)
730 rw_enter(&hash->mh_contents, RW_WRITER);
732 if (i_mod_hash_remove_nosync(hash, key, &v) == 0) {
736 MH_VAL_DESTROY(hash, v);
738 res = i_mod_hash_insert_nosync(hash, key, val, (mod_hash_hndl_t)0);
740 rw_exit(&hash->mh_contents);
747 * Remove an element from the hash table matching 'key', and destroy it.
750 mod_hash_destroy(mod_hash_t *hash, mod_hash_key_t key)
755 rw_enter(&hash->mh_contents, RW_WRITER);
757 if ((rv = i_mod_hash_remove_nosync(hash, key, &val)) == 0) {
761 MH_VAL_DESTROY(hash, val);
764 rw_exit(&hash->mh_contents);
771 * Find a value in the hash table corresponding to the given key.
774 i_mod_hash_find_nosync(mod_hash_t *hash, mod_hash_key_t key,
780 hashidx = i_mod_hash(hash, key);
782 for (e = hash->mh_entries[hashidx]; e != NULL; e = e->mhe_next) {
783 if (MH_KEYCMP(hash, e->mhe_key, key) == 0) {
785 hash->mh_stat.mhs_hit++;
789 hash->mh_stat.mhs_miss++;
794 mod_hash_find(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val)
798 rw_enter(&hash->mh_contents, RW_READER);
799 res = i_mod_hash_find_nosync(hash, key, val);
800 rw_exit(&hash->mh_contents);
806 mod_hash_find_cb(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val,
811 rw_enter(&hash->mh_contents, RW_READER);
812 res = i_mod_hash_find_nosync(hash, key, val);
816 rw_exit(&hash->mh_contents);
822 mod_hash_find_cb_rval(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val,
827 rw_enter(&hash->mh_contents, RW_READER);
828 res = i_mod_hash_find_nosync(hash, key, val);
832 rw_exit(&hash->mh_contents);
838 i_mod_hash_walk_nosync(mod_hash_t *hash,
846 (hashidx < (hash->mh_nchains - 1)) && (res == MH_WALK_CONTINUE);
848 e = hash->mh_entries[hashidx];
866 mod_hash_walk(mod_hash_t *hash,
869 rw_enter(&hash->mh_contents, RW_READER);
870 i_mod_hash_walk_nosync(hash, callback, arg);
871 rw_exit(&hash->mh_contents);
878 * Clears the given hash table by calling the destructor of every hash
882 i_mod_hash_clear_nosync(mod_hash_t *hash)
887 for (i = 0; i < hash->mh_nchains; i++) {
888 e = hash->mh_entries[i];
890 MH_KEY_DESTROY(hash, e->mhe_key);
891 MH_VAL_DESTROY(hash, e->mhe_val);
896 hash->mh_entries[i] = NULL;
898 hash->mh_stat.mhs_nelems = 0;
902 mod_hash_clear(mod_hash_t *hash)
904 ASSERT(hash);
905 rw_enter(&hash->mh_contents, RW_WRITER);
906 i_mod_hash_clear_nosync(hash);
907 rw_exit(&hash->mh_contents);