workbench/network/stacks/AROSTCP/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 #if 0
  36 static char copyright[] =
  37 "$Id$ Copyright (c) 2004 Internet Systems Consortium.  All rights reserved.\n";
  38 #endif
  39
  40 #include <omapip/omapip_p.h>
  41 #include <ctype.h>
  42 #include <string.h>
  43
  44 static int do_hash (const unsigned char *, unsigned, unsigned);
  45 static int do_case_hash (const unsigned char *, unsigned, unsigned);
  46
  47 int new_hash_table (tp, count, file, line)
  48         struct hash_table **tp;
  49         int count;
  50         const char *file;
  51         int line;
  52 {
  53         struct hash_table *rval;
  54
  55         if (!tp) {
  56                 log_error ("%s(%d): new_hash_table called with null pointer.",
  57                            file, line);
  58 #if defined (POINTER_DEBUG)
  59                 abort ();
  60 #endif
  61                 return 0;
  62         }
  63         if (*tp) {
  64                 log_error ("%s(%d): non-null target for new_hash_table.",
  65                            file, line);
  66 #if defined (POINTER_DEBUG)
  67                 abort ();
  68 #endif
  69         }
  70         rval = dmalloc (sizeof (struct hash_table) -
  71                         (DEFAULT_HASH_SIZE * sizeof (struct hash_bucket *)) +
  72                         (count * sizeof (struct hash_bucket *)), file, line);
  73         if (!rval)
  74                 return 0;
  75         rval -> hash_count = count;
  76         *tp = rval;
  77         return 1;
  78 }
  79
  80 void free_hash_table (tp, file, line)
  81         struct hash_table **tp;
  82         const char *file;
  83         int line;
  84 {
  85         __unused int i;
  86         __unused struct hash_bucket *hbc, *hbn = (struct hash_bucket *)0;
  87         struct hash_table *ptr = *tp;
  88
  89 #if defined (DEBUG_MEMORY_LEAKAGE) || \
  90                 defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
  91         for (i = 0; i < ptr -> hash_count; i++) {
  92             for (hbc = ptr -> buckets [i]; hbc; hbc = hbn) {
  93                 hbn = hbc -> next;
  94                 if (ptr -> dereferencer && hbc -> value)
  95                     (*ptr -> dereferencer) (&hbc -> value, MDL);
  96             }
  97             for (hbc = ptr -> buckets [i]; hbc; hbc = hbn) {
  98                 hbn = hbc -> next;
  99                 free_hash_bucket (hbc, MDL);
 100             }
 101             ptr -> buckets [i] = (struct hash_bucket *)0;
 102         }
 103 #endif
 104
 105         dfree ((VOIDPTR)ptr, MDL);
 106         *tp = (struct hash_table *)0;
 107 }
 108
 109 struct hash_bucket *free_hash_buckets;
 110
 111 #if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
 112 struct hash_bucket *hash_bucket_hunks;
 113
 114 void relinquish_hash_bucket_hunks ()
 115 {
 116         struct hash_bucket *c, *n, **p;
 117
 118         /* Account for all the hash buckets on the free list. */
 119         p = &free_hash_buckets;
 120         for (c = free_hash_buckets; c; c = c -> next) {
 121                 for (n = hash_bucket_hunks; n; n = n -> next) {
 122                         if (c > n && c < n + 127) {
 123                                 *p = c -> next;
 124                                 n -> len++;
 125                                 break;
 126                         }
 127                 }
 128                 /* If we didn't delete the hash bucket from the free list,
 129                    advance the pointer. */
 130                 if (!n)
 131                         p = &c -> next;
 132         }
 133
 134         for (c = hash_bucket_hunks; c; c = n) {
 135                 n = c -> next;
 136                 if (c -> len != 126) {
 137                         log_info ("hashbucket %lx hash_buckets %d free %u",
 138                                   (unsigned long)c, 127, c -> len);
 139                 }
 140                 dfree (c, MDL);
 141         }
 142 }
 143 #endif
 144
 145 struct hash_bucket *new_hash_bucket (file, line)
 146         const char *file;
 147         int line;
 148 {
 149         struct hash_bucket *rval;
 150         int i = 0;
 151         if (!free_hash_buckets) {
 152                 rval = dmalloc (127 * sizeof (struct hash_bucket),
 153                                 file, line);
 154                 if (!rval)
 155                         return rval;
 156 # if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
 157                 rval -> next = hash_bucket_hunks;
 158                 hash_bucket_hunks = rval;
 159                 hash_bucket_hunks -> len = 0;
 160                 i++;
 161                 rval++;
 162 #endif
 163                 for (; i < 127; i++) {
 164                         rval -> next = free_hash_buckets;
 165                         free_hash_buckets = rval;
 166                         rval++;
 167                 }
 168         }
 169         rval = free_hash_buckets;
 170         free_hash_buckets = rval -> next;
 171         return rval;
 172 }
 173
 174 void free_hash_bucket (ptr, file, line)
 175         struct hash_bucket *ptr;
 176         const char *file;
 177         int line;
 178 {
 179         __unused struct hash_bucket *hp;
 180 #if defined (DEBUG_MALLOC_POOL)
 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 (isascii (s [i]) && isupper (s [i]))
 402                         c1 = tolower (s [i]);
 403                 else
 404                         c1 = s [i];
 405
 406                 if (isascii (t [i]) && isupper (t [i]))
 407                         c2 = tolower (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 }