1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* 23 * Copyright 2005 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 */ 26 27 #pragma ident "%Z%%M% %I% %E% SMI" 28 29 /* 30 * mod_hash: flexible hash table implementation. 31 * 32 * This is a reasonably fast, reasonably flexible hash table implementation 33 * which features pluggable hash algorithms to support storing arbitrary keys 34 * and values. It is designed to handle small (< 100,000 items) amounts of 35 * data. The hash uses chaining to resolve collisions, and does not feature a 36 * mechanism to grow the hash. Care must be taken to pick nchains to be large 37 * enough for the application at hand, or lots of time will be wasted searching 38 * hash chains. 39 * 40 * The client of the hash is required to supply a number of items to support 41 * the various hash functions: 42 * 43 * - Destructor functions for the key and value being hashed. 44 * A destructor is responsible for freeing an object when the hash 45 * table is no longer storing it. Since keys and values can be of 46 * arbitrary type, separate destructors for keys & values are used. 47 * These may be mod_hash_null_keydtor and mod_hash_null_valdtor if no 48 * destructor is needed for either a key or value. 49 * 50 * - A hashing algorithm which returns a uint_t representing a hash index 51 * The number returned need _not_ be between 0 and nchains. The mod_hash 52 * code will take care of doing that. The second argument (after the 53 * key) to the hashing function is a void * that represents 54 * hash_alg_data-- this is provided so that the hashing algrorithm can 55 * maintain some state across calls, or keep algorithm-specific 56 * constants associated with the hash table. 57 * 58 * A pointer-hashing and a string-hashing algorithm are supplied in 59 * this file. 60 * 61 * - A key comparator (a la qsort). 62 * This is used when searching the hash chain. The key comparator 63 * determines if two keys match. It should follow the return value 64 * semantics of strcmp. 65 * 66 * string and pointer comparators are supplied in this file. 67 * 68 * mod_hash_create_strhash() and mod_hash_create_ptrhash() provide good 69 * examples of how to create a customized hash table. 70 * 71 * Basic hash operations: 72 * 73 * mod_hash_create_strhash(name, nchains, dtor), 74 * create a hash using strings as keys. 75 * NOTE: This create a hash which automatically cleans up the string 76 * values it is given for keys. 77 * 78 * mod_hash_create_ptrhash(name, nchains, dtor, key_elem_size): 79 * create a hash using pointers as keys. 80 * 81 * mod_hash_create_extended(name, nchains, kdtor, vdtor, 82 * hash_alg, hash_alg_data, 83 * keycmp, sleep) 84 * create a customized hash table. 85 * 86 * mod_hash_destroy_hash(hash): 87 * destroy the given hash table, calling the key and value destructors 88 * on each key-value pair stored in the hash. 89 * 90 * mod_hash_insert(hash, key, val): 91 * place a key, value pair into the given hash. 92 * duplicate keys are rejected. 93 * 94 * mod_hash_insert_reserve(hash, key, val, handle): 95 * place a key, value pair into the given hash, using handle to indicate 96 * the reserved storage for the pair. (no memory allocation is needed 97 * during a mod_hash_insert_reserve.) duplicate keys are rejected. 98 * 99 * mod_hash_reserve(hash, *handle): 100 * reserve storage for a key-value pair using the memory allocation 101 * policy of 'hash', returning the storage handle in 'handle'. 102 * 103 * mod_hash_reserve_nosleep(hash, *handle): reserve storage for a key-value 104 * pair ignoring the memory allocation policy of 'hash' and always without 105 * sleep, returning the storage handle in 'handle'. 106 * 107 * mod_hash_remove(hash, key, *val): 108 * remove a key-value pair with key 'key' from 'hash', destroying the 109 * stored key, and returning the value in val. 110 * 111 * mod_hash_replace(hash, key, val) 112 * atomically remove an existing key-value pair from a hash, and replace 113 * the key and value with the ones supplied. The removed key and value 114 * (if any) are destroyed. 115 * 116 * mod_hash_destroy(hash, key): 117 * remove a key-value pair with key 'key' from 'hash', destroying both 118 * stored key and stored value. 119 * 120 * mod_hash_find(hash, key, val): 121 * find a value in the hash table corresponding to the given key. 122 * 123 * mod_hash_find_cb(hash, key, val, found_callback) 124 * find a value in the hash table corresponding to the given key. 125 * If a value is found, call specified callback passing key and val to it. 126 * The callback is called with the hash lock held. 127 * It is intended to be used in situations where the act of locating the 128 * data must also modify it - such as in reference counting schemes. 129 * 130 * mod_hash_walk(hash, callback(key, elem, arg), arg) 131 * walks all the elements in the hashtable and invokes the callback 132 * function with the key/value pair for each element. the hashtable 133 * is locked for readers so the callback function should not attempt 134 * to do any updates to the hashable. the callback function should 135 * return MH_WALK_CONTINUE to continue walking the hashtable or 136 * MH_WALK_TERMINATE to abort the walk of the hashtable. 137 * 138 * mod_hash_clear(hash): 139 * clears the given hash table of entries, calling the key and value 140 * destructors for every element in the hash. 141 */ 142 143 #include <sys/bitmap.h> 144 #include <sys/debug.h> 145 #include <sys/kmem.h> 146 #include <sys/sunddi.h> 147 148 #include <sys/modhash_impl.h> 149 150 /* 151 * MH_KEY_DESTROY() 152 * Invoke the key destructor. 153 */ 154 #define MH_KEY_DESTROY(hash, key) ((hash->mh_kdtor)(key)) 155 156 /* 157 * MH_VAL_DESTROY() 158 * Invoke the value destructor. 159 */ 160 #define MH_VAL_DESTROY(hash, val) ((hash->mh_vdtor)(val)) 161 162 /* 163 * MH_KEYCMP() 164 * Call the key comparator for the given hash keys. 165 */ 166 #define MH_KEYCMP(hash, key1, key2) ((hash->mh_keycmp)(key1, key2)) 167 168 static void i_mod_hash_clear_nosync(mod_hash_t *); 169 static int i_mod_hash_find_nosync(mod_hash_t *, mod_hash_key_t, 170 mod_hash_val_t *); 171 static int i_mod_hash_insert_nosync(mod_hash_t *, mod_hash_key_t, 172 mod_hash_val_t, mod_hash_hndl_t); 173 static int i_mod_hash_remove_nosync(mod_hash_t *, mod_hash_key_t, 174 mod_hash_val_t *); 175 static uint_t i_mod_hash(mod_hash_t *, mod_hash_key_t); 176 177 /* 178 * Cache for struct mod_hash_entry 179 */ 180 kmem_cache_t *mh_e_cache = NULL; 181 mod_hash_t *mh_head = NULL; 182 kmutex_t mh_head_lock; 183 184 /* 185 * mod_hash_null_keydtor() 186 * mod_hash_null_valdtor() 187 * no-op key and value destructors. 188 */ 189 /*ARGSUSED*/ 190 void 191 mod_hash_null_keydtor(mod_hash_key_t key) 192 { 193 } 194 195 /*ARGSUSED*/ 196 void 197 mod_hash_null_valdtor(mod_hash_val_t val) 198 { 199 } 200 201 /* 202 * mod_hash_bystr() 203 * mod_hash_strkey_cmp() 204 * mod_hash_strkey_dtor() 205 * mod_hash_strval_dtor() 206 * Hash and key comparison routines for hashes with string keys. 207 * 208 * mod_hash_create_strhash() 209 * Create a hash using strings as keys 210 * 211 * The string hashing algorithm is from the "Dragon Book" -- 212 * "Compilers: Principles, Tools & Techniques", by Aho, Sethi, Ullman 213 */ 214 215 /*ARGSUSED*/ 216 uint_t 217 mod_hash_bystr(void *hash_data, mod_hash_key_t key) 218 { 219 uint_t hash = 0; 220 uint_t g; 221 char *p, *k = (char *)key; 222 223 ASSERT(k); 224 for (p = k; *p != '\0'; p++) { 225 hash = (hash << 4) + *p; 226 if ((g = (hash & 0xf0000000)) != 0) { 227 hash ^= (g >> 24); 228 hash ^= g; 229 } 230 } 231 return (hash); 232 } 233 234 int 235 mod_hash_strkey_cmp(mod_hash_key_t key1, mod_hash_key_t key2) 236 { 237 return (strcmp((char *)key1, (char *)key2)); 238 } 239 240 void 241 mod_hash_strkey_dtor(mod_hash_key_t key) 242 { 243 char *c = (char *)key; 244 kmem_free(c, strlen(c) + 1); 245 } 246 247 void 248 mod_hash_strval_dtor(mod_hash_val_t val) 249 { 250 char *c = (char *)val; 251 kmem_free(c, strlen(c) + 1); 252 } 253 254 mod_hash_t * 255 mod_hash_create_strhash(char *name, size_t nchains, 256 void (*val_dtor)(mod_hash_val_t)) 257 { 258 return mod_hash_create_extended(name, nchains, mod_hash_strkey_dtor, 259 val_dtor, mod_hash_bystr, NULL, mod_hash_strkey_cmp, KM_SLEEP); 260 } 261 262 void 263 mod_hash_destroy_strhash(mod_hash_t *strhash) 264 { 265 ASSERT(strhash); 266 mod_hash_destroy_hash(strhash); 267 } 268 269 270 /* 271 * mod_hash_byptr() 272 * mod_hash_ptrkey_cmp() 273 * Hash and key comparison routines for hashes with pointer keys. 274 * 275 * mod_hash_create_ptrhash() 276 * mod_hash_destroy_ptrhash() 277 * Create a hash that uses pointers as keys. This hash algorithm 278 * picks an appropriate set of middle bits in the address to hash on 279 * based on the size of the hash table and a hint about the size of 280 * the items pointed at. 281 */ 282 uint_t 283 mod_hash_byptr(void *hash_data, mod_hash_key_t key) 284 { 285 uintptr_t k = (uintptr_t)key; 286 k >>= (int)(uintptr_t)hash_data; 287 288 return ((uint_t)k); 289 } 290 291 int 292 mod_hash_ptrkey_cmp(mod_hash_key_t key1, mod_hash_key_t key2) 293 { 294 uintptr_t k1 = (uintptr_t)key1; 295 uintptr_t k2 = (uintptr_t)key2; 296 if (k1 > k2) 297 return (-1); 298 else if (k1 < k2) 299 return (1); 300 else 301 return (0); 302 } 303 304 mod_hash_t * 305 mod_hash_create_ptrhash(char *name, size_t nchains, 306 void (*val_dtor)(mod_hash_val_t), size_t key_elem_size) 307 { 308 size_t rshift; 309 310 /* 311 * We want to hash on the bits in the middle of the address word 312 * Bits far to the right in the word have little significance, and 313 * are likely to all look the same (for example, an array of 314 * 256-byte structures will have the bottom 8 bits of address 315 * words the same). So we want to right-shift each address to 316 * ignore the bottom bits. 317 * 318 * The high bits, which are also unused, will get taken out when 319 * mod_hash takes hashkey % nchains. 320 */ 321 rshift = highbit(key_elem_size); 322 323 return mod_hash_create_extended(name, nchains, mod_hash_null_keydtor, 324 val_dtor, mod_hash_byptr, (void *)rshift, mod_hash_ptrkey_cmp, 325 KM_SLEEP); 326 } 327 328 void 329 mod_hash_destroy_ptrhash(mod_hash_t *hash) 330 { 331 ASSERT(hash); 332 mod_hash_destroy_hash(hash); 333 } 334 335 /* 336 * mod_hash_byid() 337 * mod_hash_idkey_cmp() 338 * Hash and key comparison routines for hashes with 32-bit unsigned keys. 339 * 340 * mod_hash_create_idhash() 341 * mod_hash_destroy_idhash() 342 * mod_hash_iddata_gen() 343 * Create a hash that uses numeric keys. 344 * 345 * The hash algorithm is documented in "Introduction to Algorithms" 346 * (Cormen, Leiserson, Rivest); when the hash table is created, it 347 * attempts to find the next largest prime above the number of hash 348 * slots. The hash index is then this number times the key modulo 349 * the hash size, or (key * prime) % nchains. 350 */ 351 uint_t 352 mod_hash_byid(void *hash_data, mod_hash_key_t key) 353 { 354 uint_t kval = (uint_t)(uintptr_t)hash_data; 355 return ((uint_t)(uintptr_t)key * (uint_t)kval); 356 } 357 358 int 359 mod_hash_idkey_cmp(mod_hash_key_t key1, mod_hash_key_t key2) 360 { 361 return ((uint_t)(uintptr_t)key1 - (uint_t)(uintptr_t)key2); 362 } 363 364 /* 365 * Generate the next largest prime number greater than nchains; this value 366 * is intended to be later passed in to mod_hash_create_extended() as the 367 * hash_data. 368 */ 369 uint_t 370 mod_hash_iddata_gen(size_t nchains) 371 { 372 uint_t kval, i, prime; 373 374 /* 375 * Pick the first (odd) prime greater than nchains. Make sure kval is 376 * odd (so start with nchains +1 or +2 as appropriate). 377 */ 378 kval = (nchains % 2 == 0) ? nchains + 1 : nchains + 2; 379 380 for (;;) { 381 prime = 1; 382 for (i = 3; i * i <= kval; i += 2) { 383 if (kval % i == 0) 384 prime = 0; 385 } 386 if (prime == 1) 387 break; 388 kval += 2; 389 } 390 return (kval); 391 } 392 393 mod_hash_t * 394 mod_hash_create_idhash(char *name, size_t nchains, 395 void (*val_dtor)(mod_hash_val_t)) 396 { 397 uint_t kval = mod_hash_iddata_gen(nchains); 398 399 return (mod_hash_create_extended(name, nchains, mod_hash_null_keydtor, 400 val_dtor, mod_hash_byid, (void *)(uintptr_t)kval, 401 mod_hash_idkey_cmp, KM_SLEEP)); 402 } 403 404 void 405 mod_hash_destroy_idhash(mod_hash_t *hash) 406 { 407 ASSERT(hash); 408 mod_hash_destroy_hash(hash); 409 } 410 411 /* 412 * mod_hash_init() 413 * sets up globals, etc for mod_hash_* 414 */ 415 void 416 mod_hash_init(void) 417 { 418 ASSERT(mh_e_cache == NULL); 419 mh_e_cache = kmem_cache_create("mod_hash_entries", 420 sizeof (struct mod_hash_entry), 0, NULL, NULL, NULL, NULL, 421 NULL, 0); 422 } 423 424 /* 425 * mod_hash_create_extended() 426 * The full-blown hash creation function. 427 * 428 * notes: 429 * nchains - how many hash slots to create. More hash slots will 430 * result in shorter hash chains, but will consume 431 * slightly more memory up front. 432 * sleep - should be KM_SLEEP or KM_NOSLEEP, to indicate whether 433 * to sleep for memory, or fail in low-memory conditions. 434 * 435 * Fails only if KM_NOSLEEP was specified, and no memory was available. 436 */ 437 mod_hash_t * 438 mod_hash_create_extended( 439 char *hname, /* descriptive name for hash */ 440 size_t nchains, /* number of hash slots */ 441 void (*kdtor)(mod_hash_key_t), /* key destructor */ 442 void (*vdtor)(mod_hash_val_t), /* value destructor */ 443 uint_t (*hash_alg)(void *, mod_hash_key_t), /* hash algorithm */ 444 void *hash_alg_data, /* pass-thru arg for hash_alg */ 445 int (*keycmp)(mod_hash_key_t, mod_hash_key_t), /* key comparator */ 446 int sleep) /* whether to sleep for mem */ 447 { 448 mod_hash_t *mod_hash; 449 ASSERT(hname && keycmp && hash_alg && vdtor && kdtor); 450 451 if ((mod_hash = kmem_zalloc(MH_SIZE(nchains), sleep)) == NULL) 452 return (NULL); 453 454 mod_hash->mh_name = kmem_alloc(strlen(hname) + 1, sleep); 455 if (mod_hash->mh_name == NULL) { 456 kmem_free(mod_hash, MH_SIZE(nchains)); 457 return (NULL); 458 } 459 (void) strcpy(mod_hash->mh_name, hname); 460 461 mod_hash->mh_sleep = sleep; 462 mod_hash->mh_nchains = nchains; 463 mod_hash->mh_kdtor = kdtor; 464 mod_hash->mh_vdtor = vdtor; 465 mod_hash->mh_hashalg = hash_alg; 466 mod_hash->mh_hashalg_data = hash_alg_data; 467 mod_hash->mh_keycmp = keycmp; 468 469 /* 470 * Link the hash up on the list of hashes 471 */ 472 mutex_enter(&mh_head_lock); 473 mod_hash->mh_next = mh_head; 474 mh_head = mod_hash; 475 mutex_exit(&mh_head_lock); 476 477 return (mod_hash); 478 } 479 480 /* 481 * mod_hash_destroy_hash() 482 * destroy a hash table, destroying all of its stored keys and values 483 * as well. 484 */ 485 void 486 mod_hash_destroy_hash(mod_hash_t *hash) 487 { 488 mod_hash_t *mhp, *mhpp; 489 490 mutex_enter(&mh_head_lock); 491 /* 492 * Remove the hash from the hash list 493 */ 494 if (hash == mh_head) { /* removing 1st list elem */ 495 mh_head = mh_head->mh_next; 496 } else { 497 /* 498 * mhpp can start out NULL since we know the 1st elem isn't the 499 * droid we're looking for. 500 */ 501 mhpp = NULL; 502 for (mhp = mh_head; mhp != NULL; mhp = mhp->mh_next) { 503 if (mhp == hash) { 504 mhpp->mh_next = mhp->mh_next; 505 break; 506 } 507 mhpp = mhp; 508 } 509 } 510 mutex_exit(&mh_head_lock); 511 512 /* 513 * Clean out keys and values. 514 */ 515 mod_hash_clear(hash); 516 517 kmem_free(hash->mh_name, strlen(hash->mh_name) + 1); 518 kmem_free(hash, MH_SIZE(hash->mh_nchains)); 519 } 520 521 /* 522 * i_mod_hash() 523 * Call the hashing algorithm for this hash table, with the given key. 524 */ 525 static uint_t 526 i_mod_hash(mod_hash_t *hash, mod_hash_key_t key) 527 { 528 uint_t h; 529 /* 530 * Prevent div by 0 problems; 531 * Also a nice shortcut when using a hash as a list 532 */ 533 if (hash->mh_nchains == 1) 534 return (0); 535 536 h = (hash->mh_hashalg)(hash->mh_hashalg_data, key); 537 return (h % (hash->mh_nchains - 1)); 538 } 539 540 /* 541 * i_mod_hash_insert_nosync() 542 * mod_hash_insert() 543 * mod_hash_insert_reserve() 544 * insert 'val' into the hash table, using 'key' as its key. If 'key' is 545 * already a key in the hash, an error will be returned, and the key-val 546 * pair will not be inserted. i_mod_hash_insert_nosync() supports a simple 547 * handle abstraction, allowing hash entry allocation to be separated from 548 * the hash insertion. this abstraction allows simple use of the mod_hash 549 * structure in situations where mod_hash_insert() with a KM_SLEEP 550 * allocation policy would otherwise be unsafe. 551 */ 552 int 553 i_mod_hash_insert_nosync(mod_hash_t *hash, mod_hash_key_t key, 554 mod_hash_val_t val, mod_hash_hndl_t handle) 555 { 556 uint_t hashidx; 557 struct mod_hash_entry *entry; 558 559 ASSERT(hash); 560 561 /* 562 * If we've not been given reserved storage, allocate storage directly, 563 * using the hash's allocation policy. 564 */ 565 if (handle == (mod_hash_hndl_t)0) { 566 entry = kmem_cache_alloc(mh_e_cache, hash->mh_sleep); 567 if (entry == NULL) { 568 hash->mh_stat.mhs_nomem++; 569 return (MH_ERR_NOMEM); 570 } 571 } else { 572 entry = (struct mod_hash_entry *)handle; 573 } 574 575 hashidx = i_mod_hash(hash, key); 576 entry->mhe_key = key; 577 entry->mhe_val = val; 578 entry->mhe_next = hash->mh_entries[hashidx]; 579 580 hash->mh_entries[hashidx] = entry; 581 hash->mh_stat.mhs_nelems++; 582 583 return (0); 584 } 585 586 int 587 mod_hash_insert(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t val) 588 { 589 int res; 590 mod_hash_val_t v; 591 592 rw_enter(&hash->mh_contents, RW_WRITER); 593 594 /* 595 * Disallow duplicate keys in the hash 596 */ 597 if (i_mod_hash_find_nosync(hash, key, &v) == 0) { 598 rw_exit(&hash->mh_contents); 599 hash->mh_stat.mhs_coll++; 600 return (MH_ERR_DUPLICATE); 601 } 602 603 res = i_mod_hash_insert_nosync(hash, key, val, (mod_hash_hndl_t)0); 604 rw_exit(&hash->mh_contents); 605 606 return (res); 607 } 608 609 int 610 mod_hash_insert_reserve(mod_hash_t *hash, mod_hash_key_t key, 611 mod_hash_val_t val, mod_hash_hndl_t handle) 612 { 613 int res; 614 mod_hash_val_t v; 615 616 rw_enter(&hash->mh_contents, RW_WRITER); 617 618 /* 619 * Disallow duplicate keys in the hash 620 */ 621 if (i_mod_hash_find_nosync(hash, key, &v) == 0) { 622 rw_exit(&hash->mh_contents); 623 hash->mh_stat.mhs_coll++; 624 return (MH_ERR_DUPLICATE); 625 } 626 res = i_mod_hash_insert_nosync(hash, key, val, handle); 627 rw_exit(&hash->mh_contents); 628 629 return (res); 630 } 631 632 /* 633 * mod_hash_reserve() 634 * mod_hash_reserve_nosleep() 635 * mod_hash_cancel() 636 * Make or cancel a mod_hash_entry_t reservation. Reservations are used in 637 * mod_hash_insert_reserve() above. 638 */ 639 int 640 mod_hash_reserve(mod_hash_t *hash, mod_hash_hndl_t *handlep) 641 { 642 *handlep = kmem_cache_alloc(mh_e_cache, hash->mh_sleep); 643 if (*handlep == NULL) { 644 hash->mh_stat.mhs_nomem++; 645 return (MH_ERR_NOMEM); 646 } 647 648 return (0); 649 } 650 651 int 652 mod_hash_reserve_nosleep(mod_hash_t *hash, mod_hash_hndl_t *handlep) 653 { 654 *handlep = kmem_cache_alloc(mh_e_cache, KM_NOSLEEP); 655 if (*handlep == NULL) { 656 hash->mh_stat.mhs_nomem++; 657 return (MH_ERR_NOMEM); 658 } 659 660 return (0); 661 662 } 663 664 /*ARGSUSED*/ 665 void 666 mod_hash_cancel(mod_hash_t *hash, mod_hash_hndl_t *handlep) 667 { 668 kmem_cache_free(mh_e_cache, *handlep); 669 *handlep = (mod_hash_hndl_t)0; 670 } 671 672 /* 673 * i_mod_hash_remove_nosync() 674 * mod_hash_remove() 675 * Remove an element from the hash table. 676 */ 677 int 678 i_mod_hash_remove_nosync(mod_hash_t *hash, mod_hash_key_t key, 679 mod_hash_val_t *val) 680 { 681 int hashidx; 682 struct mod_hash_entry *e, *ep; 683 684 hashidx = i_mod_hash(hash, key); 685 ep = NULL; /* e's parent */ 686 687 for (e = hash->mh_entries[hashidx]; e != NULL; e = e->mhe_next) { 688 if (MH_KEYCMP(hash, e->mhe_key, key) == 0) 689 break; 690 ep = e; 691 } 692 693 if (e == NULL) { /* not found */ 694 return (MH_ERR_NOTFOUND); 695 } 696 697 if (ep == NULL) /* special case 1st element in bucket */ 698 hash->mh_entries[hashidx] = e->mhe_next; 699 else 700 ep->mhe_next = e->mhe_next; 701 702 /* 703 * Clean up resources used by the node's key. 704 */ 705 MH_KEY_DESTROY(hash, e->mhe_key); 706 707 *val = e->mhe_val; 708 kmem_cache_free(mh_e_cache, e); 709 hash->mh_stat.mhs_nelems--; 710 711 return (0); 712 } 713 714 int 715 mod_hash_remove(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val) 716 { 717 int res; 718 719 rw_enter(&hash->mh_contents, RW_WRITER); 720 res = i_mod_hash_remove_nosync(hash, key, val); 721 rw_exit(&hash->mh_contents); 722 723 return (res); 724 } 725 726 /* 727 * mod_hash_replace() 728 * atomically remove an existing key-value pair from a hash, and replace 729 * the key and value with the ones supplied. The removed key and value 730 * (if any) are destroyed. 731 */ 732 int 733 mod_hash_replace(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t val) 734 { 735 int res; 736 mod_hash_val_t v; 737 738 rw_enter(&hash->mh_contents, RW_WRITER); 739 740 if (i_mod_hash_remove_nosync(hash, key, &v) == 0) { 741 /* 742 * mod_hash_remove() takes care of freeing up the key resources. 743 */ 744 MH_VAL_DESTROY(hash, v); 745 } 746 res = i_mod_hash_insert_nosync(hash, key, val, (mod_hash_hndl_t)0); 747 748 rw_exit(&hash->mh_contents); 749 750 return (res); 751 } 752 753 /* 754 * mod_hash_destroy() 755 * Remove an element from the hash table matching 'key', and destroy it. 756 */ 757 int 758 mod_hash_destroy(mod_hash_t *hash, mod_hash_key_t key) 759 { 760 mod_hash_val_t val; 761 int rv; 762 763 rw_enter(&hash->mh_contents, RW_WRITER); 764 765 if ((rv = i_mod_hash_remove_nosync(hash, key, &val)) == 0) { 766 /* 767 * mod_hash_remove() takes care of freeing up the key resources. 768 */ 769 MH_VAL_DESTROY(hash, val); 770 } 771 772 rw_exit(&hash->mh_contents); 773 return (rv); 774 } 775 776 /* 777 * i_mod_hash_find_nosync() 778 * mod_hash_find() 779 * Find a value in the hash table corresponding to the given key. 780 */ 781 static int 782 i_mod_hash_find_nosync(mod_hash_t *hash, mod_hash_key_t key, 783 mod_hash_val_t *val) 784 { 785 uint_t hashidx; 786 struct mod_hash_entry *e; 787 788 hashidx = i_mod_hash(hash, key); 789 790 for (e = hash->mh_entries[hashidx]; e != NULL; e = e->mhe_next) { 791 if (MH_KEYCMP(hash, e->mhe_key, key) == 0) { 792 *val = e->mhe_val; 793 hash->mh_stat.mhs_hit++; 794 return (0); 795 } 796 } 797 hash->mh_stat.mhs_miss++; 798 return (MH_ERR_NOTFOUND); 799 } 800 801 int 802 mod_hash_find(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val) 803 { 804 int res; 805 806 rw_enter(&hash->mh_contents, RW_READER); 807 res = i_mod_hash_find_nosync(hash, key, val); 808 rw_exit(&hash->mh_contents); 809 810 return (res); 811 } 812 813 int 814 mod_hash_find_cb(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val, 815 void (*find_cb)(mod_hash_key_t, mod_hash_val_t)) 816 { 817 int res; 818 819 rw_enter(&hash->mh_contents, RW_READER); 820 res = i_mod_hash_find_nosync(hash, key, val); 821 if (res == 0) { 822 find_cb(key, *val); 823 } 824 rw_exit(&hash->mh_contents); 825 826 return (res); 827 } 828 829 static void 830 i_mod_hash_walk_nosync(mod_hash_t *hash, 831 uint_t (*callback)(mod_hash_key_t, mod_hash_val_t *, void *), void *arg) 832 { 833 struct mod_hash_entry *e; 834 uint_t hashidx; 835 int res = MH_WALK_CONTINUE; 836 837 for (hashidx = 0; 838 (hashidx < (hash->mh_nchains - 1)) && (res == MH_WALK_CONTINUE); 839 hashidx++) { 840 e = hash->mh_entries[hashidx]; 841 while ((e != NULL) && (res == MH_WALK_CONTINUE)) { 842 res = callback(e->mhe_key, e->mhe_val, arg); 843 e = e->mhe_next; 844 } 845 } 846 } 847 848 /* 849 * mod_hash_walk() 850 * Walks all the elements in the hashtable and invokes the callback 851 * function with the key/value pair for each element. The hashtable 852 * is locked for readers so the callback function should not attempt 853 * to do any updates to the hashable. The callback function should 854 * return MH_WALK_CONTINUE to continue walking the hashtable or 855 * MH_WALK_TERMINATE to abort the walk of the hashtable. 856 */ 857 void 858 mod_hash_walk(mod_hash_t *hash, 859 uint_t (*callback)(mod_hash_key_t, mod_hash_val_t *, void *), void *arg) 860 { 861 rw_enter(&hash->mh_contents, RW_READER); 862 i_mod_hash_walk_nosync(hash, callback, arg); 863 rw_exit(&hash->mh_contents); 864 } 865 866 867 /* 868 * i_mod_hash_clear_nosync() 869 * mod_hash_clear() 870 * Clears the given hash table by calling the destructor of every hash 871 * element and freeing up all mod_hash_entry's. 872 */ 873 static void 874 i_mod_hash_clear_nosync(mod_hash_t *hash) 875 { 876 int i; 877 struct mod_hash_entry *e, *old_e; 878 879 for (i = 0; i < hash->mh_nchains; i++) { 880 e = hash->mh_entries[i]; 881 while (e != NULL) { 882 MH_KEY_DESTROY(hash, e->mhe_key); 883 MH_VAL_DESTROY(hash, e->mhe_val); 884 old_e = e; 885 e = e->mhe_next; 886 kmem_cache_free(mh_e_cache, old_e); 887 } 888 hash->mh_entries[i] = NULL; 889 } 890 hash->mh_stat.mhs_nelems = 0; 891 } 892 893 void 894 mod_hash_clear(mod_hash_t *hash) 895 { 896 ASSERT(hash); 897 rw_enter(&hash->mh_contents, RW_WRITER); 898 i_mod_hash_clear_nosync(hash); 899 rw_exit(&hash->mh_contents); 900 } 901