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 *
new_hash(void)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
do_hash(unsigned char * name,int len,int size)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
add_hash(struct hash_table * table,unsigned char * name,int len,unsigned char * pointer)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
delete_hash_entry(struct hash_table * table,unsigned char * name,int len)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 *
hash_lookup(struct hash_table * table,unsigned char * name,int len)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