1147072Sbrooks/* $OpenBSD: hash.c,v 1.9 2004/05/10 15:30:47 deraadt Exp $ */ 2147072Sbrooks 3147072Sbrooks/* Routines for manipulating hash tables... */ 4147072Sbrooks 5147072Sbrooks/* 6147072Sbrooks * Copyright (c) 1995, 1996, 1997, 1998 The Internet Software Consortium. 7147072Sbrooks * All rights reserved. 8147072Sbrooks * 9147072Sbrooks * Redistribution and use in source and binary forms, with or without 10147072Sbrooks * modification, are permitted provided that the following conditions 11147072Sbrooks * are met: 12147072Sbrooks * 13147072Sbrooks * 1. Redistributions of source code must retain the above copyright 14147072Sbrooks * notice, this list of conditions and the following disclaimer. 15147072Sbrooks * 2. Redistributions in binary form must reproduce the above copyright 16147072Sbrooks * notice, this list of conditions and the following disclaimer in the 17147072Sbrooks * documentation and/or other materials provided with the distribution. 18147072Sbrooks * 3. Neither the name of The Internet Software Consortium nor the names 19147072Sbrooks * of its contributors may be used to endorse or promote products derived 20147072Sbrooks * from this software without specific prior written permission. 21147072Sbrooks * 22147072Sbrooks * THIS SOFTWARE IS PROVIDED BY THE INTERNET SOFTWARE CONSORTIUM AND 23147072Sbrooks * CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, 24147072Sbrooks * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 25147072Sbrooks * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 26147072Sbrooks * DISCLAIMED. IN NO EVENT SHALL THE INTERNET SOFTWARE CONSORTIUM OR 27147072Sbrooks * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28147072Sbrooks * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 29147072Sbrooks * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF 30147072Sbrooks * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 31147072Sbrooks * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 32147072Sbrooks * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 33147072Sbrooks * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34147072Sbrooks * SUCH DAMAGE. 35147072Sbrooks * 36147072Sbrooks * This software has been written for the Internet Software Consortium 37147072Sbrooks * by Ted Lemon <mellon@fugue.com> in cooperation with Vixie 38147072Sbrooks * Enterprises. To learn more about the Internet Software Consortium, 39147072Sbrooks * see ``http://www.vix.com/isc''. To learn more about Vixie 40147072Sbrooks * Enterprises, see ``http://www.vix.com''. 41147072Sbrooks */ 42147072Sbrooks 43149399Sbrooks#include <sys/cdefs.h> 44149399Sbrooks__FBSDID("$FreeBSD$"); 45149399Sbrooks 46147072Sbrooks#include "dhcpd.h" 47147072Sbrooks 48147072Sbrooksstatic int do_hash(unsigned char *, int, int); 49147072Sbrooks 50147072Sbrooksstruct hash_table * 51147072Sbrooksnew_hash(void) 52147072Sbrooks{ 53147072Sbrooks struct hash_table *rv = new_hash_table(DEFAULT_HASH_SIZE); 54147072Sbrooks 55147072Sbrooks if (!rv) 56147072Sbrooks return (rv); 57147072Sbrooks memset(&rv->buckets[0], 0, 58147072Sbrooks DEFAULT_HASH_SIZE * sizeof(struct hash_bucket *)); 59147072Sbrooks return (rv); 60147072Sbrooks} 61147072Sbrooks 62147072Sbrooksstatic int 63147072Sbrooksdo_hash(unsigned char *name, int len, int size) 64147072Sbrooks{ 65147072Sbrooks unsigned char *s = name; 66147072Sbrooks int accum = 0, i = len; 67147072Sbrooks 68147072Sbrooks while (i--) { 69147072Sbrooks /* Add the character in... */ 70147072Sbrooks accum += *s++; 71147072Sbrooks /* Add carry back in... */ 72147072Sbrooks while (accum > 255) 73147072Sbrooks accum = (accum & 255) + (accum >> 8); 74147072Sbrooks } 75147072Sbrooks return (accum % size); 76147072Sbrooks} 77147072Sbrooks 78147072Sbrooksvoid add_hash(struct hash_table *table, unsigned char *name, int len, 79147072Sbrooks unsigned char *pointer) 80147072Sbrooks{ 81147072Sbrooks struct hash_bucket *bp; 82147072Sbrooks int hashno; 83147072Sbrooks 84147072Sbrooks if (!table) 85147072Sbrooks return; 86147072Sbrooks if (!len) 87147072Sbrooks len = strlen((char *)name); 88147072Sbrooks 89147072Sbrooks hashno = do_hash(name, len, table->hash_count); 90147072Sbrooks bp = new_hash_bucket(); 91147072Sbrooks 92147072Sbrooks if (!bp) { 93147072Sbrooks warning("Can't add %s to hash table.", name); 94147072Sbrooks return; 95147072Sbrooks } 96147072Sbrooks bp->name = name; 97147072Sbrooks bp->value = pointer; 98147072Sbrooks bp->next = table->buckets[hashno]; 99147072Sbrooks bp->len = len; 100147072Sbrooks table->buckets[hashno] = bp; 101147072Sbrooks} 102147072Sbrooks 103147072Sbrooksunsigned char * 104147072Sbrookshash_lookup(struct hash_table *table, unsigned char *name, int len) 105147072Sbrooks{ 106147072Sbrooks struct hash_bucket *bp; 107147072Sbrooks int hashno; 108147072Sbrooks 109147072Sbrooks if (!table) 110147072Sbrooks return (NULL); 111147072Sbrooks 112147072Sbrooks if (!len) 113147072Sbrooks len = strlen((char *)name); 114147072Sbrooks 115147072Sbrooks hashno = do_hash(name, len, table->hash_count); 116147072Sbrooks 117147072Sbrooks for (bp = table->buckets[hashno]; bp; bp = bp->next) 118147072Sbrooks if (len == bp->len && !memcmp(bp->name, name, len)) 119147072Sbrooks return (bp->value); 120147072Sbrooks 121147072Sbrooks return (NULL); 122147072Sbrooks} 123