contrib/isc-dhcp/omapip/hash.c

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