common/os/modhash.c

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#pragma ident	"@(#)modhash.c	1.14	08/02/06 SMI"

/*
 * mod_hash: flexible hash table implementation.
 *
 * This is a reasonably fast, reasonably flexible hash table implementation
 * which features pluggable hash algorithms to support storing arbitrary keys
 * and values.  It is designed to handle small (< 100,000 items) amounts of
 * data.  The hash uses chaining to resolve collisions, and does not feature a
 * mechanism to grow the hash.  Care must be taken to pick nchains to be large
 * enough for the application at hand, or lots of time will be wasted searching
 * hash chains.
 *
 * The client of the hash is required to supply a number of items to support
 * the various hash functions:
 *
 * 	- Destructor functions for the key and value being hashed.
 *	  A destructor is responsible for freeing an object when the hash
 *	  table is no longer storing it.  Since keys and values can be of
 *	  arbitrary type, separate destructors for keys & values are used.
 *	  These may be mod_hash_null_keydtor and mod_hash_null_valdtor if no
 *	  destructor is needed for either a key or value.
 *
 *	- A hashing algorithm which returns a uint_t representing a hash index
 *	  The number returned need _not_ be between 0 and nchains.  The mod_hash
 *	  code will take care of doing that.  The second argument (after the
 *	  key) to the hashing function is a void * that represents
 *	  hash_alg_data-- this is provided so that the hashing algrorithm can
 *	  maintain some state across calls, or keep algorithm-specific
 *	  constants associated with the hash table.
 *
 *	  A pointer-hashing and a string-hashing algorithm are supplied in
 *	  this file.
 *
 *	- A key comparator (a la qsort).
 *	  This is used when searching the hash chain.  The key comparator
 *	  determines if two keys match.  It should follow the return value
 *	  semantics of strcmp.
 *
 *	  string and pointer comparators are supplied in this file.
 *
 * mod_hash_create_strhash() and mod_hash_create_ptrhash() provide good
 * examples of how to create a customized hash table.
 *
 * Basic hash operations:
 *
 *   mod_hash_create_strhash(name, nchains, dtor),
 *	create a hash using strings as keys.
 *	NOTE: This create a hash which automatically cleans up the string
 *	      values it is given for keys.
 *
 *   mod_hash_create_ptrhash(name, nchains, dtor, key_elem_size):
 *	create a hash using pointers as keys.
 *
 *   mod_hash_create_extended(name, nchains, kdtor, vdtor,
 *			      hash_alg, hash_alg_data,
 *			      keycmp, sleep)
 *	create a customized hash table.
 *
 *   mod_hash_destroy_hash(hash):
 *	destroy the given hash table, calling the key and value destructors
 *	on each key-value pair stored in the hash.
 *
 *   mod_hash_insert(hash, key, val):
 *	place a key, value pair into the given hash.
 *	duplicate keys are rejected.
 *
 *   mod_hash_insert_reserve(hash, key, val, handle):
 *	place a key, value pair into the given hash, using handle to indicate
 *	the reserved storage for the pair.  (no memory allocation is needed
 *	during a mod_hash_insert_reserve.)  duplicate keys are rejected.
 *
 *   mod_hash_reserve(hash, *handle):
 *      reserve storage for a key-value pair using the memory allocation
 *      policy of 'hash', returning the storage handle in 'handle'.
 *
 *   mod_hash_reserve_nosleep(hash, *handle): reserve storage for a key-value
 *	pair ignoring the memory allocation policy of 'hash' and always without
 *	sleep, returning the storage handle in 'handle'.
 *
 *   mod_hash_remove(hash, key, *val):
 *	remove a key-value pair with key 'key' from 'hash', destroying the
 *	stored key, and returning the value in val.
 *
 *   mod_hash_replace(hash, key, val)
 * 	atomically remove an existing key-value pair from a hash, and replace
 * 	the key and value with the ones supplied.  The removed key and value
 * 	(if any) are destroyed.
 *
 *   mod_hash_destroy(hash, key):
 *	remove a key-value pair with key 'key' from 'hash', destroying both
 *	stored key and stored value.
 *
 *   mod_hash_find(hash, key, val):
 *	find a value in the hash table corresponding to the given key.
 *
 *   mod_hash_find_cb(hash, key, val, found_callback)
 *	find a value in the hash table corresponding to the given key.
 *	If a value is found, call specified callback passing key and val to it.
 *      The callback is called with the hash lock held.
 *	It is intended to be used in situations where the act of locating the
 *	data must also modify it - such as in reference counting schemes.
 *
 *   mod_hash_walk(hash, callback(key, elem, arg), arg)
 * 	walks all the elements in the hashtable and invokes the callback
 * 	function with the key/value pair for each element.  the hashtable
 * 	is locked for readers so the callback function should not attempt
 * 	to do any updates to the hashable.  the callback function should
 * 	return MH_WALK_CONTINUE to continue walking the hashtable or
 * 	MH_WALK_TERMINATE to abort the walk of the hashtable.
 *
 *   mod_hash_clear(hash):
 *	clears the given hash table of entries, calling the key and value
 *	destructors for every element in the hash.
 */

