1/*	$NetBSD: hash.c,v 1.10 2009/04/14 08:59:45 lukem Exp $	*/
2
3/*
4 * Copyright (c) 1994, 1995 Jochen Pohl
5 * All Rights Reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 *    notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 *    notice, this list of conditions and the following disclaimer in the
14 *    documentation and/or other materials provided with the distribution.
15 * 3. All advertising materials mentioning features or use of this software
16 *    must display the following acknowledgement:
17 *      This product includes software developed by Jochen Pohl for
18 *	The NetBSD Project.
19 * 4. The name of the author may not be used to endorse or promote products
20 *    derived from this software without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
23 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
24 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
25 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
27 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
31 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 */
33
34#if HAVE_NBTOOL_CONFIG_H
35#include "nbtool_config.h"
36#endif
37
38#include <sys/cdefs.h>
39#if defined(__RCSID) && !defined(lint)
40__RCSID("$NetBSD: hash.c,v 1.10 2009/04/14 08:59:45 lukem Exp $");
41#endif
42
43/*
44 * XXX Really need a generalized hash table package
45 */
46
47#include <limits.h>
48#include <stddef.h>
49#include <stdlib.h>
50#include <string.h>
51
52#include "lint2.h"
53
54/* pointer to hash table, initialized in inithash() */
55static	hte_t	**htab;
56
57static	int	hash(const char *);
58
59/*
60 * Initialize hash table.
61 */
62void
63_inithash(hte_t ***tablep)
64{
65
66	if (tablep == NULL)
67		tablep = &htab;
68
69	*tablep = xcalloc(HSHSIZ2, sizeof (hte_t *));
70}
71
72/*
73 * Compute hash value from a string.
74 */
75static int
76hash(const char *s)
77{
78	u_int	v;
79	const	u_char *us;
80
81	v = 0;
82	for (us = (const u_char *)s; *us != '\0'; us++) {
83		v = (v << sizeof (v)) + *us;
84		v ^= v >> (sizeof (v) * CHAR_BIT - sizeof (v));
85	}
86	return (v % HSHSIZ2);
87}
88
89/*
90 * Look for a hash table entry. If no hash table entry for the
91 * given name exists and mknew is set, create a new one.
92 */
93hte_t *
94_hsearch(hte_t **table, const char *s, int mknew)
95{
96	int	h;
97	hte_t	*hte;
98
99	if (table == NULL)
100		table = htab;
101
102	h = hash(s);
103	for (hte = table[h]; hte != NULL; hte = hte->h_link) {
104		if (strcmp(hte->h_name, s) == 0)
105			break;
106	}
107
108	if (hte != NULL || !mknew)
109		return (hte);
110
111	/* create a new hte */
112	hte = xmalloc(sizeof (hte_t));
113	hte->h_name = xstrdup(s);
114	hte->h_used = 0;
115	hte->h_def = 0;
116	hte->h_static = 0;
117	hte->h_syms = NULL;
118	hte->h_lsym = &hte->h_syms;
119	hte->h_calls = NULL;
120	hte->h_lcall = &hte->h_calls;
121	hte->h_usyms = NULL;
122	hte->h_lusym = &hte->h_usyms;
123	hte->h_link = table[h];
124	hte->h_hte = NULL;
125	table[h] = hte;
126
127	return (hte);
128}
129
130/*
131 * Call function f for each name in the hash table.
132 */
133void
134_forall(hte_t **table, void (*f)(hte_t *))
135{
136	int	i;
137	hte_t	*hte;
138
139	if (table == NULL)
140		table = htab;
141
142	for (i = 0; i < HSHSIZ2; i++) {
143		for (hte = table[i]; hte != NULL; hte = hte->h_link)
144			(*f)(hte);
145	}
146}
147
148/*
149 * Free all contents of the hash table that this module allocated.
150 */
151void
152_destroyhash(hte_t **table)
153{
154	int	i;
155	hte_t	*hte, *nexthte;
156
157	if (table == NULL)
158		err(1, "_destroyhash called on main hash table");
159
160	for (i = 0; i < HSHSIZ2; i++) {
161		for (hte = table[i]; hte != NULL; hte = nexthte) {
162			free(__UNCONST(hte->h_name));
163			nexthte = hte->h_link;
164			free(hte);
165		}
166	}
167	free(table);
168}
169