1 /* $OpenBSD: hash.c,v 1.19 2021/11/28 19:26:03 deraadt Exp $ */
2 /* $NetBSD: hash.c,v 1.4 1996/11/07 22:59:43 gwr Exp $ */
3
4 /*
5 * Copyright (c) 1992, 1993
6 * The Regents of the University of California. All rights reserved.
7 *
8 * This software was developed by the Computer Systems Engineering group
9 * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and
10 * contributed to Berkeley.
11 *
12 * All advertising materials mentioning features or use of this software
13 * must display the following acknowledgement:
14 * This product includes software developed by the University of
15 * California, Lawrence Berkeley Laboratories.
16 *
17 * Redistribution and use in source and binary forms, with or without
18 * modification, are permitted provided that the following conditions
19 * are met:
20 * 1. Redistributions of source code must retain the above copyright
21 * notice, this list of conditions and the following disclaimer.
22 * 2. Redistributions in binary form must reproduce the above copyright
23 * notice, this list of conditions and the following disclaimer in the
24 * documentation and/or other materials provided with the distribution.
25 * 3. Neither the name of the University nor the names of its contributors
26 * may be used to endorse or promote products derived from this software
27 * without specific prior written permission.
28 *
29 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
30 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
31 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
32 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
33 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
34 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
35 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
36 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
37 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
38 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
39 * SUCH DAMAGE.
40 *
41 * from: @(#)hash.c 8.1 (Berkeley) 6/6/93
42 */
43
44 #include <sys/types.h>
45
46 #include <stdlib.h>
47 #include <string.h>
48
49 #include "config.h"
50
51 /*
52 * Interned strings are kept in a hash table. By making each string
53 * unique, the program can compare strings by comparing pointers.
54 */
55 struct hashent {
56 struct hashent *h_next; /* hash buckets are chained */
57 const char *h_name; /* the string */
58 u_int h_hash; /* its hash value */
59 void *h_value; /* other values (for name=value) */
60 };
61 struct hashtab {
62 size_t ht_size; /* size (power of 2) */
63 u_int ht_mask; /* == ht_size - 1 */
64 u_int ht_used; /* number of entries used */
65 u_int ht_lim; /* when to expand */
66 struct hashent **ht_tab; /* base of table */
67 };
68 static struct hashtab strings;
69
70 /*
71 * HASHFRACTION controls ht_lim, which in turn controls the average chain
72 * length. We allow a few entries, on average, as comparing them is usually
73 * cheap (the h_hash values prevent a strcmp).
74 */
75 #define HASHFRACTION(sz) ((sz) * 3 / 2)
76
77 /* round up to next multiple of y, where y is a power of 2 */
78 #define ROUND(x, y) (((x) + (y) - 1) & ~((y) - 1))
79
80 static void ht_init(struct hashtab *, size_t);
81 static void ht_expand(struct hashtab *);
82
83 /*
84 * Initialize a new hash table. The size must be a power of 2.
85 */
86 static void
ht_init(struct hashtab * ht,size_t sz)87 ht_init(struct hashtab *ht, size_t sz)
88 {
89 struct hashent **h;
90 u_int n;
91
92 h = ereallocarray(NULL, sz, sizeof *h);
93 ht->ht_tab = h;
94 ht->ht_size = sz;
95 ht->ht_mask = sz - 1;
96 for (n = 0; n < sz; n++)
97 *h++ = NULL;
98 ht->ht_used = 0;
99 ht->ht_lim = HASHFRACTION(sz);
100 }
101
102 /*
103 * Expand an existing hash table.
104 */
105 static void
ht_expand(struct hashtab * ht)106 ht_expand(struct hashtab *ht)
107 {
108 struct hashent *p, **h, **oldh, *q;
109 u_int n, i;
110
111 n = ht->ht_size * 2;
112 h = ecalloc(n, sizeof *h);
113 oldh = ht->ht_tab;
114 n--;
115 for (i = ht->ht_size; i != 0; i--) {
116 for (p = *oldh++; p != NULL; p = q) {
117 q = p->h_next;
118 p->h_next = h[p->h_hash & n];
119 h[p->h_hash & n] = p;
120 }
121 }
122 free(ht->ht_tab);
123 ht->ht_tab = h;
124 ht->ht_mask = n;
125 ht->ht_size = ++n;
126 ht->ht_lim = HASHFRACTION(n);
127 }
128
129 /*
130 * Make a new hash entry, setting its h_next to NULL.
131 */
132 static __inline struct hashent *
newhashent(const char * name,u_int h)133 newhashent(const char *name, u_int h)
134 {
135 struct hashent *hp;
136
137 hp = emalloc(sizeof(*hp));
138 hp->h_name = name;
139 hp->h_hash = h;
140 hp->h_next = NULL;
141 return (hp);
142 }
143
144 /*
145 * Hash a string.
146 */
147 static __inline u_int
hash(const char * str)148 hash(const char *str)
149 {
150 u_int h;
151
152 for (h = 0; *str;)
153 h = (h << 5) + h + *str++;
154 return (h);
155 }
156
157 void
initintern(void)158 initintern(void)
159 {
160
161 ht_init(&strings, 128);
162 }
163
164 /*
165 * Generate a single unique copy of the given string. We expect this
166 * function to be used frequently, so it should be fast.
167 */
168 const char *
intern(const char * s)169 intern(const char *s)
170 {
171 struct hashtab *ht;
172 struct hashent *hp, **hpp;
173 u_int h;
174 char *p;
175 size_t l;
176
177 ht = &strings;
178 h = hash(s);
179 hpp = &ht->ht_tab[h & ht->ht_mask];
180 for (; (hp = *hpp) != NULL; hpp = &hp->h_next)
181 if (hp->h_hash == h && strcmp(hp->h_name, s) == 0)
182 return (hp->h_name);
183 l = strlen(s) + 1;
184 p = malloc(l);
185 bcopy(s, p, l);
186 *hpp = newhashent(p, h);
187 if (++ht->ht_used > ht->ht_lim)
188 ht_expand(ht);
189 return (p);
190 }
191
192 struct hashtab *
ht_new(void)193 ht_new(void)
194 {
195 struct hashtab *ht;
196
197 ht = emalloc(sizeof *ht);
198 ht_init(ht, 8);
199 return (ht);
200 }
201
202 /*
203 * Remove.
204 */
205 int
ht_remove(struct hashtab * ht,const char * nam)206 ht_remove(struct hashtab *ht, const char *nam)
207 {
208 struct hashent *hp, *thp;
209 u_int h;
210
211 h = hash(nam);
212 hp = ht->ht_tab[h & ht->ht_mask];
213 while (hp && hp->h_name == nam) {
214 ht->ht_tab[h & ht->ht_mask] = hp->h_next;
215 /* XXX free hp ? */
216 hp = ht->ht_tab[h & ht->ht_mask];
217 }
218
219 if ((hp = ht->ht_tab[h & ht->ht_mask]) == NULL)
220 return (0);
221
222 for (thp = hp->h_next; thp != NULL; thp = hp->h_next) {
223 if (thp->h_name == nam) {
224 hp->h_next = thp->h_next;
225 /* XXX free thp ? */
226 } else
227 hp = thp;
228 }
229
230 return (0);
231 }
232
233 /*
234 * Insert and/or replace.
235 */
236 int
ht_insrep(struct hashtab * ht,const char * nam,void * val,int replace)237 ht_insrep(struct hashtab *ht, const char *nam, void *val, int replace)
238 {
239 struct hashent *hp, **hpp;
240 u_int h;
241
242 h = hash(nam);
243 hpp = &ht->ht_tab[h & ht->ht_mask];
244 for (; (hp = *hpp) != NULL; hpp = &hp->h_next) {
245 if (hp->h_name == nam) {
246 if (replace)
247 hp->h_value = val;
248 return (1);
249 }
250 }
251 *hpp = hp = newhashent(nam, h);
252 hp->h_value = val;
253 if (++ht->ht_used > ht->ht_lim)
254 ht_expand(ht);
255 return (0);
256 }
257
258 void *
ht_lookup(struct hashtab * ht,const char * nam)259 ht_lookup(struct hashtab *ht, const char *nam)
260 {
261 struct hashent *hp, **hpp;
262 u_int h;
263
264 h = hash(nam);
265 hpp = &ht->ht_tab[h & ht->ht_mask];
266 for (; (hp = *hpp) != NULL; hpp = &hp->h_next)
267 if (hp->h_name == nam)
268 return (hp->h_value);
269 return (NULL);
270 }
271