#include <sys/bitmap.h>
#include <sys/debug.h>
#include <sys/kmem.h>
#include <sys/sunddi.h>

#include <sys/modhash_impl.h>

/*
 * MH_KEY_DESTROY()
 * 	Invoke the key destructor.
 */
#define	MH_KEY_DESTROY(hash, key) ((hash->mh_kdtor)(key))

/*
 * MH_VAL_DESTROY()
 * 	Invoke the value destructor.
 */
#define	MH_VAL_DESTROY(hash, val) ((hash->mh_vdtor)(val))

/*
 * MH_KEYCMP()
 * 	Call the key comparator for the given hash keys.
 */
#define	MH_KEYCMP(hash, key1, key2) ((hash->mh_keycmp)(key1, key2))

/*
 * Cache for struct mod_hash_entry
 */
kmem_cache_t *mh_e_cache = NULL;
mod_hash_t *mh_head = NULL;
kmutex_t mh_head_lock;

/*
 * mod_hash_null_keydtor()
 * mod_hash_null_valdtor()
 * 	no-op key and value destructors.
 */
/*ARGSUSED*/
void
mod_hash_null_keydtor(mod_hash_key_t key)
{
}

/*ARGSUSED*/
void
mod_hash_null_valdtor(mod_hash_val_t val)
{
}

/*
 * mod_hash_bystr()
 * mod_hash_strkey_cmp()
 * mod_hash_strkey_dtor()
 * mod_hash_strval_dtor()
 *	Hash and key comparison routines for hashes with string keys.
 *
 * mod_hash_create_strhash()
 * 	Create a hash using strings as keys
 *
 *	The string hashing algorithm is from the "Dragon Book" --
 *	"Compilers: Principles, Tools & Techniques", by Aho, Sethi, Ullman
 */

/*ARGSUSED*/
uint_t
mod_hash_bystr(void *hash_data, mod_hash_key_t key)
{
	uint_t hash = 0;
	uint_t g;
	char *p, *k = (char *)key;

	ASSERT(k);
	for (p = k; *p != '\0'; p++) {
		hash = (hash << 4) + *p;
		if ((g = (hash & 0xf0000000)) != 0) {
			hash ^= (g >> 24);
			hash ^= g;
		}
	}
	return (hash);
}

int
mod_hash_strkey_cmp(mod_hash_key_t key1, mod_hash_key_t key2)
{
	return (strcmp((char *)key1, (char *)key2));
}

void
mod_hash_strkey_dtor(mod_hash_key_t key)
{
	char *c = (char *)key;
	kmem_free(c, strlen(c) + 1);
}

void
mod_hash_strval_dtor(mod_hash_val_t val)
{
	char *c = (char *)val;
	kmem_free(c, strlen(c) + 1);
}

mod_hash_t *
mod_hash_create_strhash(char *name, size_t nchains,
    void (*val_dtor)(mod_hash_val_t))
{
	return mod_hash_create_extended(name, nchains, mod_hash_strkey_dtor,
	    val_dtor, mod_hash_bystr, NULL, mod_hash_strkey_cmp, KM_SLEEP);
}

