00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030 #include "dhcpd.h"
00031
00032 #include <omapip/omapip_p.h>
00033 #include <limits.h>
00034 #include <ctype.h>
00035
00036 static unsigned
00037 find_length(const void *key,
00038 unsigned (*do_hash)(const void *, unsigned, unsigned))
00039 {
00040 if (do_hash == do_case_hash || do_hash == do_string_hash)
00041 return strlen((const char *)key);
00042 if (do_hash == do_number_hash)
00043 return sizeof(unsigned);
00044 if (do_hash == do_ip4_hash)
00045 return 4;
00046
00047 log_debug("Unexpected hash function at %s:%d.", MDL);
00048
00049
00050
00051
00052
00053 return 0;
00054 }
00055
00056 int new_hash_table (tp, count, file, line)
00057 struct hash_table **tp;
00058 unsigned count;
00059 const char *file;
00060 int line;
00061 {
00062 struct hash_table *rval;
00063 unsigned extra;
00064
00065 if (!tp) {
00066 log_error ("%s(%d): new_hash_table called with null pointer.",
00067 file, line);
00068 #if defined (POINTER_DEBUG)
00069 abort ();
00070 #endif
00071 return 0;
00072 }
00073 if (*tp) {
00074 log_error ("%s(%d): non-null target for new_hash_table.",
00075 file, line);
00076 #if defined (POINTER_DEBUG)
00077 abort ();
00078 #endif
00079 }
00080
00081
00082
00083
00084
00085 if (count <= 1)
00086 extra = 0;
00087 else
00088 extra = count - 1;
00089
00090 rval = dmalloc(sizeof(struct hash_table) +
00091 (extra * sizeof(struct hash_bucket *)), file, line);
00092 if (!rval)
00093 return 0;
00094 rval -> hash_count = count;
00095 *tp = rval;
00096 return 1;
00097 }
00098
00099 void free_hash_table (tp, file, line)
00100 struct hash_table **tp;
00101 const char *file;
00102 int line;
00103 {
00104 struct hash_table *ptr = *tp;
00105
00106 #if defined (DEBUG_MEMORY_LEAKAGE) || \
00107 defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
00108 int i;
00109 struct hash_bucket *hbc, *hbn = (struct hash_bucket *)0;
00110
00111 for (i = 0; i < ptr -> hash_count; i++) {
00112 for (hbc = ptr -> buckets [i]; hbc; hbc = hbn) {
00113 hbn = hbc -> next;
00114 if (ptr -> dereferencer && hbc -> value)
00115 (*ptr -> dereferencer) (&hbc -> value, MDL);
00116 }
00117 for (hbc = ptr -> buckets [i]; hbc; hbc = hbn) {
00118 hbn = hbc -> next;
00119 free_hash_bucket (hbc, MDL);
00120 }
00121 ptr -> buckets [i] = (struct hash_bucket *)0;
00122 }
00123 #endif
00124
00125 dfree((void *)ptr, MDL);
00126 *tp = (struct hash_table *)0;
00127 }
00128
00129 struct hash_bucket *free_hash_buckets;
00130
00131 #if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
00132 struct hash_bucket *hash_bucket_hunks;
00133
00134 void relinquish_hash_bucket_hunks ()
00135 {
00136 struct hash_bucket *c, *n, **p;
00137
00138
00139 p = &free_hash_buckets;
00140 for (c = free_hash_buckets; c; c = c -> next) {
00141 for (n = hash_bucket_hunks; n; n = n -> next) {
00142 if (c > n && c < n + 127) {
00143 *p = c -> next;
00144 n -> len++;
00145 break;
00146 }
00147 }
00148
00149
00150 if (!n)
00151 p = &c -> next;
00152 }
00153
00154 for (c = hash_bucket_hunks; c; c = n) {
00155 n = c -> next;
00156 if (c -> len != 126) {
00157 log_info ("hashbucket %lx hash_buckets %d free %u",
00158 (unsigned long)c, 127, c -> len);
00159 }
00160 dfree (c, MDL);
00161 }
00162 }
00163 #endif
00164
00165 struct hash_bucket *new_hash_bucket (file, line)
00166 const char *file;
00167 int line;
00168 {
00169 struct hash_bucket *rval;
00170 int i = 0;
00171 if (!free_hash_buckets) {
00172 rval = dmalloc (127 * sizeof (struct hash_bucket),
00173 file, line);
00174 if (!rval)
00175 return rval;
00176 # if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
00177 rval -> next = hash_bucket_hunks;
00178 hash_bucket_hunks = rval;
00179 hash_bucket_hunks -> len = 0;
00180 i++;
00181 rval++;
00182 #endif
00183 for (; i < 127; i++) {
00184 rval -> next = free_hash_buckets;
00185 free_hash_buckets = rval;
00186 rval++;
00187 }
00188 }
00189 rval = free_hash_buckets;
00190 free_hash_buckets = rval -> next;
00191 return rval;
00192 }
00193
00194 void free_hash_bucket (ptr, file, line)
00195 struct hash_bucket *ptr;
00196 const char *file;
00197 int line;
00198 {
00199 #if defined (DEBUG_MALLOC_POOL)
00200 struct hash_bucket *hp;
00201
00202 for (hp = free_hash_buckets; hp; hp = hp -> next) {
00203 if (hp == ptr) {
00204 log_error ("hash bucket freed twice!");
00205 abort ();
00206 }
00207 }
00208 #endif
00209 ptr -> next = free_hash_buckets;
00210 free_hash_buckets = ptr;
00211 }
00212
00213 int new_hash(struct hash_table **rp,
00214 hash_reference referencer,
00215 hash_dereference dereferencer,
00216 unsigned hsize,
00217 unsigned (*hasher)(const void *, unsigned, unsigned),
00218 const char *file, int line)
00219 {
00220 if (hsize == 0)
00221 hsize = DEFAULT_HASH_SIZE;
00222
00223 if (!new_hash_table (rp, hsize, file, line))
00224 return 0;
00225
00226 memset ((*rp)->buckets, 0, hsize * sizeof(struct hash_bucket *));
00227
00228 (*rp)->referencer = referencer;
00229 (*rp)->dereferencer = dereferencer;
00230 (*rp)->do_hash = hasher;
00231
00232 if (hasher == do_case_hash)
00233 (*rp)->cmp = casecmp;
00234 else
00235 (*rp)->cmp = memcmp;
00236
00237 return 1;
00238 }
00239
00240 unsigned
00241 do_case_hash(const void *name, unsigned len, unsigned size)
00242 {
00243 register unsigned accum = 0;
00244 register const unsigned char *s = name;
00245 int i = len;
00246 register unsigned c;
00247
00248 while (i--) {
00249
00250 c = *s++;
00251 if (isascii(c))
00252 c = tolower(c);
00253
00254
00255 accum = (accum << 1) + c;
00256
00257
00258 while (accum > 65535) {
00259 accum = (accum & 65535) + (accum >> 16);
00260 }
00261
00262 }
00263 return accum % size;
00264 }
00265
00266 unsigned
00267 do_string_hash(const void *name, unsigned len, unsigned size)
00268 {
00269 register unsigned accum = 0;
00270 register const unsigned char *s = (const unsigned char *)name;
00271 int i = len;
00272
00273 while (i--) {
00274
00275 accum = (accum << 1) + *s++;
00276
00277
00278 while (accum > 65535) {
00279 accum = (accum & 65535) + (accum >> 16);
00280 }
00281 }
00282 return accum % size;
00283 }
00284
00285
00286
00287
00288
00289
00290 unsigned
00291 do_id_hash(const void *name, unsigned len, unsigned size)
00292 {
00293 register unsigned accum = 0;
00294 register const unsigned char *s = (const unsigned char *)name;
00295 const unsigned char *end = s + len;
00296
00297 if (len == 0)
00298 return 0;
00299
00300
00301
00302
00303
00304
00305 switch (len % 3) {
00306 case 0:
00307 break;
00308 case 2:
00309 accum ^= *s++ << 8;
00310 case 1:
00311 accum ^= *s++;
00312 break;
00313 }
00314
00315 while (s < end) {
00316 accum ^= *s++ << 16;
00317 accum ^= *s++ << 8;
00318 accum ^= *s++;
00319 }
00320
00321 return accum % size;
00322 }
00323
00324 unsigned
00325 do_number_hash(const void *key, unsigned len, unsigned size)
00326 {
00327 register unsigned number = *((const unsigned *)key);
00328
00329 return number % size;
00330 }
00331
00332 unsigned
00333 do_ip4_hash(const void *key, unsigned len, unsigned size)
00334 {
00335 u_int32_t number;
00336
00337 memcpy(&number, key, 4);
00338
00339 number = ntohl(number);
00340
00341 return number % size;
00342 }
00343
00344 unsigned char *
00345 hash_report(struct hash_table *table)
00346 {
00347 static unsigned char retbuf[sizeof("Contents/Size (%): "
00348 "2147483647/2147483647 "
00349 "(2147483647%). "
00350 "Min/max: 2147483647/2147483647")];
00351 unsigned curlen, pct, contents=0, minlen=UINT_MAX, maxlen=0;
00352 unsigned i;
00353 struct hash_bucket *bp;
00354
00355 if (table == NULL)
00356 return (unsigned char *) "No table.";
00357
00358 if (table->hash_count == 0)
00359 return (unsigned char *) "Invalid hash table.";
00360
00361 for (i = 0 ; i < table->hash_count ; i++) {
00362 curlen = 0;
00363
00364 bp = table->buckets[i];
00365 while (bp != NULL) {
00366 curlen++;
00367 bp = bp->next;
00368 }
00369
00370 if (curlen < minlen)
00371 minlen = curlen;
00372 if (curlen > maxlen)
00373 maxlen = curlen;
00374
00375 contents += curlen;
00376 }
00377
00378 if (contents >= (UINT_MAX / 100))
00379 pct = contents / ((table->hash_count / 100) + 1);
00380 else
00381 pct = (contents * 100) / table->hash_count;
00382
00383 if (contents > 2147483647 ||
00384 table->hash_count > 2147483647 ||
00385 pct > 2147483647 ||
00386 minlen > 2147483647 ||
00387 maxlen > 2147483647)
00388 return (unsigned char *) "Report out of range for display.";
00389
00390 sprintf((char *)retbuf,
00391 "Contents/Size (%%): %u/%u (%u%%). Min/max: %u/%u",
00392 contents, table->hash_count, pct, minlen, maxlen);
00393
00394 return retbuf;
00395 }
00396
00397 void add_hash (table, key, len, pointer, file, line)
00398 struct hash_table *table;
00399 unsigned len;
00400 const void *key;
00401 hashed_object_t *pointer;
00402 const char *file;
00403 int line;
00404 {
00405 int hashno;
00406 struct hash_bucket *bp;
00407 void *foo;
00408
00409 if (!table)
00410 return;
00411
00412 if (!len)
00413 len = find_length(key, table->do_hash);
00414
00415 hashno = (*table->do_hash)(key, len, table->hash_count);
00416 bp = new_hash_bucket (file, line);
00417
00418 if (!bp) {
00419 log_error ("Can't add entry to hash table: no memory.");
00420 return;
00421 }
00422 bp -> name = key;
00423 if (table -> referencer) {
00424 foo = &bp -> value;
00425 (*(table -> referencer)) (foo, pointer, file, line);
00426 } else
00427 bp -> value = pointer;
00428 bp -> next = table -> buckets [hashno];
00429 bp -> len = len;
00430 table -> buckets [hashno] = bp;
00431 }
00432
00433 void delete_hash_entry (table, key, len, file, line)
00434 struct hash_table *table;
00435 unsigned len;
00436 const void *key;
00437 const char *file;
00438 int line;
00439 {
00440 int hashno;
00441 struct hash_bucket *bp, *pbp = (struct hash_bucket *)0;
00442 void *foo;
00443
00444 if (!table)
00445 return;
00446
00447 if (!len)
00448 len = find_length(key, table->do_hash);
00449
00450 hashno = (*table->do_hash)(key, len, table->hash_count);
00451
00452
00453
00454 for (bp = table -> buckets [hashno]; bp; bp = bp -> next) {
00455 if ((!bp -> len &&
00456 !strcmp ((const char *)bp->name, key)) ||
00457 (bp -> len == len &&
00458 !(table -> cmp)(bp->name, key, len))) {
00459 if (pbp) {
00460 pbp -> next = bp -> next;
00461 } else {
00462 table -> buckets [hashno] = bp -> next;
00463 }
00464 if (bp -> value && table -> dereferencer) {
00465 foo = &bp -> value;
00466 (*(table -> dereferencer)) (foo, file, line);
00467 }
00468 free_hash_bucket (bp, file, line);
00469 break;
00470 }
00471 pbp = bp;
00472 }
00473 }
00474
00475 int hash_lookup (vp, table, key, len, file, line)
00476 hashed_object_t **vp;
00477 struct hash_table *table;
00478 const void *key;
00479 unsigned len;
00480 const char *file;
00481 int line;
00482 {
00483 int hashno;
00484 struct hash_bucket *bp;
00485
00486 if (!table)
00487 return 0;
00488 if (!len)
00489 len = find_length(key, table->do_hash);
00490
00491 if (*vp != NULL) {
00492 log_fatal("Internal inconsistency: storage value has not been "
00493 "initialized to zero (from %s:%d).", file, line);
00494 }
00495
00496 hashno = (*table->do_hash)(key, len, table->hash_count);
00497
00498 for (bp = table -> buckets [hashno]; bp; bp = bp -> next) {
00499 if (len == bp -> len
00500 && !(*table->cmp)(bp->name, key, len)) {
00501 if (table -> referencer)
00502 (*table -> referencer) (vp, bp -> value,
00503 file, line);
00504 else
00505 *vp = bp -> value;
00506 return 1;
00507 }
00508 }
00509 return 0;
00510 }
00511
00512 int hash_foreach (struct hash_table *table, hash_foreach_func func)
00513 {
00514 int i;
00515 struct hash_bucket *bp, *next;
00516 int count = 0;
00517
00518 if (!table)
00519 return 0;
00520
00521 for (i = 0; i < table -> hash_count; i++) {
00522 bp = table -> buckets [i];
00523 while (bp) {
00524 next = bp -> next;
00525 if ((*func)(bp->name, bp->len, bp->value)
00526 != ISC_R_SUCCESS)
00527 return count;
00528 bp = next;
00529 count++;
00530 }
00531 }
00532 return count;
00533 }
00534
00535 int casecmp (const void *v1, const void *v2, size_t len)
00536 {
00537 size_t i;
00538 const unsigned char *s = v1;
00539 const unsigned char *t = v2;
00540
00541 for (i = 0; i < len; i++)
00542 {
00543 int c1, c2;
00544 if (isascii(s[i]))
00545 c1 = tolower(s[i]);
00546 else
00547 c1 = s[i];
00548
00549 if (isascii(t[i]))
00550 c2 = tolower(t[i]);
00551 else
00552 c2 = t[i];
00553
00554 if (c1 < c2)
00555 return -1;
00556 if (c1 > c2)
00557 return 1;
00558 }
00559 return 0;
00560 }