xref: /onnv-gate/usr/src/uts/common/os/modhash.c (revision 8275:7c223a798022)
10Sstevel@tonic-gate /*
20Sstevel@tonic-gate  * CDDL HEADER START
30Sstevel@tonic-gate  *
40Sstevel@tonic-gate  * The contents of this file are subject to the terms of the
53247Sgjelinek  * Common Development and Distribution License (the "License").
63247Sgjelinek  * You may not use this file except in compliance with the License.
70Sstevel@tonic-gate  *
80Sstevel@tonic-gate  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
90Sstevel@tonic-gate  * or http://www.opensolaris.org/os/licensing.
100Sstevel@tonic-gate  * See the License for the specific language governing permissions
110Sstevel@tonic-gate  * and limitations under the License.
120Sstevel@tonic-gate  *
130Sstevel@tonic-gate  * When distributing Covered Code, include this CDDL HEADER in each
140Sstevel@tonic-gate  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
150Sstevel@tonic-gate  * If applicable, add the following below this CDDL HEADER, with the
160Sstevel@tonic-gate  * fields enclosed by brackets "[]" replaced with your own identifying
170Sstevel@tonic-gate  * information: Portions Copyright [yyyy] [name of copyright owner]
180Sstevel@tonic-gate  *
190Sstevel@tonic-gate  * CDDL HEADER END
200Sstevel@tonic-gate  */
210Sstevel@tonic-gate /*
22*8275SEric Cheng  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
230Sstevel@tonic-gate  * Use is subject to license terms.
240Sstevel@tonic-gate  */
250Sstevel@tonic-gate 
260Sstevel@tonic-gate /*
270Sstevel@tonic-gate  * mod_hash: flexible hash table implementation.
280Sstevel@tonic-gate  *
290Sstevel@tonic-gate  * This is a reasonably fast, reasonably flexible hash table implementation
300Sstevel@tonic-gate  * which features pluggable hash algorithms to support storing arbitrary keys
310Sstevel@tonic-gate  * and values.  It is designed to handle small (< 100,000 items) amounts of
320Sstevel@tonic-gate  * data.  The hash uses chaining to resolve collisions, and does not feature a
330Sstevel@tonic-gate  * mechanism to grow the hash.  Care must be taken to pick nchains to be large
340Sstevel@tonic-gate  * enough for the application at hand, or lots of time will be wasted searching
350Sstevel@tonic-gate  * hash chains.
360Sstevel@tonic-gate  *
370Sstevel@tonic-gate  * The client of the hash is required to supply a number of items to support
380Sstevel@tonic-gate  * the various hash functions:
390Sstevel@tonic-gate  *
400Sstevel@tonic-gate  * 	- Destructor functions for the key and value being hashed.
410Sstevel@tonic-gate  *	  A destructor is responsible for freeing an object when the hash
420Sstevel@tonic-gate  *	  table is no longer storing it.  Since keys and values can be of
430Sstevel@tonic-gate  *	  arbitrary type, separate destructors for keys & values are used.
440Sstevel@tonic-gate  *	  These may be mod_hash_null_keydtor and mod_hash_null_valdtor if no
450Sstevel@tonic-gate  *	  destructor is needed for either a key or value.
460Sstevel@tonic-gate  *
470Sstevel@tonic-gate  *	- A hashing algorithm which returns a uint_t representing a hash index
480Sstevel@tonic-gate  *	  The number returned need _not_ be between 0 and nchains.  The mod_hash
490Sstevel@tonic-gate  *	  code will take care of doing that.  The second argument (after the
500Sstevel@tonic-gate  *	  key) to the hashing function is a void * that represents
510Sstevel@tonic-gate  *	  hash_alg_data-- this is provided so that the hashing algrorithm can
520Sstevel@tonic-gate  *	  maintain some state across calls, or keep algorithm-specific
530Sstevel@tonic-gate  *	  constants associated with the hash table.
540Sstevel@tonic-gate  *
550Sstevel@tonic-gate  *	  A pointer-hashing and a string-hashing algorithm are supplied in
560Sstevel@tonic-gate  *	  this file.
570Sstevel@tonic-gate  *
580Sstevel@tonic-gate  *	- A key comparator (a la qsort).
590Sstevel@tonic-gate  *	  This is used when searching the hash chain.  The key comparator
600Sstevel@tonic-gate  *	  determines if two keys match.  It should follow the return value
610Sstevel@tonic-gate  *	  semantics of strcmp.
620Sstevel@tonic-gate  *
630Sstevel@tonic-gate  *	  string and pointer comparators are supplied in this file.
640Sstevel@tonic-gate  *
650Sstevel@tonic-gate  * mod_hash_create_strhash() and mod_hash_create_ptrhash() provide good
660Sstevel@tonic-gate  * examples of how to create a customized hash table.
670Sstevel@tonic-gate  *
680Sstevel@tonic-gate  * Basic hash operations:
690Sstevel@tonic-gate  *
700Sstevel@tonic-gate  *   mod_hash_create_strhash(name, nchains, dtor),
710Sstevel@tonic-gate  *	create a hash using strings as keys.
720Sstevel@tonic-gate  *	NOTE: This create a hash which automatically cleans up the string
730Sstevel@tonic-gate  *	      values it is given for keys.
740Sstevel@tonic-gate  *
750Sstevel@tonic-gate  *   mod_hash_create_ptrhash(name, nchains, dtor, key_elem_size):
760Sstevel@tonic-gate  *	create a hash using pointers as keys.
770Sstevel@tonic-gate  *
780Sstevel@tonic-gate  *   mod_hash_create_extended(name, nchains, kdtor, vdtor,
790Sstevel@tonic-gate  *			      hash_alg, hash_alg_data,
800Sstevel@tonic-gate  *			      keycmp, sleep)
810Sstevel@tonic-gate  *	create a customized hash table.
820Sstevel@tonic-gate  *
830Sstevel@tonic-gate  *   mod_hash_destroy_hash(hash):
840Sstevel@tonic-gate  *	destroy the given hash table, calling the key and value destructors
850Sstevel@tonic-gate  *	on each key-value pair stored in the hash.
860Sstevel@tonic-gate  *
870Sstevel@tonic-gate  *   mod_hash_insert(hash, key, val):
880Sstevel@tonic-gate  *	place a key, value pair into the given hash.
890Sstevel@tonic-gate  *	duplicate keys are rejected.
900Sstevel@tonic-gate  *
910Sstevel@tonic-gate  *   mod_hash_insert_reserve(hash, key, val, handle):
920Sstevel@tonic-gate  *	place a key, value pair into the given hash, using handle to indicate
930Sstevel@tonic-gate  *	the reserved storage for the pair.  (no memory allocation is needed
940Sstevel@tonic-gate  *	during a mod_hash_insert_reserve.)  duplicate keys are rejected.
950Sstevel@tonic-gate  *
960Sstevel@tonic-gate  *   mod_hash_reserve(hash, *handle):
970Sstevel@tonic-gate  *      reserve storage for a key-value pair using the memory allocation
980Sstevel@tonic-gate  *      policy of 'hash', returning the storage handle in 'handle'.
990Sstevel@tonic-gate  *
1000Sstevel@tonic-gate  *   mod_hash_reserve_nosleep(hash, *handle): reserve storage for a key-value
1010Sstevel@tonic-gate  *	pair ignoring the memory allocation policy of 'hash' and always without
1020Sstevel@tonic-gate  *	sleep, returning the storage handle in 'handle'.
1030Sstevel@tonic-gate  *
1040Sstevel@tonic-gate  *   mod_hash_remove(hash, key, *val):
1050Sstevel@tonic-gate  *	remove a key-value pair with key 'key' from 'hash', destroying the
1060Sstevel@tonic-gate  *	stored key, and returning the value in val.
1070Sstevel@tonic-gate  *
1080Sstevel@tonic-gate  *   mod_hash_replace(hash, key, val)
1090Sstevel@tonic-gate  * 	atomically remove an existing key-value pair from a hash, and replace
1100Sstevel@tonic-gate  * 	the key and value with the ones supplied.  The removed key and value
1110Sstevel@tonic-gate  * 	(if any) are destroyed.
1120Sstevel@tonic-gate  *
1130Sstevel@tonic-gate  *   mod_hash_destroy(hash, key):
1140Sstevel@tonic-gate  *	remove a key-value pair with key 'key' from 'hash', destroying both
1150Sstevel@tonic-gate  *	stored key and stored value.
1160Sstevel@tonic-gate  *
1170Sstevel@tonic-gate  *   mod_hash_find(hash, key, val):
1180Sstevel@tonic-gate  *	find a value in the hash table corresponding to the given key.
1190Sstevel@tonic-gate  *
1200Sstevel@tonic-gate  *   mod_hash_find_cb(hash, key, val, found_callback)
1210Sstevel@tonic-gate  *	find a value in the hash table corresponding to the given key.
1220Sstevel@tonic-gate  *	If a value is found, call specified callback passing key and val to it.
1230Sstevel@tonic-gate  *      The callback is called with the hash lock held.
1240Sstevel@tonic-gate  *	It is intended to be used in situations where the act of locating the
1250Sstevel@tonic-gate  *	data must also modify it - such as in reference counting schemes.
1260Sstevel@tonic-gate  *
1270Sstevel@tonic-gate  *   mod_hash_walk(hash, callback(key, elem, arg), arg)
1280Sstevel@tonic-gate  * 	walks all the elements in the hashtable and invokes the callback
1290Sstevel@tonic-gate  * 	function with the key/value pair for each element.  the hashtable
1300Sstevel@tonic-gate  * 	is locked for readers so the callback function should not attempt
1310Sstevel@tonic-gate  * 	to do any updates to the hashable.  the callback function should
1320Sstevel@tonic-gate  * 	return MH_WALK_CONTINUE to continue walking the hashtable or
1330Sstevel@tonic-gate  * 	MH_WALK_TERMINATE to abort the walk of the hashtable.
1340Sstevel@tonic-gate  *
1350Sstevel@tonic-gate  *   mod_hash_clear(hash):
1360Sstevel@tonic-gate  *	clears the given hash table of entries, calling the key and value
1370Sstevel@tonic-gate  *	destructors for every element in the hash.
1380Sstevel@tonic-gate  */
1390Sstevel@tonic-gate 
1400Sstevel@tonic-gate #include <sys/bitmap.h>
1410Sstevel@tonic-gate #include <sys/debug.h>
1420Sstevel@tonic-gate #include <sys/kmem.h>
1430Sstevel@tonic-gate #include <sys/sunddi.h>
1440Sstevel@tonic-gate 
1450Sstevel@tonic-gate #include <sys/modhash_impl.h>
1460Sstevel@tonic-gate 
1470Sstevel@tonic-gate /*
1480Sstevel@tonic-gate  * MH_KEY_DESTROY()
1490Sstevel@tonic-gate  * 	Invoke the key destructor.
1500Sstevel@tonic-gate  */
1510Sstevel@tonic-gate #define	MH_KEY_DESTROY(hash, key) ((hash->mh_kdtor)(key))
1520Sstevel@tonic-gate 
1530Sstevel@tonic-gate /*
1540Sstevel@tonic-gate  * MH_VAL_DESTROY()
1550Sstevel@tonic-gate  * 	Invoke the value destructor.
1560Sstevel@tonic-gate  */
1570Sstevel@tonic-gate #define	MH_VAL_DESTROY(hash, val) ((hash->mh_vdtor)(val))
1580Sstevel@tonic-gate 
1590Sstevel@tonic-gate /*
1600Sstevel@tonic-gate  * MH_KEYCMP()
1610Sstevel@tonic-gate  * 	Call the key comparator for the given hash keys.
1620Sstevel@tonic-gate  */
1630Sstevel@tonic-gate #define	MH_KEYCMP(hash, key1, key2) ((hash->mh_keycmp)(key1, key2))
1640Sstevel@tonic-gate 
1650Sstevel@tonic-gate /*
1660Sstevel@tonic-gate  * Cache for struct mod_hash_entry
1670Sstevel@tonic-gate  */
1680Sstevel@tonic-gate kmem_cache_t *mh_e_cache = NULL;
1690Sstevel@tonic-gate mod_hash_t *mh_head = NULL;
1700Sstevel@tonic-gate kmutex_t mh_head_lock;
1710Sstevel@tonic-gate 
1720Sstevel@tonic-gate /*
1730Sstevel@tonic-gate  * mod_hash_null_keydtor()
1740Sstevel@tonic-gate  * mod_hash_null_valdtor()
1750Sstevel@tonic-gate  * 	no-op key and value destructors.
1760Sstevel@tonic-gate  */
1770Sstevel@tonic-gate /*ARGSUSED*/
1780Sstevel@tonic-gate void
mod_hash_null_keydtor(mod_hash_key_t key)1790Sstevel@tonic-gate mod_hash_null_keydtor(mod_hash_key_t key)
1800Sstevel@tonic-gate {
1810Sstevel@tonic-gate }
1820Sstevel@tonic-gate 
1830Sstevel@tonic-gate /*ARGSUSED*/
1840Sstevel@tonic-gate void
mod_hash_null_valdtor(mod_hash_val_t val)1850Sstevel@tonic-gate mod_hash_null_valdtor(mod_hash_val_t val)
1860Sstevel@tonic-gate {
1870Sstevel@tonic-gate }
1880Sstevel@tonic-gate 
1890Sstevel@tonic-gate /*
1900Sstevel@tonic-gate  * mod_hash_bystr()
1910Sstevel@tonic-gate  * mod_hash_strkey_cmp()
1920Sstevel@tonic-gate  * mod_hash_strkey_dtor()
1930Sstevel@tonic-gate  * mod_hash_strval_dtor()
1940Sstevel@tonic-gate  *	Hash and key comparison routines for hashes with string keys.
1950Sstevel@tonic-gate  *
1960Sstevel@tonic-gate  * mod_hash_create_strhash()
1970Sstevel@tonic-gate  * 	Create a hash using strings as keys
1980Sstevel@tonic-gate  *
1990Sstevel@tonic-gate  *	The string hashing algorithm is from the "Dragon Book" --
2000Sstevel@tonic-gate  *	"Compilers: Principles, Tools & Techniques", by Aho, Sethi, Ullman
2010Sstevel@tonic-gate  */
2020Sstevel@tonic-gate 
2030Sstevel@tonic-gate /*ARGSUSED*/
2040Sstevel@tonic-gate uint_t
mod_hash_bystr(void * hash_data,mod_hash_key_t key)2050Sstevel@tonic-gate mod_hash_bystr(void *hash_data, mod_hash_key_t key)
2060Sstevel@tonic-gate {
2070Sstevel@tonic-gate 	uint_t hash = 0;
2080Sstevel@tonic-gate 	uint_t g;
2090Sstevel@tonic-gate 	char *p, *k = (char *)key;
2100Sstevel@tonic-gate 
2110Sstevel@tonic-gate 	ASSERT(k);
2120Sstevel@tonic-gate 	for (p = k; *p != '\0'; p++) {
2130Sstevel@tonic-gate 		hash = (hash << 4) + *p;
2140Sstevel@tonic-gate 		if ((g = (hash & 0xf0000000)) != 0) {
2150Sstevel@tonic-gate 			hash ^= (g >> 24);
2160Sstevel@tonic-gate 			hash ^= g;
2170Sstevel@tonic-gate 		}
2180Sstevel@tonic-gate 	}
2190Sstevel@tonic-gate 	return (hash);
2200Sstevel@tonic-gate }
2210Sstevel@tonic-gate 
2220Sstevel@tonic-gate int
mod_hash_strkey_cmp(mod_hash_key_t key1,mod_hash_key_t key2)2230Sstevel@tonic-gate mod_hash_strkey_cmp(mod_hash_key_t key1, mod_hash_key_t key2)
2240Sstevel@tonic-gate {
2250Sstevel@tonic-gate 	return (strcmp((char *)key1, (char *)key2));
2260Sstevel@tonic-gate }
2270Sstevel@tonic-gate 
2280Sstevel@tonic-gate void
mod_hash_strkey_dtor(mod_hash_key_t key)2290Sstevel@tonic-gate mod_hash_strkey_dtor(mod_hash_key_t key)
2300Sstevel@tonic-gate {
2310Sstevel@tonic-gate 	char *c = (char *)key;
2320Sstevel@tonic-gate 	kmem_free(c, strlen(c) + 1);
2330Sstevel@tonic-gate }
2340Sstevel@tonic-gate 
2350Sstevel@tonic-gate void
mod_hash_strval_dtor(mod_hash_val_t val)2360Sstevel@tonic-gate mod_hash_strval_dtor(mod_hash_val_t val)
2370Sstevel@tonic-gate {
2380Sstevel@tonic-gate 	char *c = (char *)val;
2390Sstevel@tonic-gate 	kmem_free(c, strlen(c) + 1);
2400Sstevel@tonic-gate }
2410Sstevel@tonic-gate 
2420Sstevel@tonic-gate mod_hash_t *
mod_hash_create_strhash(char * name,size_t nchains,void (* val_dtor)(mod_hash_val_t))2430Sstevel@tonic-gate mod_hash_create_strhash(char *name, size_t nchains,
2440Sstevel@tonic-gate     void (*val_dtor)(mod_hash_val_t))
2450Sstevel@tonic-gate {
2460Sstevel@tonic-gate 	return mod_hash_create_extended(name, nchains, mod_hash_strkey_dtor,
2470Sstevel@tonic-gate 	    val_dtor, mod_hash_bystr, NULL, mod_hash_strkey_cmp, KM_SLEEP);
2480Sstevel@tonic-gate }
2490Sstevel@tonic-gate 
2500Sstevel@tonic-gate void
mod_hash_destroy_strhash(mod_hash_t * strhash)2510Sstevel@tonic-gate mod_hash_destroy_strhash(mod_hash_t *strhash)
2520Sstevel@tonic-gate {
2530Sstevel@tonic-gate 	ASSERT(strhash);
2540Sstevel@tonic-gate 	mod_hash_destroy_hash(strhash);
2550Sstevel@tonic-gate }
2560Sstevel@tonic-gate 
2570Sstevel@tonic-gate 
2580Sstevel@tonic-gate /*
2590Sstevel@tonic-gate  * mod_hash_byptr()
2600Sstevel@tonic-gate  * mod_hash_ptrkey_cmp()
2610Sstevel@tonic-gate  *	Hash and key comparison routines for hashes with pointer keys.
2620Sstevel@tonic-gate  *
2630Sstevel@tonic-gate  * mod_hash_create_ptrhash()
2640Sstevel@tonic-gate  * mod_hash_destroy_ptrhash()
2650Sstevel@tonic-gate  * 	Create a hash that uses pointers as keys.  This hash algorithm
2660Sstevel@tonic-gate  * 	picks an appropriate set of middle bits in the address to hash on
2670Sstevel@tonic-gate  * 	based on the size of the hash table and a hint about the size of
2680Sstevel@tonic-gate  * 	the items pointed at.
2690Sstevel@tonic-gate  */
2700Sstevel@tonic-gate uint_t
mod_hash_byptr(void * hash_data,mod_hash_key_t key)2710Sstevel@tonic-gate mod_hash_byptr(void *hash_data, mod_hash_key_t key)
2720Sstevel@tonic-gate {
2730Sstevel@tonic-gate 	uintptr_t k = (uintptr_t)key;
2740Sstevel@tonic-gate 	k >>= (int)(uintptr_t)hash_data;
2750Sstevel@tonic-gate 
2760Sstevel@tonic-gate 	return ((uint_t)k);
2770Sstevel@tonic-gate }
2780Sstevel@tonic-gate 
2790Sstevel@tonic-gate int
mod_hash_ptrkey_cmp(mod_hash_key_t key1,mod_hash_key_t key2)2800Sstevel@tonic-gate mod_hash_ptrkey_cmp(mod_hash_key_t key1, mod_hash_key_t key2)
2810Sstevel@tonic-gate {
2820Sstevel@tonic-gate 	uintptr_t k1 = (uintptr_t)key1;
2830Sstevel@tonic-gate 	uintptr_t k2 = (uintptr_t)key2;
2840Sstevel@tonic-gate 	if (k1 > k2)
2850Sstevel@tonic-gate 		return (-1);
2860Sstevel@tonic-gate 	else if (k1 < k2)
2870Sstevel@tonic-gate 		return (1);
2880Sstevel@tonic-gate 	else
2890Sstevel@tonic-gate 		return (0);
2900Sstevel@tonic-gate }
2910Sstevel@tonic-gate 
2920Sstevel@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)2930Sstevel@tonic-gate mod_hash_create_ptrhash(char *name, size_t nchains,
2940Sstevel@tonic-gate     void (*val_dtor)(mod_hash_val_t), size_t key_elem_size)
2950Sstevel@tonic-gate {
2960Sstevel@tonic-gate 	size_t rshift;
2970Sstevel@tonic-gate 
2980Sstevel@tonic-gate 	/*
2990Sstevel@tonic-gate 	 * We want to hash on the bits in the middle of the address word
3000Sstevel@tonic-gate 	 * Bits far to the right in the word have little significance, and
3010Sstevel@tonic-gate 	 * are likely to all look the same (for example, an array of
3020Sstevel@tonic-gate 	 * 256-byte structures will have the bottom 8 bits of address
3030Sstevel@tonic-gate 	 * words the same).  So we want to right-shift each address to
3040Sstevel@tonic-gate 	 * ignore the bottom bits.
3050Sstevel@tonic-gate 	 *
3060Sstevel@tonic-gate 	 * The high bits, which are also unused, will get taken out when
3070Sstevel@tonic-gate 	 * mod_hash takes hashkey % nchains.
3080Sstevel@tonic-gate 	 */
3090Sstevel@tonic-gate 	rshift = highbit(key_elem_size);
3100Sstevel@tonic-gate 
3110Sstevel@tonic-gate 	return mod_hash_create_extended(name, nchains, mod_hash_null_keydtor,
3120Sstevel@tonic-gate 	    val_dtor, mod_hash_byptr, (void *)rshift, mod_hash_ptrkey_cmp,
3130Sstevel@tonic-gate 	    KM_SLEEP);
3140Sstevel@tonic-gate }
3150Sstevel@tonic-gate 
3160Sstevel@tonic-gate void
mod_hash_destroy_ptrhash(mod_hash_t * hash)3170Sstevel@tonic-gate mod_hash_destroy_ptrhash(mod_hash_t *hash)
3180Sstevel@tonic-gate {
3190Sstevel@tonic-gate 	ASSERT(hash);
3200Sstevel@tonic-gate 	mod_hash_destroy_hash(hash);
3210Sstevel@tonic-gate }
3220Sstevel@tonic-gate 
3230Sstevel@tonic-gate /*
3240Sstevel@tonic-gate  * mod_hash_byid()
3250Sstevel@tonic-gate  * mod_hash_idkey_cmp()
3260Sstevel@tonic-gate  *	Hash and key comparison routines for hashes with 32-bit unsigned keys.
3270Sstevel@tonic-gate  *
3280Sstevel@tonic-gate  * mod_hash_create_idhash()
3290Sstevel@tonic-gate  * mod_hash_destroy_idhash()
3300Sstevel@tonic-gate  * mod_hash_iddata_gen()
3310Sstevel@tonic-gate  * 	Create a hash that uses numeric keys.
3320Sstevel@tonic-gate  *
3330Sstevel@tonic-gate  *	The hash algorithm is documented in "Introduction to Algorithms"
3340Sstevel@tonic-gate  *	(Cormen, Leiserson, Rivest);  when the hash table is created, it
3350Sstevel@tonic-gate  *	attempts to find the next largest prime above the number of hash
3360Sstevel@tonic-gate  *	slots.  The hash index is then this number times the key modulo
3370Sstevel@tonic-gate  *	the hash size, or (key * prime) % nchains.
3380Sstevel@tonic-gate  */
3390Sstevel@tonic-gate uint_t
mod_hash_byid(void * hash_data,mod_hash_key_t key)3400Sstevel@tonic-gate mod_hash_byid(void *hash_data, mod_hash_key_t key)
3410Sstevel@tonic-gate {
3420Sstevel@tonic-gate 	uint_t kval = (uint_t)(uintptr_t)hash_data;
3430Sstevel@tonic-gate 	return ((uint_t)(uintptr_t)key * (uint_t)kval);
3440Sstevel@tonic-gate }
3450Sstevel@tonic-gate 
3460Sstevel@tonic-gate int
mod_hash_idkey_cmp(mod_hash_key_t key1,mod_hash_key_t key2)3470Sstevel@tonic-gate mod_hash_idkey_cmp(mod_hash_key_t key1, mod_hash_key_t key2)
3480Sstevel@tonic-gate {
3490Sstevel@tonic-gate 	return ((uint_t)(uintptr_t)key1 - (uint_t)(uintptr_t)key2);
3500Sstevel@tonic-gate }
3510Sstevel@tonic-gate 
3520Sstevel@tonic-gate /*
3530Sstevel@tonic-gate  * Generate the next largest prime number greater than nchains; this value
3540Sstevel@tonic-gate  * is intended to be later passed in to mod_hash_create_extended() as the
3550Sstevel@tonic-gate  * hash_data.
3560Sstevel@tonic-gate  */
3570Sstevel@tonic-gate uint_t
mod_hash_iddata_gen(size_t nchains)3580Sstevel@tonic-gate mod_hash_iddata_gen(size_t nchains)
3590Sstevel@tonic-gate {
3600Sstevel@tonic-gate 	uint_t kval, i, prime;
3610Sstevel@tonic-gate 
3620Sstevel@tonic-gate 	/*
3630Sstevel@tonic-gate 	 * Pick the first (odd) prime greater than nchains.  Make sure kval is
3640Sstevel@tonic-gate 	 * odd (so start with nchains +1 or +2 as appropriate).
3650Sstevel@tonic-gate 	 */
3660Sstevel@tonic-gate 	kval = (nchains % 2 == 0) ? nchains + 1 : nchains + 2;
3670Sstevel@tonic-gate 
3680Sstevel@tonic-gate 	for (;;) {
3690Sstevel@tonic-gate 		prime = 1;
3700Sstevel@tonic-gate 		for (i = 3; i * i <= kval; i += 2) {
3710Sstevel@tonic-gate 			if (kval % i == 0)
3720Sstevel@tonic-gate 				prime = 0;
3730Sstevel@tonic-gate 		}
3740Sstevel@tonic-gate 		if (prime == 1)
3750Sstevel@tonic-gate 			break;
3760Sstevel@tonic-gate 		kval += 2;
3770Sstevel@tonic-gate 	}
3780Sstevel@tonic-gate 	return (kval);
3790Sstevel@tonic-gate }
3800Sstevel@tonic-gate 
3810Sstevel@tonic-gate mod_hash_t *
mod_hash_create_idhash(char * name,size_t nchains,void (* val_dtor)(mod_hash_val_t))3820Sstevel@tonic-gate mod_hash_create_idhash(char *name, size_t nchains,
3830Sstevel@tonic-gate     void (*val_dtor)(mod_hash_val_t))
3840Sstevel@tonic-gate {
3850Sstevel@tonic-gate 	uint_t kval = mod_hash_iddata_gen(nchains);
3860Sstevel@tonic-gate 
3870Sstevel@tonic-gate 	return (mod_hash_create_extended(name, nchains, mod_hash_null_keydtor,
3880Sstevel@tonic-gate 	    val_dtor, mod_hash_byid, (void *)(uintptr_t)kval,
3890Sstevel@tonic-gate 	    mod_hash_idkey_cmp, KM_SLEEP));
3900Sstevel@tonic-gate }
3910Sstevel@tonic-gate 
3920Sstevel@tonic-gate void
mod_hash_destroy_idhash(mod_hash_t * hash)3930Sstevel@tonic-gate mod_hash_destroy_idhash(mod_hash_t *hash)
3940Sstevel@tonic-gate {
3950Sstevel@tonic-gate 	ASSERT(hash);
3960Sstevel@tonic-gate 	mod_hash_destroy_hash(hash);
3970Sstevel@tonic-gate }
3980Sstevel@tonic-gate 
3990Sstevel@tonic-gate /*
4000Sstevel@tonic-gate  * mod_hash_init()
4010Sstevel@tonic-gate  * 	sets up globals, etc for mod_hash_*
4020Sstevel@tonic-gate  */
4030Sstevel@tonic-gate void
mod_hash_init(void)4040Sstevel@tonic-gate mod_hash_init(void)
4050Sstevel@tonic-gate {
4060Sstevel@tonic-gate 	ASSERT(mh_e_cache == NULL);
4070Sstevel@tonic-gate 	mh_e_cache = kmem_cache_create("mod_hash_entries",
4080Sstevel@tonic-gate 	    sizeof (struct mod_hash_entry), 0, NULL, NULL, NULL, NULL,
4090Sstevel@tonic-gate 	    NULL, 0);
4100Sstevel@tonic-gate }
4110Sstevel@tonic-gate 
4120Sstevel@tonic-gate /*
4130Sstevel@tonic-gate  * mod_hash_create_extended()
4140Sstevel@tonic-gate  * 	The full-blown hash creation function.
4150Sstevel@tonic-gate  *
4160Sstevel@tonic-gate  * notes:
4170Sstevel@tonic-gate  * 	nchains		- how many hash slots to create.  More hash slots will
4180Sstevel@tonic-gate  *			  result in shorter hash chains, but will consume
4190Sstevel@tonic-gate  *			  slightly more memory up front.
4200Sstevel@tonic-gate  *	sleep		- should be KM_SLEEP or KM_NOSLEEP, to indicate whether
4210Sstevel@tonic-gate  *			  to sleep for memory, or fail in low-memory conditions.
4220Sstevel@tonic-gate  *
4230Sstevel@tonic-gate  * 	Fails only if KM_NOSLEEP was specified, and no memory was available.
4240Sstevel@tonic-gate  */
4250Sstevel@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)4260Sstevel@tonic-gate mod_hash_create_extended(
4270Sstevel@tonic-gate     char *hname,			/* descriptive name for hash */
4280Sstevel@tonic-gate     size_t nchains,			/* number of hash slots */
4290Sstevel@tonic-gate     void (*kdtor)(mod_hash_key_t),	/* key destructor */
4300Sstevel@tonic-gate     void (*vdtor)(mod_hash_val_t),	/* value destructor */
4310Sstevel@tonic-gate     uint_t (*hash_alg)(void *, mod_hash_key_t), /* hash algorithm */
4320Sstevel@tonic-gate     void *hash_alg_data,		/* pass-thru arg for hash_alg */
4330Sstevel@tonic-gate     int (*keycmp)(mod_hash_key_t, mod_hash_key_t), /* key comparator */
4340Sstevel@tonic-gate     int sleep)				/* whether to sleep for mem */
4350Sstevel@tonic-gate {
4360Sstevel@tonic-gate 	mod_hash_t *mod_hash;
4370Sstevel@tonic-gate 	ASSERT(hname && keycmp && hash_alg && vdtor && kdtor);
4380Sstevel@tonic-gate 
4390Sstevel@tonic-gate 	if ((mod_hash = kmem_zalloc(MH_SIZE(nchains), sleep)) == NULL)
4400Sstevel@tonic-gate 		return (NULL);
4410Sstevel@tonic-gate 
4420Sstevel@tonic-gate 	mod_hash->mh_name = kmem_alloc(strlen(hname) + 1, sleep);
4430Sstevel@tonic-gate 	if (mod_hash->mh_name == NULL) {
4440Sstevel@tonic-gate 		kmem_free(mod_hash, MH_SIZE(nchains));
4450Sstevel@tonic-gate 		return (NULL);
4460Sstevel@tonic-gate 	}
4470Sstevel@tonic-gate 	(void) strcpy(mod_hash->mh_name, hname);
4480Sstevel@tonic-gate 
4490Sstevel@tonic-gate 	mod_hash->mh_sleep = sleep;
4500Sstevel@tonic-gate 	mod_hash->mh_nchains = nchains;
4510Sstevel@tonic-gate 	mod_hash->mh_kdtor = kdtor;
4520Sstevel@tonic-gate 	mod_hash->mh_vdtor = vdtor;
4530Sstevel@tonic-gate 	mod_hash->mh_hashalg = hash_alg;
4540Sstevel@tonic-gate 	mod_hash->mh_hashalg_data = hash_alg_data;
4550Sstevel@tonic-gate 	mod_hash->mh_keycmp = keycmp;
4560Sstevel@tonic-gate 
4570Sstevel@tonic-gate 	/*
4580Sstevel@tonic-gate 	 * Link the hash up on the list of hashes
4590Sstevel@tonic-gate 	 */
4600Sstevel@tonic-gate 	mutex_enter(&mh_head_lock);
4610Sstevel@tonic-gate 	mod_hash->mh_next = mh_head;
4620Sstevel@tonic-gate 	mh_head = mod_hash;
4630Sstevel@tonic-gate 	mutex_exit(&mh_head_lock);
4640Sstevel@tonic-gate 
4650Sstevel@tonic-gate 	return (mod_hash);
4660Sstevel@tonic-gate }
4670Sstevel@tonic-gate 
4680Sstevel@tonic-gate /*
4690Sstevel@tonic-gate  * mod_hash_destroy_hash()
4700Sstevel@tonic-gate  * 	destroy a hash table, destroying all of its stored keys and values
4710Sstevel@tonic-gate  * 	as well.
4720Sstevel@tonic-gate  */
4730Sstevel@tonic-gate void
mod_hash_destroy_hash(mod_hash_t * hash)4740Sstevel@tonic-gate mod_hash_destroy_hash(mod_hash_t *hash)
4750Sstevel@tonic-gate {
4760Sstevel@tonic-gate 	mod_hash_t *mhp, *mhpp;
4770Sstevel@tonic-gate 
4780Sstevel@tonic-gate 	mutex_enter(&mh_head_lock);
4790Sstevel@tonic-gate 	/*
4800Sstevel@tonic-gate 	 * Remove the hash from the hash list
4810Sstevel@tonic-gate 	 */
4820Sstevel@tonic-gate 	if (hash == mh_head) {		/* removing 1st list elem */
4830Sstevel@tonic-gate 		mh_head = mh_head->mh_next;
4840Sstevel@tonic-gate 	} else {
4850Sstevel@tonic-gate 		/*
4860Sstevel@tonic-gate 		 * mhpp can start out NULL since we know the 1st elem isn't the
4870Sstevel@tonic-gate 		 * droid we're looking for.
4880Sstevel@tonic-gate 		 */
4890Sstevel@tonic-gate 		mhpp = NULL;
4900Sstevel@tonic-gate 		for (mhp = mh_head; mhp != NULL; mhp = mhp->mh_next) {
4910Sstevel@tonic-gate 			if (mhp == hash) {
4920Sstevel@tonic-gate 				mhpp->mh_next = mhp->mh_next;
4930Sstevel@tonic-gate 				break;
4940Sstevel@tonic-gate 			}
4950Sstevel@tonic-gate 			mhpp = mhp;
4960Sstevel@tonic-gate 		}
4970Sstevel@tonic-gate 	}
4980Sstevel@tonic-gate 	mutex_exit(&mh_head_lock);
4990Sstevel@tonic-gate 
5000Sstevel@tonic-gate 	/*
5010Sstevel@tonic-gate 	 * Clean out keys and values.
5020Sstevel@tonic-gate 	 */
5030Sstevel@tonic-gate 	mod_hash_clear(hash);
5040Sstevel@tonic-gate 
5050Sstevel@tonic-gate 	kmem_free(hash->mh_name, strlen(hash->mh_name) + 1);
5060Sstevel@tonic-gate 	kmem_free(hash, MH_SIZE(hash->mh_nchains));
5070Sstevel@tonic-gate }
5080Sstevel@tonic-gate 
5090Sstevel@tonic-gate /*
5100Sstevel@tonic-gate  * i_mod_hash()
5110Sstevel@tonic-gate  * 	Call the hashing algorithm for this hash table, with the given key.
5120Sstevel@tonic-gate  */
5133247Sgjelinek uint_t
i_mod_hash(mod_hash_t * hash,mod_hash_key_t key)5140Sstevel@tonic-gate i_mod_hash(mod_hash_t *hash, mod_hash_key_t key)
5150Sstevel@tonic-gate {
5160Sstevel@tonic-gate 	uint_t h;
5170Sstevel@tonic-gate 	/*
5180Sstevel@tonic-gate 	 * Prevent div by 0 problems;
5190Sstevel@tonic-gate 	 * Also a nice shortcut when using a hash as a list
5200Sstevel@tonic-gate 	 */
5210Sstevel@tonic-gate 	if (hash->mh_nchains == 1)
5220Sstevel@tonic-gate 		return (0);
5230Sstevel@tonic-gate 
5240Sstevel@tonic-gate 	h = (hash->mh_hashalg)(hash->mh_hashalg_data, key);
5250Sstevel@tonic-gate 	return (h % (hash->mh_nchains - 1));
5260Sstevel@tonic-gate }
5270Sstevel@tonic-gate 
5280Sstevel@tonic-gate /*
5290Sstevel@tonic-gate  * i_mod_hash_insert_nosync()
5300Sstevel@tonic-gate  * mod_hash_insert()
5310Sstevel@tonic-gate  * mod_hash_insert_reserve()
5320Sstevel@tonic-gate  * 	insert 'val' into the hash table, using 'key' as its key.  If 'key' is
5330Sstevel@tonic-gate  * 	already a key in the hash, an error will be returned, and the key-val
5340Sstevel@tonic-gate  * 	pair will not be inserted.  i_mod_hash_insert_nosync() supports a simple
5350Sstevel@tonic-gate  * 	handle abstraction, allowing hash entry allocation to be separated from
5360Sstevel@tonic-gate  * 	the hash insertion.  this abstraction allows simple use of the mod_hash
5370Sstevel@tonic-gate  * 	structure in situations where mod_hash_insert() with a KM_SLEEP
5380Sstevel@tonic-gate  * 	allocation policy would otherwise be unsafe.
5390Sstevel@tonic-gate  */
5400Sstevel@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)5410Sstevel@tonic-gate i_mod_hash_insert_nosync(mod_hash_t *hash, mod_hash_key_t key,
5420Sstevel@tonic-gate     mod_hash_val_t val, mod_hash_hndl_t handle)
5430Sstevel@tonic-gate {
5440Sstevel@tonic-gate 	uint_t hashidx;
5450Sstevel@tonic-gate 	struct mod_hash_entry *entry;
5460Sstevel@tonic-gate 
5470Sstevel@tonic-gate 	ASSERT(hash);
5480Sstevel@tonic-gate 
5490Sstevel@tonic-gate 	/*
5500Sstevel@tonic-gate 	 * If we've not been given reserved storage, allocate storage directly,
5510Sstevel@tonic-gate 	 * using the hash's allocation policy.
5520Sstevel@tonic-gate 	 */
5530Sstevel@tonic-gate 	if (handle == (mod_hash_hndl_t)0) {
5540Sstevel@tonic-gate 		entry = kmem_cache_alloc(mh_e_cache, hash->mh_sleep);
5550Sstevel@tonic-gate 		if (entry == NULL) {
5560Sstevel@tonic-gate 			hash->mh_stat.mhs_nomem++;
5570Sstevel@tonic-gate 			return (MH_ERR_NOMEM);
5580Sstevel@tonic-gate 		}
5590Sstevel@tonic-gate 	} else {
5600Sstevel@tonic-gate 		entry = (struct mod_hash_entry *)handle;
5610Sstevel@tonic-gate 	}
5620Sstevel@tonic-gate 
5630Sstevel@tonic-gate 	hashidx = i_mod_hash(hash, key);
5640Sstevel@tonic-gate 	entry->mhe_key = key;
5650Sstevel@tonic-gate 	entry->mhe_val = val;
5660Sstevel@tonic-gate 	entry->mhe_next = hash->mh_entries[hashidx];
5670Sstevel@tonic-gate 
5680Sstevel@tonic-gate 	hash->mh_entries[hashidx] = entry;
5690Sstevel@tonic-gate 	hash->mh_stat.mhs_nelems++;
5700Sstevel@tonic-gate 
5710Sstevel@tonic-gate 	return (0);
5720Sstevel@tonic-gate }
5730Sstevel@tonic-gate 
5740Sstevel@tonic-gate int
mod_hash_insert(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t val)5750Sstevel@tonic-gate mod_hash_insert(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t val)
5760Sstevel@tonic-gate {
5770Sstevel@tonic-gate 	int res;
5780Sstevel@tonic-gate 	mod_hash_val_t v;
5790Sstevel@tonic-gate 
5800Sstevel@tonic-gate 	rw_enter(&hash->mh_contents, RW_WRITER);
5810Sstevel@tonic-gate 
5820Sstevel@tonic-gate 	/*
5830Sstevel@tonic-gate 	 * Disallow duplicate keys in the hash
5840Sstevel@tonic-gate 	 */
5850Sstevel@tonic-gate 	if (i_mod_hash_find_nosync(hash, key, &v) == 0) {
5860Sstevel@tonic-gate 		rw_exit(&hash->mh_contents);
5870Sstevel@tonic-gate 		hash->mh_stat.mhs_coll++;
5880Sstevel@tonic-gate 		return (MH_ERR_DUPLICATE);
5890Sstevel@tonic-gate 	}
5900Sstevel@tonic-gate 
5910Sstevel@tonic-gate 	res = i_mod_hash_insert_nosync(hash, key, val, (mod_hash_hndl_t)0);
5920Sstevel@tonic-gate 	rw_exit(&hash->mh_contents);
5930Sstevel@tonic-gate 
5940Sstevel@tonic-gate 	return (res);
5950Sstevel@tonic-gate }
5960Sstevel@tonic-gate 
5970Sstevel@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)5980Sstevel@tonic-gate mod_hash_insert_reserve(mod_hash_t *hash, mod_hash_key_t key,
5990Sstevel@tonic-gate     mod_hash_val_t val, mod_hash_hndl_t handle)
6000Sstevel@tonic-gate {
6010Sstevel@tonic-gate 	int res;
6020Sstevel@tonic-gate 	mod_hash_val_t v;
6030Sstevel@tonic-gate 
6040Sstevel@tonic-gate 	rw_enter(&hash->mh_contents, RW_WRITER);
6050Sstevel@tonic-gate 
6060Sstevel@tonic-gate 	/*
6070Sstevel@tonic-gate 	 * Disallow duplicate keys in the hash
6080Sstevel@tonic-gate 	 */
6090Sstevel@tonic-gate 	if (i_mod_hash_find_nosync(hash, key, &v) == 0) {
6100Sstevel@tonic-gate 		rw_exit(&hash->mh_contents);
6110Sstevel@tonic-gate 		hash->mh_stat.mhs_coll++;
6120Sstevel@tonic-gate 		return (MH_ERR_DUPLICATE);
6130Sstevel@tonic-gate 	}
6140Sstevel@tonic-gate 	res = i_mod_hash_insert_nosync(hash, key, val, handle);
6150Sstevel@tonic-gate 	rw_exit(&hash->mh_contents);
6160Sstevel@tonic-gate 
6170Sstevel@tonic-gate 	return (res);
6180Sstevel@tonic-gate }
6190Sstevel@tonic-gate 
6200Sstevel@tonic-gate /*
6210Sstevel@tonic-gate  * mod_hash_reserve()
6220Sstevel@tonic-gate  * mod_hash_reserve_nosleep()
6230Sstevel@tonic-gate  * mod_hash_cancel()
6240Sstevel@tonic-gate  *   Make or cancel a mod_hash_entry_t reservation.  Reservations are used in
6250Sstevel@tonic-gate  *   mod_hash_insert_reserve() above.
6260Sstevel@tonic-gate  */
6270Sstevel@tonic-gate int
mod_hash_reserve(mod_hash_t * hash,mod_hash_hndl_t * handlep)6280Sstevel@tonic-gate mod_hash_reserve(mod_hash_t *hash, mod_hash_hndl_t *handlep)
6290Sstevel@tonic-gate {
6300Sstevel@tonic-gate 	*handlep = kmem_cache_alloc(mh_e_cache, hash->mh_sleep);
6310Sstevel@tonic-gate 	if (*handlep == NULL) {
6320Sstevel@tonic-gate 		hash->mh_stat.mhs_nomem++;
6330Sstevel@tonic-gate 		return (MH_ERR_NOMEM);
6340Sstevel@tonic-gate 	}
6350Sstevel@tonic-gate 
6360Sstevel@tonic-gate 	return (0);
6370Sstevel@tonic-gate }
6380Sstevel@tonic-gate 
6390Sstevel@tonic-gate int
mod_hash_reserve_nosleep(mod_hash_t * hash,mod_hash_hndl_t * handlep)6400Sstevel@tonic-gate mod_hash_reserve_nosleep(mod_hash_t *hash, mod_hash_hndl_t *handlep)
6410Sstevel@tonic-gate {
6420Sstevel@tonic-gate 	*handlep = kmem_cache_alloc(mh_e_cache, KM_NOSLEEP);
6430Sstevel@tonic-gate 	if (*handlep == NULL) {
6440Sstevel@tonic-gate 		hash->mh_stat.mhs_nomem++;
6450Sstevel@tonic-gate 		return (MH_ERR_NOMEM);
6460Sstevel@tonic-gate 	}
6470Sstevel@tonic-gate 
6480Sstevel@tonic-gate 	return (0);
6490Sstevel@tonic-gate 
6500Sstevel@tonic-gate }
6510Sstevel@tonic-gate 
6520Sstevel@tonic-gate /*ARGSUSED*/
6530Sstevel@tonic-gate void
mod_hash_cancel(mod_hash_t * hash,mod_hash_hndl_t * handlep)6540Sstevel@tonic-gate mod_hash_cancel(mod_hash_t *hash, mod_hash_hndl_t *handlep)
6550Sstevel@tonic-gate {
6560Sstevel@tonic-gate 	kmem_cache_free(mh_e_cache, *handlep);
6570Sstevel@tonic-gate 	*handlep = (mod_hash_hndl_t)0;
6580Sstevel@tonic-gate }
6590Sstevel@tonic-gate 
6600Sstevel@tonic-gate /*
6610Sstevel@tonic-gate  * i_mod_hash_remove_nosync()
6620Sstevel@tonic-gate  * mod_hash_remove()
6630Sstevel@tonic-gate  * 	Remove an element from the hash table.
6640Sstevel@tonic-gate  */
6650Sstevel@tonic-gate int
i_mod_hash_remove_nosync(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t * val)6660Sstevel@tonic-gate i_mod_hash_remove_nosync(mod_hash_t *hash, mod_hash_key_t key,
6670Sstevel@tonic-gate     mod_hash_val_t *val)
6680Sstevel@tonic-gate {
6690Sstevel@tonic-gate 	int hashidx;
6700Sstevel@tonic-gate 	struct mod_hash_entry *e, *ep;
6710Sstevel@tonic-gate 
6720Sstevel@tonic-gate 	hashidx = i_mod_hash(hash, key);
6730Sstevel@tonic-gate 	ep = NULL; /* e's parent */
6740Sstevel@tonic-gate 
6750Sstevel@tonic-gate 	for (e = hash->mh_entries[hashidx]; e != NULL; e = e->mhe_next) {
6760Sstevel@tonic-gate 		if (MH_KEYCMP(hash, e->mhe_key, key) == 0)
6770Sstevel@tonic-gate 			break;
6780Sstevel@tonic-gate 		ep = e;
6790Sstevel@tonic-gate 	}
6800Sstevel@tonic-gate 
6810Sstevel@tonic-gate 	if (e == NULL) {	/* not found */
6820Sstevel@tonic-gate 		return (MH_ERR_NOTFOUND);
6830Sstevel@tonic-gate 	}
6840Sstevel@tonic-gate 
6850Sstevel@tonic-gate 	if (ep == NULL) 	/* special case 1st element in bucket */
6860Sstevel@tonic-gate 		hash->mh_entries[hashidx] = e->mhe_next;
6870Sstevel@tonic-gate 	else
6880Sstevel@tonic-gate 		ep->mhe_next = e->mhe_next;
6890Sstevel@tonic-gate 
6900Sstevel@tonic-gate 	/*
6910Sstevel@tonic-gate 	 * Clean up resources used by the node's key.
6920Sstevel@tonic-gate 	 */
6930Sstevel@tonic-gate 	MH_KEY_DESTROY(hash, e->mhe_key);
6940Sstevel@tonic-gate 
6950Sstevel@tonic-gate 	*val = e->mhe_val;
6960Sstevel@tonic-gate 	kmem_cache_free(mh_e_cache, e);
6970Sstevel@tonic-gate 	hash->mh_stat.mhs_nelems--;
6980Sstevel@tonic-gate 
6990Sstevel@tonic-gate 	return (0);
7000Sstevel@tonic-gate }
7010Sstevel@tonic-gate 
7020Sstevel@tonic-gate int
mod_hash_remove(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t * val)7030Sstevel@tonic-gate mod_hash_remove(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val)
7040Sstevel@tonic-gate {
7050Sstevel@tonic-gate 	int res;
7060Sstevel@tonic-gate 
7070Sstevel@tonic-gate 	rw_enter(&hash->mh_contents, RW_WRITER);
7080Sstevel@tonic-gate 	res = i_mod_hash_remove_nosync(hash, key, val);
7090Sstevel@tonic-gate 	rw_exit(&hash->mh_contents);
7100Sstevel@tonic-gate 
7110Sstevel@tonic-gate 	return (res);
7120Sstevel@tonic-gate }
7130Sstevel@tonic-gate 
7140Sstevel@tonic-gate /*
7150Sstevel@tonic-gate  * mod_hash_replace()
7160Sstevel@tonic-gate  * 	atomically remove an existing key-value pair from a hash, and replace
7170Sstevel@tonic-gate  * 	the key and value with the ones supplied.  The removed key and value
7180Sstevel@tonic-gate  * 	(if any) are destroyed.
7190Sstevel@tonic-gate  */
7200Sstevel@tonic-gate int
mod_hash_replace(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t val)7210Sstevel@tonic-gate mod_hash_replace(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t val)
7220Sstevel@tonic-gate {
7230Sstevel@tonic-gate 	int res;
7240Sstevel@tonic-gate 	mod_hash_val_t v;
7250Sstevel@tonic-gate 
7260Sstevel@tonic-gate 	rw_enter(&hash->mh_contents, RW_WRITER);
7270Sstevel@tonic-gate 
7280Sstevel@tonic-gate 	if (i_mod_hash_remove_nosync(hash, key, &v) == 0) {
7290Sstevel@tonic-gate 		/*
7300Sstevel@tonic-gate 		 * mod_hash_remove() takes care of freeing up the key resources.
7310Sstevel@tonic-gate 		 */
7320Sstevel@tonic-gate 		MH_VAL_DESTROY(hash, v);
7330Sstevel@tonic-gate 	}
7340Sstevel@tonic-gate 	res = i_mod_hash_insert_nosync(hash, key, val, (mod_hash_hndl_t)0);
7350Sstevel@tonic-gate 
7360Sstevel@tonic-gate 	rw_exit(&hash->mh_contents);
7370Sstevel@tonic-gate 
7380Sstevel@tonic-gate 	return (res);
7390Sstevel@tonic-gate }
7400Sstevel@tonic-gate 
7410Sstevel@tonic-gate /*
7420Sstevel@tonic-gate  * mod_hash_destroy()
7430Sstevel@tonic-gate  * 	Remove an element from the hash table matching 'key', and destroy it.
7440Sstevel@tonic-gate  */
7450Sstevel@tonic-gate int
mod_hash_destroy(mod_hash_t * hash,mod_hash_key_t key)7460Sstevel@tonic-gate mod_hash_destroy(mod_hash_t *hash, mod_hash_key_t key)
7470Sstevel@tonic-gate {
7480Sstevel@tonic-gate 	mod_hash_val_t val;
7490Sstevel@tonic-gate 	int rv;
7500Sstevel@tonic-gate 
7510Sstevel@tonic-gate 	rw_enter(&hash->mh_contents, RW_WRITER);
7520Sstevel@tonic-gate 
7530Sstevel@tonic-gate 	if ((rv = i_mod_hash_remove_nosync(hash, key, &val)) == 0) {
7540Sstevel@tonic-gate 		/*
7550Sstevel@tonic-gate 		 * mod_hash_remove() takes care of freeing up the key resources.
7560Sstevel@tonic-gate 		 */
7570Sstevel@tonic-gate 		MH_VAL_DESTROY(hash, val);
7580Sstevel@tonic-gate 	}
7590Sstevel@tonic-gate 
7600Sstevel@tonic-gate 	rw_exit(&hash->mh_contents);
7610Sstevel@tonic-gate 	return (rv);
7620Sstevel@tonic-gate }
7630Sstevel@tonic-gate 
7640Sstevel@tonic-gate /*
7650Sstevel@tonic-gate  * i_mod_hash_find_nosync()
7660Sstevel@tonic-gate  * mod_hash_find()
7670Sstevel@tonic-gate  * 	Find a value in the hash table corresponding to the given key.
7680Sstevel@tonic-gate  */
7693247Sgjelinek int
i_mod_hash_find_nosync(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t * val)7700Sstevel@tonic-gate i_mod_hash_find_nosync(mod_hash_t *hash, mod_hash_key_t key,
7710Sstevel@tonic-gate     mod_hash_val_t *val)
7720Sstevel@tonic-gate {
7730Sstevel@tonic-gate 	uint_t hashidx;
7740Sstevel@tonic-gate 	struct mod_hash_entry *e;
7750Sstevel@tonic-gate 
7760Sstevel@tonic-gate 	hashidx = i_mod_hash(hash, key);
7770Sstevel@tonic-gate 
7780Sstevel@tonic-gate 	for (e = hash->mh_entries[hashidx]; e != NULL; e = e->mhe_next) {
7790Sstevel@tonic-gate 		if (MH_KEYCMP(hash, e->mhe_key, key) == 0) {
7800Sstevel@tonic-gate 			*val = e->mhe_val;
7810Sstevel@tonic-gate 			hash->mh_stat.mhs_hit++;
7820Sstevel@tonic-gate 			return (0);
7830Sstevel@tonic-gate 		}
7840Sstevel@tonic-gate 	}
7850Sstevel@tonic-gate 	hash->mh_stat.mhs_miss++;
7860Sstevel@tonic-gate 	return (MH_ERR_NOTFOUND);
7870Sstevel@tonic-gate }
7880Sstevel@tonic-gate 
7890Sstevel@tonic-gate int
mod_hash_find(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t * val)7900Sstevel@tonic-gate mod_hash_find(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val)
7910Sstevel@tonic-gate {
7920Sstevel@tonic-gate 	int res;
7930Sstevel@tonic-gate 
7940Sstevel@tonic-gate 	rw_enter(&hash->mh_contents, RW_READER);
7950Sstevel@tonic-gate 	res = i_mod_hash_find_nosync(hash, key, val);
7960Sstevel@tonic-gate 	rw_exit(&hash->mh_contents);
7970Sstevel@tonic-gate 
7980Sstevel@tonic-gate 	return (res);
7990Sstevel@tonic-gate }
8000Sstevel@tonic-gate 
8010Sstevel@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))8020Sstevel@tonic-gate mod_hash_find_cb(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val,
8030Sstevel@tonic-gate     void (*find_cb)(mod_hash_key_t, mod_hash_val_t))
8040Sstevel@tonic-gate {
8050Sstevel@tonic-gate 	int res;
8060Sstevel@tonic-gate 
8070Sstevel@tonic-gate 	rw_enter(&hash->mh_contents, RW_READER);
8080Sstevel@tonic-gate 	res = i_mod_hash_find_nosync(hash, key, val);
8090Sstevel@tonic-gate 	if (res == 0) {
8100Sstevel@tonic-gate 		find_cb(key, *val);
8110Sstevel@tonic-gate 	}
8120Sstevel@tonic-gate 	rw_exit(&hash->mh_contents);
8130Sstevel@tonic-gate 
8140Sstevel@tonic-gate 	return (res);
8150Sstevel@tonic-gate }
8160Sstevel@tonic-gate 
817*8275SEric 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)818*8275SEric Cheng mod_hash_find_cb_rval(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val,
819*8275SEric Cheng     int (*find_cb)(mod_hash_key_t, mod_hash_val_t), int *cb_rval)
820*8275SEric Cheng {
821*8275SEric Cheng 	int res;
822*8275SEric Cheng 
823*8275SEric Cheng 	rw_enter(&hash->mh_contents, RW_READER);
824*8275SEric Cheng 	res = i_mod_hash_find_nosync(hash, key, val);
825*8275SEric Cheng 	if (res == 0) {
826*8275SEric Cheng 		*cb_rval = find_cb(key, *val);
827*8275SEric Cheng 	}
828*8275SEric Cheng 	rw_exit(&hash->mh_contents);
829*8275SEric Cheng 
830*8275SEric Cheng 	return (res);
831*8275SEric Cheng }
832*8275SEric Cheng 
8333247Sgjelinek void
i_mod_hash_walk_nosync(mod_hash_t * hash,uint_t (* callback)(mod_hash_key_t,mod_hash_val_t *,void *),void * arg)8340Sstevel@tonic-gate i_mod_hash_walk_nosync(mod_hash_t *hash,
8350Sstevel@tonic-gate     uint_t (*callback)(mod_hash_key_t, mod_hash_val_t *, void *), void *arg)
8360Sstevel@tonic-gate {
8370Sstevel@tonic-gate 	struct mod_hash_entry	*e;
8380Sstevel@tonic-gate 	uint_t			hashidx;
8390Sstevel@tonic-gate 	int			res = MH_WALK_CONTINUE;
8400Sstevel@tonic-gate 
8410Sstevel@tonic-gate 	for (hashidx = 0;
8420Sstevel@tonic-gate 	    (hashidx < (hash->mh_nchains - 1)) && (res == MH_WALK_CONTINUE);
8430Sstevel@tonic-gate 	    hashidx++) {
8440Sstevel@tonic-gate 		e = hash->mh_entries[hashidx];
8450Sstevel@tonic-gate 		while ((e != NULL) && (res == MH_WALK_CONTINUE)) {
8460Sstevel@tonic-gate 			res = callback(e->mhe_key, e->mhe_val, arg);
8470Sstevel@tonic-gate 			e = e->mhe_next;
8480Sstevel@tonic-gate 		}
8490Sstevel@tonic-gate 	}
8500Sstevel@tonic-gate }
8510Sstevel@tonic-gate 
8520Sstevel@tonic-gate /*
8530Sstevel@tonic-gate  * mod_hash_walk()
8540Sstevel@tonic-gate  * 	Walks all the elements in the hashtable and invokes the callback
8550Sstevel@tonic-gate  * 	function with the key/value pair for each element.  The hashtable
8560Sstevel@tonic-gate  * 	is locked for readers so the callback function should not attempt
8570Sstevel@tonic-gate  * 	to do any updates to the hashable.  The callback function should
8580Sstevel@tonic-gate  * 	return MH_WALK_CONTINUE to continue walking the hashtable or
8590Sstevel@tonic-gate  * 	MH_WALK_TERMINATE to abort the walk of the hashtable.
8600Sstevel@tonic-gate  */
8610Sstevel@tonic-gate void
mod_hash_walk(mod_hash_t * hash,uint_t (* callback)(mod_hash_key_t,mod_hash_val_t *,void *),void * arg)8620Sstevel@tonic-gate mod_hash_walk(mod_hash_t *hash,
8630Sstevel@tonic-gate     uint_t (*callback)(mod_hash_key_t, mod_hash_val_t *, void *), void *arg)
8640Sstevel@tonic-gate {
8650Sstevel@tonic-gate 	rw_enter(&hash->mh_contents, RW_READER);
8660Sstevel@tonic-gate 	i_mod_hash_walk_nosync(hash, callback, arg);
8670Sstevel@tonic-gate 	rw_exit(&hash->mh_contents);
8680Sstevel@tonic-gate }
8690Sstevel@tonic-gate 
8700Sstevel@tonic-gate 
8710Sstevel@tonic-gate /*
8720Sstevel@tonic-gate  * i_mod_hash_clear_nosync()
8730Sstevel@tonic-gate  * mod_hash_clear()
8740Sstevel@tonic-gate  *	Clears the given hash table by calling the destructor of every hash
8750Sstevel@tonic-gate  *	element and freeing up all mod_hash_entry's.
8760Sstevel@tonic-gate  */
8773247Sgjelinek void
i_mod_hash_clear_nosync(mod_hash_t * hash)8780Sstevel@tonic-gate i_mod_hash_clear_nosync(mod_hash_t *hash)
8790Sstevel@tonic-gate {
8800Sstevel@tonic-gate 	int i;
8810Sstevel@tonic-gate 	struct mod_hash_entry *e, *old_e;
8820Sstevel@tonic-gate 
8830Sstevel@tonic-gate 	for (i = 0; i < hash->mh_nchains; i++) {
8840Sstevel@tonic-gate 		e = hash->mh_entries[i];
8850Sstevel@tonic-gate 		while (e != NULL) {
8860Sstevel@tonic-gate 			MH_KEY_DESTROY(hash, e->mhe_key);
8870Sstevel@tonic-gate 			MH_VAL_DESTROY(hash, e->mhe_val);
8880Sstevel@tonic-gate 			old_e = e;
8890Sstevel@tonic-gate 			e = e->mhe_next;
8900Sstevel@tonic-gate 			kmem_cache_free(mh_e_cache, old_e);
8910Sstevel@tonic-gate 		}
8920Sstevel@tonic-gate 		hash->mh_entries[i] = NULL;
8930Sstevel@tonic-gate 	}
8940Sstevel@tonic-gate 	hash->mh_stat.mhs_nelems = 0;
8950Sstevel@tonic-gate }
8960Sstevel@tonic-gate 
8970Sstevel@tonic-gate void
mod_hash_clear(mod_hash_t * hash)8980Sstevel@tonic-gate mod_hash_clear(mod_hash_t *hash)
8990Sstevel@tonic-gate {
9000Sstevel@tonic-gate 	ASSERT(hash);
9010Sstevel@tonic-gate 	rw_enter(&hash->mh_contents, RW_WRITER);
9020Sstevel@tonic-gate 	i_mod_hash_clear_nosync(hash);
9030Sstevel@tonic-gate 	rw_exit(&hash->mh_contents);
9040Sstevel@tonic-gate }
905