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