void
mod_hash_destroy_strhash(mod_hash_t *strhash)
{
	ASSERT(strhash);
	mod_hash_destroy_hash(strhash);
}


/*
 * mod_hash_byptr()
 * mod_hash_ptrkey_cmp()
 *	Hash and key comparison routines for hashes with pointer keys.
 *
 * mod_hash_create_ptrhash()
 * mod_hash_destroy_ptrhash()
 * 	Create a hash that uses pointers as keys.  This hash algorithm
 * 	picks an appropriate set of middle bits in the address to hash on
 * 	based on the size of the hash table and a hint about the size of
 * 	the items pointed at.
 */
uint_t
mod_hash_byptr(void *hash_data, mod_hash_key_t key)
{
	uintptr_t k = (uintptr_t)key;
	k >>= (int)(uintptr_t)hash_data;

	return ((uint_t)k);
}

int
mod_hash_ptrkey_cmp(mod_hash_key_t key1, mod_hash_key_t key2)
{
	uintptr_t k1 = (uintptr_t)key1;
	uintptr_t k2 = (uintptr_t)key2;
	if (k1 > k2)
		return (-1);
	else if (k1 < k2)
		return (1);
	else
		return (0);
}

mod_hash_t *
mod_hash_create_ptrhash(char *name, size_t nchains,
    void (*val_dtor)(mod_hash_val_t), size_t key_elem_size)
{
	size_t rshift;

	/*
	 * We want to hash on the bits in the middle of the address word
	 * Bits far to the right in the word have little significance, and
	 * are likely to all look the same (for example, an array of
	 * 256-byte structures will have the bottom 8 bits of address
	 * words the same).  So we want to right-shift each address to
	 * ignore the bottom bits.
	 *
	 * The high bits, which are also unused, will get taken out when
	 * mod_hash takes hashkey % nchains.
	 */
	rshift = highbit(key_elem_size);

	return mod_hash_create_extended(name, nchains, mod_hash_null_keydtor,
	    val_dtor, mod_hash_byptr, (void *)rshift, mod_hash_ptrkey_cmp,
	    KM_SLEEP);
}

void
mod_hash_destroy_ptrhash(mod_hash_t *hash)
{
	ASSERT(hash);
	mod_hash_destroy_hash(hash);
}

/*
 * mod_hash_byid()
 * mod_hash_idkey_cmp()
 *	Hash and key comparison routines for hashes with 32-bit unsigned keys.
 *
 * mod_hash_create_idhash()
 * mod_hash_destroy_idhash()
 * mod_hash_iddata_gen()
 * 	Create a hash that uses numeric keys.
 *
 *	The hash algorithm is documented in "Introduction to Algorithms"
 *	(Cormen, Leiserson, Rivest);  when the hash table is created, it
 *	attempts to find the next largest prime above the number of hash
 *	slots.  The hash index is then this number times the key modulo
 *	the hash size, or (key * prime) % nchains.
 */
uint_t
mod_hash_byid(void *hash_data, mod_hash_key_t key)
{
	uint_t kval = (uint_t)(uintptr_t)hash_data;
	return ((uint_t)(uintptr_t)key * (uint_t)kval);
}

int
mod_hash_idkey_cmp(mod_hash_key_t key1, mod_hash_key_t key2)
{
	return ((uint_t)(uintptr_t)key1 - (uint_t)(uintptr_t)key2);
}

/*
 * Generate the next largest prime number greater than nchains; this value
 * is intended to be later passed in to mod_hash_create_extended() as the
 * hash_data.
 */
uint_t
mod_hash_iddata_gen(size_t nchains)
{
	uint_t kval, i, prime;

	/*
	 * Pick the first (odd) prime greater than nchains.  Make sure kval is
	 * odd (so start with nchains +1 or +2 as appropriate).
	 */
	kval = (nchains % 2 == 0) ? nchains + 1 : nchains + 2;

	for (;;) {
		prime = 1;
		for (i = 3; i * i <= kval; i += 2) {
			if (kval % i == 0)
				prime = 0;
		}
		if (prime == 1)
			break;
		kval += 2;
	}
	return (kval);
}

