1 /* $NetBSD: ht.c,v 1.1 2024/02/18 20:57:49 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 #include <inttypes.h> 17 #include <string.h> 18 19 #include <isc/hash.h> 20 #include <isc/ht.h> 21 #include <isc/magic.h> 22 #include <isc/mem.h> 23 #include <isc/result.h> 24 #include <isc/types.h> 25 #include <isc/util.h> 26 27 typedef struct isc_ht_node isc_ht_node_t; 28 29 #define ISC_HT_MAGIC ISC_MAGIC('H', 'T', 'a', 'b') 30 #define ISC_HT_VALID(ht) ISC_MAGIC_VALID(ht, ISC_HT_MAGIC) 31 32 #define HT_NO_BITS 0 33 #define HT_MIN_BITS 1 34 #define HT_MAX_BITS 32 35 #define HT_OVERCOMMIT 3 36 37 #define HT_NEXTTABLE(idx) ((idx == 0) ? 1 : 0) 38 #define TRY_NEXTTABLE(idx, ht) (idx == ht->hindex && rehashing_in_progress(ht)) 39 40 #define GOLDEN_RATIO_32 0x61C88647 41 42 #define HASHSIZE(bits) (UINT64_C(1) << (bits)) 43 44 struct isc_ht_node { 45 void *value; 46 isc_ht_node_t *next; 47 uint32_t hashval; 48 size_t keysize; 49 unsigned char key[]; 50 }; 51 52 struct isc_ht { 53 unsigned int magic; 54 isc_mem_t *mctx; 55 size_t count; 56 bool case_sensitive; 57 size_t size[2]; 58 uint8_t hashbits[2]; 59 isc_ht_node_t **table[2]; 60 uint8_t hindex; 61 uint32_t hiter; /* rehashing iterator */ 62 }; 63 64 struct isc_ht_iter { 65 isc_ht_t *ht; 66 size_t i; 67 uint8_t hindex; 68 isc_ht_node_t *cur; 69 }; 70 71 static isc_ht_node_t * 72 isc__ht_find(const isc_ht_t *ht, const unsigned char *key, 73 const uint32_t keysize, const uint32_t hashval, const uint8_t idx); 74 static void 75 isc__ht_add(isc_ht_t *ht, const unsigned char *key, const uint32_t keysize, 76 const uint32_t hashval, const uint8_t idx, void *value); 77 static isc_result_t 78 isc__ht_delete(isc_ht_t *ht, const unsigned char *key, const uint32_t keysize, 79 const uint32_t hashval, const uint8_t idx); 80 81 static uint32_t 82 rehash_bits(isc_ht_t *ht, size_t newcount); 83 84 static void 85 hashtable_new(isc_ht_t *ht, const uint8_t idx, const uint8_t bits); 86 static void 87 hashtable_free(isc_ht_t *ht, const uint8_t idx); 88 static void 89 hashtable_rehash(isc_ht_t *ht, uint32_t newbits); 90 static void 91 hashtable_rehash_one(isc_ht_t *ht); 92 static void 93 maybe_rehash(isc_ht_t *ht, size_t newcount); 94 95 static isc_result_t 96 isc__ht_iter_next(isc_ht_iter_t *it); 97 98 static uint8_t maptolower[] = { 99 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 100 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 101 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20, 0x21, 0x22, 0x23, 102 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, 103 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x3b, 104 0x3c, 0x3d, 0x3e, 0x3f, 0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 105 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 106 0x74, 0x75, 0x76, 0x77, 0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, 107 0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 108 0x6c, 0x6d, 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 109 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83, 110 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f, 111 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 0x9a, 0x9b, 112 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7, 113 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 0xb0, 0xb1, 0xb2, 0xb3, 114 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 115 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 116 0xcc, 0xcd, 0xce, 0xcf, 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 117 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 118 0xe4, 0xe5, 0xe6, 0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 119 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 120 0xfc, 0xfd, 0xfe, 0xff 121 }; 122 123 static int 124 memcasecmp(const void *vs1, const void *vs2, size_t len) { 125 uint8_t const *s1 = vs1; 126 uint8_t const *s2 = vs2; 127 for (size_t i = 0; i < len; i++) { 128 uint8_t u1 = s1[i]; 129 uint8_t u2 = s2[i]; 130 int U1 = maptolower[u1]; 131 int U2 = maptolower[u2]; 132 int diff = U1 - U2; 133 if (diff) { 134 return diff; 135 } 136 } 137 return 0; 138 } 139 140 static bool 141 isc__ht_node_match(isc_ht_node_t *node, const uint32_t hashval, 142 const uint8_t *key, uint32_t keysize, bool case_sensitive) { 143 return (node->hashval == hashval && node->keysize == keysize && 144 (case_sensitive ? (memcmp(node->key, key, keysize) == 0) 145 : (memcasecmp(node->key, key, keysize) == 0))); 146 } 147 148 static uint32_t 149 hash_32(uint32_t val, unsigned int bits) { 150 REQUIRE(bits <= HT_MAX_BITS); 151 /* High bits are more random. */ 152 return (val * GOLDEN_RATIO_32 >> (32 - bits)); 153 } 154 155 static bool 156 rehashing_in_progress(const isc_ht_t *ht) { 157 return (ht->table[HT_NEXTTABLE(ht->hindex)] != NULL); 158 } 159 160 static bool 161 hashtable_is_overcommited(isc_ht_t *ht) { 162 return (ht->count >= (ht->size[ht->hindex] * HT_OVERCOMMIT)); 163 } 164 165 static uint32_t 166 rehash_bits(isc_ht_t *ht, size_t newcount) { 167 uint32_t newbits = ht->hashbits[ht->hindex]; 168 169 while (newcount >= HASHSIZE(newbits) && newbits <= HT_MAX_BITS) { 170 newbits += 1; 171 } 172 173 return (newbits); 174 } 175 176 /* 177 * Rebuild the hashtable to reduce the load factor 178 */ 179 static void 180 hashtable_rehash(isc_ht_t *ht, uint32_t newbits) { 181 uint8_t oldindex = ht->hindex; 182 uint32_t oldbits = ht->hashbits[oldindex]; 183 uint8_t newindex = HT_NEXTTABLE(oldindex); 184 185 REQUIRE(ht->hashbits[oldindex] >= HT_MIN_BITS); 186 REQUIRE(ht->hashbits[oldindex] <= HT_MAX_BITS); 187 REQUIRE(ht->table[oldindex] != NULL); 188 189 REQUIRE(newbits <= HT_MAX_BITS); 190 REQUIRE(ht->hashbits[newindex] == HT_NO_BITS); 191 REQUIRE(ht->table[newindex] == NULL); 192 193 REQUIRE(newbits > oldbits); 194 195 hashtable_new(ht, newindex, newbits); 196 197 ht->hindex = newindex; 198 199 hashtable_rehash_one(ht); 200 } 201 202 static void 203 hashtable_rehash_one(isc_ht_t *ht) { 204 isc_ht_node_t **newtable = ht->table[ht->hindex]; 205 uint32_t oldsize = ht->size[HT_NEXTTABLE(ht->hindex)]; 206 isc_ht_node_t **oldtable = ht->table[HT_NEXTTABLE(ht->hindex)]; 207 isc_ht_node_t *node = NULL; 208 isc_ht_node_t *nextnode; 209 210 /* Find first non-empty node */ 211 while (ht->hiter < oldsize && oldtable[ht->hiter] == NULL) { 212 ht->hiter++; 213 } 214 215 /* Rehashing complete */ 216 if (ht->hiter == oldsize) { 217 hashtable_free(ht, HT_NEXTTABLE(ht->hindex)); 218 ht->hiter = 0; 219 return; 220 } 221 222 /* Move the first non-empty node from old hashtable to new hashtable */ 223 for (node = oldtable[ht->hiter]; node != NULL; node = nextnode) { 224 uint32_t hash = hash_32(node->hashval, 225 ht->hashbits[ht->hindex]); 226 nextnode = node->next; 227 node->next = newtable[hash]; 228 newtable[hash] = node; 229 } 230 231 oldtable[ht->hiter] = NULL; 232 233 ht->hiter++; 234 } 235 236 static void 237 maybe_rehash(isc_ht_t *ht, size_t newcount) { 238 uint32_t newbits = rehash_bits(ht, newcount); 239 240 if (ht->hashbits[ht->hindex] < newbits && newbits <= HT_MAX_BITS) { 241 hashtable_rehash(ht, newbits); 242 } 243 } 244 245 static void 246 hashtable_new(isc_ht_t *ht, const uint8_t idx, const uint8_t bits) { 247 size_t size; 248 REQUIRE(ht->hashbits[idx] == HT_NO_BITS); 249 REQUIRE(ht->table[idx] == NULL); 250 REQUIRE(bits >= HT_MIN_BITS); 251 REQUIRE(bits <= HT_MAX_BITS); 252 253 ht->hashbits[idx] = bits; 254 ht->size[idx] = HASHSIZE(ht->hashbits[idx]); 255 256 size = ht->size[idx] * sizeof(isc_ht_node_t *); 257 258 ht->table[idx] = isc_mem_get(ht->mctx, size); 259 memset(ht->table[idx], 0, size); 260 } 261 262 static void 263 hashtable_free(isc_ht_t *ht, const uint8_t idx) { 264 size_t size = ht->size[idx] * sizeof(isc_ht_node_t *); 265 266 for (size_t i = 0; i < ht->size[idx]; i++) { 267 isc_ht_node_t *node = ht->table[idx][i]; 268 while (node != NULL) { 269 isc_ht_node_t *next = node->next; 270 ht->count--; 271 isc_mem_put(ht->mctx, node, 272 sizeof(*node) + node->keysize); 273 node = next; 274 } 275 } 276 277 isc_mem_put(ht->mctx, ht->table[idx], size); 278 ht->hashbits[idx] = HT_NO_BITS; 279 ht->table[idx] = NULL; 280 } 281 282 void 283 isc_ht_init(isc_ht_t **htp, isc_mem_t *mctx, uint8_t bits, 284 unsigned int options) { 285 isc_ht_t *ht = NULL; 286 bool case_sensitive = ((options & ISC_HT_CASE_INSENSITIVE) == 0); 287 288 REQUIRE(htp != NULL && *htp == NULL); 289 REQUIRE(mctx != NULL); 290 REQUIRE(bits >= 1 && bits <= HT_MAX_BITS); 291 292 ht = isc_mem_get(mctx, sizeof(*ht)); 293 *ht = (isc_ht_t){ 294 .case_sensitive = case_sensitive, 295 }; 296 297 isc_mem_attach(mctx, &ht->mctx); 298 299 hashtable_new(ht, 0, bits); 300 301 ht->magic = ISC_HT_MAGIC; 302 303 *htp = ht; 304 } 305 306 void 307 isc_ht_destroy(isc_ht_t **htp) { 308 isc_ht_t *ht; 309 310 REQUIRE(htp != NULL); 311 REQUIRE(ISC_HT_VALID(*htp)); 312 313 ht = *htp; 314 *htp = NULL; 315 ht->magic = 0; 316 317 for (size_t i = 0; i <= 1; i++) { 318 if (ht->table[i] != NULL) { 319 hashtable_free(ht, i); 320 } 321 } 322 323 INSIST(ht->count == 0); 324 325 isc_mem_putanddetach(&ht->mctx, ht, sizeof(*ht)); 326 } 327 328 static void 329 isc__ht_add(isc_ht_t *ht, const unsigned char *key, const uint32_t keysize, 330 const uint32_t hashval, const uint8_t idx, void *value) { 331 isc_ht_node_t *node; 332 uint32_t hash; 333 334 hash = hash_32(hashval, ht->hashbits[idx]); 335 336 node = isc_mem_get(ht->mctx, sizeof(*node) + keysize); 337 *node = (isc_ht_node_t){ 338 .keysize = keysize, 339 .hashval = hashval, 340 .next = ht->table[idx][hash], 341 .value = value, 342 }; 343 344 memmove(node->key, key, keysize); 345 346 ht->count++; 347 ht->table[idx][hash] = node; 348 } 349 350 isc_result_t 351 isc_ht_add(isc_ht_t *ht, const unsigned char *key, const uint32_t keysize, 352 void *value) { 353 uint32_t hashval; 354 355 REQUIRE(ISC_HT_VALID(ht)); 356 REQUIRE(key != NULL && keysize > 0); 357 358 if (rehashing_in_progress(ht)) { 359 /* Rehash in progress */ 360 hashtable_rehash_one(ht); 361 } else if (hashtable_is_overcommited(ht)) { 362 /* Rehash requested */ 363 maybe_rehash(ht, ht->count); 364 } 365 366 hashval = isc_hash32(key, keysize, ht->case_sensitive); 367 368 if (isc__ht_find(ht, key, keysize, hashval, ht->hindex) != NULL) { 369 return (ISC_R_EXISTS); 370 } 371 372 isc__ht_add(ht, key, keysize, hashval, ht->hindex, value); 373 374 return (ISC_R_SUCCESS); 375 } 376 377 static isc_ht_node_t * 378 isc__ht_find(const isc_ht_t *ht, const unsigned char *key, 379 const uint32_t keysize, const uint32_t hashval, 380 const uint8_t idx) { 381 uint32_t hash; 382 uint8_t findex = idx; 383 384 nexttable: 385 hash = hash_32(hashval, ht->hashbits[findex]); 386 for (isc_ht_node_t *node = ht->table[findex][hash]; node != NULL; 387 node = node->next) 388 { 389 if (isc__ht_node_match(node, hashval, key, keysize, 390 ht->case_sensitive)) 391 { 392 return (node); 393 } 394 } 395 if (TRY_NEXTTABLE(findex, ht)) { 396 /* 397 * Rehashing in progress, check the other table 398 */ 399 findex = HT_NEXTTABLE(findex); 400 goto nexttable; 401 } 402 403 return (NULL); 404 } 405 406 isc_result_t 407 isc_ht_find(const isc_ht_t *ht, const unsigned char *key, 408 const uint32_t keysize, void **valuep) { 409 uint32_t hashval; 410 isc_ht_node_t *node; 411 412 REQUIRE(ISC_HT_VALID(ht)); 413 REQUIRE(key != NULL && keysize > 0); 414 REQUIRE(valuep == NULL || *valuep == NULL); 415 416 hashval = isc_hash32(key, keysize, ht->case_sensitive); 417 418 node = isc__ht_find(ht, key, keysize, hashval, ht->hindex); 419 if (node == NULL) { 420 return (ISC_R_NOTFOUND); 421 } 422 423 if (valuep != NULL) { 424 *valuep = node->value; 425 } 426 return (ISC_R_SUCCESS); 427 } 428 429 static isc_result_t 430 isc__ht_delete(isc_ht_t *ht, const unsigned char *key, const uint32_t keysize, 431 const uint32_t hashval, const uint8_t idx) { 432 isc_ht_node_t *prev = NULL; 433 uint32_t hash; 434 435 hash = hash_32(hashval, ht->hashbits[idx]); 436 437 for (isc_ht_node_t *node = ht->table[idx][hash]; node != NULL; 438 prev = node, node = node->next) 439 { 440 if (isc__ht_node_match(node, hashval, key, keysize, 441 ht->case_sensitive)) 442 { 443 if (prev == NULL) { 444 ht->table[idx][hash] = node->next; 445 } else { 446 prev->next = node->next; 447 } 448 isc_mem_put(ht->mctx, node, 449 sizeof(*node) + node->keysize); 450 ht->count--; 451 452 return (ISC_R_SUCCESS); 453 } 454 } 455 456 return (ISC_R_NOTFOUND); 457 } 458 459 isc_result_t 460 isc_ht_delete(isc_ht_t *ht, const unsigned char *key, const uint32_t keysize) { 461 uint32_t hashval; 462 uint8_t hindex; 463 isc_result_t result; 464 465 REQUIRE(ISC_HT_VALID(ht)); 466 REQUIRE(key != NULL && keysize > 0); 467 468 if (rehashing_in_progress(ht)) { 469 /* Rehash in progress */ 470 hashtable_rehash_one(ht); 471 } 472 473 hindex = ht->hindex; 474 hashval = isc_hash32(key, keysize, ht->case_sensitive); 475 nexttable: 476 result = isc__ht_delete(ht, key, keysize, hashval, hindex); 477 478 if (result == ISC_R_NOTFOUND && TRY_NEXTTABLE(hindex, ht)) { 479 /* 480 * Rehashing in progress, check the other table 481 */ 482 hindex = HT_NEXTTABLE(hindex); 483 goto nexttable; 484 } 485 486 return (result); 487 } 488 489 void 490 isc_ht_iter_create(isc_ht_t *ht, isc_ht_iter_t **itp) { 491 isc_ht_iter_t *it; 492 493 REQUIRE(ISC_HT_VALID(ht)); 494 REQUIRE(itp != NULL && *itp == NULL); 495 496 it = isc_mem_get(ht->mctx, sizeof(isc_ht_iter_t)); 497 *it = (isc_ht_iter_t){ 498 .ht = ht, 499 .hindex = ht->hindex, 500 }; 501 502 *itp = it; 503 } 504 505 void 506 isc_ht_iter_destroy(isc_ht_iter_t **itp) { 507 isc_ht_iter_t *it; 508 isc_ht_t *ht; 509 510 REQUIRE(itp != NULL && *itp != NULL); 511 512 it = *itp; 513 *itp = NULL; 514 ht = it->ht; 515 isc_mem_put(ht->mctx, it, sizeof(*it)); 516 } 517 518 isc_result_t 519 isc_ht_iter_first(isc_ht_iter_t *it) { 520 isc_ht_t *ht; 521 522 REQUIRE(it != NULL); 523 524 ht = it->ht; 525 526 it->hindex = ht->hindex; 527 it->i = 0; 528 529 return (isc__ht_iter_next(it)); 530 } 531 532 static isc_result_t 533 isc__ht_iter_next(isc_ht_iter_t *it) { 534 isc_ht_t *ht = it->ht; 535 536 while (it->i < ht->size[it->hindex] && 537 ht->table[it->hindex][it->i] == NULL) 538 { 539 it->i++; 540 } 541 542 if (it->i < ht->size[it->hindex]) { 543 it->cur = ht->table[it->hindex][it->i]; 544 545 return (ISC_R_SUCCESS); 546 } 547 548 if (TRY_NEXTTABLE(it->hindex, ht)) { 549 it->hindex = HT_NEXTTABLE(it->hindex); 550 it->i = 0; 551 return (isc__ht_iter_next(it)); 552 } 553 554 return (ISC_R_NOMORE); 555 } 556 557 isc_result_t 558 isc_ht_iter_next(isc_ht_iter_t *it) { 559 REQUIRE(it != NULL); 560 REQUIRE(it->cur != NULL); 561 562 it->cur = it->cur->next; 563 564 if (it->cur != NULL) { 565 return (ISC_R_SUCCESS); 566 } 567 568 it->i++; 569 570 return (isc__ht_iter_next(it)); 571 } 572 573 isc_result_t 574 isc_ht_iter_delcurrent_next(isc_ht_iter_t *it) { 575 isc_result_t result = ISC_R_SUCCESS; 576 isc_ht_node_t *dnode = NULL; 577 uint8_t dindex; 578 isc_ht_t *ht; 579 isc_result_t dresult; 580 581 REQUIRE(it != NULL); 582 REQUIRE(it->cur != NULL); 583 584 ht = it->ht; 585 dnode = it->cur; 586 dindex = it->hindex; 587 588 result = isc_ht_iter_next(it); 589 590 dresult = isc__ht_delete(ht, dnode->key, dnode->keysize, dnode->hashval, 591 dindex); 592 INSIST(dresult == ISC_R_SUCCESS); 593 594 return (result); 595 } 596 597 void 598 isc_ht_iter_current(isc_ht_iter_t *it, void **valuep) { 599 REQUIRE(it != NULL); 600 REQUIRE(it->cur != NULL); 601 REQUIRE(valuep != NULL && *valuep == NULL); 602 603 *valuep = it->cur->value; 604 } 605 606 void 607 isc_ht_iter_currentkey(isc_ht_iter_t *it, unsigned char **key, 608 size_t *keysize) { 609 REQUIRE(it != NULL); 610 REQUIRE(it->cur != NULL); 611 REQUIRE(key != NULL && *key == NULL); 612 613 *key = it->cur->key; 614 *keysize = it->cur->keysize; 615 } 616 617 size_t 618 isc_ht_count(const isc_ht_t *ht) { 619 REQUIRE(ISC_HT_VALID(ht)); 620 621 return (ht->count); 622 } 623
Indexes created Tue Mar 03 05:31:39 UTC 2026