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