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