mod_hash_t *
mod_hash_create_idhash(char *name, size_t nchains,
    void (*val_dtor)(mod_hash_val_t))
{
	uint_t kval = mod_hash_iddata_gen(nchains);

	return (mod_hash_create_extended(name, nchains, mod_hash_null_keydtor,
	    val_dtor, mod_hash_byid, (void *)(uintptr_t)kval,
	    mod_hash_idkey_cmp, KM_SLEEP));
}

void
mod_hash_destroy_idhash(mod_hash_t *hash)
{
	ASSERT(hash);
	mod_hash_destroy_hash(hash);
}

/*
 * mod_hash_init()
 * 	sets up globals, etc for mod_hash_*
 */
void
mod_hash_init(void)
{
	ASSERT(mh_e_cache == NULL);
	mh_e_cache = kmem_cache_create("mod_hash_entries",
	    sizeof (struct mod_hash_entry), 0, NULL, NULL, NULL, NULL,
	    NULL, 0);
}

/*
 * mod_hash_create_extended()
 * 	The full-blown hash creation function.
 *
 * notes:
 * 	nchains		- how many hash slots to create.  More hash slots will
 *			  result in shorter hash chains, but will consume
 *			  slightly more memory up front.
 *	sleep		- should be KM_SLEEP or KM_NOSLEEP, to indicate whether
 *			  to sleep for memory, or fail in low-memory conditions.
 *
 * 	Fails only if KM_NOSLEEP was specified, and no memory was available.
 */
mod_hash_t *
mod_hash_create_extended(
    char *hname,			/* descriptive name for hash */
    size_t nchains,			/* number of hash slots */
    void (*kdtor)(mod_hash_key_t),	/* key destructor */
    void (*vdtor)(mod_hash_val_t),	/* value destructor */
    uint_t (*hash_alg)(void *, mod_hash_key_t), /* hash algorithm */
    void *hash_alg_data,		/* pass-thru arg for hash_alg */
    int (*keycmp)(mod_hash_key_t, mod_hash_key_t), /* key comparator */
    int sleep)				/* whether to sleep for mem */
{
	mod_hash_t *mod_hash;
	ASSERT(hname && keycmp && hash_alg && vdtor && kdtor);

	if ((mod_hash = kmem_zalloc(MH_SIZE(nchains), sleep)) == NULL)
		return (NULL);

	mod_hash->mh_name = kmem_alloc(strlen(hname) + 1, sleep);
	if (mod_hash->mh_name == NULL) {
		kmem_free(mod_hash, MH_SIZE(nchains));
		return (NULL);
	}
	(void) strcpy(mod_hash->mh_name, hname);

	mod_hash->mh_sleep = sleep;
	mod_hash->mh_nchains = nchains;
	mod_hash->mh_kdtor = kdtor;
	mod_hash->mh_vdtor = vdtor;
	mod_hash->mh_hashalg = hash_alg;
	mod_hash->mh_hashalg_data = hash_alg_data;
	mod_hash->mh_keycmp = keycmp;

	/*
	 * Link the hash up on the list of hashes
	 */
	mutex_enter(&mh_head_lock);
	mod_hash->mh_next = mh_head;
	mh_head = mod_hash;
	mutex_exit(&mh_head_lock);

	return (mod_hash);
}

/*
 * mod_hash_destroy_hash()
 * 	destroy a hash table, destroying all of its stored keys and values
 * 	as well.
 */
