17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate * CDDL HEADER START
37c478bd9Sstevel@tonic-gate *
47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the
50209230bSgjelinek * Common Development and Distribution License (the "License").
60209230bSgjelinek * You may not use this file except in compliance with the License.
77c478bd9Sstevel@tonic-gate *
87c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
97c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
107c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions
117c478bd9Sstevel@tonic-gate * and limitations under the License.
127c478bd9Sstevel@tonic-gate *
137c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
147c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
157c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
167c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
177c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
187c478bd9Sstevel@tonic-gate *
197c478bd9Sstevel@tonic-gate * CDDL HEADER END
207c478bd9Sstevel@tonic-gate */
217c478bd9Sstevel@tonic-gate /*
22da14cebeSEric Cheng * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
237c478bd9Sstevel@tonic-gate * Use is subject to license terms.
247c478bd9Sstevel@tonic-gate */
257c478bd9Sstevel@tonic-gate
267c478bd9Sstevel@tonic-gate /*
277c478bd9Sstevel@tonic-gate * mod_hash: flexible hash table implementation.
287c478bd9Sstevel@tonic-gate *
297c478bd9Sstevel@tonic-gate * This is a reasonably fast, reasonably flexible hash table implementation
307c478bd9Sstevel@tonic-gate * which features pluggable hash algorithms to support storing arbitrary keys
317c478bd9Sstevel@tonic-gate * and values. It is designed to handle small (< 100,000 items) amounts of
327c478bd9Sstevel@tonic-gate * data. The hash uses chaining to resolve collisions, and does not feature a
337c478bd9Sstevel@tonic-gate * mechanism to grow the hash. Care must be taken to pick nchains to be large
347c478bd9Sstevel@tonic-gate * enough for the application at hand, or lots of time will be wasted searching
357c478bd9Sstevel@tonic-gate * hash chains.
367c478bd9Sstevel@tonic-gate *
377c478bd9Sstevel@tonic-gate * The client of the hash is required to supply a number of items to support
387c478bd9Sstevel@tonic-gate * the various hash functions:
397c478bd9Sstevel@tonic-gate *
407c478bd9Sstevel@tonic-gate * - Destructor functions for the key and value being hashed.
417c478bd9Sstevel@tonic-gate * A destructor is responsible for freeing an object when the hash
427c478bd9Sstevel@tonic-gate * table is no longer storing it. Since keys and values can be of
437c478bd9Sstevel@tonic-gate * arbitrary type, separate destructors for keys & values are used.
447c478bd9Sstevel@tonic-gate * These may be mod_hash_null_keydtor and mod_hash_null_valdtor if no
457c478bd9Sstevel@tonic-gate * destructor is needed for either a key or value.
467c478bd9Sstevel@tonic-gate *
477c478bd9Sstevel@tonic-gate * - A hashing algorithm which returns a uint_t representing a hash index
487c478bd9Sstevel@tonic-gate * The number returned need _not_ be between 0 and nchains. The mod_hash
497c478bd9Sstevel@tonic-gate * code will take care of doing that. The second argument (after the
507c478bd9Sstevel@tonic-gate * key) to the hashing function is a void * that represents
517c478bd9Sstevel@tonic-gate * hash_alg_data-- this is provided so that the hashing algrorithm can
527c478bd9Sstevel@tonic-gate * maintain some state across calls, or keep algorithm-specific
537c478bd9Sstevel@tonic-gate * constants associated with the hash table.
547c478bd9Sstevel@tonic-gate *
557c478bd9Sstevel@tonic-gate * A pointer-hashing and a string-hashing algorithm are supplied in
567c478bd9Sstevel@tonic-gate * this file.
577c478bd9Sstevel@tonic-gate *
587c478bd9Sstevel@tonic-gate * - A key comparator (a la qsort).
597c478bd9Sstevel@tonic-gate * This is used when searching the hash chain. The key comparator
607c478bd9Sstevel@tonic-gate * determines if two keys match. It should follow the return value
617c478bd9Sstevel@tonic-gate * semantics of strcmp.
627c478bd9Sstevel@tonic-gate *
637c478bd9Sstevel@tonic-gate * string and pointer comparators are supplied in this file.
647c478bd9Sstevel@tonic-gate *
657c478bd9Sstevel@tonic-gate * mod_hash_create_strhash() and mod_hash_create_ptrhash() provide good
667c478bd9Sstevel@tonic-gate * examples of how to create a customized hash table.
677c478bd9Sstevel@tonic-gate *
687c478bd9Sstevel@tonic-gate * Basic hash operations:
697c478bd9Sstevel@tonic-gate *
707c478bd9Sstevel@tonic-gate * mod_hash_create_strhash(name, nchains, dtor),
717c478bd9Sstevel@tonic-gate * create a hash using strings as keys.
727c478bd9Sstevel@tonic-gate * NOTE: This create a hash which automatically cleans up the string
737c478bd9Sstevel@tonic-gate * values it is given for keys.
747c478bd9Sstevel@tonic-gate *
757c478bd9Sstevel@tonic-gate * mod_hash_create_ptrhash(name, nchains, dtor, key_elem_size):
767c478bd9Sstevel@tonic-gate * create a hash using pointers as keys.
777c478bd9Sstevel@tonic-gate *
787c478bd9Sstevel@tonic-gate * mod_hash_create_extended(name, nchains, kdtor, vdtor,
797c478bd9Sstevel@tonic-gate * hash_alg, hash_alg_data,
807c478bd9Sstevel@tonic-gate * keycmp, sleep)
817c478bd9Sstevel@tonic-gate * create a customized hash table.
827c478bd9Sstevel@tonic-gate *
837c478bd9Sstevel@tonic-gate * mod_hash_destroy_hash(hash):
847c478bd9Sstevel@tonic-gate * destroy the given hash table, calling the key and value destructors
857c478bd9Sstevel@tonic-gate * on each key-value pair stored in the hash.
867c478bd9Sstevel@tonic-gate *
877c478bd9Sstevel@tonic-gate * mod_hash_insert(hash, key, val):
887c478bd9Sstevel@tonic-gate * place a key, value pair into the given hash.
897c478bd9Sstevel@tonic-gate * duplicate keys are rejected.
907c478bd9Sstevel@tonic-gate *
917c478bd9Sstevel@tonic-gate * mod_hash_insert_reserve(hash, key, val, handle):
927c478bd9Sstevel@tonic-gate * place a key, value pair into the given hash, using handle to indicate
937c478bd9Sstevel@tonic-gate * the reserved storage for the pair. (no memory allocation is needed
947c478bd9Sstevel@tonic-gate * during a mod_hash_insert_reserve.) duplicate keys are rejected.
957c478bd9Sstevel@tonic-gate *
967c478bd9Sstevel@tonic-gate * mod_hash_reserve(hash, *handle):
977c478bd9Sstevel@tonic-gate * reserve storage for a key-value pair using the memory allocation
987c478bd9Sstevel@tonic-gate * policy of 'hash', returning the storage handle in 'handle'.
997c478bd9Sstevel@tonic-gate *
1007c478bd9Sstevel@tonic-gate * mod_hash_reserve_nosleep(hash, *handle): reserve storage for a key-value
1017c478bd9Sstevel@tonic-gate * pair ignoring the memory allocation policy of 'hash' and always without
1027c478bd9Sstevel@tonic-gate * sleep, returning the storage handle in 'handle'.
1037c478bd9Sstevel@tonic-gate *
1047c478bd9Sstevel@tonic-gate * mod_hash_remove(hash, key, *val):
1057c478bd9Sstevel@tonic-gate * remove a key-value pair with key 'key' from 'hash', destroying the
1067c478bd9Sstevel@tonic-gate * stored key, and returning the value in val.
1077c478bd9Sstevel@tonic-gate *
1087c478bd9Sstevel@tonic-gate * mod_hash_replace(hash, key, val)
1097c478bd9Sstevel@tonic-gate * atomically remove an existing key-value pair from a hash, and replace
1107c478bd9Sstevel@tonic-gate * the key and value with the ones supplied. The removed key and value
1117c478bd9Sstevel@tonic-gate * (if any) are destroyed.
1127c478bd9Sstevel@tonic-gate *
1137c478bd9Sstevel@tonic-gate * mod_hash_destroy(hash, key):
1147c478bd9Sstevel@tonic-gate * remove a key-value pair with key 'key' from 'hash', destroying both
1157c478bd9Sstevel@tonic-gate * stored key and stored value.
1167c478bd9Sstevel@tonic-gate *
1177c478bd9Sstevel@tonic-gate * mod_hash_find(hash, key, val):
1187c478bd9Sstevel@tonic-gate * find a value in the hash table corresponding to the given key.
1197c478bd9Sstevel@tonic-gate *
1207c478bd9Sstevel@tonic-gate * mod_hash_find_cb(hash, key, val, found_callback)
1217c478bd9Sstevel@tonic-gate * find a value in the hash table corresponding to the given key.
1227c478bd9Sstevel@tonic-gate * If a value is found, call specified callback passing key and val to it.
1237c478bd9Sstevel@tonic-gate * The callback is called with the hash lock held.
1247c478bd9Sstevel@tonic-gate * It is intended to be used in situations where the act of locating the
1257c478bd9Sstevel@tonic-gate * data must also modify it - such as in reference counting schemes.
1267c478bd9Sstevel@tonic-gate *
1277c478bd9Sstevel@tonic-gate * mod_hash_walk(hash, callback(key, elem, arg), arg)
1287c478bd9Sstevel@tonic-gate * walks all the elements in the hashtable and invokes the callback
1297c478bd9Sstevel@tonic-gate * function with the key/value pair for each element. the hashtable
1307c478bd9Sstevel@tonic-gate * is locked for readers so the callback function should not attempt
1317c478bd9Sstevel@tonic-gate * to do any updates to the hashable. the callback function should
1327c478bd9Sstevel@tonic-gate * return MH_WALK_CONTINUE to continue walking the hashtable or
1337c478bd9Sstevel@tonic-gate * MH_WALK_TERMINATE to abort the walk of the hashtable.
1347c478bd9Sstevel@tonic-gate *
1357c478bd9Sstevel@tonic-gate * mod_hash_clear(hash):
1367c478bd9Sstevel@tonic-gate * clears the given hash table of entries, calling the key and value
1377c478bd9Sstevel@tonic-gate * destructors for every element in the hash.
1387c478bd9Sstevel@tonic-gate */
1397c478bd9Sstevel@tonic-gate
1407c478bd9Sstevel@tonic-gate #include <sys/bitmap.h>
1417c478bd9Sstevel@tonic-gate #include <sys/debug.h>
1427c478bd9Sstevel@tonic-gate #include <sys/kmem.h>
1437c478bd9Sstevel@tonic-gate #include <sys/sunddi.h>
1447c478bd9Sstevel@tonic-gate
1457c478bd9Sstevel@tonic-gate #include <sys/modhash_impl.h>
1467c478bd9Sstevel@tonic-gate
1477c478bd9Sstevel@tonic-gate /*
1487c478bd9Sstevel@tonic-gate * MH_KEY_DESTROY()
1497c478bd9Sstevel@tonic-gate * Invoke the key destructor.
1507c478bd9Sstevel@tonic-gate */
1517c478bd9Sstevel@tonic-gate #define MH_KEY_DESTROY(hash, key) ((hash->mh_kdtor)(key))
1527c478bd9Sstevel@tonic-gate
1537c478bd9Sstevel@tonic-gate /*
1547c478bd9Sstevel@tonic-gate * MH_VAL_DESTROY()
1557c478bd9Sstevel@tonic-gate * Invoke the value destructor.
1567c478bd9Sstevel@tonic-gate */
1577c478bd9Sstevel@tonic-gate #define MH_VAL_DESTROY(hash, val) ((hash->mh_vdtor)(val))
1587c478bd9Sstevel@tonic-gate
1597c478bd9Sstevel@tonic-gate /*
1607c478bd9Sstevel@tonic-gate * MH_KEYCMP()
1617c478bd9Sstevel@tonic-gate * Call the key comparator for the given hash keys.
1627c478bd9Sstevel@tonic-gate */
1637c478bd9Sstevel@tonic-gate #define MH_KEYCMP(hash, key1, key2) ((hash->mh_keycmp)(key1, key2))
1647c478bd9Sstevel@tonic-gate
1657c478bd9Sstevel@tonic-gate /*
1667c478bd9Sstevel@tonic-gate * Cache for struct mod_hash_entry
1677c478bd9Sstevel@tonic-gate */
1687c478bd9Sstevel@tonic-gate kmem_cache_t *mh_e_cache = NULL;
1697c478bd9Sstevel@tonic-gate mod_hash_t *mh_head = NULL;
1707c478bd9Sstevel@tonic-gate kmutex_t mh_head_lock;
1717c478bd9Sstevel@tonic-gate
1727c478bd9Sstevel@tonic-gate /*
1737c478bd9Sstevel@tonic-gate * mod_hash_null_keydtor()
1747c478bd9Sstevel@tonic-gate * mod_hash_null_valdtor()
1757c478bd9Sstevel@tonic-gate * no-op key and value destructors.
1767c478bd9Sstevel@tonic-gate */
1777c478bd9Sstevel@tonic-gate /*ARGSUSED*/
1787c478bd9Sstevel@tonic-gate void
mod_hash_null_keydtor(mod_hash_key_t key)1797c478bd9Sstevel@tonic-gate mod_hash_null_keydtor(mod_hash_key_t key)
1807c478bd9Sstevel@tonic-gate {
1817c478bd9Sstevel@tonic-gate }
1827c478bd9Sstevel@tonic-gate
1837c478bd9Sstevel@tonic-gate /*ARGSUSED*/
1847c478bd9Sstevel@tonic-gate void
mod_hash_null_valdtor(mod_hash_val_t val)1857c478bd9Sstevel@tonic-gate mod_hash_null_valdtor(mod_hash_val_t val)
1867c478bd9Sstevel@tonic-gate {
1877c478bd9Sstevel@tonic-gate }
1887c478bd9Sstevel@tonic-gate
1897c478bd9Sstevel@tonic-gate /*
1907c478bd9Sstevel@tonic-gate * mod_hash_bystr()
1917c478bd9Sstevel@tonic-gate * mod_hash_strkey_cmp()
1927c478bd9Sstevel@tonic-gate * mod_hash_strkey_dtor()
1937c478bd9Sstevel@tonic-gate * mod_hash_strval_dtor()
1947c478bd9Sstevel@tonic-gate * Hash and key comparison routines for hashes with string keys.
1957c478bd9Sstevel@tonic-gate *
1967c478bd9Sstevel@tonic-gate * mod_hash_create_strhash()
1977c478bd9Sstevel@tonic-gate * Create a hash using strings as keys
1987c478bd9Sstevel@tonic-gate *
1997c478bd9Sstevel@tonic-gate * The string hashing algorithm is from the "Dragon Book" --
2007c478bd9Sstevel@tonic-gate * "Compilers: Principles, Tools & Techniques", by Aho, Sethi, Ullman
2017c478bd9Sstevel@tonic-gate */
2027c478bd9Sstevel@tonic-gate
2037c478bd9Sstevel@tonic-gate /*ARGSUSED*/
2047c478bd9Sstevel@tonic-gate uint_t
mod_hash_bystr(void * hash_data,mod_hash_key_t key)2057c478bd9Sstevel@tonic-gate mod_hash_bystr(void *hash_data, mod_hash_key_t key)
2067c478bd9Sstevel@tonic-gate {
2077c478bd9Sstevel@tonic-gate uint_t hash = 0;
2087c478bd9Sstevel@tonic-gate uint_t g;
2097c478bd9Sstevel@tonic-gate char *p, *k = (char *)key;
2107c478bd9Sstevel@tonic-gate
2117c478bd9Sstevel@tonic-gate ASSERT(k);
2127c478bd9Sstevel@tonic-gate for (p = k; *p != '\0'; p++) {
2137c478bd9Sstevel@tonic-gate hash = (hash << 4) + *p;
2147c478bd9Sstevel@tonic-gate if ((g = (hash & 0xf0000000)) != 0) {
2157c478bd9Sstevel@tonic-gate hash ^= (g >> 24);
2167c478bd9Sstevel@tonic-gate hash ^= g;
2177c478bd9Sstevel@tonic-gate }
2187c478bd9Sstevel@tonic-gate }
2197c478bd9Sstevel@tonic-gate return (hash);
2207c478bd9Sstevel@tonic-gate }
2217c478bd9Sstevel@tonic-gate
2227c478bd9Sstevel@tonic-gate int
mod_hash_strkey_cmp(mod_hash_key_t key1,mod_hash_key_t key2)2237c478bd9Sstevel@tonic-gate mod_hash_strkey_cmp(mod_hash_key_t key1, mod_hash_key_t key2)
2247c478bd9Sstevel@tonic-gate {
2257c478bd9Sstevel@tonic-gate return (strcmp((char *)key1, (char *)key2));
2267c478bd9Sstevel@tonic-gate }
2277c478bd9Sstevel@tonic-gate
2287c478bd9Sstevel@tonic-gate void
mod_hash_strkey_dtor(mod_hash_key_t key)2297c478bd9Sstevel@tonic-gate mod_hash_strkey_dtor(mod_hash_key_t key)
2307c478bd9Sstevel@tonic-gate {
2317c478bd9Sstevel@tonic-gate char *c = (char *)key;
2327c478bd9Sstevel@tonic-gate kmem_free(c, strlen(c) + 1);
2337c478bd9Sstevel@tonic-gate }
2347c478bd9Sstevel@tonic-gate
2357c478bd9Sstevel@tonic-gate void
mod_hash_strval_dtor(mod_hash_val_t val)2367c478bd9Sstevel@tonic-gate mod_hash_strval_dtor(mod_hash_val_t val)
2377c478bd9Sstevel@tonic-gate {
2387c478bd9Sstevel@tonic-gate char *c = (char *)val;
2397c478bd9Sstevel@tonic-gate kmem_free(c, strlen(c) + 1);
2407c478bd9Sstevel@tonic-gate }
2417c478bd9Sstevel@tonic-gate
2427c478bd9Sstevel@tonic-gate mod_hash_t *
mod_hash_create_strhash(char * name,size_t nchains,void (* val_dtor)(mod_hash_val_t))2437c478bd9Sstevel@tonic-gate mod_hash_create_strhash(char *name, size_t nchains,
2447c478bd9Sstevel@tonic-gate void (*val_dtor)(mod_hash_val_t))
2457c478bd9Sstevel@tonic-gate {
2467c478bd9Sstevel@tonic-gate return mod_hash_create_extended(name, nchains, mod_hash_strkey_dtor,
2477c478bd9Sstevel@tonic-gate val_dtor, mod_hash_bystr, NULL, mod_hash_strkey_cmp, KM_SLEEP);
2487c478bd9Sstevel@tonic-gate }
2497c478bd9Sstevel@tonic-gate
2507c478bd9Sstevel@tonic-gate void
mod_hash_destroy_strhash(mod_hash_t * strhash)2517c478bd9Sstevel@tonic-gate mod_hash_destroy_strhash(mod_hash_t *strhash)
2527c478bd9Sstevel@tonic-gate {
2537c478bd9Sstevel@tonic-gate ASSERT(strhash);
2547c478bd9Sstevel@tonic-gate mod_hash_destroy_hash(strhash);
2557c478bd9Sstevel@tonic-gate }
2567c478bd9Sstevel@tonic-gate
2577c478bd9Sstevel@tonic-gate
2587c478bd9Sstevel@tonic-gate /*
2597c478bd9Sstevel@tonic-gate * mod_hash_byptr()
2607c478bd9Sstevel@tonic-gate * mod_hash_ptrkey_cmp()
2617c478bd9Sstevel@tonic-gate * Hash and key comparison routines for hashes with pointer keys.
2627c478bd9Sstevel@tonic-gate *
2637c478bd9Sstevel@tonic-gate * mod_hash_create_ptrhash()
2647c478bd9Sstevel@tonic-gate * mod_hash_destroy_ptrhash()
2657c478bd9Sstevel@tonic-gate * Create a hash that uses pointers as keys. This hash algorithm
2667c478bd9Sstevel@tonic-gate * picks an appropriate set of middle bits in the address to hash on
2677c478bd9Sstevel@tonic-gate * based on the size of the hash table and a hint about the size of
2687c478bd9Sstevel@tonic-gate * the items pointed at.
2697c478bd9Sstevel@tonic-gate */
2707c478bd9Sstevel@tonic-gate uint_t
mod_hash_byptr(void * hash_data,mod_hash_key_t key)2717c478bd9Sstevel@tonic-gate mod_hash_byptr(void *hash_data, mod_hash_key_t key)
2727c478bd9Sstevel@tonic-gate {
2737c478bd9Sstevel@tonic-gate uintptr_t k = (uintptr_t)key;
2747c478bd9Sstevel@tonic-gate k >>= (int)(uintptr_t)hash_data;
2757c478bd9Sstevel@tonic-gate
2767c478bd9Sstevel@tonic-gate return ((uint_t)k);
2777c478bd9Sstevel@tonic-gate }
2787c478bd9Sstevel@tonic-gate
2797c478bd9Sstevel@tonic-gate int
mod_hash_ptrkey_cmp(mod_hash_key_t key1,mod_hash_key_t key2)2807c478bd9Sstevel@tonic-gate mod_hash_ptrkey_cmp(mod_hash_key_t key1, mod_hash_key_t key2)
2817c478bd9Sstevel@tonic-gate {
2827c478bd9Sstevel@tonic-gate uintptr_t k1 = (uintptr_t)key1;
2837c478bd9Sstevel@tonic-gate uintptr_t k2 = (uintptr_t)key2;
2847c478bd9Sstevel@tonic-gate if (k1 > k2)
2857c478bd9Sstevel@tonic-gate return (-1);
2867c478bd9Sstevel@tonic-gate else if (k1 < k2)
2877c478bd9Sstevel@tonic-gate return (1);
2887c478bd9Sstevel@tonic-gate else
2897c478bd9Sstevel@tonic-gate return (0);
2907c478bd9Sstevel@tonic-gate }
2917c478bd9Sstevel@tonic-gate
2927c478bd9Sstevel@tonic-gate mod_hash_t *
mod_hash_create_ptrhash(char * name,size_t nchains,void (* val_dtor)(mod_hash_val_t),size_t key_elem_size)2937c478bd9Sstevel@tonic-gate mod_hash_create_ptrhash(char *name, size_t nchains,
2947c478bd9Sstevel@tonic-gate void (*val_dtor)(mod_hash_val_t), size_t key_elem_size)
2957c478bd9Sstevel@tonic-gate {
2967c478bd9Sstevel@tonic-gate size_t rshift;
2977c478bd9Sstevel@tonic-gate
2987c478bd9Sstevel@tonic-gate /*
2997c478bd9Sstevel@tonic-gate * We want to hash on the bits in the middle of the address word
3007c478bd9Sstevel@tonic-gate * Bits far to the right in the word have little significance, and
3017c478bd9Sstevel@tonic-gate * are likely to all look the same (for example, an array of
3027c478bd9Sstevel@tonic-gate * 256-byte structures will have the bottom 8 bits of address
3037c478bd9Sstevel@tonic-gate * words the same). So we want to right-shift each address to
3047c478bd9Sstevel@tonic-gate * ignore the bottom bits.
3057c478bd9Sstevel@tonic-gate *
3067c478bd9Sstevel@tonic-gate * The high bits, which are also unused, will get taken out when
3077c478bd9Sstevel@tonic-gate * mod_hash takes hashkey % nchains.
3087c478bd9Sstevel@tonic-gate */
3097c478bd9Sstevel@tonic-gate rshift = highbit(key_elem_size);
3107c478bd9Sstevel@tonic-gate
3117c478bd9Sstevel@tonic-gate return mod_hash_create_extended(name, nchains, mod_hash_null_keydtor,
3127c478bd9Sstevel@tonic-gate val_dtor, mod_hash_byptr, (void *)rshift, mod_hash_ptrkey_cmp,
3137c478bd9Sstevel@tonic-gate KM_SLEEP);
3147c478bd9Sstevel@tonic-gate }
3157c478bd9Sstevel@tonic-gate
3167c478bd9Sstevel@tonic-gate void
mod_hash_destroy_ptrhash(mod_hash_t * hash)3177c478bd9Sstevel@tonic-gate mod_hash_destroy_ptrhash(mod_hash_t *hash)
3187c478bd9Sstevel@tonic-gate {
3197c478bd9Sstevel@tonic-gate ASSERT(hash);
3207c478bd9Sstevel@tonic-gate mod_hash_destroy_hash(hash);
3217c478bd9Sstevel@tonic-gate }
3227c478bd9Sstevel@tonic-gate
3237c478bd9Sstevel@tonic-gate /*
3247c478bd9Sstevel@tonic-gate * mod_hash_byid()
3257c478bd9Sstevel@tonic-gate * mod_hash_idkey_cmp()
3267c478bd9Sstevel@tonic-gate * Hash and key comparison routines for hashes with 32-bit unsigned keys.
3277c478bd9Sstevel@tonic-gate *
3287c478bd9Sstevel@tonic-gate * mod_hash_create_idhash()
3297c478bd9Sstevel@tonic-gate * mod_hash_destroy_idhash()
3307c478bd9Sstevel@tonic-gate * mod_hash_iddata_gen()
3317c478bd9Sstevel@tonic-gate * Create a hash that uses numeric keys.
3327c478bd9Sstevel@tonic-gate *
3337c478bd9Sstevel@tonic-gate * The hash algorithm is documented in "Introduction to Algorithms"
3347c478bd9Sstevel@tonic-gate * (Cormen, Leiserson, Rivest); when the hash table is created, it
3357c478bd9Sstevel@tonic-gate * attempts to find the next largest prime above the number of hash
3367c478bd9Sstevel@tonic-gate * slots. The hash index is then this number times the key modulo
3377c478bd9Sstevel@tonic-gate * the hash size, or (key * prime) % nchains.
3387c478bd9Sstevel@tonic-gate */
3397c478bd9Sstevel@tonic-gate uint_t
mod_hash_byid(void * hash_data,mod_hash_key_t key)3407c478bd9Sstevel@tonic-gate mod_hash_byid(void *hash_data, mod_hash_key_t key)
3417c478bd9Sstevel@tonic-gate {
3427c478bd9Sstevel@tonic-gate uint_t kval = (uint_t)(uintptr_t)hash_data;
3437c478bd9Sstevel@tonic-gate return ((uint_t)(uintptr_t)key * (uint_t)kval);
3447c478bd9Sstevel@tonic-gate }
3457c478bd9Sstevel@tonic-gate
3467c478bd9Sstevel@tonic-gate int
mod_hash_idkey_cmp(mod_hash_key_t key1,mod_hash_key_t key2)3477c478bd9Sstevel@tonic-gate mod_hash_idkey_cmp(mod_hash_key_t key1, mod_hash_key_t key2)
3487c478bd9Sstevel@tonic-gate {
3497c478bd9Sstevel@tonic-gate return ((uint_t)(uintptr_t)key1 - (uint_t)(uintptr_t)key2);
3507c478bd9Sstevel@tonic-gate }
3517c478bd9Sstevel@tonic-gate
3527c478bd9Sstevel@tonic-gate /*
3537c478bd9Sstevel@tonic-gate * Generate the next largest prime number greater than nchains; this value
3547c478bd9Sstevel@tonic-gate * is intended to be later passed in to mod_hash_create_extended() as the
3557c478bd9Sstevel@tonic-gate * hash_data.
3567c478bd9Sstevel@tonic-gate */
3577c478bd9Sstevel@tonic-gate uint_t
mod_hash_iddata_gen(size_t nchains)3587c478bd9Sstevel@tonic-gate mod_hash_iddata_gen(size_t nchains)
3597c478bd9Sstevel@tonic-gate {
3607c478bd9Sstevel@tonic-gate uint_t kval, i, prime;
3617c478bd9Sstevel@tonic-gate
3627c478bd9Sstevel@tonic-gate /*
3637c478bd9Sstevel@tonic-gate * Pick the first (odd) prime greater than nchains. Make sure kval is
3647c478bd9Sstevel@tonic-gate * odd (so start with nchains +1 or +2 as appropriate).
3657c478bd9Sstevel@tonic-gate */
3667c478bd9Sstevel@tonic-gate kval = (nchains % 2 == 0) ? nchains + 1 : nchains + 2;
3677c478bd9Sstevel@tonic-gate
3687c478bd9Sstevel@tonic-gate for (;;) {
3697c478bd9Sstevel@tonic-gate prime = 1;
3707c478bd9Sstevel@tonic-gate for (i = 3; i * i <= kval; i += 2) {
3717c478bd9Sstevel@tonic-gate if (kval % i == 0)
3727c478bd9Sstevel@tonic-gate prime = 0;
3737c478bd9Sstevel@tonic-gate }
3747c478bd9Sstevel@tonic-gate if (prime == 1)
3757c478bd9Sstevel@tonic-gate break;
3767c478bd9Sstevel@tonic-gate kval += 2;
3777c478bd9Sstevel@tonic-gate }
3787c478bd9Sstevel@tonic-gate return (kval);
3797c478bd9Sstevel@tonic-gate }
3807c478bd9Sstevel@tonic-gate
3817c478bd9Sstevel@tonic-gate mod_hash_t *
mod_hash_create_idhash(char * name,size_t nchains,void (* val_dtor)(mod_hash_val_t))3827c478bd9Sstevel@tonic-gate mod_hash_create_idhash(char *name, size_t nchains,
3837c478bd9Sstevel@tonic-gate void (*val_dtor)(mod_hash_val_t))
3847c478bd9Sstevel@tonic-gate {
3857c478bd9Sstevel@tonic-gate uint_t kval = mod_hash_iddata_gen(nchains);
3867c478bd9Sstevel@tonic-gate
3877c478bd9Sstevel@tonic-gate return (mod_hash_create_extended(name, nchains, mod_hash_null_keydtor,
3887c478bd9Sstevel@tonic-gate val_dtor, mod_hash_byid, (void *)(uintptr_t)kval,
3897c478bd9Sstevel@tonic-gate mod_hash_idkey_cmp, KM_SLEEP));
3907c478bd9Sstevel@tonic-gate }
3917c478bd9Sstevel@tonic-gate
3927c478bd9Sstevel@tonic-gate void
mod_hash_destroy_idhash(mod_hash_t * hash)3937c478bd9Sstevel@tonic-gate mod_hash_destroy_idhash(mod_hash_t *hash)
3947c478bd9Sstevel@tonic-gate {
3957c478bd9Sstevel@tonic-gate ASSERT(hash);
3967c478bd9Sstevel@tonic-gate mod_hash_destroy_hash(hash);
3977c478bd9Sstevel@tonic-gate }
3987c478bd9Sstevel@tonic-gate
3997c478bd9Sstevel@tonic-gate /*
4007c478bd9Sstevel@tonic-gate * mod_hash_init()
4017c478bd9Sstevel@tonic-gate * sets up globals, etc for mod_hash_*
4027c478bd9Sstevel@tonic-gate */
4037c478bd9Sstevel@tonic-gate void
mod_hash_init(void)4047c478bd9Sstevel@tonic-gate mod_hash_init(void)
4057c478bd9Sstevel@tonic-gate {
4067c478bd9Sstevel@tonic-gate ASSERT(mh_e_cache == NULL);
4077c478bd9Sstevel@tonic-gate mh_e_cache = kmem_cache_create("mod_hash_entries",
4087c478bd9Sstevel@tonic-gate sizeof (struct mod_hash_entry), 0, NULL, NULL, NULL, NULL,
4097c478bd9Sstevel@tonic-gate NULL, 0);
4107c478bd9Sstevel@tonic-gate }
4117c478bd9Sstevel@tonic-gate
4127c478bd9Sstevel@tonic-gate /*
4137c478bd9Sstevel@tonic-gate * mod_hash_create_extended()
4147c478bd9Sstevel@tonic-gate * The full-blown hash creation function.
4157c478bd9Sstevel@tonic-gate *
4167c478bd9Sstevel@tonic-gate * notes:
4177c478bd9Sstevel@tonic-gate * nchains - how many hash slots to create. More hash slots will
4187c478bd9Sstevel@tonic-gate * result in shorter hash chains, but will consume
4197c478bd9Sstevel@tonic-gate * slightly more memory up front.
4207c478bd9Sstevel@tonic-gate * sleep - should be KM_SLEEP or KM_NOSLEEP, to indicate whether
4217c478bd9Sstevel@tonic-gate * to sleep for memory, or fail in low-memory conditions.
4227c478bd9Sstevel@tonic-gate *
4237c478bd9Sstevel@tonic-gate * Fails only if KM_NOSLEEP was specified, and no memory was available.
4247c478bd9Sstevel@tonic-gate */
4257c478bd9Sstevel@tonic-gate mod_hash_t *
mod_hash_create_extended(char * hname,size_t nchains,void (* kdtor)(mod_hash_key_t),void (* vdtor)(mod_hash_val_t),uint_t (* hash_alg)(void *,mod_hash_key_t),void * hash_alg_data,int (* keycmp)(mod_hash_key_t,mod_hash_key_t),int sleep)4267c478bd9Sstevel@tonic-gate mod_hash_create_extended(
4277c478bd9Sstevel@tonic-gate char *hname, /* descriptive name for hash */
4287c478bd9Sstevel@tonic-gate size_t nchains, /* number of hash slots */
4297c478bd9Sstevel@tonic-gate void (*kdtor)(mod_hash_key_t), /* key destructor */
4307c478bd9Sstevel@tonic-gate void (*vdtor)(mod_hash_val_t), /* value destructor */
4317c478bd9Sstevel@tonic-gate uint_t (*hash_alg)(void *, mod_hash_key_t), /* hash algorithm */
4327c478bd9Sstevel@tonic-gate void *hash_alg_data, /* pass-thru arg for hash_alg */
4337c478bd9Sstevel@tonic-gate int (*keycmp)(mod_hash_key_t, mod_hash_key_t), /* key comparator */
4347c478bd9Sstevel@tonic-gate int sleep) /* whether to sleep for mem */
4357c478bd9Sstevel@tonic-gate {
4367c478bd9Sstevel@tonic-gate mod_hash_t *mod_hash;
4377c478bd9Sstevel@tonic-gate ASSERT(hname && keycmp && hash_alg && vdtor && kdtor);
4387c478bd9Sstevel@tonic-gate
4397c478bd9Sstevel@tonic-gate if ((mod_hash = kmem_zalloc(MH_SIZE(nchains), sleep)) == NULL)
4407c478bd9Sstevel@tonic-gate return (NULL);
4417c478bd9Sstevel@tonic-gate
4427c478bd9Sstevel@tonic-gate mod_hash->mh_name = kmem_alloc(strlen(hname) + 1, sleep);
4437c478bd9Sstevel@tonic-gate if (mod_hash->mh_name == NULL) {
4447c478bd9Sstevel@tonic-gate kmem_free(mod_hash, MH_SIZE(nchains));
4457c478bd9Sstevel@tonic-gate return (NULL);
4467c478bd9Sstevel@tonic-gate }
4477c478bd9Sstevel@tonic-gate (void) strcpy(mod_hash->mh_name, hname);
4487c478bd9Sstevel@tonic-gate
4497c478bd9Sstevel@tonic-gate mod_hash->mh_sleep = sleep;
4507c478bd9Sstevel@tonic-gate mod_hash->mh_nchains = nchains;
4517c478bd9Sstevel@tonic-gate mod_hash->mh_kdtor = kdtor;
4527c478bd9Sstevel@tonic-gate mod_hash->mh_vdtor = vdtor;
4537c478bd9Sstevel@tonic-gate mod_hash->mh_hashalg = hash_alg;
4547c478bd9Sstevel@tonic-gate mod_hash->mh_hashalg_data = hash_alg_data;
4557c478bd9Sstevel@tonic-gate mod_hash->mh_keycmp = keycmp;
4567c478bd9Sstevel@tonic-gate
457*debed2c9SJorgen Lundman rw_init(&mod_hash->mh_contents, NULL, RW_DEFAULT, NULL);
458*debed2c9SJorgen Lundman
4597c478bd9Sstevel@tonic-gate /*
4607c478bd9Sstevel@tonic-gate * Link the hash up on the list of hashes
4617c478bd9Sstevel@tonic-gate */
4627c478bd9Sstevel@tonic-gate mutex_enter(&mh_head_lock);
4637c478bd9Sstevel@tonic-gate mod_hash->mh_next = mh_head;
4647c478bd9Sstevel@tonic-gate mh_head = mod_hash;
4657c478bd9Sstevel@tonic-gate mutex_exit(&mh_head_lock);
4667c478bd9Sstevel@tonic-gate
4677c478bd9Sstevel@tonic-gate return (mod_hash);
4687c478bd9Sstevel@tonic-gate }
4697c478bd9Sstevel@tonic-gate
4707c478bd9Sstevel@tonic-gate /*
4717c478bd9Sstevel@tonic-gate * mod_hash_destroy_hash()
4727c478bd9Sstevel@tonic-gate * destroy a hash table, destroying all of its stored keys and values
4737c478bd9Sstevel@tonic-gate * as well.
4747c478bd9Sstevel@tonic-gate */
4757c478bd9Sstevel@tonic-gate void
mod_hash_destroy_hash(mod_hash_t * hash)4767c478bd9Sstevel@tonic-gate mod_hash_destroy_hash(mod_hash_t *hash)
4777c478bd9Sstevel@tonic-gate {
4787c478bd9Sstevel@tonic-gate mod_hash_t *mhp, *mhpp;
4797c478bd9Sstevel@tonic-gate
4807c478bd9Sstevel@tonic-gate mutex_enter(&mh_head_lock);
4817c478bd9Sstevel@tonic-gate /*
4827c478bd9Sstevel@tonic-gate * Remove the hash from the hash list
4837c478bd9Sstevel@tonic-gate */
4847c478bd9Sstevel@tonic-gate if (hash == mh_head) { /* removing 1st list elem */
4857c478bd9Sstevel@tonic-gate mh_head = mh_head->mh_next;
4867c478bd9Sstevel@tonic-gate } else {
4877c478bd9Sstevel@tonic-gate /*
4887c478bd9Sstevel@tonic-gate * mhpp can start out NULL since we know the 1st elem isn't the
4897c478bd9Sstevel@tonic-gate * droid we're looking for.
4907c478bd9Sstevel@tonic-gate */
4917c478bd9Sstevel@tonic-gate mhpp = NULL;
4927c478bd9Sstevel@tonic-gate for (mhp = mh_head; mhp != NULL; mhp = mhp->mh_next) {
4937c478bd9Sstevel@tonic-gate if (mhp == hash) {
4947c478bd9Sstevel@tonic-gate mhpp->mh_next = mhp->mh_next;
4957c478bd9Sstevel@tonic-gate break;
4967c478bd9Sstevel@tonic-gate }
4977c478bd9Sstevel@tonic-gate mhpp = mhp;
4987c478bd9Sstevel@tonic-gate }
4997c478bd9Sstevel@tonic-gate }
5007c478bd9Sstevel@tonic-gate mutex_exit(&mh_head_lock);
5017c478bd9Sstevel@tonic-gate
5027c478bd9Sstevel@tonic-gate /*
5037c478bd9Sstevel@tonic-gate * Clean out keys and values.
5047c478bd9Sstevel@tonic-gate */
5057c478bd9Sstevel@tonic-gate mod_hash_clear(hash);
5067c478bd9Sstevel@tonic-gate
507*debed2c9SJorgen Lundman rw_destroy(&hash->mh_contents);
508*debed2c9SJorgen Lundman
5097c478bd9Sstevel@tonic-gate kmem_free(hash->mh_name, strlen(hash->mh_name) + 1);
5107c478bd9Sstevel@tonic-gate kmem_free(hash, MH_SIZE(hash->mh_nchains));
5117c478bd9Sstevel@tonic-gate }
5127c478bd9Sstevel@tonic-gate
5137c478bd9Sstevel@tonic-gate /*
5147c478bd9Sstevel@tonic-gate * i_mod_hash()
5157c478bd9Sstevel@tonic-gate * Call the hashing algorithm for this hash table, with the given key.
5167c478bd9Sstevel@tonic-gate */
5170209230bSgjelinek uint_t
i_mod_hash(mod_hash_t * hash,mod_hash_key_t key)5187c478bd9Sstevel@tonic-gate i_mod_hash(mod_hash_t *hash, mod_hash_key_t key)
5197c478bd9Sstevel@tonic-gate {
5207c478bd9Sstevel@tonic-gate uint_t h;
5217c478bd9Sstevel@tonic-gate /*
5227c478bd9Sstevel@tonic-gate * Prevent div by 0 problems;
5237c478bd9Sstevel@tonic-gate * Also a nice shortcut when using a hash as a list
5247c478bd9Sstevel@tonic-gate */
5257c478bd9Sstevel@tonic-gate if (hash->mh_nchains == 1)
5267c478bd9Sstevel@tonic-gate return (0);
5277c478bd9Sstevel@tonic-gate
5287c478bd9Sstevel@tonic-gate h = (hash->mh_hashalg)(hash->mh_hashalg_data, key);
5297c478bd9Sstevel@tonic-gate return (h % (hash->mh_nchains - 1));
5307c478bd9Sstevel@tonic-gate }
5317c478bd9Sstevel@tonic-gate
5327c478bd9Sstevel@tonic-gate /*
5337c478bd9Sstevel@tonic-gate * i_mod_hash_insert_nosync()
5347c478bd9Sstevel@tonic-gate * mod_hash_insert()
5357c478bd9Sstevel@tonic-gate * mod_hash_insert_reserve()
5367c478bd9Sstevel@tonic-gate * insert 'val' into the hash table, using 'key' as its key. If 'key' is
5377c478bd9Sstevel@tonic-gate * already a key in the hash, an error will be returned, and the key-val
5387c478bd9Sstevel@tonic-gate * pair will not be inserted. i_mod_hash_insert_nosync() supports a simple
5397c478bd9Sstevel@tonic-gate * handle abstraction, allowing hash entry allocation to be separated from
5407c478bd9Sstevel@tonic-gate * the hash insertion. this abstraction allows simple use of the mod_hash
5417c478bd9Sstevel@tonic-gate * structure in situations where mod_hash_insert() with a KM_SLEEP
5427c478bd9Sstevel@tonic-gate * allocation policy would otherwise be unsafe.
5437c478bd9Sstevel@tonic-gate */
5447c478bd9Sstevel@tonic-gate int
i_mod_hash_insert_nosync(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t val,mod_hash_hndl_t handle)5457c478bd9Sstevel@tonic-gate i_mod_hash_insert_nosync(mod_hash_t *hash, mod_hash_key_t key,
5467c478bd9Sstevel@tonic-gate mod_hash_val_t val, mod_hash_hndl_t handle)
5477c478bd9Sstevel@tonic-gate {
5487c478bd9Sstevel@tonic-gate uint_t hashidx;
5497c478bd9Sstevel@tonic-gate struct mod_hash_entry *entry;
5507c478bd9Sstevel@tonic-gate
5517c478bd9Sstevel@tonic-gate ASSERT(hash);
5527c478bd9Sstevel@tonic-gate
5537c478bd9Sstevel@tonic-gate /*
5547c478bd9Sstevel@tonic-gate * If we've not been given reserved storage, allocate storage directly,
5557c478bd9Sstevel@tonic-gate * using the hash's allocation policy.
5567c478bd9Sstevel@tonic-gate */
5577c478bd9Sstevel@tonic-gate if (handle == (mod_hash_hndl_t)0) {
5587c478bd9Sstevel@tonic-gate entry = kmem_cache_alloc(mh_e_cache, hash->mh_sleep);
5597c478bd9Sstevel@tonic-gate if (entry == NULL) {
5607c478bd9Sstevel@tonic-gate hash->mh_stat.mhs_nomem++;
5617c478bd9Sstevel@tonic-gate return (MH_ERR_NOMEM);
5627c478bd9Sstevel@tonic-gate }
5637c478bd9Sstevel@tonic-gate } else {
5647c478bd9Sstevel@tonic-gate entry = (struct mod_hash_entry *)handle;
5657c478bd9Sstevel@tonic-gate }
5667c478bd9Sstevel@tonic-gate
5677c478bd9Sstevel@tonic-gate hashidx = i_mod_hash(hash, key);
5687c478bd9Sstevel@tonic-gate entry->mhe_key = key;
5697c478bd9Sstevel@tonic-gate entry->mhe_val = val;
5707c478bd9Sstevel@tonic-gate entry->mhe_next = hash->mh_entries[hashidx];
5717c478bd9Sstevel@tonic-gate
5727c478bd9Sstevel@tonic-gate hash->mh_entries[hashidx] = entry;
5737c478bd9Sstevel@tonic-gate hash->mh_stat.mhs_nelems++;
5747c478bd9Sstevel@tonic-gate
5757c478bd9Sstevel@tonic-gate return (0);
5767c478bd9Sstevel@tonic-gate }
5777c478bd9Sstevel@tonic-gate
5787c478bd9Sstevel@tonic-gate int
mod_hash_insert(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t val)5797c478bd9Sstevel@tonic-gate mod_hash_insert(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t val)
5807c478bd9Sstevel@tonic-gate {
5817c478bd9Sstevel@tonic-gate int res;
5827c478bd9Sstevel@tonic-gate mod_hash_val_t v;
5837c478bd9Sstevel@tonic-gate
5847c478bd9Sstevel@tonic-gate rw_enter(&hash->mh_contents, RW_WRITER);
5857c478bd9Sstevel@tonic-gate
5867c478bd9Sstevel@tonic-gate /*
5877c478bd9Sstevel@tonic-gate * Disallow duplicate keys in the hash
5887c478bd9Sstevel@tonic-gate */
5897c478bd9Sstevel@tonic-gate if (i_mod_hash_find_nosync(hash, key, &v) == 0) {
5907c478bd9Sstevel@tonic-gate rw_exit(&hash->mh_contents);
5917c478bd9Sstevel@tonic-gate hash->mh_stat.mhs_coll++;
5927c478bd9Sstevel@tonic-gate return (MH_ERR_DUPLICATE);
5937c478bd9Sstevel@tonic-gate }
5947c478bd9Sstevel@tonic-gate
5957c478bd9Sstevel@tonic-gate res = i_mod_hash_insert_nosync(hash, key, val, (mod_hash_hndl_t)0);
5967c478bd9Sstevel@tonic-gate rw_exit(&hash->mh_contents);
5977c478bd9Sstevel@tonic-gate
5987c478bd9Sstevel@tonic-gate return (res);
5997c478bd9Sstevel@tonic-gate }
6007c478bd9Sstevel@tonic-gate
6017c478bd9Sstevel@tonic-gate int
mod_hash_insert_reserve(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t val,mod_hash_hndl_t handle)6027c478bd9Sstevel@tonic-gate mod_hash_insert_reserve(mod_hash_t *hash, mod_hash_key_t key,
6037c478bd9Sstevel@tonic-gate mod_hash_val_t val, mod_hash_hndl_t handle)
6047c478bd9Sstevel@tonic-gate {
6057c478bd9Sstevel@tonic-gate int res;
6067c478bd9Sstevel@tonic-gate mod_hash_val_t v;
6077c478bd9Sstevel@tonic-gate
6087c478bd9Sstevel@tonic-gate rw_enter(&hash->mh_contents, RW_WRITER);
6097c478bd9Sstevel@tonic-gate
6107c478bd9Sstevel@tonic-gate /*
6117c478bd9Sstevel@tonic-gate * Disallow duplicate keys in the hash
6127c478bd9Sstevel@tonic-gate */
6137c478bd9Sstevel@tonic-gate if (i_mod_hash_find_nosync(hash, key, &v) == 0) {
6147c478bd9Sstevel@tonic-gate rw_exit(&hash->mh_contents);
6157c478bd9Sstevel@tonic-gate hash->mh_stat.mhs_coll++;
6167c478bd9Sstevel@tonic-gate return (MH_ERR_DUPLICATE);
6177c478bd9Sstevel@tonic-gate }
6187c478bd9Sstevel@tonic-gate res = i_mod_hash_insert_nosync(hash, key, val, handle);
6197c478bd9Sstevel@tonic-gate rw_exit(&hash->mh_contents);
6207c478bd9Sstevel@tonic-gate
6217c478bd9Sstevel@tonic-gate return (res);
6227c478bd9Sstevel@tonic-gate }
6237c478bd9Sstevel@tonic-gate
6247c478bd9Sstevel@tonic-gate /*
6257c478bd9Sstevel@tonic-gate * mod_hash_reserve()
6267c478bd9Sstevel@tonic-gate * mod_hash_reserve_nosleep()
6277c478bd9Sstevel@tonic-gate * mod_hash_cancel()
6287c478bd9Sstevel@tonic-gate * Make or cancel a mod_hash_entry_t reservation. Reservations are used in
6297c478bd9Sstevel@tonic-gate * mod_hash_insert_reserve() above.
6307c478bd9Sstevel@tonic-gate */
6317c478bd9Sstevel@tonic-gate int
mod_hash_reserve(mod_hash_t * hash,mod_hash_hndl_t * handlep)6327c478bd9Sstevel@tonic-gate mod_hash_reserve(mod_hash_t *hash, mod_hash_hndl_t *handlep)
6337c478bd9Sstevel@tonic-gate {
6347c478bd9Sstevel@tonic-gate *handlep = kmem_cache_alloc(mh_e_cache, hash->mh_sleep);
6357c478bd9Sstevel@tonic-gate if (*handlep == NULL) {
6367c478bd9Sstevel@tonic-gate hash->mh_stat.mhs_nomem++;
6377c478bd9Sstevel@tonic-gate return (MH_ERR_NOMEM);
6387c478bd9Sstevel@tonic-gate }
6397c478bd9Sstevel@tonic-gate
6407c478bd9Sstevel@tonic-gate return (0);
6417c478bd9Sstevel@tonic-gate }
6427c478bd9Sstevel@tonic-gate
6437c478bd9Sstevel@tonic-gate int
mod_hash_reserve_nosleep(mod_hash_t * hash,mod_hash_hndl_t * handlep)6447c478bd9Sstevel@tonic-gate mod_hash_reserve_nosleep(mod_hash_t *hash, mod_hash_hndl_t *handlep)
6457c478bd9Sstevel@tonic-gate {
6467c478bd9Sstevel@tonic-gate *handlep = kmem_cache_alloc(mh_e_cache, KM_NOSLEEP);
6477c478bd9Sstevel@tonic-gate if (*handlep == NULL) {
6487c478bd9Sstevel@tonic-gate hash->mh_stat.mhs_nomem++;
6497c478bd9Sstevel@tonic-gate return (MH_ERR_NOMEM);
6507c478bd9Sstevel@tonic-gate }
6517c478bd9Sstevel@tonic-gate
6527c478bd9Sstevel@tonic-gate return (0);
6537c478bd9Sstevel@tonic-gate
6547c478bd9Sstevel@tonic-gate }
6557c478bd9Sstevel@tonic-gate
6567c478bd9Sstevel@tonic-gate /*ARGSUSED*/
6577c478bd9Sstevel@tonic-gate void
mod_hash_cancel(mod_hash_t * hash,mod_hash_hndl_t * handlep)6587c478bd9Sstevel@tonic-gate mod_hash_cancel(mod_hash_t *hash, mod_hash_hndl_t *handlep)
6597c478bd9Sstevel@tonic-gate {
6607c478bd9Sstevel@tonic-gate kmem_cache_free(mh_e_cache, *handlep);
6617c478bd9Sstevel@tonic-gate *handlep = (mod_hash_hndl_t)0;
6627c478bd9Sstevel@tonic-gate }
6637c478bd9Sstevel@tonic-gate
6647c478bd9Sstevel@tonic-gate /*
6657c478bd9Sstevel@tonic-gate * i_mod_hash_remove_nosync()
6667c478bd9Sstevel@tonic-gate * mod_hash_remove()
6677c478bd9Sstevel@tonic-gate * Remove an element from the hash table.
6687c478bd9Sstevel@tonic-gate */
6697c478bd9Sstevel@tonic-gate int
i_mod_hash_remove_nosync(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t * val)6707c478bd9Sstevel@tonic-gate i_mod_hash_remove_nosync(mod_hash_t *hash, mod_hash_key_t key,
6717c478bd9Sstevel@tonic-gate mod_hash_val_t *val)
6727c478bd9Sstevel@tonic-gate {
6737c478bd9Sstevel@tonic-gate int hashidx;
6747c478bd9Sstevel@tonic-gate struct mod_hash_entry *e, *ep;
6757c478bd9Sstevel@tonic-gate
6767c478bd9Sstevel@tonic-gate hashidx = i_mod_hash(hash, key);
6777c478bd9Sstevel@tonic-gate ep = NULL; /* e's parent */
6787c478bd9Sstevel@tonic-gate
6797c478bd9Sstevel@tonic-gate for (e = hash->mh_entries[hashidx]; e != NULL; e = e->mhe_next) {
6807c478bd9Sstevel@tonic-gate if (MH_KEYCMP(hash, e->mhe_key, key) == 0)
6817c478bd9Sstevel@tonic-gate break;
6827c478bd9Sstevel@tonic-gate ep = e;
6837c478bd9Sstevel@tonic-gate }
6847c478bd9Sstevel@tonic-gate
6857c478bd9Sstevel@tonic-gate if (e == NULL) { /* not found */
6867c478bd9Sstevel@tonic-gate return (MH_ERR_NOTFOUND);
6877c478bd9Sstevel@tonic-gate }
6887c478bd9Sstevel@tonic-gate
6897c478bd9Sstevel@tonic-gate if (ep == NULL) /* special case 1st element in bucket */
6907c478bd9Sstevel@tonic-gate hash->mh_entries[hashidx] = e->mhe_next;
6917c478bd9Sstevel@tonic-gate else
6927c478bd9Sstevel@tonic-gate ep->mhe_next = e->mhe_next;
6937c478bd9Sstevel@tonic-gate
6947c478bd9Sstevel@tonic-gate /*
6957c478bd9Sstevel@tonic-gate * Clean up resources used by the node's key.
6967c478bd9Sstevel@tonic-gate */
6977c478bd9Sstevel@tonic-gate MH_KEY_DESTROY(hash, e->mhe_key);
6987c478bd9Sstevel@tonic-gate
6997c478bd9Sstevel@tonic-gate *val = e->mhe_val;
7007c478bd9Sstevel@tonic-gate kmem_cache_free(mh_e_cache, e);
7017c478bd9Sstevel@tonic-gate hash->mh_stat.mhs_nelems--;
7027c478bd9Sstevel@tonic-gate
7037c478bd9Sstevel@tonic-gate return (0);
7047c478bd9Sstevel@tonic-gate }
7057c478bd9Sstevel@tonic-gate
7067c478bd9Sstevel@tonic-gate int
mod_hash_remove(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t * val)7077c478bd9Sstevel@tonic-gate mod_hash_remove(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val)
7087c478bd9Sstevel@tonic-gate {
7097c478bd9Sstevel@tonic-gate int res;
7107c478bd9Sstevel@tonic-gate
7117c478bd9Sstevel@tonic-gate rw_enter(&hash->mh_contents, RW_WRITER);
7127c478bd9Sstevel@tonic-gate res = i_mod_hash_remove_nosync(hash, key, val);
7137c478bd9Sstevel@tonic-gate rw_exit(&hash->mh_contents);
7147c478bd9Sstevel@tonic-gate
7157c478bd9Sstevel@tonic-gate return (res);
7167c478bd9Sstevel@tonic-gate }
7177c478bd9Sstevel@tonic-gate
7187c478bd9Sstevel@tonic-gate /*
7197c478bd9Sstevel@tonic-gate * mod_hash_replace()
7207c478bd9Sstevel@tonic-gate * atomically remove an existing key-value pair from a hash, and replace
7217c478bd9Sstevel@tonic-gate * the key and value with the ones supplied. The removed key and value
7227c478bd9Sstevel@tonic-gate * (if any) are destroyed.
7237c478bd9Sstevel@tonic-gate */
7247c478bd9Sstevel@tonic-gate int
mod_hash_replace(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t val)7257c478bd9Sstevel@tonic-gate mod_hash_replace(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t val)
7267c478bd9Sstevel@tonic-gate {
7277c478bd9Sstevel@tonic-gate int res;
7287c478bd9Sstevel@tonic-gate mod_hash_val_t v;
7297c478bd9Sstevel@tonic-gate
7307c478bd9Sstevel@tonic-gate rw_enter(&hash->mh_contents, RW_WRITER);
7317c478bd9Sstevel@tonic-gate
7327c478bd9Sstevel@tonic-gate if (i_mod_hash_remove_nosync(hash, key, &v) == 0) {
7337c478bd9Sstevel@tonic-gate /*
7347c478bd9Sstevel@tonic-gate * mod_hash_remove() takes care of freeing up the key resources.
7357c478bd9Sstevel@tonic-gate */
7367c478bd9Sstevel@tonic-gate MH_VAL_DESTROY(hash, v);
7377c478bd9Sstevel@tonic-gate }
7387c478bd9Sstevel@tonic-gate res = i_mod_hash_insert_nosync(hash, key, val, (mod_hash_hndl_t)0);
7397c478bd9Sstevel@tonic-gate
7407c478bd9Sstevel@tonic-gate rw_exit(&hash->mh_contents);
7417c478bd9Sstevel@tonic-gate
7427c478bd9Sstevel@tonic-gate return (res);
7437c478bd9Sstevel@tonic-gate }
7447c478bd9Sstevel@tonic-gate
7457c478bd9Sstevel@tonic-gate /*
7467c478bd9Sstevel@tonic-gate * mod_hash_destroy()
7477c478bd9Sstevel@tonic-gate * Remove an element from the hash table matching 'key', and destroy it.
7487c478bd9Sstevel@tonic-gate */
7497c478bd9Sstevel@tonic-gate int
mod_hash_destroy(mod_hash_t * hash,mod_hash_key_t key)7507c478bd9Sstevel@tonic-gate mod_hash_destroy(mod_hash_t *hash, mod_hash_key_t key)
7517c478bd9Sstevel@tonic-gate {
7527c478bd9Sstevel@tonic-gate mod_hash_val_t val;
7537c478bd9Sstevel@tonic-gate int rv;
7547c478bd9Sstevel@tonic-gate
7557c478bd9Sstevel@tonic-gate rw_enter(&hash->mh_contents, RW_WRITER);
7567c478bd9Sstevel@tonic-gate
7577c478bd9Sstevel@tonic-gate if ((rv = i_mod_hash_remove_nosync(hash, key, &val)) == 0) {
7587c478bd9Sstevel@tonic-gate /*
7597c478bd9Sstevel@tonic-gate * mod_hash_remove() takes care of freeing up the key resources.
7607c478bd9Sstevel@tonic-gate */
7617c478bd9Sstevel@tonic-gate MH_VAL_DESTROY(hash, val);
7627c478bd9Sstevel@tonic-gate }
7637c478bd9Sstevel@tonic-gate
7647c478bd9Sstevel@tonic-gate rw_exit(&hash->mh_contents);
7657c478bd9Sstevel@tonic-gate return (rv);
7667c478bd9Sstevel@tonic-gate }
7677c478bd9Sstevel@tonic-gate
7687c478bd9Sstevel@tonic-gate /*
7697c478bd9Sstevel@tonic-gate * i_mod_hash_find_nosync()
7707c478bd9Sstevel@tonic-gate * mod_hash_find()
7717c478bd9Sstevel@tonic-gate * Find a value in the hash table corresponding to the given key.
7727c478bd9Sstevel@tonic-gate */
7730209230bSgjelinek int
i_mod_hash_find_nosync(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t * val)7747c478bd9Sstevel@tonic-gate i_mod_hash_find_nosync(mod_hash_t *hash, mod_hash_key_t key,
7757c478bd9Sstevel@tonic-gate mod_hash_val_t *val)
7767c478bd9Sstevel@tonic-gate {
7777c478bd9Sstevel@tonic-gate uint_t hashidx;
7787c478bd9Sstevel@tonic-gate struct mod_hash_entry *e;
7797c478bd9Sstevel@tonic-gate
7807c478bd9Sstevel@tonic-gate hashidx = i_mod_hash(hash, key);
7817c478bd9Sstevel@tonic-gate
7827c478bd9Sstevel@tonic-gate for (e = hash->mh_entries[hashidx]; e != NULL; e = e->mhe_next) {
7837c478bd9Sstevel@tonic-gate if (MH_KEYCMP(hash, e->mhe_key, key) == 0) {
7847c478bd9Sstevel@tonic-gate *val = e->mhe_val;
7857c478bd9Sstevel@tonic-gate hash->mh_stat.mhs_hit++;
7867c478bd9Sstevel@tonic-gate return (0);
7877c478bd9Sstevel@tonic-gate }
7887c478bd9Sstevel@tonic-gate }
7897c478bd9Sstevel@tonic-gate hash->mh_stat.mhs_miss++;
7907c478bd9Sstevel@tonic-gate return (MH_ERR_NOTFOUND);
7917c478bd9Sstevel@tonic-gate }
7927c478bd9Sstevel@tonic-gate
7937c478bd9Sstevel@tonic-gate int
mod_hash_find(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t * val)7947c478bd9Sstevel@tonic-gate mod_hash_find(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val)
7957c478bd9Sstevel@tonic-gate {
7967c478bd9Sstevel@tonic-gate int res;
7977c478bd9Sstevel@tonic-gate
7987c478bd9Sstevel@tonic-gate rw_enter(&hash->mh_contents, RW_READER);
7997c478bd9Sstevel@tonic-gate res = i_mod_hash_find_nosync(hash, key, val);
8007c478bd9Sstevel@tonic-gate rw_exit(&hash->mh_contents);
8017c478bd9Sstevel@tonic-gate
8027c478bd9Sstevel@tonic-gate return (res);
8037c478bd9Sstevel@tonic-gate }
8047c478bd9Sstevel@tonic-gate
8057c478bd9Sstevel@tonic-gate int
mod_hash_find_cb(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t * val,void (* find_cb)(mod_hash_key_t,mod_hash_val_t))8067c478bd9Sstevel@tonic-gate mod_hash_find_cb(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val,
8077c478bd9Sstevel@tonic-gate void (*find_cb)(mod_hash_key_t, mod_hash_val_t))
8087c478bd9Sstevel@tonic-gate {
8097c478bd9Sstevel@tonic-gate int res;
8107c478bd9Sstevel@tonic-gate
8117c478bd9Sstevel@tonic-gate rw_enter(&hash->mh_contents, RW_READER);
8127c478bd9Sstevel@tonic-gate res = i_mod_hash_find_nosync(hash, key, val);
8137c478bd9Sstevel@tonic-gate if (res == 0) {
8147c478bd9Sstevel@tonic-gate find_cb(key, *val);
8157c478bd9Sstevel@tonic-gate }
8167c478bd9Sstevel@tonic-gate rw_exit(&hash->mh_contents);
8177c478bd9Sstevel@tonic-gate
8187c478bd9Sstevel@tonic-gate return (res);
8197c478bd9Sstevel@tonic-gate }
8207c478bd9Sstevel@tonic-gate
821da14cebeSEric Cheng int
mod_hash_find_cb_rval(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t * val,int (* find_cb)(mod_hash_key_t,mod_hash_val_t),int * cb_rval)822da14cebeSEric Cheng mod_hash_find_cb_rval(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val,
823da14cebeSEric Cheng int (*find_cb)(mod_hash_key_t, mod_hash_val_t), int *cb_rval)
824da14cebeSEric Cheng {
825da14cebeSEric Cheng int res;
826da14cebeSEric Cheng
827da14cebeSEric Cheng rw_enter(&hash->mh_contents, RW_READER);
828da14cebeSEric Cheng res = i_mod_hash_find_nosync(hash, key, val);
829da14cebeSEric Cheng if (res == 0) {
830da14cebeSEric Cheng *cb_rval = find_cb(key, *val);
831da14cebeSEric Cheng }
832da14cebeSEric Cheng rw_exit(&hash->mh_contents);
833da14cebeSEric Cheng
834da14cebeSEric Cheng return (res);
835da14cebeSEric Cheng }
836da14cebeSEric Cheng
8370209230bSgjelinek void
i_mod_hash_walk_nosync(mod_hash_t * hash,uint_t (* callback)(mod_hash_key_t,mod_hash_val_t *,void *),void * arg)8387c478bd9Sstevel@tonic-gate i_mod_hash_walk_nosync(mod_hash_t *hash,
8397c478bd9Sstevel@tonic-gate uint_t (*callback)(mod_hash_key_t, mod_hash_val_t *, void *), void *arg)
8407c478bd9Sstevel@tonic-gate {
8417c478bd9Sstevel@tonic-gate struct mod_hash_entry *e;
8427c478bd9Sstevel@tonic-gate uint_t hashidx;
8437c478bd9Sstevel@tonic-gate int res = MH_WALK_CONTINUE;
8447c478bd9Sstevel@tonic-gate
8457c478bd9Sstevel@tonic-gate for (hashidx = 0;
8467c478bd9Sstevel@tonic-gate (hashidx < (hash->mh_nchains - 1)) && (res == MH_WALK_CONTINUE);
8477c478bd9Sstevel@tonic-gate hashidx++) {
8487c478bd9Sstevel@tonic-gate e = hash->mh_entries[hashidx];
8497c478bd9Sstevel@tonic-gate while ((e != NULL) && (res == MH_WALK_CONTINUE)) {
8507c478bd9Sstevel@tonic-gate res = callback(e->mhe_key, e->mhe_val, arg);
8517c478bd9Sstevel@tonic-gate e = e->mhe_next;
8527c478bd9Sstevel@tonic-gate }
8537c478bd9Sstevel@tonic-gate }
8547c478bd9Sstevel@tonic-gate }
8557c478bd9Sstevel@tonic-gate
8567c478bd9Sstevel@tonic-gate /*
8577c478bd9Sstevel@tonic-gate * mod_hash_walk()
8587c478bd9Sstevel@tonic-gate * Walks all the elements in the hashtable and invokes the callback
8597c478bd9Sstevel@tonic-gate * function with the key/value pair for each element. The hashtable
8607c478bd9Sstevel@tonic-gate * is locked for readers so the callback function should not attempt
8617c478bd9Sstevel@tonic-gate * to do any updates to the hashable. The callback function should
8627c478bd9Sstevel@tonic-gate * return MH_WALK_CONTINUE to continue walking the hashtable or
8637c478bd9Sstevel@tonic-gate * MH_WALK_TERMINATE to abort the walk of the hashtable.
8647c478bd9Sstevel@tonic-gate */
8657c478bd9Sstevel@tonic-gate void
mod_hash_walk(mod_hash_t * hash,uint_t (* callback)(mod_hash_key_t,mod_hash_val_t *,void *),void * arg)8667c478bd9Sstevel@tonic-gate mod_hash_walk(mod_hash_t *hash,
8677c478bd9Sstevel@tonic-gate uint_t (*callback)(mod_hash_key_t, mod_hash_val_t *, void *), void *arg)
8687c478bd9Sstevel@tonic-gate {
8697c478bd9Sstevel@tonic-gate rw_enter(&hash->mh_contents, RW_READER);
8707c478bd9Sstevel@tonic-gate i_mod_hash_walk_nosync(hash, callback, arg);
8717c478bd9Sstevel@tonic-gate rw_exit(&hash->mh_contents);
8727c478bd9Sstevel@tonic-gate }
8737c478bd9Sstevel@tonic-gate
8747c478bd9Sstevel@tonic-gate
8757c478bd9Sstevel@tonic-gate /*
8767c478bd9Sstevel@tonic-gate * i_mod_hash_clear_nosync()
8777c478bd9Sstevel@tonic-gate * mod_hash_clear()
8787c478bd9Sstevel@tonic-gate * Clears the given hash table by calling the destructor of every hash
8797c478bd9Sstevel@tonic-gate * element and freeing up all mod_hash_entry's.
8807c478bd9Sstevel@tonic-gate */
8810209230bSgjelinek void
i_mod_hash_clear_nosync(mod_hash_t * hash)8827c478bd9Sstevel@tonic-gate i_mod_hash_clear_nosync(mod_hash_t *hash)
8837c478bd9Sstevel@tonic-gate {
8847c478bd9Sstevel@tonic-gate int i;
8857c478bd9Sstevel@tonic-gate struct mod_hash_entry *e, *old_e;
8867c478bd9Sstevel@tonic-gate
8877c478bd9Sstevel@tonic-gate for (i = 0; i < hash->mh_nchains; i++) {
8887c478bd9Sstevel@tonic-gate e = hash->mh_entries[i];
8897c478bd9Sstevel@tonic-gate while (e != NULL) {
8907c478bd9Sstevel@tonic-gate MH_KEY_DESTROY(hash, e->mhe_key);
8917c478bd9Sstevel@tonic-gate MH_VAL_DESTROY(hash, e->mhe_val);
8927c478bd9Sstevel@tonic-gate old_e = e;
8937c478bd9Sstevel@tonic-gate e = e->mhe_next;
8947c478bd9Sstevel@tonic-gate kmem_cache_free(mh_e_cache, old_e);
8957c478bd9Sstevel@tonic-gate }
8967c478bd9Sstevel@tonic-gate hash->mh_entries[i] = NULL;
8977c478bd9Sstevel@tonic-gate }
8987c478bd9Sstevel@tonic-gate hash->mh_stat.mhs_nelems = 0;
8997c478bd9Sstevel@tonic-gate }
9007c478bd9Sstevel@tonic-gate
9017c478bd9Sstevel@tonic-gate void
mod_hash_clear(mod_hash_t * hash)9027c478bd9Sstevel@tonic-gate mod_hash_clear(mod_hash_t *hash)
9037c478bd9Sstevel@tonic-gate {
9047c478bd9Sstevel@tonic-gate ASSERT(hash);
9057c478bd9Sstevel@tonic-gate rw_enter(&hash->mh_contents, RW_WRITER);
9067c478bd9Sstevel@tonic-gate i_mod_hash_clear_nosync(hash);
9077c478bd9Sstevel@tonic-gate rw_exit(&hash->mh_contents);
9087c478bd9Sstevel@tonic-gate }
909