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