1 /* $NetBSD: hash.c,v 1.3 2022/04/03 01:10:59 christos Exp $ */ 2 3 /* hash.c 4 5 Routines for manipulating hash tables... */ 6 7 /* 8 * Copyright (C) 2004-2022 Internet Systems Consortium, Inc. ("ISC") 9 * Copyright (c) 1995-2003 by Internet Software Consortium 10 * 11 * This Source Code Form is subject to the terms of the Mozilla Public 12 * License, v. 2.0. If a copy of the MPL was not distributed with this 13 * file, You can obtain one at http://mozilla.org/MPL/2.0/. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES 16 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 17 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR 18 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 19 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 20 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT 21 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 22 * 23 * Internet Systems Consortium, Inc. 24 * PO Box 360 25 * Newmarket, NH 03857 USA 26 * <info (at) isc.org> 27 * https://www.isc.org/ 28 * 29 */ 30 31 #include <sys/cdefs.h> 32 __RCSID("$NetBSD: hash.c,v 1.3 2022/04/03 01:10:59 christos Exp $"); 33 34 #include "dhcpd.h" 35 36 #include <omapip/omapip_p.h> 37 #include <limits.h> 38 #include <ctype.h> 39 40 static unsigned 41 find_length(const void *key, 42 unsigned (*do_hash)(const void *, unsigned, unsigned)) 43 { 44 if (do_hash == do_case_hash || do_hash == do_string_hash) 45 return strlen((const char *)key); 46 if (do_hash == do_number_hash) 47 return sizeof(unsigned); 48 if (do_hash == do_ip4_hash) 49 return 4; 50 51 log_debug("Unexpected hash function at %s:%d.", MDL); 52 /* 53 * If we get a hash function we don't specifically expect 54 * return a length of 0, this covers the case where a client 55 * id has a length of 0. 56 */ 57 return 0; 58 } 59 60 int new_hash_table (tp, count, file, line) 61 struct hash_table **tp; 62 unsigned count; 63 const char *file; 64 int line; 65 { 66 struct hash_table *rval; 67 unsigned extra; 68 69 if (!tp) { 70 log_error ("%s(%d): new_hash_table called with null pointer.", 71 file, line); 72 #if defined (POINTER_DEBUG) 73 abort (); 74 #endif 75 return 0; 76 } 77 if (*tp) { 78 log_error ("%s(%d): non-null target for new_hash_table.", 79 file, line); 80 #if defined (POINTER_DEBUG) 81 abort (); 82 #endif 83 } 84 85 /* There is one hash bucket in the structure. Allocate extra 86 * memory beyond the end of the structure to fulfill the requested 87 * count ("count - 1"). Do not let there be less than one. 88 */ 89 if (count <= 1) 90 extra = 0; 91 else 92 extra = count - 1; 93 94 rval = dmalloc(sizeof(struct hash_table) + 95 (extra * sizeof(struct hash_bucket *)), file, line); 96 if (!rval) 97 return 0; 98 rval -> hash_count = count; 99 *tp = rval; 100 return 1; 101 } 102 103 void free_hash_table (tp, file, line) 104 struct hash_table **tp; 105 const char *file; 106 int line; 107 { 108 struct hash_table *ptr = *tp; 109 110 #if defined (DEBUG_MEMORY_LEAKAGE) || \ 111 defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT) 112 int i; 113 struct hash_bucket *hbc, *hbn = (struct hash_bucket *)0; 114 115 for (i = 0; ptr != NULL && i < ptr -> hash_count; i++) { 116 for (hbc = ptr -> buckets [i]; hbc; hbc = hbn) { 117 hbn = hbc -> next; 118 if (ptr -> dereferencer && hbc -> value) 119 (*ptr -> dereferencer) (&hbc -> value, MDL); 120 } 121 for (hbc = ptr -> buckets [i]; hbc; hbc = hbn) { 122 hbn = hbc -> next; 123 free_hash_bucket (hbc, MDL); 124 } 125 ptr -> buckets [i] = (struct hash_bucket *)0; 126 } 127 #endif 128 129 dfree((void *)ptr, MDL); 130 *tp = (struct hash_table *)0; 131 } 132 133 struct hash_bucket *free_hash_buckets; 134 135 #if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT) 136 struct hash_bucket *hash_bucket_hunks; 137 138 void relinquish_hash_bucket_hunks () 139 { 140 struct hash_bucket *c, *n, **p; 141 142 /* Account for all the hash buckets on the free list. */ 143 p = &free_hash_buckets; 144 for (c = free_hash_buckets; c; c = c -> next) { 145 for (n = hash_bucket_hunks; n; n = n -> next) { 146 if (c > n && c < n + 127) { 147 *p = c -> next; 148 n -> len++; 149 break; 150 } 151 } 152 /* If we didn't delete the hash bucket from the free list, 153 advance the pointer. */ 154 if (!n) 155 p = &c -> next; 156 } 157 158 for (c = hash_bucket_hunks; c; c = n) { 159 n = c -> next; 160 if (c -> len != 126) { 161 log_info ("hashbucket %lx hash_buckets %d free %u", 162 (unsigned long)c, 127, c -> len); 163 } 164 dfree (c, MDL); 165 } 166 } 167 #endif 168 169 struct hash_bucket *new_hash_bucket (file, line) 170 const char *file; 171 int line; 172 { 173 struct hash_bucket *rval; 174 int i = 0; 175 if (!free_hash_buckets) { 176 rval = dmalloc (127 * sizeof (struct hash_bucket), 177 file, line); 178 if (!rval) 179 return rval; 180 # if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT) 181 rval -> next = hash_bucket_hunks; 182 hash_bucket_hunks = rval; 183 hash_bucket_hunks -> len = 0; 184 i++; 185 rval++; 186 #endif 187 for (; i < 127; i++) { 188 rval -> next = free_hash_buckets; 189 free_hash_buckets = rval; 190 rval++; 191 } 192 } 193 rval = free_hash_buckets; 194 free_hash_buckets = rval -> next; 195 return rval; 196 } 197 198 void free_hash_bucket (ptr, file, line) 199 struct hash_bucket *ptr; 200 const char *file; 201 int line; 202 { 203 #if defined (DEBUG_MALLOC_POOL) 204 struct hash_bucket *hp; 205 206 for (hp = free_hash_buckets; hp; hp = hp -> next) { 207 if (hp == ptr) { 208 log_error ("hash bucket freed twice!"); 209 abort (); 210 } 211 } 212 #endif 213 ptr -> next = free_hash_buckets; 214 free_hash_buckets = ptr; 215 } 216 217 int new_hash(struct hash_table **rp, 218 hash_reference referencer, 219 hash_dereference dereferencer, 220 unsigned hsize, 221 unsigned (*hasher)(const void *, unsigned, unsigned), 222 const char *file, int line) 223 { 224 if (hsize == 0) 225 hsize = DEFAULT_HASH_SIZE; 226 227 if (!new_hash_table (rp, hsize, file, line)) 228 return 0; 229 230 memset ((*rp)->buckets, 0, hsize * sizeof(struct hash_bucket *)); 231 232 (*rp)->referencer = referencer; 233 (*rp)->dereferencer = dereferencer; 234 (*rp)->do_hash = hasher; 235 236 if (hasher == do_case_hash) 237 (*rp)->cmp = casecmp; 238 else 239 (*rp)->cmp = memcmp; 240 241 return 1; 242 } 243 244 unsigned 245 do_case_hash(const void *name, unsigned len, unsigned size) 246 { 247 register unsigned accum = 0; 248 register const unsigned char *s = name; 249 int i = len; 250 register unsigned c; 251 252 while (i--) { 253 /* Make the hash case-insensitive. */ 254 c = *s++; 255 if (isascii(c)) 256 c = tolower(c); 257 258 /* Add the character in... */ 259 accum = (accum << 1) + c; 260 261 /* Add carry back in... */ 262 while (accum > 65535) { 263 accum = (accum & 65535) + (accum >> 16); 264 } 265 266 } 267 return accum % size; 268 } 269 270 unsigned 271 do_string_hash(const void *name, unsigned len, unsigned size) 272 { 273 register unsigned accum = 0; 274 register const unsigned char *s = (const unsigned char *)name; 275 int i = len; 276 277 while (i--) { 278 /* Add the character in... */ 279 accum = (accum << 1) + *s++; 280 281 /* Add carry back in... */ 282 while (accum > 65535) { 283 accum = (accum & 65535) + (accum >> 16); 284 } 285 } 286 return accum % size; 287 } 288 289 /* Client identifiers are generally 32-bits of ordinary 290 * non-randomness followed by 24-bits of unordinary randomness. 291 * So, end-align in 24-bit chunks, and xor any preceding data 292 * just to mix it up a little. 293 */ 294 unsigned 295 do_id_hash(const void *name, unsigned len, unsigned size) 296 { 297 register unsigned accum = 0; 298 register const unsigned char *s = (const unsigned char *)name; 299 const unsigned char *end = s + len; 300 301 if (len == 0) 302 return 0; 303 304 /* 305 * The switch handles our starting conditions, then we hash the 306 * remaining bytes in groups of 3 307 */ 308 309 switch (len % 3) { 310 case 0: 311 break; 312 case 2: 313 accum ^= *s++ << 8; 314 case 1: 315 accum ^= *s++; 316 break; 317 } 318 319 while (s < end) { 320 accum ^= *s++ << 16; 321 accum ^= *s++ << 8; 322 accum ^= *s++; 323 } 324 325 return accum % size; 326 } 327 328 unsigned 329 do_number_hash(const void *key, unsigned len, unsigned size) 330 { 331 register unsigned number = *((const unsigned *)key); 332 333 return number % size; 334 } 335 336 unsigned 337 do_ip4_hash(const void *key, unsigned len, unsigned size) 338 { 339 u_int32_t number; 340 341 memcpy(&number, key, 4); 342 343 number = ntohl(number); 344 345 return number % size; 346 } 347 348 unsigned char * 349 hash_report(struct hash_table *table) 350 { 351 static unsigned char retbuf[sizeof("Contents/Size (%): " 352 "2147483647/2147483647 " 353 "(2147483647%). " 354 "Min/max: 2147483647/2147483647")]; 355 unsigned curlen, pct, contents=0, minlen=UINT_MAX, maxlen=0; 356 unsigned i; 357 struct hash_bucket *bp; 358 359 if (table == NULL) 360 return (unsigned char *) "No table."; 361 362 if (table->hash_count == 0) 363 return (unsigned char *) "Invalid hash table."; 364 365 for (i = 0 ; i < table->hash_count ; i++) { 366 curlen = 0; 367 368 bp = table->buckets[i]; 369 while (bp != NULL) { 370 curlen++; 371 bp = bp->next; 372 } 373 374 if (curlen < minlen) 375 minlen = curlen; 376 if (curlen > maxlen) 377 maxlen = curlen; 378 379 contents += curlen; 380 } 381 382 if (contents >= (UINT_MAX / 100)) 383 pct = contents / ((table->hash_count / 100) + 1); 384 else 385 pct = (contents * 100) / table->hash_count; 386 387 if (contents > 2147483647 || 388 table->hash_count > 2147483647 || 389 pct > 2147483647 || 390 minlen > 2147483647 || 391 maxlen > 2147483647) 392 return (unsigned char *) "Report out of range for display."; 393 394 sprintf((char *)retbuf, 395 "Contents/Size (%%): %u/%u (%u%%). Min/max: %u/%u", 396 contents, table->hash_count, pct, minlen, maxlen); 397 398 return retbuf; 399 } 400 401 void add_hash (table, key, len, pointer, file, line) 402 struct hash_table *table; 403 unsigned len; 404 const void *key; 405 hashed_object_t *pointer; 406 const char *file; 407 int line; 408 { 409 int hashno; 410 struct hash_bucket *bp; 411 void *foo; 412 413 if (!table) 414 return; 415 416 if (!len) 417 len = find_length(key, table->do_hash); 418 419 hashno = (*table->do_hash)(key, len, table->hash_count); 420 bp = new_hash_bucket (file, line); 421 422 if (!bp) { 423 log_error ("Can't add entry to hash table: no memory."); 424 return; 425 } 426 bp -> name = key; 427 if (table -> referencer) { 428 foo = &bp -> value; 429 (*(table -> referencer)) (foo, pointer, file, line); 430 } else 431 bp -> value = pointer; 432 bp -> next = table -> buckets [hashno]; 433 bp -> len = len; 434 table -> buckets [hashno] = bp; 435 } 436 437 void delete_hash_entry (table, key, len, file, line) 438 struct hash_table *table; 439 unsigned len; 440 const void *key; 441 const char *file; 442 int line; 443 { 444 int hashno; 445 struct hash_bucket *bp, *pbp = (struct hash_bucket *)0; 446 void *foo; 447 448 if (!table) 449 return; 450 451 if (!len) 452 len = find_length(key, table->do_hash); 453 454 hashno = (*table->do_hash)(key, len, table->hash_count); 455 456 /* Go through the list looking for an entry that matches; 457 if we find it, delete it. */ 458 for (bp = table -> buckets [hashno]; bp; bp = bp -> next) { 459 if ((!bp -> len && 460 !strcmp ((const char *)bp->name, key)) || 461 (bp -> len == len && 462 !(table -> cmp)(bp->name, key, len))) { 463 if (pbp) { 464 pbp -> next = bp -> next; 465 } else { 466 table -> buckets [hashno] = bp -> next; 467 } 468 if (bp -> value && table -> dereferencer) { 469 foo = &bp -> value; 470 (*(table -> dereferencer)) (foo, file, line); 471 } 472 free_hash_bucket (bp, file, line); 473 break; 474 } 475 pbp = bp; /* jwg, 9/6/96 - nice catch! */ 476 } 477 } 478 479 int hash_lookup (vp, table, key, len, file, line) 480 hashed_object_t **vp; 481 struct hash_table *table; 482 const void *key; 483 unsigned len; 484 const char *file; 485 int line; 486 { 487 int hashno; 488 struct hash_bucket *bp; 489 490 if (!table) 491 return 0; 492 if (!len) 493 len = find_length(key, table->do_hash); 494 495 if (*vp != NULL) { 496 log_fatal("Internal inconsistency: storage value has not been " 497 "initialized to zero (from %s:%d).", file, line); 498 } 499 500 hashno = (*table->do_hash)(key, len, table->hash_count); 501 502 for (bp = table -> buckets [hashno]; bp; bp = bp -> next) { 503 if (len == bp -> len 504 && !(*table->cmp)(bp->name, key, len)) { 505 if (table -> referencer) 506 (*table -> referencer) (vp, bp -> value, 507 file, line); 508 else 509 *vp = bp -> value; 510 return 1; 511 } 512 } 513 return 0; 514 } 515 516 int hash_foreach (struct hash_table *table, hash_foreach_func func) 517 { 518 int i; 519 struct hash_bucket *bp, *next; 520 int count = 0; 521 522 if (!table) 523 return 0; 524 525 for (i = 0; i < table -> hash_count; i++) { 526 bp = table -> buckets [i]; 527 while (bp) { 528 next = bp -> next; 529 if ((*func)(bp->name, bp->len, bp->value) 530 != ISC_R_SUCCESS) 531 return count; 532 bp = next; 533 count++; 534 } 535 } 536 return count; 537 } 538 539 int casecmp (const void *v1, const void *v2, size_t len) 540 { 541 size_t i; 542 const unsigned char *s = v1; 543 const unsigned char *t = v2; 544 545 for (i = 0; i < len; i++) 546 { 547 int c1, c2; 548 if (isascii(s[i])) 549 c1 = tolower(s[i]); 550 else 551 c1 = s[i]; 552 553 if (isascii(t[i])) 554 c2 = tolower(t[i]); 555 else 556 c2 = t[i]; 557 558 if (c1 < c2) 559 return -1; 560 if (c1 > c2) 561 return 1; 562 } 563 return 0; 564 } 565
Indexes created Sun Mar 01 05:31:48 UTC 2026