void
mod_hash_destroy_hash(mod_hash_t *hash)
{
	mod_hash_t *mhp, *mhpp;

	mutex_enter(&mh_head_lock);
	/*
	 * Remove the hash from the hash list
	 */
	if (hash == mh_head) {		/* removing 1st list elem */
		mh_head = mh_head->mh_next;
	} else {
		/*
		 * mhpp can start out NULL since we know the 1st elem isn't the
		 * droid we're looking for.
		 */
		mhpp = NULL;
		for (mhp = mh_head; mhp != NULL; mhp = mhp->mh_next) {
			if (mhp == hash) {
				mhpp->mh_next = mhp->mh_next;
				break;
			}
			mhpp = mhp;
		}
	}
	mutex_exit(&mh_head_lock);

	/*
	 * Clean out keys and values.
	 */
	mod_hash_clear(hash);

	kmem_free(hash->mh_name, strlen(hash->mh_name) + 1);
	kmem_free(hash, MH_SIZE(hash->mh_nchains));
}

/*
 * i_mod_hash()
 * 	Call the hashing algorithm for this hash table, with the given key.
 */
uint_t
i_mod_hash(mod_hash_t *hash, mod_hash_key_t key)
{
	uint_t h;
	/*
	 * Prevent div by 0 problems;
	 * Also a nice shortcut when using a hash as a list
	 */
	if (hash->mh_nchains == 1)
		return (0);

	h = (hash->mh_hashalg)(hash->mh_hashalg_data, key);
	return (h % (hash->mh_nchains - 1));
}

/*
 * i_mod_hash_insert_nosync()
 * mod_hash_insert()
 * mod_hash_insert_reserve()
 * 	insert 'val' into the hash table, using 'key' as its key.  If 'key' is
 * 	already a key in the hash, an error will be returned, and the key-val
 * 	pair will not be inserted.  i_mod_hash_insert_nosync() supports a simple
 * 	handle abstraction, allowing hash entry allocation to be separated from
 * 	the hash insertion.  this abstraction allows simple use of the mod_hash
 * 	structure in situations where mod_hash_insert() with a KM_SLEEP
 * 	allocation policy would otherwise be unsafe.
 */
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)
{
	uint_t hashidx;
	struct mod_hash_entry *entry;

	ASSERT(hash);

	/*
	 * If we've not been given reserved storage, allocate storage directly,
	 * using the hash's allocation policy.
	 */
	if (handle == (mod_hash_hndl_t)0) {
		entry = kmem_cache_alloc(mh_e_cache, hash->mh_sleep);
		if (entry == NULL) {
			hash->mh_stat.mhs_nomem++;
			return (MH_ERR_NOMEM);
		}
	} else {
		entry = (struct mod_hash_entry *)handle;
	}

	hashidx = i_mod_hash(hash, key);
	entry->mhe_key = key;
	entry->mhe_val = val;
	entry->mhe_next = hash->mh_entries[hashidx];

	hash->mh_entries[hashidx] = entry;
	hash->mh_stat.mhs_nelems++;

	return (0);
}

int
mod_hash_insert(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t val)
{
	int res;
	mod_hash_val_t v;

	rw_enter(&hash->mh_contents, RW_WRITER);

	/*
	 * Disallow duplicate keys in the hash
	 */
	if (i_mod_hash_find_nosync(hash, key, &v) == 0) {
		rw_exit(&hash->mh_contents);
		hash->mh_stat.mhs_coll++;
		return (MH_ERR_DUPLICATE);
	}

	res = i_mod_hash_insert_nosync(hash, key, val, (mod_hash_hndl_t)0);
	rw_exit(&hash->mh_contents);

	return (res);
}

int
mod_hash_insert_reserve(mod_hash_t *hash, mod_hash_key_t key,
    mod_hash_val_t val, mod_hash_hndl_t handle)
{
	int res;
	mod_hash_val_t v;

	rw_enter(&hash->mh_contents, RW_WRITER);

	/*
	 * Disallow duplicate keys in the hash
	 */
	if (i_mod_hash_find_nosync(hash, key, &v) == 0) {
		rw_exit(&hash->mh_contents);
		hash->mh_stat.mhs_coll++;
		return (MH_ERR_DUPLICATE);
	}
	res = i_mod_hash_insert_nosync(hash, key, val, handle);
	rw_exit(&hash->mh_contents);

	return (res);
}

