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 } 125