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