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