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	"%Z%%M%	%I%	%E% SMI"
28
29/*
30 * Routines for manipulating hash tables
31 */
32
33#include <stdio.h>
34#include <stdlib.h>
35#include <strings.h>
36#include <sys/types.h>
37#include <sys/sysmacros.h>
38
39#include "hash.h"
40#include "memory.h"
41#include "list.h"
42
43struct hash {
44	int h_nbuckets;
45	list_t **h_buckets;
46
47	int (*h_hashfn)(int, void *);
48	int (*h_cmp)(void *, void *);
49};
50
51struct hash_data {
52	hash_t *hd_hash;
53	int (*hd_fun)();
54	void *hd_key;
55	void *hd_private;
56
57	void *hd_ret;
58};
59
60static int
61hash_def_hash(int nbuckets, uintptr_t data)
62{
63	return (data % nbuckets);
64}
65
66static int
67hash_def_cmp(uintptr_t d1, uintptr_t d2)
68{
69	return (d1 != d2);
70}
71
72
73int
74hash_name(int nbuckets, const char *name)
75{
76	const char *c;
77	ulong_t g;
78	int h = 0;
79
80	for (c = name; *c; c++) {
81		h = (h << 4) + *c;
82		if ((g = (h & 0xf0000000)) != 0) {
83			h ^= (g >> 24);
84			h ^= g;
85		}
86	}
87
88	return (h % nbuckets);
89}
90
91hash_t *
92hash_new(int nbuckets, int (*hashfn)(int, void *), int (*cmp)(void *, void *))
93{
94	hash_t *hash;
95
96	hash = xmalloc(sizeof (hash_t));
97	hash->h_buckets = xcalloc(sizeof (list_t *) * nbuckets);
98	hash->h_nbuckets = nbuckets;
99	hash->h_hashfn = hashfn ? hashfn : (int (*)())hash_def_hash;
100	hash->h_cmp = cmp ? cmp : (int (*)())hash_def_cmp;
101
102	return (hash);
103}
104
105void
106hash_add(hash_t *hash, void *key)
107{
108	int bucket = hash->h_hashfn(hash->h_nbuckets, key);
109
110	list_add(&hash->h_buckets[bucket], key);
111}
112
113static int
114hash_add_cb(void *node, void *private)
115{
116	hash_add((hash_t *)private, node);
117	return (0);
118}
119
120void
121hash_merge(hash_t *to, hash_t *from)
122{
123	(void) hash_iter(from, hash_add_cb, to);
124}
125
126static int
127hash_remove_cb(void *key1, void *key2, hash_t *hash)
128{
129	return (hash->h_cmp(key1, key2));
130}
131
132void
133hash_remove(hash_t *hash, void *key)
134{
135	int bucket = hash->h_hashfn(hash->h_nbuckets, key);
136
137	(void) list_remove(&hash->h_buckets[bucket], key,
138	    (int (*)())hash_remove_cb, hash);
139}
140
141int
142hash_match(hash_t *hash, void *key, int (*fun)(void *, void *),
143    void *private)
144{
145	int bucket = hash->h_hashfn(hash->h_nbuckets, key);
146
147	return (list_iter(hash->h_buckets[bucket], fun, private) < 0);
148}
149
150static int
151hash_find_list_cb(void *node, struct hash_data *hd)
152{
153	int cbrc;
154	int rc = 0;
155
156	if (hd->hd_hash->h_cmp(hd->hd_key, node) == 0) {
157		if ((cbrc = hd->hd_fun(node, hd->hd_private)) < 0)
158			return (cbrc);
159		rc += cbrc;
160	}
161
162	return (rc);
163}
164
165int
166hash_find_iter(hash_t *hash, void *key, int (*fun)(void *, void *),
167    void *private)
168{
169	int bucket = hash->h_hashfn(hash->h_nbuckets, key);
170	struct hash_data hd;
171
172	hd.hd_hash = hash;
173	hd.hd_fun = fun;
174	hd.hd_key = key;
175	hd.hd_private = private;
176
177	return (list_iter(hash->h_buckets[bucket], (int (*)())hash_find_list_cb,
178	    &hd));
179}
180
181/* stop on first match */
182static int
183hash_find_first_cb(void *node, struct hash_data *hd)
184{
185	if (hd->hd_hash->h_cmp(hd->hd_key, node) == 0) {
186		hd->hd_ret = node;
187		return (-1);
188	}
189
190	return (0);
191}
192
193int
194hash_find(hash_t *hash, void *key, void **value)
195{
196	int ret;
197	struct hash_data hd;
198
199	hd.hd_hash = hash;
200	hd.hd_fun = hash_find_first_cb;
201	hd.hd_key = key;
202
203	ret = hash_match(hash, key, (int (*)())hash_find_first_cb, &hd);
204	if (ret && value)
205		*value = hd.hd_ret;
206
207	return (ret);
208}
209
210int
211hash_iter(hash_t *hash, int (*fun)(void *, void *), void *private)
212{
213	int cumrc = 0;
214	int cbrc;
215	int i;
216
217	for (i = 0; i < hash->h_nbuckets; i++) {
218		if (hash->h_buckets[i] != NULL) {
219			if ((cbrc = list_iter(hash->h_buckets[i], fun,
220			    private)) < 0)
221				return (cbrc);
222			cumrc += cbrc;
223		}
224	}
225
226	return (cumrc);
227}
228
229int
230hash_count(hash_t *hash)
231{
232	int num, i;
233
234	for (num = 0, i = 0; i < hash->h_nbuckets; i++)
235		num += list_count(hash->h_buckets[i]);
236
237	return (num);
238}
239
240void
241hash_free(hash_t *hash, void (*datafree)(void *, void *), void *private)
242{
243	int i;
244
245	if (hash == NULL)
246		return;
247
248	for (i = 0; i < hash->h_nbuckets; i++)
249		list_free(hash->h_buckets[i], datafree, private);
250	free(hash->h_buckets);
251	free(hash);
252}
253
254void
255hash_stats(hash_t *hash, int verbose)
256{
257	int min = list_count(hash->h_buckets[0]);
258	int minidx = 0;
259	int max = min;
260	int maxidx = 0;
261	int tot = min;
262	int count;
263	int i;
264
265	if (min && verbose)
266		printf("%3d: %d\n", 0, min);
267	for (i = 1; i < hash->h_nbuckets; i++) {
268		count = list_count(hash->h_buckets[i]);
269		if (min > count) {
270			min = count;
271			minidx = i;
272		}
273		if (max < count) {
274			max = count;
275			maxidx = i;
276		}
277		if (count && verbose)
278			printf("%3d: %d\n", i, count);
279		tot += count;
280	}
281
282	printf("Hash statistics:\n");
283	printf(" Buckets: %d\n", hash->h_nbuckets);
284	printf(" Items  : %d\n", tot);
285	printf(" Min/Max: %d in #%d, %d in #%d\n", min, minidx, max, maxidx);
286	printf(" Average: %5.2f\n", (float)tot / (float)hash->h_nbuckets);
287}
288