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