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 2003 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 * This file contains a basic dictionary implementation which stores
31 * arbitrary key-value mappings. It is used by libpool to store
32 * information about element pointers (pool_elem_t) in the kernel
33 * provider implementation.
34 */
35
36 #include <stdio.h>
37 #include <stdlib.h>
38 #include <sys/types.h>
39 #include <unistd.h>
40 #include <string.h>
41 #include <assert.h>
42
43 #include "dict.h"
44
45 /*
46 * HASH_64_INIT is the same as the INIT value since it is the value
47 * used by FNV (FNV1_64_INIT). More details on FNV are available at:
48 *
49 * http://www.isthe.com/chongo/tech/comp/fnv/index.html
50 */
51 #define HASH_64_INIT (0xcbf29ce484222325ULL) /* Hash initializer */
52
53 /*
54 * HASH_64_PRIME is a large prime number chosen to minimize hashing
55 * collisions.
56 */
57 #define HASH_64_PRIME (0x100000001b3ULL) /* Large Prime */
58
59 /*
60 * DICT_SIZE is chosen as it is the nearest prime to 2^9 (512). 512 is
61 * chosen as it is unlikely that this dictionary will contain more
62 * elements than this in normal operation. Of course overflow in each
63 * bucket is acceptable, but if there is too much overflow, then
64 * performance will degrade to that of a list.
65 */
66 #define DICT_SIZE 509 /* Reasonable prime */
67
68 /*
69 * Data Types
70 */
71
72 /*
73 * A key bucket.
74 */
75 typedef struct dict_bucket
76 {
77 const void *db_key; /* key */
78 void *db_value; /* value */
79 struct dict_bucket *db_next; /* next bucket */
80 } dict_bucket_t;
81
82 /*
83 * A dictionary which holds a mapping between a key and a value.
84 * dh_change - detects changes to the dictionary.
85 * dh_cmp - comparison function
86 * dh_hash - hashing function
87 * dh_buckets - key storage
88 * dh_size - # of buckets
89 */
90 struct dict_hdl {
91 uint64_t dh_change;
92 int (*dh_cmp)(const void *, const void *);
93 uint64_t (*dh_hash)(const void *);
94 uint64_t dh_length;
95 dict_bucket_t **dh_buckets;
96 uint64_t dh_size;
97 };
98
99 /*
100 * Utility functions. Mainly used for debugging
101 */
102
103 #if defined(DEBUG)
104
105 static void bit_print_32(unsigned int);
106 static void bit_print_64(unsigned long long);
107
108 #endif /* DEBUG */
109
110 /*
111 * Default functions for hashing and comparing if the user does not specify
112 * these values when creating the dictionary.
113 */
114 static int cmp_addr(const void *, const void *);
115 static uint64_t hash_addr(const void *);
116
117 /*
118 * static functions
119 */
120
121 #if defined(DEBUG)
122
123 /*
124 * Print to standard out the bit representation of the supplied value
125 */
126 void
bit_print_32(unsigned int v)127 bit_print_32(unsigned int v)
128 {
129 #pragma error_messages(off, E_INTEGER_OVERFLOW_DETECTED)
130 int i, mask = 1 << 31;
131 #pragma error_messages(on, E_INTEGER_OVERFLOW_DETECTED)
132
133 for (i = 1; i <= 32; i++) {
134 (void) putchar(((v & mask) == 0) ? '0' : '1');
135 v <<= 1;
136 if (i % 8 == 0 && i != 32)
137 (void) putchar(' ');
138 }
139 (void) putchar('\n');
140 }
141
142 /*
143 * Print to standard out the bit representation of the supplied value
144 */
145 void
bit_print_64(unsigned long long v)146 bit_print_64(unsigned long long v)
147 {
148 #pragma error_messages(off, E_INTEGER_OVERFLOW_DETECTED)
149 long long mask = 1ll << 63;
150 #pragma error_messages(on, E_INTEGER_OVERFLOW_DETECTED)
151 int i;
152
153 for (i = 1; i <= 64; i++) {
154 (void) putchar(((v & mask) == 0) ? '0' : '1');
155 v <<= 1;
156 if (i % 8 == 0 && i != 64)
157 (void) putchar(' ');
158 }
159 (void) putchar('\n');
160 }
161
162
163
164 #endif /* DEBUG */
165
166 /*
167 * Default comparison function which is used if no comparison function
168 * is supplied when the dictionary is created. The default behaviour
169 * is to compare memory address.
170 */
171 int
cmp_addr(const void * x,const void * y)172 cmp_addr(const void *x, const void *y)
173 {
174 return (x != y);
175 }
176
177
178 /*
179 * The default hashing function which is used if no hashing function
180 * is provided when the dictionary is created. The default behaviour
181 * is to use the hash_buf() function.
182 */
183 uint64_t
hash_addr(const void * key)184 hash_addr(const void *key)
185 {
186 return (hash_buf(&key, sizeof (key)));
187 }
188
189
190 /*
191 * public interface
192 */
193
194 /*
195 * Return a hash which is built by manipulating each byte in the
196 * supplied data. The hash logic follows the approach suggested in the
197 * FNV hash.
198 */
199 uint64_t
hash_buf(const void * buf,size_t len)200 hash_buf(const void *buf, size_t len)
201 {
202 uchar_t *start = (uchar_t *)buf;
203 uchar_t *end = start + len;
204 uint64_t hash = HASH_64_INIT;
205
206 while (start < end) {
207 hash *= HASH_64_PRIME;
208 hash ^= (uint64_t)*start++;
209 }
210
211 return (hash);
212 }
213
214
215 /*
216 * Return a hash which is built by manipulating each byte in the
217 * supplied string. The hash logic follows the approach suggested in
218 * the FNV hash.
219 */
220 uint64_t
hash_str(const char * str)221 hash_str(const char *str)
222 {
223 uchar_t *p = (uchar_t *)str;
224 uint64_t hash = HASH_64_INIT;
225
226 while (*p) {
227 hash *= HASH_64_PRIME;
228 hash ^= (uint64_t)*p++;
229 }
230
231 return (hash);
232 }
233
234 /*
235 * Return the number of keys held in the supplied dictionary.
236 */
237 uint64_t
dict_length(dict_hdl_t * hdl)238 dict_length(dict_hdl_t *hdl)
239 {
240 return (hdl->dh_length);
241 }
242
243 /*
244 * Free the supplied dictionary and all it's associated resource.
245 */
246 void
dict_free(dict_hdl_t ** hdl)247 dict_free(dict_hdl_t **hdl)
248 {
249 if ((*hdl)->dh_length > 0) {
250 uint64_t i;
251 for (i = 0; i < (*hdl)->dh_size; i++) {
252 dict_bucket_t *this, *next;
253 for (this = (*hdl)->dh_buckets[i]; this != NULL;
254 this = next) {
255 next = this->db_next;
256 free(this);
257 }
258 }
259 }
260 free((*hdl)->dh_buckets);
261 free((*hdl));
262 *hdl = NULL;
263 }
264
265 /*
266 * Create a new dictionary using the supplied comparison and hashing
267 * functions. If none are supplied then the defaults are used.
268 */
269 dict_hdl_t *
dict_new(int (* cmp)(const void *,const void *),uint64_t (* hash)(const void *))270 dict_new(int (*cmp)(const void *, const void *),
271 uint64_t (*hash)(const void *))
272 {
273 dict_hdl_t *hdl;
274
275 if ((hdl = calloc(1, sizeof (dict_hdl_t))) == NULL)
276 return (NULL);
277 hdl->dh_size = DICT_SIZE;
278 if ((hdl->dh_buckets = calloc(hdl->dh_size, sizeof (dict_bucket_t *)))
279 == NULL) {
280 free(hdl);
281 return (NULL);
282 }
283 hdl->dh_cmp = cmp ? cmp : cmp_addr;
284 hdl->dh_hash = hash ? hash : hash_addr;
285 return (hdl);
286 }
287
288 /*
289 * Get a value from the hash. Null is returned if the key cannot be
290 * found.
291 */
292 void *
dict_get(dict_hdl_t * hdl,const void * key)293 dict_get(dict_hdl_t *hdl, const void *key)
294 {
295 uint64_t i;
296 dict_bucket_t *bucket;
297
298 i = (*hdl->dh_hash)(key)%hdl->dh_size;
299 for (bucket = hdl->dh_buckets[i]; bucket != NULL;
300 bucket = bucket->db_next)
301 if ((*hdl->dh_cmp)(key, bucket->db_key) == 0)
302 break;
303 return (bucket ? bucket->db_value : NULL);
304 }
305
306 /*
307 * Put an entry into the hash. Null is returned if this key was not
308 * already present, otherwise the previous value is returned.
309 */
310 void *
dict_put(dict_hdl_t * hdl,const void * key,void * value)311 dict_put(dict_hdl_t *hdl, const void *key, void *value)
312 {
313 uint64_t i;
314 dict_bucket_t *bucket;
315 void *prev = NULL;
316
317 i = (*hdl->dh_hash)(key)%hdl->dh_size;
318 for (bucket = hdl->dh_buckets[i]; bucket != NULL;
319 bucket = bucket->db_next)
320 if ((*hdl->dh_cmp)(key, bucket->db_key) == 0)
321 break;
322 if (bucket) {
323 prev = bucket->db_value;
324 } else {
325 bucket = malloc(sizeof (dict_bucket_t));
326 bucket->db_key = key;
327 bucket->db_next = hdl->dh_buckets[i];
328 hdl->dh_buckets[i] = bucket;
329 hdl->dh_length++;
330 }
331 hdl->dh_change++;
332 bucket->db_value = value;
333 return (prev);
334 }
335
336 /*
337 * Remove the key/value from the dictionary. The value is returned if
338 * the key is found. NULL is returned if the key cannot be located.
339 */
340 void *
dict_remove(dict_hdl_t * hdl,const void * key)341 dict_remove(dict_hdl_t *hdl, const void *key)
342 {
343 uint64_t i;
344 dict_bucket_t **pbucket;
345
346 hdl->dh_change++;
347 i = (*hdl->dh_hash)(key)%hdl->dh_size;
348
349 for (pbucket = &hdl->dh_buckets[i]; *pbucket != NULL;
350 pbucket = &(*pbucket)->db_next) {
351 if ((*hdl->dh_cmp)(key, (*pbucket)->db_key) == 0) {
352 dict_bucket_t *bucket = *pbucket;
353 void *value = bucket->db_value;
354
355 *pbucket = bucket->db_next;
356 free(bucket);
357 hdl->dh_length--;
358 return (value);
359 }
360 }
361 return (NULL);
362 }
363
364 /*
365 * For all entries in the dictionary call the user supplied function
366 * (apply) with the key, value and user supplied data. If the
367 * dictionary is modifed while this function is executing, then the
368 * function will fail with an assertion about table modifcation.
369 */
370 void
dict_map(dict_hdl_t * hdl,void (* apply)(const void *,void **,void *),void * cl)371 dict_map(dict_hdl_t *hdl, void (*apply)(const void *, void **, void *),
372 void *cl)
373 {
374 uint64_t i;
375 dict_bucket_t *bucket = NULL;
376 uint64_t change_stamp = hdl->dh_change;
377
378 for (i = 0; i < hdl->dh_size; i++) {
379 for (bucket = hdl->dh_buckets[i]; bucket != NULL;
380 bucket = bucket->db_next) {
381 apply(bucket->db_key, &bucket->db_value, cl);
382 if (hdl->dh_change != change_stamp)
383 assert(!"table modified illegally");
384 }
385 }
386 }
387