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  * SPDX-License-Identifier: BSD-3-Clause
   7  *
   8  * Copyright (c) 1995, 1996, 1997, 1998 The Internet Software Consortium.
   9  * All rights reserved.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions
  13  * are met:
  14  *
  15  * 1. Redistributions of source code must retain the above copyright
  16  *    notice, this list of conditions and the following disclaimer.
  17  * 2. Redistributions in binary form must reproduce the above copyright
  18  *    notice, this list of conditions and the following disclaimer in the
  19  *    documentation and/or other materials provided with the distribution.
  20  * 3. Neither the name of The Internet Software Consortium nor the names
  21  *    of its contributors may be used to endorse or promote products derived
  22  *    from this software without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE INTERNET SOFTWARE CONSORTIUM AND
  25  * CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
  26  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  27  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  28  * DISCLAIMED.  IN NO EVENT SHALL THE INTERNET SOFTWARE CONSORTIUM OR
  29  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  30  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  31  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  32  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  33  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  34  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  35  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  36  * SUCH DAMAGE.
  37  *
  38  * This software has been written for the Internet Software Consortium
  39  * by Ted Lemon <mellon@fugue.com> in cooperation with Vixie
  40  * Enterprises.  To learn more about the Internet Software Consortium,
  41  * see ``http://www.vix.com/isc''.  To learn more about Vixie
  42  * Enterprises, see ``http://www.vix.com''.
  43  */
  44
  45 #include <sys/cdefs.h>
  46 __FBSDID("$FreeBSD$");
  47
  48 #include "dhcpd.h"
  49
  50 static int do_hash(const unsigned char *, int, int);
  51
  52 struct hash_table *
  53 new_hash(void)
  54 {
  55         struct hash_table *rv = new_hash_table(DEFAULT_HASH_SIZE);
  56
  57         if (!rv)
  58                 return (rv);
  59         memset(&rv->buckets[0], 0,
  60             DEFAULT_HASH_SIZE * sizeof(struct hash_bucket *));
  61         return (rv);
  62 }
  63
  64 static int
  65 do_hash(const unsigned char *name, int len, int size)
  66 {
  67         const unsigned char *s = name;
  68         int accum = 0, i = len;
  69
  70         while (i--) {
  71                 /* Add the character in... */
  72                 accum += *s++;
  73                 /* Add carry back in... */
  74                 while (accum > 255)
  75                         accum = (accum & 255) + (accum >> 8);
  76         }
  77         return (accum % size);
  78 }
  79
  80 void add_hash(struct hash_table *table, const unsigned char *name, int len,
  81     unsigned char *pointer)
  82 {
  83         struct hash_bucket *bp;
  84         int hashno;
  85
  86         if (!table)
  87                 return;
  88         if (!len)
  89                 len = strlen((const char *)name);
  90
  91         hashno = do_hash(name, len, table->hash_count);
  92         bp = new_hash_bucket();
  93
  94         if (!bp) {
  95                 warning("Can't add %s to hash table.", name);
  96                 return;
  97         }
  98         bp->name = name;
  99         bp->value = pointer;
 100         bp->next = table->buckets[hashno];
 101         bp->len = len;
 102         table->buckets[hashno] = bp;
 103 }
 104
 105 void *
 106 hash_lookup(struct hash_table *table, unsigned char *name, int len)
 107 {
 108         struct hash_bucket *bp;
 109         int hashno;
 110
 111         if (!table)
 112                 return (NULL);
 113
 114         if (!len)
 115                 len = strlen((char *)name);
 116
 117         hashno = do_hash(name, len, table->hash_count);
 118
 119         for (bp = table->buckets[hashno]; bp; bp = bp->next)
 120                 if (len == bp->len && !memcmp(bp->name, name, len))
 121                         return (bp->value);
 122
 123         return (NULL);
 124 }