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