1/*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License, Version 1.0 only
6 * (the "License").  You may not use this file except in compliance
7 * with the License.
8 *
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or http://www.opensolaris.org/os/licensing.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
13 *
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
19 *
20 * CDDL HEADER END
21 */
22/*
23 * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
24 * Use is subject to license terms.
25 */
26
27#pragma ident	"@(#)hash.c	1.5	05/06/08 SMI"
28
29/*
30 * Routines for manipulating hash tables
31 */
32
33#if !defined(__APPLE__)
34#include <stdio.h>
35#include <stdlib.h>
36#include <strings.h>
37#include <sys/types.h>
38#include <sys/sysmacros.h>
39
40#include "hash.h"
41#include "memory.h"
42#include "list.h"
43
44#else
45#include <stdio.h>
46#include <stdlib.h>
47#include <strings.h>
48#include <sys/types.h>
49// #include <sys/sysmacros.h>
50
51#include "darwin_shim.h"
52#include "hash.h"
53#include "memory.h"
54#include "list.h"
55
56#endif /* __APPLE__ */
57
58struct hash {
59	int h_nbuckets;
60	list_t **h_buckets;
61
62	int (*h_hashfn)(int, void *);
63	int (*h_cmp)(void *, void *);
64};
65
66struct hash_data {
67	hash_t *hd_hash;
68	int (*hd_fun)();
69	void *hd_key;
70	void *hd_private;
71
72	void *hd_ret;
73};
74
75static int
76hash_def_hash(int nbuckets, uintptr_t data)
77{
78	return (data % nbuckets);
79}
80
81static int
82hash_def_cmp(uintptr_t d1, uintptr_t d2)
83{
84	return (d1 != d2);
85}
86
87
88int
89hash_name(int nbuckets, const char *name)
90{
91	const char *c;
92	ulong_t g;
93	int h = 0;
94
95	for (c = name; *c; c++) {
96		h = (h << 4) + *c;
97		if ((g = (h & 0xf0000000)) != 0) {
98			h ^= (g >> 24);
99			h ^= g;
100		}
101	}
102
103	return (h % nbuckets);
104}
105
106hash_t *
107hash_new(int nbuckets, int (*hashfn)(int, void *), int (*cmp)(void *, void *))
108{
109	hash_t *hash;
110
111	hash = xmalloc(sizeof (hash_t));
112	hash->h_buckets = xcalloc(sizeof (list_t *) * nbuckets);
113	hash->h_nbuckets = nbuckets;
114	hash->h_hashfn = hashfn ? hashfn : (int (*)())hash_def_hash;
115	hash->h_cmp = cmp ? cmp : (int (*)())hash_def_cmp;
116
117	return (hash);
118}
119
120void
121hash_add(hash_t *hash, void *key)
122{
123	int bucket = hash->h_hashfn(hash->h_nbuckets, key);
124
125	list_add(&hash->h_buckets[bucket], key);
126}
127
128static int
129hash_add_cb(void *node, void *private)
130{
131	hash_add((hash_t *)private, node);
132	return (0);
133}
134
135void
136hash_merge(hash_t *to, hash_t *from)
137{
138	(void) hash_iter(from, hash_add_cb, to);
139}
140
141static int
142hash_remove_cb(void *key1, void *key2, hash_t *hash)
143{
144	return (hash->h_cmp(key1, key2));
145}
146
147void
148hash_remove(hash_t *hash, void *key)
149{
150	int bucket = hash->h_hashfn(hash->h_nbuckets, key);
151
152	(void) list_remove(&hash->h_buckets[bucket], key,
153	    (int (*)())hash_remove_cb, hash);
154}
155
156int
157hash_match(hash_t *hash, void *key, int (*fun)(void *, void *),
158    void *private)
159{
160	int bucket = hash->h_hashfn(hash->h_nbuckets, key);
161
162	return (list_iter(hash->h_buckets[bucket], fun, private) < 0);
163}
164
165static int
166hash_find_list_cb(void *node, struct hash_data *hd)
167{
168	int cbrc;
169	int rc = 0;
170
171	if (hd->hd_hash->h_cmp(hd->hd_key, node) == 0) {
172		if ((cbrc = hd->hd_fun(node, hd->hd_private)) < 0)
173			return (cbrc);
174		rc += cbrc;
175	}
176
177	return (rc);
178}
179
180int
181hash_find_iter(hash_t *hash, void *key, int (*fun)(void *, void *),
182    void *private)
183{
184	int bucket = hash->h_hashfn(hash->h_nbuckets, key);
185	struct hash_data hd;
186
187	hd.hd_hash = hash;
188	hd.hd_fun = fun;
189	hd.hd_key = key;
190	hd.hd_private = private;
191
192	return (list_iter(hash->h_buckets[bucket], (int (*)())hash_find_list_cb,
193	    &hd));
194}
195
196/* stop on first match */
197static int
198hash_find_first_cb(void *node, struct hash_data *hd)
199{
200	if (hd->hd_hash->h_cmp(hd->hd_key, node) == 0) {
201		hd->hd_ret = node;
202		return (-1);
203	}
204
205	return (0);
206}
207
208int
209hash_find(hash_t *hash, void *key, void **value)
210{
211	int ret;
212	struct hash_data hd;
213
214	hd.hd_hash = hash;
215	hd.hd_fun = hash_find_first_cb;
216	hd.hd_key = key;
217
218	ret = hash_match(hash, key, (int (*)())hash_find_first_cb, &hd);
219	if (ret && value)
220		*value = hd.hd_ret;
221
222	return (ret);
223}
224
225int
226hash_iter(hash_t *hash, int (*fun)(void *, void *), void *private)
227{
228	int cumrc = 0;
229	int cbrc;
230	int i;
231
232	for (i = 0; i < hash->h_nbuckets; i++) {
233		if (hash->h_buckets[i] != NULL) {
234			if ((cbrc = list_iter(hash->h_buckets[i], fun,
235			    private)) < 0)
236				return (cbrc);
237			cumrc += cbrc;
238		}
239	}
240
241	return (cumrc);
242}
243
244int
245hash_count(hash_t *hash)
246{
247	int num, i;
248
249	for (num = 0, i = 0; i < hash->h_nbuckets; i++)
250		num += list_count(hash->h_buckets[i]);
251
252	return (num);
253}
254
255void
256hash_free(hash_t *hash, void (*datafree)(void *, void *), void *private)
257{
258	int i;
259
260	if (hash == NULL)
261		return;
262
263	for (i = 0; i < hash->h_nbuckets; i++)
264		list_free(hash->h_buckets[i], datafree, private);
265	free(hash->h_buckets);
266	free(hash);
267}
268
269void
270hash_stats(hash_t *hash, int verbose)
271{
272	int min = list_count(hash->h_buckets[0]);
273	int minidx = 0;
274	int max = min;
275	int maxidx = 0;
276	int tot = min;
277	int count;
278	int i;
279
280	if (min && verbose)
281		printf("%3d: %d\n", 0, min);
282	for (i = 1; i < hash->h_nbuckets; i++) {
283		count = list_count(hash->h_buckets[i]);
284		if (min > count) {
285			min = count;
286			minidx = i;
287		}
288		if (max < count) {
289			max = count;
290			maxidx = i;
291		}
292		if (count && verbose)
293			printf("%3d: %d\n", i, count);
294		tot += count;
295	}
296
297	printf("Hash statistics:\n");
298	printf(" Buckets: %d\n", hash->h_nbuckets);
299	printf(" Items  : %d\n", tot);
300	printf(" Min/Max: %d in #%d, %d in #%d\n", min, minidx, max, maxidx);
301	printf(" Average: %5.2f\n", (float)tot / (float)hash->h_nbuckets);
302}
303