omapip/hash.c

Go to the documentation of this file.
00001 /* hash.c
00002 
00003    Routines for manipulating hash tables... */
00004 
00005 /*
00006  * Copyright (c) 2009-2010,2014 by Internet Systems Consortium, Inc. ("ISC")
00007  * Copyright (c) 2004-2007 by Internet Systems Consortium, Inc. ("ISC")
00008  * Copyright (c) 1995-2003 by Internet Software Consortium
00009  *
00010  * Permission to use, copy, modify, and distribute this software for any
00011  * purpose with or without fee is hereby granted, provided that the above
00012  * copyright notice and this permission notice appear in all copies.
00013  *
00014  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
00015  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
00016  * MERCHANTABILITY AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR
00017  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
00018  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
00019  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
00020  * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
00021  *
00022  *   Internet Systems Consortium, Inc.
00023  *   950 Charter Street
00024  *   Redwood City, CA 94063
00025  *   <info@isc.org>
00026  *   https://www.isc.org/
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          * If we get a hash function we don't specifically expect
00050          * return a length of 0, this covers the case where a client
00051          * id has a length of 0.
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         /* There is one hash bucket in the structure.  Allocate extra
00082          * memory beyond the end of the structure to fulfill the requested
00083          * count ("count - 1").  Do not let there be less than one.
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         /* Account for all the hash buckets on the free list. */
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                 /* If we didn't delete the hash bucket from the free list,
00149                    advance the pointer. */
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                 /* Make the hash case-insensitive. */
00250                 c = *s++;
00251                 if (isascii(c))
00252                         c = tolower(c);
00253 
00254                 /* Add the character in... */
00255                 accum = (accum << 1) + c;
00256 
00257                 /* Add carry back in... */
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                 /* Add the character in... */
00275                 accum = (accum << 1) + *s++;
00276 
00277                 /* Add carry back in... */
00278                 while (accum > 65535) {
00279                         accum = (accum & 65535) + (accum >> 16);
00280                 }
00281         }
00282         return accum % size;
00283 }
00284 
00285 /* Client identifiers are generally 32-bits of ordinary
00286  * non-randomness followed by 24-bits of unordinary randomness.
00287  * So, end-align in 24-bit chunks, and xor any preceding data
00288  * just to mix it up a little.
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          * The switch handles our starting conditions, then we hash the
00302          * remaining bytes in groups of 3
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         /* Go through the list looking for an entry that matches;
00453            if we find it, delete it. */
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;       /* jwg, 9/6/96 - nice catch! */
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 }

Generated on 5 Apr 2014 for ISC DHCP by  doxygen 1.6.1