dist/dhcp/omapip/hash.c

   1 /* hash.c
   2
   3    Routines for manipulating hash tables... */
   4
   5 /*
   6  * Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC")
   7  * Copyright (c) 1995-2003 by Internet Software Consortium
   8  *
   9  * Permission to use, copy, modify, and distribute this software for any
  10  * purpose with or without fee is hereby granted, provided that the above
  11  * copyright notice and this permission notice appear in all copies.
  12  *
  13  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
  14  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  15  * MERCHANTABILITY AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR
  16  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  17  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  18  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
  19  * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  20  *
  21  *   Internet Systems Consortium, Inc.
  22  *   950 Charter Street
  23  *   Redwood City, CA 94063
  24  *   <info@isc.org>
  25  *   http://www.isc.org/
  26  *
  27  * This software has been written for Internet Systems Consortium
  28  * by Ted Lemon in cooperation with Vixie Enterprises and Nominum, Inc.
  29  * To learn more about Internet Systems Consortium, see
  30  * ``http://www.isc.org/''.  To learn more about Vixie Enterprises,
  31  * see ``http://www.vix.com''.   To learn more about Nominum, Inc., see
  32  * ``http://www.nominum.com''.
  33  */
  34
  35 #ifndef lint
  36 static char copyright[] =
  37 "$Id: hash.c,v 1.5 2005/08/11 17:13:30 drochner Exp $ Copyright (c) 2004 Internet Systems Consortium.  All rights reserved.\n";
  38 #endif /* not lint */
  39
  40 #include <omapip/omapip_p.h>
  41 #include <ctype.h>
  42
  43 static int do_hash (const unsigned char *, unsigned, unsigned);
  44 static int do_case_hash (const unsigned char *, unsigned, unsigned);
  45
  46 int new_hash_table (tp, count, file, line)
  47         struct hash_table **tp;
  48         int count;
  49         const char *file;
  50         int line;
  51 {
  52         struct hash_table *rval;
  53
  54         if (!tp) {
  55                 log_error ("%s(%d): new_hash_table called with null pointer.",
  56                            file, line);
  57 #if defined (POINTER_DEBUG)
  58                 abort ();
  59 #endif
  60                 return 0;
  61         }
  62         if (*tp) {
  63                 log_error ("%s(%d): non-null target for new_hash_table.",
  64                            file, line);
  65 #if defined (POINTER_DEBUG)
  66                 abort ();
  67 #endif
  68         }
  69         rval = dmalloc (sizeof (struct hash_table) -
  70                         (DEFAULT_HASH_SIZE * sizeof (struct hash_bucket *)) +
  71                         (count * sizeof (struct hash_bucket *)), file, line);
  72         if (!rval)
  73                 return 0;
  74         rval -> hash_count = count;
  75         *tp = rval;
  76         return 1;
  77 }
  78
  79 void free_hash_table (tp, file, line)
  80         struct hash_table **tp;
  81         const char *file;
  82         int line;
  83 {
  84         struct hash_table *ptr = *tp;
  85 #if defined (DEBUG_MEMORY_LEAKAGE) || \
  86                 defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
  87         int i;
  88         struct hash_bucket *hbc, *hbn = (struct hash_bucket *)0;
  89
  90         for (i = 0; i < ptr -> hash_count; i++) {
  91             for (hbc = ptr -> buckets [i]; hbc; hbc = hbn) {
  92                 hbn = hbc -> next;
  93                 if (ptr -> dereferencer && hbc -> value)
  94                     (*ptr -> dereferencer) (&hbc -> value, MDL);
  95             }
  96             for (hbc = ptr -> buckets [i]; hbc; hbc = hbn) {
  97                 hbn = hbc -> next;
  98                 free_hash_bucket (hbc, MDL);
  99             }
 100             ptr -> buckets [i] = (struct hash_bucket *)0;
 101         }
 102 #endif
 103
 104         dfree ((VOIDPTR)ptr, MDL);
 105         *tp = (struct hash_table *)0;
 106 }
 107
 108 struct hash_bucket *free_hash_buckets;
 109
 110 #if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
 111 struct hash_bucket *hash_bucket_hunks;
 112
 113 void relinquish_hash_bucket_hunks ()
 114 {
 115         struct hash_bucket *c, *n, **p;
 116
 117         /* Account for all the hash buckets on the free list. */
 118         p = &free_hash_buckets;
 119         for (c = free_hash_buckets; c; c = c -> next) {
 120                 for (n = hash_bucket_hunks; n; n = n -> next) {
 121                         if (c > n && c < n + 127) {
 122                                 *p = c -> next;
 123                                 n -> len++;
 124                                 break;
 125                         }
 126                 }
 127                 /* If we didn't delete the hash bucket from the free list,
 128                    advance the pointer. */
 129                 if (!n)
 130                         p = &c -> next;
 131         }
 132
 133         for (c = hash_bucket_hunks; c; c = n) {
 134                 n = c -> next;
 135                 if (c -> len != 126) {
 136                         log_info ("hashbucket %lx hash_buckets %d free %u",
 137                                   (unsigned long)c, 127, c -> len);
 138                 }
 139                 dfree (c, MDL);
 140         }
 141 }
 142 #endif
 143
 144 struct hash_bucket *new_hash_bucket (file, line)
 145         const char *file;
 146         int line;
 147 {
 148         struct hash_bucket *rval;
 149         int i = 0;
 150         if (!free_hash_buckets) {
 151                 rval = dmalloc (127 * sizeof (struct hash_bucket),
 152                                 file, line);
 153                 if (!rval)
 154                         return rval;
 155 # if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
 156                 rval -> next = hash_bucket_hunks;
 157                 hash_bucket_hunks = rval;
 158                 hash_bucket_hunks -> len = 0;
 159                 i++;
 160                 rval++;
 161 #endif
 162                 for (; i < 127; i++) {
 163                         rval -> next = free_hash_buckets;
 164                         free_hash_buckets = rval;
 165                         rval++;
 166                 }
 167         }
 168         rval = free_hash_buckets;
 169         free_hash_buckets = rval -> next;
 170         return rval;
 171 }
 172
 173 void free_hash_bucket (ptr, file, line)
 174         struct hash_bucket *ptr;
 175         const char *file;
 176         int line;
 177 {
 178 #if defined (DEBUG_MALLOC_POOL)
 179         struct hash_bucket *hp;
 180
 181         for (hp = free_hash_buckets; hp; hp = hp -> next) {
 182                 if (hp == ptr) {
 183                         log_error ("hash bucket freed twice!");
 184                         abort ();
 185                 }
 186         }
 187 #endif
 188         ptr -> next = free_hash_buckets;
 189         free_hash_buckets = ptr;
 190 }
 191
 192 int new_hash (struct hash_table **rp,
 193               hash_reference referencer,
 194               hash_dereference dereferencer,
 195               int casep, const char *file, int line)
 196 {
 197         if (!new_hash_table (rp, DEFAULT_HASH_SIZE, file, line))
 198                 return 0;
 199         memset (&(*rp) -> buckets [0], 0,
 200                 DEFAULT_HASH_SIZE * sizeof (struct hash_bucket *));
 201         (*rp) -> referencer = referencer;
 202         (*rp) -> dereferencer = dereferencer;
 203         if (casep) {
 204                 (*rp) -> cmp = casecmp;
 205                 (*rp) -> do_hash = do_case_hash;
 206         } else {
 207                 (*rp) -> cmp = (hash_comparator_t)memcmp;
 208                 (*rp) -> do_hash = do_hash;
 209         }
 210         return 1;
 211 }
 212
 213 static int do_case_hash (name, len, size)
 214         const unsigned char *name;
 215         unsigned len;
 216         unsigned size;
 217 {
 218         register int accum = 0;
 219         register const unsigned char *s = (const unsigned char *)name;
 220         int i = len;
 221         register unsigned c;
 222
 223         while (i--) {
 224                 /* Make the hash case-insensitive. */
 225                 c = *s++;
 226                 if (isascii (c) && isupper (c))
 227                         c = tolower (c);
 228
 229                 /* Add the character in... */
 230                 accum = (accum << 1) + c;
 231
 232                 /* Add carry back in... */
 233                 while (accum > 65535) {
 234                         accum = (accum & 65535) + (accum >> 16);
 235                 }
 236         }
 237         return accum % size;
 238 }
 239
 240 static int do_hash (name, len, size)
 241         const unsigned char *name;
 242         unsigned len;
 243         unsigned size;
 244 {
 245         register int accum = 0;
 246         register const unsigned char *s = (const unsigned char *)name;
 247         int i = len;
 248
 249         while (i--) {
 250                 /* Add the character in... */
 251                 accum = (accum << 1) + *s++;
 252
 253                 /* Add carry back in... */
 254                 while (accum > 65535) {
 255                         accum = (accum & 65535) + (accum >> 16);
 256                 }
 257         }
 258         return accum % size;
 259 }
 260
 261 void add_hash (table, name, len, pointer, file, line)
 262         struct hash_table *table;
 263         unsigned len;
 264         const unsigned char *name;
 265         hashed_object_t *pointer;
 266         const char *file;
 267         int line;
 268 {
 269         int hashno;
 270         struct hash_bucket *bp;
 271         void *foo;
 272
 273         if (!table)
 274                 return;
 275
 276         if (!len)
 277                 len = strlen ((const char *)name);
 278
 279         hashno = (*table -> do_hash) (name, len, table -> hash_count);
 280         bp = new_hash_bucket (file, line);
 281
 282         if (!bp) {
 283                 log_error ("Can't add %s to hash table.", name);
 284                 return;
 285         }
 286         bp -> name = name;
 287         if (table -> referencer) {
 288                 foo = &bp -> value;
 289                 (*(table -> referencer)) (foo, pointer, file, line);
 290         } else
 291                 bp -> value = pointer;
 292         bp -> next = table -> buckets [hashno];
 293         bp -> len = len;
 294         table -> buckets [hashno] = bp;
 295 }
 296
 297 void delete_hash_entry (table, name, len, file, line)
 298         struct hash_table *table;
 299         unsigned len;
 300         const unsigned char *name;
 301         const char *file;
 302         int line;
 303 {
 304         int hashno;
 305         struct hash_bucket *bp, *pbp = (struct hash_bucket *)0;
 306         void *foo;
 307
 308         if (!table)
 309                 return;
 310
 311         if (!len)
 312                 len = strlen ((const char *)name);
 313
 314         hashno = (*table -> do_hash) (name, len, table -> hash_count);
 315
 316         /* Go through the list looking for an entry that matches;
 317            if we find it, delete it. */
 318         for (bp = table -> buckets [hashno]; bp; bp = bp -> next) {
 319                 if ((!bp -> len &&
 320                      !strcmp ((const char *)bp -> name, (const char *)name)) ||
 321                     (bp -> len == len &&
 322                      !(*table -> cmp) (bp -> name, name, len))) {
 323                         if (pbp) {
 324                                 pbp -> next = bp -> next;
 325                         } else {
 326                                 table -> buckets [hashno] = bp -> next;
 327                         }
 328                         if (bp -> value && table -> dereferencer) {
 329                                 foo = &bp -> value;
 330                                 (*(table -> dereferencer)) (foo, file, line);
 331                         }
 332                         free_hash_bucket (bp, file, line);
 333                         break;
 334                 }
 335                 pbp = bp;       /* jwg, 9/6/96 - nice catch! */
 336         }
 337 }
 338
 339 int hash_lookup (vp, table, name, len, file, line)
 340         hashed_object_t **vp;
 341         struct hash_table *table;
 342         const unsigned char *name;
 343         unsigned len;
 344         const char *file;
 345         int line;
 346 {
 347         int hashno;
 348         struct hash_bucket *bp;
 349
 350         if (!table)
 351                 return 0;
 352         if (!len)
 353                 len = strlen ((const char *)name);
 354
 355         hashno = (*table -> do_hash) (name, len, table -> hash_count);
 356
 357         for (bp = table -> buckets [hashno]; bp; bp = bp -> next) {
 358                 if (len == bp -> len
 359                     && !(*table -> cmp) (bp -> name, name, len)) {
 360                         if (table -> referencer)
 361                                 (*table -> referencer) (vp, bp -> value,
 362                                                         file, line);
 363                         else
 364                                 *vp = bp -> value;
 365                         return 1;
 366                 }
 367         }
 368         return 0;
 369 }
 370
 371 int hash_foreach (struct hash_table *table, hash_foreach_func func)
 372 {
 373         int i;
 374         struct hash_bucket *bp, *next;
 375         int count = 0;
 376
 377         if (!table)
 378                 return 0;
 379
 380         for (i = 0; i < table -> hash_count; i++) {
 381                 bp = table -> buckets [i];
 382                 while (bp) {
 383                         next = bp -> next;
 384                         (*func) (bp -> name, bp -> len, bp -> value);
 385                         bp = next;
 386                         count++;
 387                 }
 388         }
 389         return count;
 390 }
 391
 392 int casecmp (const void *v1, const void *v2, unsigned long len)
 393 {
 394         unsigned i;
 395         const char *s = v1;
 396         const char *t = v2;
 397
 398         for (i = 0; i < len; i++)
 399         {
 400                 int c1, c2;
 401                 if (isupper ((unsigned char)s [i]))
 402                         c1 = tolower ((unsigned char)s [i]);
 403                 else
 404                         c1 = s [i];
 405
 406                 if (isupper ((unsigned char)t [i]))
 407                         c2 = tolower ((unsigned char)t [i]);
 408                 else
 409                         c2 = t [i];
 410
 411                 if (c1 < c2)
 412                         return -1;
 413                 if (c1 > c2)
 414                         return 1;
 415         }
 416         return 0;
 417 }