/*
 * mod_hash_reserve()
 * mod_hash_reserve_nosleep()
 * mod_hash_cancel()
 *   Make or cancel a mod_hash_entry_t reservation.  Reservations are used in
 *   mod_hash_insert_reserve() above.
 */
int
mod_hash_reserve(mod_hash_t *hash, mod_hash_hndl_t *handlep)
{
	*handlep = kmem_cache_alloc(mh_e_cache, hash->mh_sleep);
	if (*handlep == NULL) {
		hash->mh_stat.mhs_nomem++;
		return (MH_ERR_NOMEM);
	}

	return (0);
}

int
mod_hash_reserve_nosleep(mod_hash_t *hash, mod_hash_hndl_t *handlep)
{
	*handlep = kmem_cache_alloc(mh_e_cache, KM_NOSLEEP);
	if (*handlep == NULL) {
		hash->mh_stat.mhs_nomem++;
		return (MH_ERR_NOMEM);
	}

	return (0);

}

/*ARGSUSED*/
void
mod_hash_cancel(mod_hash_t *hash, mod_hash_hndl_t *handlep)
{
	kmem_cache_free(mh_e_cache, *handlep);
	*handlep = (mod_hash_hndl_t)0;
}

/*
 * i_mod_hash_remove_nosync()
 * mod_hash_remove()
 * 	Remove an element from the hash table.
 */
int
i_mod_hash_remove_nosync(mod_hash_t *hash, mod_hash_key_t key,
    mod_hash_val_t *val)
{
	int hashidx;
	struct mod_hash_entry *e, *ep;

	hashidx = i_mod_hash(hash, key);
	ep = NULL; /* e's parent */

	for (e = hash->mh_entries[hashidx]; e != NULL; e = e->mhe_next) {
		if (MH_KEYCMP(hash, e->mhe_key, key) == 0)
			break;
		ep = e;
	}

	if (e == NULL) {	/* not found */
		return (MH_ERR_NOTFOUND);
	}

	if (ep == NULL) 	/* special case 1st element in bucket */
		hash->mh_entries[hashidx] = e->mhe_next;
	else
		ep->mhe_next = e->mhe_next;

	/*
	 * Clean up resources used by the node's key.
	 */
	MH_KEY_DESTROY(hash, e->mhe_key);

	*val = e->mhe_val;
	kmem_cache_free(mh_e_cache, e);
	hash->mh_stat.mhs_nelems--;

	return (0);
}

int
mod_hash_remove(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val)
{
	int res;

	rw_enter(&hash->mh_contents, RW_WRITER);
	res = i_mod_hash_remove_nosync(hash, key, val);
	rw_exit(&hash->mh_contents);

	return (res);
}

/*
 * mod_hash_replace()
 * 	atomically remove an existing key-value pair from a hash, and replace
 * 	the key and value with the ones supplied.  The removed key and value
 * 	(if any) are destroyed.
 */
int
mod_hash_replace(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t val)
{
	int res;
	mod_hash_val_t v;

	rw_enter(&hash->mh_contents, RW_WRITER);

	if (i_mod_hash_remove_nosync(hash, key, &v) == 0) {
		/*
		 * mod_hash_remove() takes care of freeing up the key resources.
		 */
		MH_VAL_DESTROY(hash, v);
	}
	res = i_mod_hash_insert_nosync(hash, key, val, (mod_hash_hndl_t)0);

	rw_exit(&hash->mh_contents);

	return (res);
}

/*
 * mod_hash_destroy()
 * 	Remove an element from the hash table matching 'key', and destroy it.
 */
int
mod_hash_destroy(mod_hash_t *hash, mod_hash_key_t key)
{
	mod_hash_val_t val;
	int rv;

	rw_enter(&hash->mh_contents, RW_WRITER);

	if ((rv = i_mod_hash_remove_nosync(hash, key, &val)) == 0) {
		/*
		 * mod_hash_remove() takes care of freeing up the key resources.
		 */
		MH_VAL_DESTROY(hash, val);
	}

	rw_exit(&hash->mh_contents);
	return (rv);
}

/*
 * i_mod_hash_find_nosync()
 * mod_hash_find()
 * 	Find a value in the hash table corresponding to the given key.
 */
