Head

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 %


/*	$OpenBSD: hash.c,v 1.18 2015/01/17 07:37:14 deraadt Exp $	*/
/*	$NetBSD: hash.c,v 1.4 1996/11/07 22:59:43 gwr Exp $	*/

/*
 * Copyright (c) 1992, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * This software was developed by the Computer Systems Engineering group
 * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and
 * contributed to Berkeley.
 *
 * All advertising materials mentioning features or use of this software
 * must display the following acknowledgement:
 *	This product includes software developed by the University of
 *	California, Lawrence Berkeley Laboratories.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *	from: @(#)hash.c	8.1 (Berkeley) 6/6/93
 */

#include <sys/param.h>	/* ALIGNBYTES */

#include <stdlib.h>
#include <string.h>

#include "config.h"

/*
 * Interned strings are kept in a hash table.  By making each string
 * unique, the program can compare strings by comparing pointers.
 */
struct hashent {
	struct	hashent *h_next;	/* hash buckets are chained */
	const char *h_name;		/* the string */
	u_int	h_hash;			/* its hash value */
	void	*h_value;		/* other values (for name=value) */
};
struct hashtab {
	size_t	ht_size;		/* size (power of 2) */
	u_int	ht_mask;		/* == ht_size - 1 */
	u_int	ht_used;		/* number of entries used */
	u_int	ht_lim;			/* when to expand */
	struct	hashent **ht_tab;	/* base of table */
};
static struct hashtab strings;

/*
 * HASHFRACTION controls ht_lim, which in turn controls the average chain
 * length.  We allow a few entries, on average, as comparing them is usually
 * cheap (the h_hash values prevent a strcmp).
 */
#define	HASHFRACTION(sz) ((sz) * 3 / 2)

/* round up to next multiple of y, where y is a power of 2 */
#define	ROUND(x, y) (((x) + (y) - 1) & ~((y) - 1))

static void *poolalloc(size_t);
static void ht_init(struct hashtab *, size_t);
static void ht_expand(struct hashtab *);
/*
 * Allocate space that will never be freed.
 */
static void *
poolalloc(size_t size)
{
	char *p;
	size_t alloc;
	static char *pool;
	static size_t nleft;

	if (nleft < size) {
		/*
		 * Compute a `good' size to allocate via malloc.
		 * 16384 is a guess at a good page size for malloc;
		 * 32 is a guess at malloc's overhead.
		 */
		alloc = ROUND(size + 32, 16384) - 32;
		p = emalloc(alloc);
		nleft = alloc - size;
	} else {
		p = pool;
		nleft -= size;
	}
	pool = p + size;
	return (p);
}

/*
 * Initialize a new hash table.  The size must be a power of 2.
 */
static void
ht_init(struct hashtab *ht, size_t sz)
{
	struct hashent **h;
	u_int n;

	h = ereallocarray(NULL, sz, sizeof *h);
	ht->ht_tab = h;
	ht->ht_size = sz;
	ht->ht_mask = sz - 1;
	for (n = 0; n < sz; n++)
		*h++ = NULL;
	ht->ht_used = 0;
	ht->ht_lim = HASHFRACTION(sz);
}

/*
 * Expand an existing hash table.
 */
static void
ht_expand(struct hashtab *ht)
{
	struct hashent *p, **h, **oldh, *q;
	u_int n, i;

	n = ht->ht_size * 2;
	h = ecalloc(n, sizeof *h);
	oldh = ht->ht_tab;
	n--;
	for (i = ht->ht_size; i != 0; i--) {
		for (p = *oldh++; p != NULL; p = q) {
			q = p->h_next;
			p->h_next = h[p->h_hash & n];
			h[p->h_hash & n] = p;
		}
	}
	free(ht->ht_tab);
	ht->ht_tab = h;
	ht->ht_mask = n;
	ht->ht_size = ++n;
	ht->ht_lim = HASHFRACTION(n);
}

/*
 * Make a new hash entry, setting its h_next to NULL.
 */
static __inline struct hashent *
newhashent(const char *name, u_int h)
{
	struct	hashent *hp;
	char	*m;

	m = poolalloc(sizeof(*hp) + ALIGNBYTES);
	hp = (struct hashent *)ALIGN(m);
	hp->h_name = name;
	hp->h_hash = h;
	hp->h_next = NULL;
	return (hp);
}

/*
 * Hash a string.
 */
static __inline u_int
hash(const char *str)
{
	u_int h;

	for (h = 0; *str;)
		h = (h << 5) + h + *str++;
	return (h);
}

void
initintern(void)
{

	ht_init(&strings, 128);
}

/*
 * Generate a single unique copy of the given string.  We expect this
 * function to be used frequently, so it should be fast.
 */
const char *
intern(const char *s)
{
	struct hashtab *ht;
	struct hashent *hp, **hpp;
	u_int h;
	char *p;
	size_t l;

	ht = &strings;
	h = hash(s);
	hpp = &ht->ht_tab[h & ht->ht_mask];
	for (; (hp = *hpp) != NULL; hpp = &hp->h_next)
		if (hp->h_hash == h && strcmp(hp->h_name, s) == 0)
			return (hp->h_name);
	l = strlen(s) + 1;
	p = poolalloc(l);
	bcopy(s, p, l);
	*hpp = newhashent(p, h);
	if (++ht->ht_used > ht->ht_lim)
		ht_expand(ht);
	return (p);
}

struct hashtab *
ht_new(void)
{
	struct hashtab *ht;

	ht = emalloc(sizeof *ht);
	ht_init(ht, 8);
	return (ht);
}

/*
 * Remove.
 */
int
ht_remove(struct hashtab *ht, const char *nam)
{
	struct hashent *hp, *thp;
	u_int h;

	h = hash(nam);
	hp = ht->ht_tab[h & ht->ht_mask];
	while (hp && hp->h_name == nam)	{
		ht->ht_tab[h & ht->ht_mask] = hp->h_next;
		/* XXX free hp ? */
		hp = ht->ht_tab[h & ht->ht_mask];
	}

	if ((hp = ht->ht_tab[h & ht->ht_mask]) == NULL)
		return (0);

	for (thp = hp->h_next; thp != NULL; thp = hp->h_next) {
		if (thp->h_name == nam) {
			hp->h_next = thp->h_next;
			/* XXX free thp ? */
		} else
			hp = thp;
	}

	return (0);
}

/*
 * Insert and/or replace.
 */
int
ht_insrep(struct hashtab *ht, const char *nam, void *val, int replace)
{
	struct hashent *hp, **hpp;
	u_int h;

	h = hash(nam);
	hpp = &ht->ht_tab[h & ht->ht_mask];
	for (; (hp = *hpp) != NULL; hpp = &hp->h_next) {
		if (hp->h_name == nam) {
			if (replace)
				hp->h_value = val;
			return (1);
		}
	}
	*hpp = hp = newhashent(nam, h);
	hp->h_value = val;
	if (++ht->ht_used > ht->ht_lim)
		ht_expand(ht);
	return (0);
}

void *
ht_lookup(struct hashtab *ht, const char *nam)
{
	struct hashent *hp, **hpp;
	u_int h;

	h = hash(nam);
	hpp = &ht->ht_tab[h & ht->ht_mask];
	for (; (hp = *hpp) != NULL; hpp = &hp->h_next)
		if (hp->h_name == nam)
			return (hp->h_value);
	return (NULL);
}


Generated by: GCOVR (Version 3.3)

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			}