common/hash.c

   1 /* hash.c
   2
   3    Routines for manipulating hash tables... */
   4
   5 /*
   6  * Copyright (c) 1995, 1996 The 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 <mellon@fugue.com> in cooperation with Vixie
  38  * Enterprises.  To learn more about the Internet Software Consortium,
  39  * see ``http://www.vix.com/isc''.  To learn more about Vixie
  40  * Enterprises, see ``http://www.vix.com''.
  41  */
  42
  43 #ifndef lint
  44 static char copyright[] =
  45 "$Id: hash.c,v 1.11 1999/02/24 17:56:45 mellon Exp $ Copyright (c) 1995, 1996 The Internet Software Consortium.  All rights reserved.\n";
  46 #endif /* not lint */
  47
  48 #include "dhcpd.h"
  49
  50 static INLINE int do_hash PROTO ((unsigned char *, int, int));
  51
  52 struct hash_table *new_hash ()
  53 {
  54         struct hash_table *rv = new_hash_table (DEFAULT_HASH_SIZE, "new_hash");
  55         if (!rv)
  56                 return rv;
  57         memset (&rv -> buckets [0], 0,
  58                 DEFAULT_HASH_SIZE * sizeof (struct hash_bucket *));
  59         return rv;
  60 }
  61
  62 static INLINE int do_hash (name, len, size)
  63         unsigned char *name;
  64         int len;
  65         int size;
  66 {
  67         register int accum = 0;
  68         register unsigned char *s = (unsigned char *)name;
  69         int i = len;
  70         if (i) {
  71                 while (i--) {
  72                         /* Add the character in... */
  73                         accum += *s++;
  74                         /* Add carry back in... */
  75                         while (accum > 255) {
  76                                 accum = (accum & 255) + (accum >> 8);
  77                         }
  78                 }
  79         } else {
  80                 while (*s) {
  81                         /* Add the character in... */
  82                         accum += *s++;
  83                         /* Add carry back in... */
  84                         while (accum > 255) {
  85                                 accum = (accum & 255) + (accum >> 8);
  86                         }
  87                 }
  88         }
  89         return accum % size;
  90 }
  91
  92 void add_hash (table, name, len, pointer)
  93         struct hash_table *table;
  94         int len;
  95         unsigned char *name;
  96         unsigned char *pointer;
  97 {
  98         int hashno;
  99         struct hash_bucket *bp;
 100
 101         if (!table)
 102                 return;
 103
 104         hashno = do_hash (name, len, table -> hash_count);
 105         bp = new_hash_bucket ("add_hash");
 106
 107         if (!bp) {
 108                 log_error ("Can't add %s to hash table.", name);
 109                 return;
 110         }
 111         bp -> name = name;
 112         bp -> value = pointer;
 113         bp -> next = table -> buckets [hashno];
 114         bp -> len = len;
 115         table -> buckets [hashno] = bp;
 116 }
 117
 118 void delete_hash_entry (table, name, len)
 119         struct hash_table *table;
 120         int len;
 121         unsigned char *name;
 122 {
 123         int hashno;
 124         struct hash_bucket *bp, *pbp = (struct hash_bucket *)0;
 125
 126         if (!table)
 127                 return;
 128
 129         hashno = do_hash (name, len, table -> hash_count);
 130
 131         /* Go through the list looking for an entry that matches;
 132            if we find it, delete it. */
 133         for (bp = table -> buckets [hashno]; bp; bp = bp -> next) {
 134                 if ((!bp -> len &&
 135                      !strcmp ((char *)bp -> name, (char *)name)) ||
 136                     (bp -> len == len &&
 137                      !memcmp (bp -> name, name, len))) {
 138                         if (pbp) {
 139                                 pbp -> next = bp -> next;
 140                         } else {
 141                                 table -> buckets [hashno] = bp -> next;
 142                         }
 143                         free_hash_bucket (bp, "delete_hash_entry");
 144                         break;
 145                 }
 146                 pbp = bp;       /* jwg, 9/6/96 - nice catch! */
 147         }
 148 }
 149
 150 unsigned char *hash_lookup (table, name, len)
 151         struct hash_table *table;
 152         unsigned char *name;
 153         int len;
 154 {
 155         int hashno;
 156         struct hash_bucket *bp;
 157
 158         if (!table)
 159                 return (unsigned char *)0;
 160         hashno = do_hash (name, len, table -> hash_count);
 161
 162         if (len) {
 163                 for (bp = table -> buckets [hashno]; bp; bp = bp -> next) {
 164                         if (len == bp -> len
 165                             && !memcmp (bp -> name, name, len))
 166                                 return bp -> value;
 167                 }
 168         } else {
 169                 for (bp = table -> buckets [hashno]; bp; bp = bp -> next)
 170                         if (!strcmp ((char *)bp -> name,
 171                                      (char *)name))
 172                                 return bp -> value;
 173         }
 174         return (unsigned char *)0;
 175 }
 176