int
i_mod_hash_find_nosync(mod_hash_t *hash, mod_hash_key_t key,
    mod_hash_val_t *val)
{
	uint_t hashidx;
	struct mod_hash_entry *e;

	hashidx = i_mod_hash(hash, key);

	for (e = hash->mh_entries[hashidx]; e != NULL; e = e->mhe_next) {
		if (MH_KEYCMP(hash, e->mhe_key, key) == 0) {
			*val = e->mhe_val;
			hash->mh_stat.mhs_hit++;
			return (0);
		}
	}
	hash->mh_stat.mhs_miss++;
	return (MH_ERR_NOTFOUND);
}

int
mod_hash_find(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val)
{
	int res;

	rw_enter(&hash->mh_contents, RW_READER);
	res = i_mod_hash_find_nosync(hash, key, val);
	rw_exit(&hash->mh_contents);

	return (res);
}

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))
{
	int res;

	rw_enter(&hash->mh_contents, RW_READER);
	res = i_mod_hash_find_nosync(hash, key, val);
	if (res == 0) {
		find_cb(key, *val);
	}
	rw_exit(&hash->mh_contents);

	return (res);
}

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)
{
	int res;

	rw_enter(&hash->mh_contents, RW_READER);
	res = i_mod_hash_find_nosync(hash, key, val);
	if (res == 0) {
		*cb_rval = find_cb(key, *val);
	}
	rw_exit(&hash->mh_contents);

	return (res);
}

void
i_mod_hash_walk_nosync(mod_hash_t *hash,
    uint_t (*callback)(mod_hash_key_t, mod_hash_val_t *, void *), void *arg)
{
	struct mod_hash_entry	*e;
	uint_t			hashidx;
	int			res = MH_WALK_CONTINUE;

	for (hashidx = 0;
	    (hashidx < (hash->mh_nchains - 1)) && (res == MH_WALK_CONTINUE);
	    hashidx++) {
		e = hash->mh_entries[hashidx];
		while ((e != NULL) && (res == MH_WALK_CONTINUE)) {
			res = callback(e->mhe_key, e->mhe_val, arg);
			e = e->mhe_next;
		}
	}
}

/*
 * mod_hash_walk()
 * 	Walks all the elements in the hashtable and invokes the callback
 * 	function with the key/value pair for each element.  The hashtable
 * 	is locked for readers so the callback function should not attempt
 * 	to do any updates to the hashable.  The callback function should
 * 	return MH_WALK_CONTINUE to continue walking the hashtable or
 * 	MH_WALK_TERMINATE to abort the walk of the hashtable.
 */
void
mod_hash_walk(mod_hash_t *hash,
    uint_t (*callback)(mod_hash_key_t, mod_hash_val_t *, void *), void *arg)
{
	rw_enter(&hash->mh_contents, RW_READER);
	i_mod_hash_walk_nosync(hash, callback, arg);
	rw_exit(&hash->mh_contents);
}


/*
 * i_mod_hash_clear_nosync()
 * mod_hash_clear()
 *	Clears the given hash table by calling the destructor of every hash
 *	element and freeing up all mod_hash_entry's.
 */
void
i_mod_hash_clear_nosync(mod_hash_t *hash)
{
	int i;
	struct mod_hash_entry *e, *old_e;

	for (i = 0; i < hash->mh_nchains; i++) {
		e = hash->mh_entries[i];
		while (e != NULL) {
			MH_KEY_DESTROY(hash, e->mhe_key);
			MH_VAL_DESTROY(hash, e->mhe_val);
			old_e = e;
			e = e->mhe_next;
			kmem_cache_free(mh_e_cache, old_e);
		}
		hash->mh_entries[i] = NULL;
	}
	hash->mh_stat.mhs_nelems = 0;
}

void
mod_hash_clear(mod_hash_t *hash)
{
	ASSERT(hash);
	rw_enter(&hash->mh_contents, RW_WRITER);
	i_mod_hash_clear_nosync(hash);
	rw_exit(&hash->mh_contents);
}