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