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/03/17 20:15:22 dhankins 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         int i;
  85         struct hash_bucket *hbc, *hbn = (struct hash_bucket *)0;
  86         struct hash_table *ptr = *tp;
  87
  88 #if defined (DEBUG_MEMORY_LEAKAGE) || \
  89                 defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
  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         struct hash_bucket *hp;
 179 #if defined (DEBUG_MALLOC_POOL)
 180         for (hp = free_hash_buckets; hp; hp = hp -> next) {
 181                 if (hp == ptr) {
 182                         log_error ("hash bucket freed twice!");
 183                         abort ();
 184                 }
 185         }
 186 #endif
 187         ptr -> next = free_hash_buckets;
 188         free_hash_buckets = ptr;
 189 }
 190
 191 int new_hash (struct hash_table **rp,
 192               hash_reference referencer,
 193               hash_dereference dereferencer,
 194               int casep, const char *file, int line)
 195 {
 196         if (!new_hash_table (rp, DEFAULT_HASH_SIZE, file, line))
 197                 return 0;
 198         memset (&(*rp) -> buckets [0], 0,
 199                 DEFAULT_HASH_SIZE * sizeof (struct hash_bucket *));
 200         (*rp) -> referencer = referencer;
 201         (*rp) -> dereferencer = dereferencer;
 202         if (casep) {
 203                 (*rp) -> cmp = casecmp;
 204                 (*rp) -> do_hash = do_case_hash;
 205         } else {
 206                 (*rp) -> cmp = (hash_comparator_t)memcmp;
 207                 (*rp) -> do_hash = do_hash;
 208         }
 209         return 1;
 210 }
 211
 212 static int do_case_hash (name, len, size)
 213         const unsigned char *name;
 214         unsigned len;
 215         unsigned size;
 216 {
 217         register int accum = 0;
 218         register const unsigned char *s = (const unsigned char *)name;
 219         int i = len;
 220         register unsigned c;
 221
 222         while (i--) {
 223                 /* Make the hash case-insensitive. */
 224                 c = *s++;
 225                 if (isascii (c) && isupper (c))
 226                         c = tolower (c);
 227
 228                 /* Add the character in... */
 229                 accum = (accum << 1) + c;
 230
 231                 /* Add carry back in... */
 232                 while (accum > 65535) {
 233                         accum = (accum & 65535) + (accum >> 16);
 234                 }
 235         }
 236         return accum % size;
 237 }
 238
 239 static int do_hash (name, len, size)
 240         const unsigned char *name;
 241         unsigned len;
 242         unsigned size;
 243 {
 244         register int accum = 0;
 245         register const unsigned char *s = (const unsigned char *)name;
 246         int i = len;
 247
 248         while (i--) {
 249                 /* Add the character in... */
 250                 accum = (accum << 1) + *s++;
 251
 252                 /* Add carry back in... */
 253                 while (accum > 65535) {
 254                         accum = (accum & 65535) + (accum >> 16);
 255                 }
 256         }
 257         return accum % size;
 258 }
 259
 260 void add_hash (table, name, len, pointer, file, line)
 261         struct hash_table *table;
 262         unsigned len;
 263         const unsigned char *name;
 264         hashed_object_t *pointer;
 265         const char *file;
 266         int line;
 267 {
 268         int hashno;
 269         struct hash_bucket *bp;
 270         void *foo;
 271
 272         if (!table)
 273                 return;
 274
 275         if (!len)
 276                 len = strlen ((const char *)name);
 277
 278         hashno = (*table -> do_hash) (name, len, table -> hash_count);
 279         bp = new_hash_bucket (file, line);
 280
 281         if (!bp) {
 282                 log_error ("Can't add %s to hash table.", name);
 283                 return;
 284         }
 285         bp -> name = name;
 286         if (table -> referencer) {
 287                 foo = &bp -> value;
 288                 (*(table -> referencer)) (foo, pointer, file, line);
 289         } else
 290                 bp -> value = pointer;
 291         bp -> next = table -> buckets [hashno];
 292         bp -> len = len;
 293         table -> buckets [hashno] = bp;
 294 }
 295
 296 void delete_hash_entry (table, name, len, file, line)
 297         struct hash_table *table;
 298         unsigned len;
 299         const unsigned char *name;
 300         const char *file;
 301         int line;
 302 {
 303         int hashno;
 304         struct hash_bucket *bp, *pbp = (struct hash_bucket *)0;
 305         void *foo;
 306
 307         if (!table)
 308                 return;
 309
 310         if (!len)
 311                 len = strlen ((const char *)name);
 312
 313         hashno = (*table -> do_hash) (name, len, table -> hash_count);
 314
 315         /* Go through the list looking for an entry that matches;
 316            if we find it, delete it. */
 317         for (bp = table -> buckets [hashno]; bp; bp = bp -> next) {
 318                 if ((!bp -> len &&
 319                      !strcmp ((const char *)bp -> name, (const char *)name)) ||
 320                     (bp -> len == len &&
 321                      !(*table -> cmp) (bp -> name, name, len))) {
 322                         if (pbp) {
 323                                 pbp -> next = bp -> next;
 324                         } else {
 325                                 table -> buckets [hashno] = bp -> next;
 326                         }
 327                         if (bp -> value && table -> dereferencer) {
 328                                 foo = &bp -> value;
 329                                 (*(table -> dereferencer)) (foo, file, line);
 330                         }
 331                         free_hash_bucket (bp, file, line);
 332                         break;
 333                 }
 334                 pbp = bp;       /* jwg, 9/6/96 - nice catch! */
 335         }
 336 }
 337
 338 int hash_lookup (vp, table, name, len, file, line)
 339         hashed_object_t **vp;
 340         struct hash_table *table;
 341         const unsigned char *name;
 342         unsigned len;
 343         const char *file;
 344         int line;
 345 {
 346         int hashno;
 347         struct hash_bucket *bp;
 348
 349         if (!table)
 350                 return 0;
 351         if (!len)
 352                 len = strlen ((const char *)name);
 353
 354         hashno = (*table -> do_hash) (name, len, table -> hash_count);
 355
 356         for (bp = table -> buckets [hashno]; bp; bp = bp -> next) {
 357                 if (len == bp -> len
 358                     && !(*table -> cmp) (bp -> name, name, len)) {
 359                         if (table -> referencer)
 360                                 (*table -> referencer) (vp, bp -> value,
 361                                                         file, line);
 362                         else
 363                                 *vp = bp -> value;
 364                         return 1;
 365                 }
 366         }
 367         return 0;
 368 }
 369
 370 int hash_foreach (struct hash_table *table, hash_foreach_func func)
 371 {
 372         int i;
 373         struct hash_bucket *bp, *next;
 374         int count = 0;
 375
 376         if (!table)
 377                 return 0;
 378
 379         for (i = 0; i < table -> hash_count; i++) {
 380                 bp = table -> buckets [i];
 381                 while (bp) {
 382                         next = bp -> next;
 383                         (*func) (bp -> name, bp -> len, bp -> value);
 384                         bp = next;
 385                         count++;
 386                 }
 387         }
 388         return count;
 389 }
 390
 391 int casecmp (const void *v1, const void *v2, unsigned long len)
 392 {
 393         unsigned i;
 394         const char *s = v1;
 395         const char *t = v2;
 396
 397         for (i = 0; i < len; i++)
 398         {
 399                 int c1, c2;
 400                 if (isascii (s [i]) && isupper (s [i]))
 401                         c1 = tolower (s [i]);
 402                 else
 403                         c1 = s [i];
 404
 405                 if (isascii (t [i]) && isupper (t [i]))
 406                         c2 = tolower (t [i]);
 407                 else
 408                         c2 = t [i];
 409
 410                 if (c1 < c2)
 411                         return -1;
 412                 if (c1 > c2)
 413                         return 1;
 414         }
 415         return 0;
 416 }