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