1 /* $OpenBSD: hash.c,v 1.7 2016/02/06 23:50:10 krw 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/types.h> 44 #include <sys/socket.h> 45 46 #include <net/if.h> 47 48 #include <netinet/in.h> 49 50 #include <stdio.h> 51 #include <stdlib.h> 52 #include <string.h> 53 54 #include "dhcp.h" 55 #include "tree.h" 56 #include "dhcpd.h" 57 58 static int do_hash(unsigned char *, int, int); 59 60 struct hash_table * 61 new_hash(void) 62 { 63 struct hash_table *rv; 64 65 rv = calloc(1, sizeof(struct hash_table)); 66 if (!rv) 67 warning("No memory for new hash."); 68 else 69 rv->hash_count = DEFAULT_HASH_SIZE; 70 71 return (rv); 72 } 73 74 static int 75 do_hash(unsigned char *name, int len, int size) 76 { 77 int accum = 0; 78 unsigned char *s = name; 79 int i = len; 80 81 while (i--) { 82 /* Add the character in... */ 83 accum += *s++; 84 /* Add carry back in... */ 85 while (accum > 255) 86 accum = (accum & 255) + (accum >> 8); 87 } 88 return (accum % size); 89 } 90 91 void add_hash(struct hash_table *table, unsigned char *name, int len, 92 unsigned char *pointer) 93 { 94 int hashno; 95 struct hash_bucket *bp; 96 97 if (!table) 98 return; 99 if (!len) 100 len = strlen((char *)name); 101 102 hashno = do_hash(name, len, table->hash_count); 103 bp = calloc(1, sizeof(struct hash_bucket)); 104 if (!bp) { 105 warning("Can't add %s to hash table.", name); 106 return; 107 } 108 bp->name = name; 109 bp->value = pointer; 110 bp->next = table->buckets[hashno]; 111 bp->len = len; 112 table->buckets[hashno] = bp; 113 } 114 115 void 116 delete_hash_entry(struct hash_table *table, unsigned char *name, int len) 117 { 118 int hashno; 119 struct hash_bucket *bp, *pbp = NULL; 120 121 if (!table) 122 return; 123 if (!len) 124 len = strlen((char *)name); 125 126 hashno = do_hash(name, len, table->hash_count); 127 128 /* 129 * Go through the list looking for an entry that matches; if we 130 * find it, delete it. 131 */ 132 for (bp = table->buckets[hashno]; bp; bp = bp->next) { 133 if ((!bp->len && 134 !strcmp((char *)bp->name, (char *)name)) || 135 (bp->len == len && !memcmp(bp->name, name, len))) { 136 if (pbp) 137 pbp->next = bp->next; 138 else 139 table->buckets[hashno] = bp->next; 140 free(bp); 141 break; 142 } 143 pbp = bp; /* jwg, 9/6/96 - nice catch! */ 144 } 145 } 146 147 unsigned char * 148 hash_lookup(struct hash_table *table, unsigned char *name, int len) 149 { 150 int hashno; 151 struct hash_bucket *bp; 152 153 if (!table) 154 return (NULL); 155 156 if (!len) 157 len = strlen((char *)name); 158 159 hashno = do_hash(name, len, table->hash_count); 160 161 for (bp = table->buckets[hashno]; bp; bp = bp->next) 162 if (len == bp->len && !memcmp(bp->name, name, len)) 163 return (bp->value); 164 165 return (NULL); 166 } 167