hashmap.c revision 1.2.4.2
1 /* $NetBSD: hashmap.c,v 1.2.4.2 2025/08/02 05:53:52 perseant Exp $ */ 2 3 /* 4 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 5 * 6 * SPDX-License-Identifier: MPL-2.0 7 * 8 * This Source Code Form is subject to the terms of the Mozilla Public 9 * License, v. 2.0. If a copy of the MPL was not distributed with this 10 * file, you can obtain one at https://mozilla.org/MPL/2.0/. 11 * 12 * See the COPYRIGHT file distributed with this work for additional 13 * information regarding copyright ownership. 14 */ 15 16 /* 17 * This is an implementation of the Robin Hood hash table algorithm as 18 * described in [a] with simple linear searching, and backwards shift 19 * deletion algorithm as described in [b] and [c]. 20 * 21 * Further work: 22 * 1. Implement 4.1 Speeding up Searches - 4.4 Smart Search [a] 23 * 2. Implement A Fast Concurrent and Resizable Robin Hood Hash Table [b] 24 * 25 * a. https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf paper. 26 * b. https://dspace.mit.edu/bitstream/handle/1721.1/130693/1251799942-MIT.pdf 27 * c. 28 * https://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/ 29 */ 30 31 #include <ctype.h> 32 #include <inttypes.h> 33 #include <string.h> 34 35 #include <isc/ascii.h> 36 #include <isc/atomic.h> 37 #include <isc/entropy.h> 38 #include <isc/hash.h> 39 #include <isc/hashmap.h> 40 #include <isc/magic.h> 41 #include <isc/mem.h> 42 #include <isc/result.h> 43 #include <isc/types.h> 44 #include <isc/util.h> 45 46 #define APPROX_99_PERCENT(x) (((x) * 1013) >> 10) 47 #define APPROX_95_PERCENT(x) (((x) * 972) >> 10) 48 #define APPROX_90_PERCENT(x) (((x) * 921) >> 10) 49 #define APPROX_85_PERCENT(x) (((x) * 870) >> 10) 50 #define APPROX_40_PERCENT(x) (((x) * 409) >> 10) 51 #define APPROX_35_PERCENT(x) (((x) * 359) >> 10) 52 #define APPROX_30_PERCENT(x) (((x) * 308) >> 10) 53 #define APPROX_25_PERCENT(x) (((x) * 256) >> 10) 54 #define APPROX_20_PERCENT(x) (((x) * 205) >> 10) 55 #define APPROX_15_PERCENT(x) (((x) * 154) >> 10) 56 #define APPROX_10_PERCENT(x) (((x) * 103) >> 10) 57 #define APPROX_05_PERCENT(x) (((x) * 52) >> 10) 58 #define APPROX_01_PERCENT(x) (((x) * 11) >> 10) 59 60 #define ISC_HASHMAP_MAGIC ISC_MAGIC('H', 'M', 'a', 'p') 61 #define ISC_HASHMAP_VALID(hashmap) ISC_MAGIC_VALID(hashmap, ISC_HASHMAP_MAGIC) 62 63 /* We have two tables for incremental rehashing */ 64 #define HASHMAP_NUM_TABLES 2 65 66 #define HASHSIZE(bits) (UINT64_C(1) << (bits)) 67 68 #define HASHMAP_NO_BITS 0U 69 #define HASHMAP_MIN_BITS 1U 70 #define HASHMAP_MAX_BITS 32U 71 72 typedef struct hashmap_node { 73 const void *key; 74 void *value; 75 uint32_t hashval; 76 uint32_t psl; 77 } hashmap_node_t; 78 79 typedef struct hashmap_table { 80 size_t size; 81 uint8_t hashbits; 82 uint32_t hashmask; 83 hashmap_node_t *table; 84 } hashmap_table_t; 85 86 struct isc_hashmap { 87 unsigned int magic; 88 uint8_t hindex; 89 uint32_t hiter; /* rehashing iterator */ 90 isc_mem_t *mctx; 91 size_t count; 92 hashmap_table_t tables[HASHMAP_NUM_TABLES]; 93 atomic_uint_fast32_t iterators; 94 }; 95 96 struct isc_hashmap_iter { 97 isc_hashmap_t *hashmap; 98 size_t i; 99 size_t size; 100 uint8_t hindex; 101 hashmap_node_t *cur; 102 }; 103 104 static isc_result_t 105 hashmap_add(isc_hashmap_t *hashmap, const uint32_t hashval, 106 isc_hashmap_match_fn match, const uint8_t *key, void *value, 107 void **foundp, uint8_t idx); 108 109 static void 110 hashmap_rehash_one(isc_hashmap_t *hashmap); 111 static void 112 hashmap_rehash_start_grow(isc_hashmap_t *hashmap); 113 static void 114 hashmap_rehash_start_shrink(isc_hashmap_t *hashmap); 115 static bool 116 over_threshold(isc_hashmap_t *hashmap); 117 static bool 118 under_threshold(isc_hashmap_t *hashmap); 119 120 static uint8_t 121 hashmap_nexttable(uint8_t idx) { 122 return (idx == 0) ? 1 : 0; 123 } 124 125 static bool 126 rehashing_in_progress(const isc_hashmap_t *hashmap) { 127 return hashmap->tables[hashmap_nexttable(hashmap->hindex)].table != 128 NULL; 129 } 130 131 static bool 132 try_nexttable(const isc_hashmap_t *hashmap, uint8_t idx) { 133 return idx == hashmap->hindex && rehashing_in_progress(hashmap); 134 } 135 136 static void 137 hashmap_node_init(hashmap_node_t *node, const uint32_t hashval, 138 const uint8_t *key, void *value) { 139 *node = (hashmap_node_t){ 140 .value = value, 141 .hashval = hashval, 142 .key = key, 143 .psl = 0, 144 }; 145 } 146 147 ISC_ATTR_UNUSED static void 148 hashmap_dump_table(const isc_hashmap_t *hashmap, const uint8_t idx) { 149 fprintf(stderr, 150 "====== %" PRIu8 " (bits = %" PRIu8 ", size = %zu =====\n", idx, 151 hashmap->tables[idx].hashbits, hashmap->tables[idx].size); 152 for (size_t i = 0; i < hashmap->tables[idx].size; i++) { 153 hashmap_node_t *node = &hashmap->tables[idx].table[i]; 154 if (node->key != NULL) { 155 uint32_t hash = isc_hash_bits32( 156 node->hashval, hashmap->tables[idx].hashbits); 157 fprintf(stderr, 158 "%p: %zu -> %p" 159 ", value = %p" 160 ", hash = %" PRIu32 ", hashval = %" PRIu32 161 ", psl = %" PRIu32 ", key = %s\n", 162 hashmap, i, node, node->value, hash, 163 node->hashval, node->psl, (char *)node->key); 164 } 165 } 166 fprintf(stderr, "================\n\n"); 167 } 168 169 static void 170 hashmap_create_table(isc_hashmap_t *hashmap, const uint8_t idx, 171 const uint8_t bits) { 172 REQUIRE(hashmap->tables[idx].hashbits == HASHMAP_NO_BITS); 173 REQUIRE(hashmap->tables[idx].table == NULL); 174 REQUIRE(bits >= HASHMAP_MIN_BITS); 175 REQUIRE(bits <= HASHMAP_MAX_BITS); 176 177 hashmap->tables[idx] = (hashmap_table_t){ 178 .hashbits = bits, 179 .hashmask = HASHSIZE(bits) - 1, 180 .size = HASHSIZE(bits), 181 }; 182 183 hashmap->tables[idx].table = 184 isc_mem_cget(hashmap->mctx, hashmap->tables[idx].size, 185 sizeof(hashmap->tables[idx].table[0])); 186 } 187 188 static void 189 hashmap_free_table(isc_hashmap_t *hashmap, const uint8_t idx, bool cleanup) { 190 size_t size; 191 192 if (cleanup) { 193 for (size_t i = 0; i < hashmap->tables[idx].size; i++) { 194 hashmap_node_t *node = &hashmap->tables[idx].table[i]; 195 if (node->key != NULL) { 196 *node = (hashmap_node_t){ 0 }; 197 hashmap->count--; 198 } 199 } 200 } 201 202 size = hashmap->tables[idx].size * 203 sizeof(hashmap->tables[idx].table[0]); 204 isc_mem_put(hashmap->mctx, hashmap->tables[idx].table, size); 205 206 hashmap->tables[idx] = (hashmap_table_t){ 207 .hashbits = HASHMAP_NO_BITS, 208 }; 209 } 210 211 void 212 isc_hashmap_create(isc_mem_t *mctx, uint8_t bits, isc_hashmap_t **hashmapp) { 213 isc_hashmap_t *hashmap = isc_mem_get(mctx, sizeof(*hashmap)); 214 215 REQUIRE(hashmapp != NULL && *hashmapp == NULL); 216 REQUIRE(mctx != NULL); 217 REQUIRE(bits >= HASHMAP_MIN_BITS && bits <= HASHMAP_MAX_BITS); 218 219 *hashmap = (isc_hashmap_t){ 220 .magic = ISC_HASHMAP_MAGIC, 221 }; 222 isc_mem_attach(mctx, &hashmap->mctx); 223 224 hashmap_create_table(hashmap, 0, bits); 225 226 hashmap->magic = ISC_HASHMAP_MAGIC; 227 228 *hashmapp = hashmap; 229 } 230 231 void 232 isc_hashmap_destroy(isc_hashmap_t **hashmapp) { 233 isc_hashmap_t *hashmap; 234 235 REQUIRE(hashmapp != NULL && *hashmapp != NULL); 236 REQUIRE(ISC_HASHMAP_VALID(*hashmapp)); 237 238 hashmap = *hashmapp; 239 *hashmapp = NULL; 240 241 hashmap->magic = 0; 242 243 for (size_t i = 0; i < HASHMAP_NUM_TABLES; i++) { 244 if (hashmap->tables[i].table != NULL) { 245 hashmap_free_table(hashmap, i, true); 246 } 247 } 248 INSIST(hashmap->count == 0); 249 250 isc_mem_putanddetach(&hashmap->mctx, hashmap, sizeof(*hashmap)); 251 } 252 253 static hashmap_node_t * 254 hashmap_find(const isc_hashmap_t *hashmap, const uint32_t hashval, 255 isc_hashmap_match_fn match, const uint8_t *key, uint32_t *pslp, 256 uint8_t *idxp) { 257 uint32_t hash; 258 uint32_t psl; 259 uint8_t idx = *idxp; 260 uint32_t pos; 261 262 nexttable: 263 psl = 0; 264 hash = isc_hash_bits32(hashval, hashmap->tables[idx].hashbits); 265 266 while (true) { 267 hashmap_node_t *node = NULL; 268 269 pos = (hash + psl) & hashmap->tables[idx].hashmask; 270 271 node = &hashmap->tables[idx].table[pos]; 272 273 if (node->key == NULL || psl > node->psl) { 274 break; 275 } 276 277 if (node->hashval == hashval) { 278 if (match(node->value, key)) { 279 *pslp = psl; 280 *idxp = idx; 281 return node; 282 } 283 } 284 285 psl++; 286 } 287 if (try_nexttable(hashmap, idx)) { 288 idx = hashmap_nexttable(idx); 289 goto nexttable; 290 } 291 292 return NULL; 293 } 294 295 isc_result_t 296 isc_hashmap_find(const isc_hashmap_t *hashmap, const uint32_t hashval, 297 isc_hashmap_match_fn match, const void *key, void **valuep) { 298 REQUIRE(ISC_HASHMAP_VALID(hashmap)); 299 REQUIRE(valuep == NULL || *valuep == NULL); 300 301 uint8_t idx = hashmap->hindex; 302 hashmap_node_t *node = hashmap_find(hashmap, hashval, match, key, 303 &(uint32_t){ 0 }, &idx); 304 if (node == NULL) { 305 return ISC_R_NOTFOUND; 306 } 307 308 INSIST(node->key != NULL); 309 SET_IF_NOT_NULL(valuep, node->value); 310 return ISC_R_SUCCESS; 311 } 312 313 static bool 314 hashmap_delete_node(isc_hashmap_t *hashmap, hashmap_node_t *entry, 315 uint32_t hashval, uint32_t psl, const uint8_t idx, 316 size_t size) { 317 uint32_t pos; 318 uint32_t hash; 319 bool last = false; 320 321 hashmap->count--; 322 323 hash = isc_hash_bits32(hashval, hashmap->tables[idx].hashbits); 324 pos = (hash + psl) & hashmap->tables[idx].hashmask; 325 326 while (true) { 327 hashmap_node_t *node = NULL; 328 329 pos = (pos + 1) & hashmap->tables[idx].hashmask; 330 INSIST(pos < hashmap->tables[idx].size); 331 332 node = &hashmap->tables[idx].table[pos]; 333 334 if (node->key == NULL || node->psl == 0) { 335 break; 336 } 337 338 if ((pos % size) == 0) { 339 last = true; 340 } 341 342 node->psl--; 343 *entry = *node; 344 entry = &hashmap->tables[idx].table[pos]; 345 } 346 347 *entry = (hashmap_node_t){ 0 }; 348 return last; 349 } 350 351 static void 352 hashmap_rehash_one(isc_hashmap_t *hashmap) { 353 uint8_t oldidx = hashmap_nexttable(hashmap->hindex); 354 uint32_t oldsize = hashmap->tables[oldidx].size; 355 hashmap_node_t *oldtable = hashmap->tables[oldidx].table; 356 hashmap_node_t node; 357 358 /* Don't rehash when iterating */ 359 INSIST(atomic_load_acquire(&hashmap->iterators) == 0); 360 361 /* Find first non-empty node */ 362 while (hashmap->hiter < oldsize && oldtable[hashmap->hiter].key == NULL) 363 { 364 hashmap->hiter++; 365 } 366 367 /* Rehashing complete */ 368 if (hashmap->hiter == oldsize) { 369 hashmap_free_table(hashmap, hashmap_nexttable(hashmap->hindex), 370 false); 371 hashmap->hiter = 0; 372 return; 373 } 374 375 /* Move the first non-empty node from old table to new table */ 376 node = oldtable[hashmap->hiter]; 377 378 (void)hashmap_delete_node(hashmap, &oldtable[hashmap->hiter], 379 node.hashval, node.psl, oldidx, UINT32_MAX); 380 381 isc_result_t result = hashmap_add(hashmap, node.hashval, NULL, node.key, 382 node.value, NULL, hashmap->hindex); 383 INSIST(result == ISC_R_SUCCESS); 384 385 /* 386 * we don't increase the hiter here because the table has been reordered 387 * when we deleted the old node 388 */ 389 } 390 391 static uint32_t 392 grow_bits(isc_hashmap_t *hashmap) { 393 uint32_t newbits = hashmap->tables[hashmap->hindex].hashbits + 1; 394 size_t newsize = HASHSIZE(newbits); 395 396 while (hashmap->count > APPROX_40_PERCENT(newsize)) { 397 newbits += 1; 398 newsize = HASHSIZE(newbits); 399 } 400 if (newbits > HASHMAP_MAX_BITS) { 401 newbits = HASHMAP_MAX_BITS; 402 } 403 404 return newbits; 405 } 406 407 static uint32_t 408 shrink_bits(isc_hashmap_t *hashmap) { 409 uint32_t newbits = hashmap->tables[hashmap->hindex].hashbits - 1; 410 411 if (newbits <= HASHMAP_MIN_BITS) { 412 newbits = HASHMAP_MIN_BITS; 413 } 414 415 return newbits; 416 } 417 418 static void 419 hashmap_rehash_start_grow(isc_hashmap_t *hashmap) { 420 uint32_t newbits; 421 uint8_t oldindex = hashmap->hindex; 422 uint32_t oldbits = hashmap->tables[oldindex].hashbits; 423 uint8_t newindex = hashmap_nexttable(oldindex); 424 425 REQUIRE(!rehashing_in_progress(hashmap)); 426 427 newbits = grow_bits(hashmap); 428 429 if (newbits > oldbits) { 430 hashmap_create_table(hashmap, newindex, newbits); 431 hashmap->hindex = newindex; 432 } 433 } 434 435 static void 436 hashmap_rehash_start_shrink(isc_hashmap_t *hashmap) { 437 uint32_t newbits; 438 uint8_t oldindex = hashmap->hindex; 439 uint32_t oldbits = hashmap->tables[oldindex].hashbits; 440 uint8_t newindex = hashmap_nexttable(oldindex); 441 442 REQUIRE(!rehashing_in_progress(hashmap)); 443 444 newbits = shrink_bits(hashmap); 445 446 if (newbits < oldbits) { 447 hashmap_create_table(hashmap, newindex, newbits); 448 hashmap->hindex = newindex; 449 } 450 } 451 452 isc_result_t 453 isc_hashmap_delete(isc_hashmap_t *hashmap, const uint32_t hashval, 454 isc_hashmap_match_fn match, const void *key) { 455 REQUIRE(ISC_HASHMAP_VALID(hashmap)); 456 REQUIRE(key != NULL); 457 458 hashmap_node_t *node; 459 isc_result_t result = ISC_R_NOTFOUND; 460 uint32_t psl = 0; 461 uint8_t idx; 462 463 if (rehashing_in_progress(hashmap)) { 464 hashmap_rehash_one(hashmap); 465 } else if (under_threshold(hashmap)) { 466 hashmap_rehash_start_shrink(hashmap); 467 hashmap_rehash_one(hashmap); 468 } 469 470 /* Initialize idx after possible shrink start */ 471 idx = hashmap->hindex; 472 473 node = hashmap_find(hashmap, hashval, match, key, &psl, &idx); 474 if (node != NULL) { 475 INSIST(node->key != NULL); 476 (void)hashmap_delete_node(hashmap, node, hashval, psl, idx, 477 UINT32_MAX); 478 result = ISC_R_SUCCESS; 479 } 480 481 return result; 482 } 483 484 static bool 485 over_threshold(isc_hashmap_t *hashmap) { 486 uint32_t bits = hashmap->tables[hashmap->hindex].hashbits; 487 if (bits == HASHMAP_MAX_BITS) { 488 return false; 489 } 490 size_t threshold = APPROX_90_PERCENT(HASHSIZE(bits)); 491 return hashmap->count > threshold; 492 } 493 494 static bool 495 under_threshold(isc_hashmap_t *hashmap) { 496 uint32_t bits = hashmap->tables[hashmap->hindex].hashbits; 497 if (bits == HASHMAP_MIN_BITS) { 498 return false; 499 } 500 size_t threshold = APPROX_20_PERCENT(HASHSIZE(bits)); 501 return hashmap->count < threshold; 502 } 503 504 static isc_result_t 505 hashmap_add(isc_hashmap_t *hashmap, const uint32_t hashval, 506 isc_hashmap_match_fn match, const uint8_t *key, void *value, 507 void **foundp, uint8_t idx) { 508 uint32_t hash; 509 uint32_t psl = 0; 510 hashmap_node_t node; 511 hashmap_node_t *current = NULL; 512 uint32_t pos; 513 514 INSIST(atomic_load_acquire(&hashmap->iterators) == 0); 515 516 hash = isc_hash_bits32(hashval, hashmap->tables[idx].hashbits); 517 518 /* Initialize the node to be store to 'node' */ 519 hashmap_node_init(&node, hashval, key, value); 520 521 psl = 0; 522 while (true) { 523 pos = (hash + psl) & hashmap->tables[idx].hashmask; 524 525 current = &hashmap->tables[idx].table[pos]; 526 527 /* Found an empty node */ 528 if (current->key == NULL) { 529 break; 530 } 531 532 if (current->hashval == hashval) { 533 if (match != NULL && match(current->value, key)) { 534 SET_IF_NOT_NULL(foundp, current->value); 535 return ISC_R_EXISTS; 536 } 537 } 538 539 /* Found rich node */ 540 if (node.psl > current->psl) { 541 /* Swap the poor with the rich node */ 542 ISC_SWAP(*current, node); 543 } 544 545 node.psl++; 546 psl++; 547 } 548 549 /* 550 * Possible optimalization - start growing when the poor node is too far 551 */ 552 #if ISC_HASHMAP_GROW_FAST 553 if (psl > hashmap->hashbits[idx]) { 554 if (!rehashing_in_progress(hashmap)) { 555 hashmap_rehash_start_grow(hashmap); 556 } 557 } 558 #endif 559 560 hashmap->count++; 561 562 /* We found an empty place, store entry into current node */ 563 *current = node; 564 565 return ISC_R_SUCCESS; 566 } 567 568 isc_result_t 569 isc_hashmap_add(isc_hashmap_t *hashmap, const uint32_t hashval, 570 isc_hashmap_match_fn match, const void *key, void *value, 571 void **foundp) { 572 REQUIRE(ISC_HASHMAP_VALID(hashmap)); 573 REQUIRE(key != NULL); 574 575 if (rehashing_in_progress(hashmap)) { 576 hashmap_rehash_one(hashmap); 577 } else if (over_threshold(hashmap)) { 578 hashmap_rehash_start_grow(hashmap); 579 hashmap_rehash_one(hashmap); 580 } 581 582 if (rehashing_in_progress(hashmap)) { 583 uint8_t fidx = hashmap_nexttable(hashmap->hindex); 584 uint32_t psl; 585 586 /* Look for the value in the old table */ 587 hashmap_node_t *found = hashmap_find(hashmap, hashval, match, 588 key, &psl, &fidx); 589 if (found != NULL) { 590 INSIST(found->key != NULL); 591 SET_IF_NOT_NULL(foundp, found->value); 592 return ISC_R_EXISTS; 593 } 594 } 595 596 return hashmap_add(hashmap, hashval, match, key, value, foundp, 597 hashmap->hindex); 598 } 599 600 void 601 isc_hashmap_iter_create(isc_hashmap_t *hashmap, isc_hashmap_iter_t **iterp) { 602 isc_hashmap_iter_t *iter; 603 604 REQUIRE(ISC_HASHMAP_VALID(hashmap)); 605 REQUIRE(iterp != NULL && *iterp == NULL); 606 607 iter = isc_mem_get(hashmap->mctx, sizeof(*iter)); 608 *iter = (isc_hashmap_iter_t){ 609 .hashmap = hashmap, 610 .hindex = hashmap->hindex, 611 }; 612 613 (void)atomic_fetch_add_release(&hashmap->iterators, 1); 614 615 *iterp = iter; 616 } 617 618 void 619 isc_hashmap_iter_destroy(isc_hashmap_iter_t **iterp) { 620 isc_hashmap_iter_t *iter; 621 isc_hashmap_t *hashmap; 622 623 REQUIRE(iterp != NULL && *iterp != NULL); 624 625 iter = *iterp; 626 *iterp = NULL; 627 hashmap = iter->hashmap; 628 isc_mem_put(hashmap->mctx, iter, sizeof(*iter)); 629 630 INSIST(atomic_fetch_sub_release(&hashmap->iterators, 1) > 0); 631 } 632 633 static isc_result_t 634 isc__hashmap_iter_next(isc_hashmap_iter_t *iter) { 635 isc_hashmap_t *hashmap = iter->hashmap; 636 637 while (iter->i < iter->size && 638 hashmap->tables[iter->hindex].table[iter->i].key == NULL) 639 { 640 iter->i++; 641 } 642 643 if (iter->i < iter->size) { 644 iter->cur = &hashmap->tables[iter->hindex].table[iter->i]; 645 646 return ISC_R_SUCCESS; 647 } 648 649 if (try_nexttable(hashmap, iter->hindex)) { 650 iter->hindex = hashmap_nexttable(iter->hindex); 651 iter->i = hashmap->hiter; 652 iter->size = hashmap->tables[iter->hindex].size; 653 return isc__hashmap_iter_next(iter); 654 } 655 656 return ISC_R_NOMORE; 657 } 658 659 isc_result_t 660 isc_hashmap_iter_first(isc_hashmap_iter_t *iter) { 661 REQUIRE(iter != NULL); 662 663 iter->hindex = iter->hashmap->hindex; 664 iter->i = 0; 665 iter->size = iter->hashmap->tables[iter->hashmap->hindex].size; 666 667 return isc__hashmap_iter_next(iter); 668 } 669 670 isc_result_t 671 isc_hashmap_iter_next(isc_hashmap_iter_t *iter) { 672 REQUIRE(iter != NULL); 673 REQUIRE(iter->cur != NULL); 674 675 iter->i++; 676 677 return isc__hashmap_iter_next(iter); 678 } 679 680 isc_result_t 681 isc_hashmap_iter_delcurrent_next(isc_hashmap_iter_t *iter) { 682 REQUIRE(iter != NULL); 683 REQUIRE(iter->cur != NULL); 684 685 hashmap_node_t *node = 686 &iter->hashmap->tables[iter->hindex].table[iter->i]; 687 688 if (hashmap_delete_node(iter->hashmap, node, node->hashval, node->psl, 689 iter->hindex, iter->size)) 690 { 691 /* 692 * We have seen the new last element so reduce the size 693 * so we don't iterate over it twice. 694 */ 695 INSIST(iter->size != 0); 696 iter->size--; 697 } 698 699 return isc__hashmap_iter_next(iter); 700 } 701 702 void 703 isc_hashmap_iter_current(isc_hashmap_iter_t *it, void **valuep) { 704 REQUIRE(it != NULL); 705 REQUIRE(it->cur != NULL); 706 REQUIRE(valuep != NULL && *valuep == NULL); 707 708 *valuep = it->cur->value; 709 } 710 711 void 712 isc_hashmap_iter_currentkey(isc_hashmap_iter_t *it, const unsigned char **key) { 713 REQUIRE(it != NULL); 714 REQUIRE(it->cur != NULL); 715 REQUIRE(key != NULL && *key == NULL); 716 717 *key = it->cur->key; 718 } 719 720 unsigned int 721 isc_hashmap_count(isc_hashmap_t *hashmap) { 722 REQUIRE(ISC_HASHMAP_VALID(hashmap)); 723 724 return hashmap->count; 725 } 726
Indexes created Mon Mar 02 05:31:46 UTC 2026