| /* |
| * 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. |
| */ |
| |
| /* |
| * 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 algorithm 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/zfs_context.h> |
| #include <sys/bitmap.h> |
| #include <sys/modhash_impl.h> |
| #include <sys/sysmacros.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_nodtr(char *name, size_t nchains, |
| void (*val_dtor)(mod_hash_val_t)) |
| { |
| return mod_hash_create_extended(name, nchains, mod_hash_null_keydtor, |
| val_dtor, mod_hash_bystr, NULL, mod_hash_strkey_cmp, KM_SLEEP); |
| } |
| |
| 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 = highbit64(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); |
| } |
| |
| void |
| mod_hash_fini(void) |
| { |
| mutex_destroy(&mh_head_lock); |
| |
| if (mh_e_cache) { |
| kmem_cache_destroy(mh_e_cache); |
| mh_e_cache = NULL; |
| } |
| } |
| |
| /* |
| * 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); |
| |
| mutex_init(&mh_head_lock, NULL, MUTEX_DEFAULT, NULL); |
| } |
| |
| /* |
| * 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; |
| size_t size; |
| ASSERT(hname && keycmp && hash_alg && vdtor && kdtor); |
| |
| if ((mod_hash = kmem_zalloc(MH_SIZE(nchains), sleep)) == NULL) |
| return (NULL); |
| |
| size = strlen(hname) + 1; |
| mod_hash->mh_name = kmem_alloc(size, sleep); |
| if (mod_hash->mh_name == NULL) { |
| kmem_free(mod_hash, MH_SIZE(nchains)); |
| return (NULL); |
| } |
| (void) strlcpy(mod_hash->mh_name, hname, size); |
| |
| rw_init(&mod_hash->mh_contents, NULL, RW_DEFAULT, NULL); |
| 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); |
| |
| rw_destroy(&hash->mh_contents); |
| 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); |
| } |