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 int i, mask = 1 << 31;
128
129 for (i = 1; i <= 32; i++) {
130 (void) putchar(((v & mask) == 0) ? '0' : '1');
131 v <<= 1;
132 if (i % 8 == 0 && i != 32)
133 (void) putchar(' ');
134 }
135 (void) putchar('\n');
136 }
137
138 /*
139 * Print to standard out the bit representation of the supplied value
140 */
141 void
bit_print_64(unsigned long long v)142 bit_print_64(unsigned long long v)
143 {
144 long long mask = 1ll << 63;
145 int i;
146
147 for (i = 1; i <= 64; i++) {
148 (void) putchar(((v & mask) == 0) ? '0' : '1');
149 v <<= 1;
150 if (i % 8 == 0 && i != 64)
151 (void) putchar(' ');
152 }
153 (void) putchar('\n');
154 }
155
156
157
158 #endif /* DEBUG */
159
160 /*
161 * Default comparison function which is used if no comparison function
162 * is supplied when the dictionary is created. The default behaviour
163 * is to compare memory address.
164 */
165 int
cmp_addr(const void * x,const void * y)166 cmp_addr(const void *x, const void *y)
167 {
168 return (x != y);
169 }
170
171
172 /*
173 * The default hashing function which is used if no hashing function
174 * is provided when the dictionary is created. The default behaviour
175 * is to use the hash_buf() function.
176 */
177 uint64_t
hash_addr(const void * key)178 hash_addr(const void *key)
179 {
180 return (hash_buf(&key, sizeof (key)));
181 }
182
183
184 /*
185 * public interface
186 */
187
188 /*
189 * Return a hash which is built by manipulating each byte in the
190 * supplied data. The hash logic follows the approach suggested in the
191 * FNV hash.
192 */
193 uint64_t
hash_buf(const void * buf,size_t len)194 hash_buf(const void *buf, size_t len)
195 {
196 uchar_t *start = (uchar_t *)buf;
197 uchar_t *end = start + len;
198 uint64_t hash = HASH_64_INIT;
199
200 while (start < end) {
201 hash *= HASH_64_PRIME;
202 hash ^= (uint64_t)*start++;
203 }
204
205 return (hash);
206 }
207
208
209 /*
210 * Return a hash which is built by manipulating each byte in the
211 * supplied string. The hash logic follows the approach suggested in
212 * the FNV hash.
213 */
214 uint64_t
hash_str(const char * str)215 hash_str(const char *str)
216 {
217 uchar_t *p = (uchar_t *)str;
218 uint64_t hash = HASH_64_INIT;
219
220 while (*p) {
221 hash *= HASH_64_PRIME;
222 hash ^= (uint64_t)*p++;
223 }
224
225 return (hash);
226 }
227
228 /*
229 * Return the number of keys held in the supplied dictionary.
230 */
231 uint64_t
dict_length(dict_hdl_t * hdl)232 dict_length(dict_hdl_t *hdl)
233 {
234 return (hdl->dh_length);
235 }
236
237 /*
238 * Free the supplied dictionary and all it's associated resource.
239 */
240 void
dict_free(dict_hdl_t ** hdl)241 dict_free(dict_hdl_t **hdl)
242 {
243 if ((*hdl)->dh_length > 0) {
244 uint64_t i;
245 for (i = 0; i < (*hdl)->dh_size; i++) {
246 dict_bucket_t *this, *next;
247 for (this = (*hdl)->dh_buckets[i]; this != NULL;
248 this = next) {
249 next = this->db_next;
250 free(this);
251 }
252 }
253 }
254 free((*hdl)->dh_buckets);
255 free((*hdl));
256 *hdl = NULL;
257 }
258
259 /*
260 * Create a new dictionary using the supplied comparison and hashing
261 * functions. If none are supplied then the defaults are used.
262 */
263 dict_hdl_t *
dict_new(int (* cmp)(const void *,const void *),uint64_t (* hash)(const void *))264 dict_new(int (*cmp)(const void *, const void *),
265 uint64_t (*hash)(const void *))
266 {
267 dict_hdl_t *hdl;
268
269 if ((hdl = calloc(1, sizeof (dict_hdl_t))) == NULL)
270 return (NULL);
271 hdl->dh_size = DICT_SIZE;
272 if ((hdl->dh_buckets = calloc(hdl->dh_size, sizeof (dict_bucket_t *)))
273 == NULL) {
274 free(hdl);
275 return (NULL);
276 }
277 hdl->dh_cmp = cmp ? cmp : cmp_addr;
278 hdl->dh_hash = hash ? hash : hash_addr;
279 return (hdl);
280 }
281
282 /*
283 * Get a value from the hash. Null is returned if the key cannot be
284 * found.
285 */
286 void *
dict_get(dict_hdl_t * hdl,const void * key)287 dict_get(dict_hdl_t *hdl, const void *key)
288 {
289 uint64_t i;
290 dict_bucket_t *bucket;
291
292 i = (*hdl->dh_hash)(key)%hdl->dh_size;
293 for (bucket = hdl->dh_buckets[i]; bucket != NULL;
294 bucket = bucket->db_next)
295 if ((*hdl->dh_cmp)(key, bucket->db_key) == 0)
296 break;
297 return (bucket ? bucket->db_value : NULL);
298 }
299
300 /*
301 * Put an entry into the hash. Null is returned if this key was not
302 * already present, otherwise the previous value is returned.
303 */
304 void *
dict_put(dict_hdl_t * hdl,const void * key,void * value)305 dict_put(dict_hdl_t *hdl, const void *key, void *value)
306 {
307 uint64_t i;
308 dict_bucket_t *bucket;
309 void *prev = NULL;
310
311 i = (*hdl->dh_hash)(key)%hdl->dh_size;
312 for (bucket = hdl->dh_buckets[i]; bucket != NULL;
313 bucket = bucket->db_next)
314 if ((*hdl->dh_cmp)(key, bucket->db_key) == 0)
315 break;
316 if (bucket) {
317 prev = bucket->db_value;
318 } else {
319 bucket = malloc(sizeof (dict_bucket_t));
320 bucket->db_key = key;
321 bucket->db_next = hdl->dh_buckets[i];
322 hdl->dh_buckets[i] = bucket;
323 hdl->dh_length++;
324 }
325 hdl->dh_change++;
326 bucket->db_value = value;
327 return (prev);
328 }
329
330 /*
331 * Remove the key/value from the dictionary. The value is returned if
332 * the key is found. NULL is returned if the key cannot be located.
333 */
334 void *
dict_remove(dict_hdl_t * hdl,const void * key)335 dict_remove(dict_hdl_t *hdl, const void *key)
336 {
337 uint64_t i;
338 dict_bucket_t **pbucket;
339
340 hdl->dh_change++;
341 i = (*hdl->dh_hash)(key)%hdl->dh_size;
342
343 for (pbucket = &hdl->dh_buckets[i]; *pbucket != NULL;
344 pbucket = &(*pbucket)->db_next) {
345 if ((*hdl->dh_cmp)(key, (*pbucket)->db_key) == 0) {
346 dict_bucket_t *bucket = *pbucket;
347 void *value = bucket->db_value;
348
349 *pbucket = bucket->db_next;
350 free(bucket);
351 hdl->dh_length--;
352 return (value);
353 }
354 }
355 return (NULL);
356 }
357
358 /*
359 * For all entries in the dictionary call the user supplied function
360 * (apply) with the key, value and user supplied data. If the
361 * dictionary is modifed while this function is executing, then the
362 * function will fail with an assertion about table modifcation.
363 */
364 void
dict_map(dict_hdl_t * hdl,void (* apply)(const void *,void **,void *),void * cl)365 dict_map(dict_hdl_t *hdl, void (*apply)(const void *, void **, void *),
366 void *cl)
367 {
368 uint64_t i;
369 dict_bucket_t *bucket = NULL;
370 uint64_t change_stamp = hdl->dh_change;
371
372 for (i = 0; i < hdl->dh_size; i++) {
373 for (bucket = hdl->dh_buckets[i]; bucket != NULL;
374 bucket = bucket->db_next) {
375 apply(bucket->db_key, &bucket->db_value, cl);
376 if (hdl->dh_change != change_stamp)
377 assert(!"table modified illegally");
378 }
379 }
380 }
381