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