sbin/dhclient/hash.c

   1 /*      $OpenBSD: hash.c,v 1.9 2004/05/10 15:30:47 deraadt Exp $        */
   2
   3 /* Routines for manipulating hash tables... */
   4
   5 /*
   6  * Copyright (c) 1995, 1996, 1997, 1998 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 #include <sys/cdefs.h>
  44 __FBSDID("$FreeBSD$");
  45
  46 #include "dhcpd.h"
  47
  48 static int do_hash(unsigned char *, int, int);
  49
  50 struct hash_table *
  51 new_hash(void)
  52 {
  53         struct hash_table *rv = new_hash_table(DEFAULT_HASH_SIZE);
  54
  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 int
  63 do_hash(unsigned char *name, int len, int size)
  64 {
  65         unsigned char *s = name;
  66         int accum = 0, i = len;
  67
  68         while (i--) {
  69                 /* Add the character in... */
  70                 accum += *s++;
  71                 /* Add carry back in... */
  72                 while (accum > 255)
  73                         accum = (accum & 255) + (accum >> 8);
  74         }
  75         return (accum % size);
  76 }
  77
  78 void add_hash(struct hash_table *table, unsigned char *name, int len,
  79     unsigned char *pointer)
  80 {
  81         struct hash_bucket *bp;
  82         int hashno;
  83
  84         if (!table)
  85                 return;
  86         if (!len)
  87                 len = strlen((char *)name);
  88
  89         hashno = do_hash(name, len, table->hash_count);
  90         bp = new_hash_bucket();
  91
  92         if (!bp) {
  93                 warning("Can't add %s to hash table.", name);
  94                 return;
  95         }
  96         bp->name = name;
  97         bp->value = pointer;
  98         bp->next = table->buckets[hashno];
  99         bp->len = len;
 100         table->buckets[hashno] = bp;
 101 }
 102
 103 unsigned char *
 104 hash_lookup(struct hash_table *table, unsigned char *name, int len)
 105 {
 106         struct hash_bucket *bp;
 107         int hashno;
 108
 109         if (!table)
 110                 return (NULL);
 111
 112         if (!len)
 113                 len = strlen((char *)name);
 114
 115         hashno = do_hash(name, len, table->hash_count);
 116
 117         for (bp = table->buckets[hashno]; bp; bp = bp->next)
 118                 if (len == bp->len && !memcmp(bp->name, name, len))
 119                         return (bp->value);
 120
 121         return (NULL);
 122 }