GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.sbin/config/hash.c Lines: 0 86 0.0 %
Date: 2017-11-13 Branches: 0 40 0.0 %

Line Branch Exec Source
1
/*	$OpenBSD: hash.c,v 1.18 2015/01/17 07:37:14 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/param.h>	/* ALIGNBYTES */
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 *poolalloc(size_t);
81
static void ht_init(struct hashtab *, size_t);
82
static void ht_expand(struct hashtab *);
83
/*
84
 * Allocate space that will never be freed.
85
 */
86
static void *
87
poolalloc(size_t size)
88
{
89
	char *p;
90
	size_t alloc;
91
	static char *pool;
92
	static size_t nleft;
93
94
	if (nleft < size) {
95
		/*
96
		 * Compute a `good' size to allocate via malloc.
97
		 * 16384 is a guess at a good page size for malloc;
98
		 * 32 is a guess at malloc's overhead.
99
		 */
100
		alloc = ROUND(size + 32, 16384) - 32;
101
		p = emalloc(alloc);
102
		nleft = alloc - size;
103
	} else {
104
		p = pool;
105
		nleft -= size;
106
	}
107
	pool = p + size;
108
	return (p);
109
}
110
111
/*
112
 * Initialize a new hash table.  The size must be a power of 2.
113
 */
114
static void
115
ht_init(struct hashtab *ht, size_t sz)
116
{
117
	struct hashent **h;
118
	u_int n;
119
120
	h = ereallocarray(NULL, sz, sizeof *h);
121
	ht->ht_tab = h;
122
	ht->ht_size = sz;
123
	ht->ht_mask = sz - 1;
124
	for (n = 0; n < sz; n++)
125
		*h++ = NULL;
126
	ht->ht_used = 0;
127
	ht->ht_lim = HASHFRACTION(sz);
128
}
129
130
/*
131
 * Expand an existing hash table.
132
 */
133
static void
134
ht_expand(struct hashtab *ht)
135
{
136
	struct hashent *p, **h, **oldh, *q;
137
	u_int n, i;
138
139
	n = ht->ht_size * 2;
140
	h = ecalloc(n, sizeof *h);
141
	oldh = ht->ht_tab;
142
	n--;
143
	for (i = ht->ht_size; i != 0; i--) {
144
		for (p = *oldh++; p != NULL; p = q) {
145
			q = p->h_next;
146
			p->h_next = h[p->h_hash & n];
147
			h[p->h_hash & n] = p;
148
		}
149
	}
150
	free(ht->ht_tab);
151
	ht->ht_tab = h;
152
	ht->ht_mask = n;
153
	ht->ht_size = ++n;
154
	ht->ht_lim = HASHFRACTION(n);
155
}
156
157
/*
158
 * Make a new hash entry, setting its h_next to NULL.
159
 */
160
static __inline struct hashent *
161
newhashent(const char *name, u_int h)
162
{
163
	struct	hashent *hp;
164
	char	*m;
165
166
	m = poolalloc(sizeof(*hp) + ALIGNBYTES);
167
	hp = (struct hashent *)ALIGN(m);
168
	hp->h_name = name;
169
	hp->h_hash = h;
170
	hp->h_next = NULL;
171
	return (hp);
172
}
173
174
/*
175
 * Hash a string.
176
 */
177
static __inline u_int
178
hash(const char *str)
179
{
180
	u_int h;
181
182
	for (h = 0; *str;)
183
		h = (h << 5) + h + *str++;
184
	return (h);
185
}
186
187
void
188
initintern(void)
189
{
190
191
	ht_init(&strings, 128);
192
}
193
194
/*
195
 * Generate a single unique copy of the given string.  We expect this
196
 * function to be used frequently, so it should be fast.
197
 */
198
const char *
199
intern(const char *s)
200
{
201
	struct hashtab *ht;
202
	struct hashent *hp, **hpp;
203
	u_int h;
204
	char *p;
205
	size_t l;
206
207
	ht = &strings;
208
	h = hash(s);
209
	hpp = &ht->ht_tab[h & ht->ht_mask];
210
	for (; (hp = *hpp) != NULL; hpp = &hp->h_next)
211
		if (hp->h_hash == h && strcmp(hp->h_name, s) == 0)
212
			return (hp->h_name);
213
	l = strlen(s) + 1;
214
	p = poolalloc(l);
215
	bcopy(s, p, l);
216
	*hpp = newhashent(p, h);
217
	if (++ht->ht_used > ht->ht_lim)
218
		ht_expand(ht);
219
	return (p);
220
}
221
222
struct hashtab *
223
ht_new(void)
224
{
225
	struct hashtab *ht;
226
227
	ht = emalloc(sizeof *ht);
228
	ht_init(ht, 8);
229
	return (ht);
230
}
231
232
/*
233
 * Remove.
234
 */
235
int
236
ht_remove(struct hashtab *ht, const char *nam)
237
{
238
	struct hashent *hp, *thp;
239
	u_int h;
240
241
	h = hash(nam);
242
	hp = ht->ht_tab[h & ht->ht_mask];
243
	while (hp && hp->h_name == nam)	{
244
		ht->ht_tab[h & ht->ht_mask] = hp->h_next;
245
		/* XXX free hp ? */
246
		hp = ht->ht_tab[h & ht->ht_mask];
247
	}
248
249
	if ((hp = ht->ht_tab[h & ht->ht_mask]) == NULL)
250
		return (0);
251
252
	for (thp = hp->h_next; thp != NULL; thp = hp->h_next) {
253
		if (thp->h_name == nam) {
254
			hp->h_next = thp->h_next;
255
			/* XXX free thp ? */
256
		} else
257
			hp = thp;
258
	}
259
260
	return (0);
261
}
262
263
/*
264
 * Insert and/or replace.
265
 */
266
int
267
ht_insrep(struct hashtab *ht, const char *nam, void *val, int replace)
268
{
269
	struct hashent *hp, **hpp;
270
	u_int h;
271
272
	h = hash(nam);
273
	hpp = &ht->ht_tab[h & ht->ht_mask];
274
	for (; (hp = *hpp) != NULL; hpp = &hp->h_next) {
275
		if (hp->h_name == nam) {
276
			if (replace)
277
				hp->h_value = val;
278
			return (1);
279
		}
280
	}
281
	*hpp = hp = newhashent(nam, h);
282
	hp->h_value = val;
283
	if (++ht->ht_used > ht->ht_lim)
284
		ht_expand(ht);
285
	return (0);
286
}
287
288
void *
289
ht_lookup(struct hashtab *ht, const char *nam)
290
{
291
	struct hashent *hp, **hpp;
292
	u_int h;
293
294
	h = hash(nam);
295
	hpp = &ht->ht_tab[h & ht->ht_mask];
296
	for (; (hp = *hpp) != NULL; hpp = &hp->h_next)
297
		if (hp->h_name == nam)
298
			return (hp->h_value);
299
	return (NULL);
300
}