1 /*
2 * Copyright (c) 2004 Stefan Walter
3 * Copyright (c) 2011 Collabora Ltd.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * * Redistributions of source code must retain the above
10 * copyright notice, this list of conditions and the
11 * following disclaimer.
12 * * Redistributions in binary form must reproduce the
13 * above copyright notice, this list of conditions and
14 * the following disclaimer in the documentation and/or
15 * other materials provided with the distribution.
16 * * The names of contributors to this software may not be
17 * used to endorse or promote products derived from this
18 * software without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
23 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
24 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
25 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
26 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
27 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
28 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
29 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
30 * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
31 * DAMAGE.
32 */
33
34 #include "config.h"
35
36 #include "debug.h"
37 #include "dict.h"
38 #include "hash.h"
39
40 #include <sys/types.h>
41
42 #include <assert.h>
43 #include <stdint.h>
44 #include <stdlib.h>
45 #include <string.h>
46
47 struct _p11_dict {
48 p11_dict_hasher hash_func;
49 p11_dict_equals equal_func;
50 p11_destroyer key_destroy_func;
51 p11_destroyer value_destroy_func;
52
53 struct _p11_dictbucket **buckets;
54 unsigned int num_items;
55 unsigned int num_buckets;
56 };
57
58 typedef struct _p11_dictbucket {
59 void *key;
60 unsigned int hashed;
61 void *value;
62 struct _p11_dictbucket *next;
63 } dictbucket;
64
65 static dictbucket *
next_entry(p11_dictiter * iter)66 next_entry (p11_dictiter *iter)
67 {
68 dictbucket *bucket = iter->next;
69 while (!bucket) {
70 if (iter->index >= iter->dict->num_buckets)
71 return NULL;
72 bucket = iter->dict->buckets[iter->index++];
73 }
74 iter->next = bucket->next;
75 return bucket;
76 }
77
78
79 bool
p11_dict_next(p11_dictiter * iter,void ** key,void ** value)80 p11_dict_next (p11_dictiter *iter,
81 void **key,
82 void **value)
83 {
84 dictbucket *bucket = next_entry (iter);
85 if (bucket == NULL)
86 return false;
87 if (key)
88 *key = bucket->key;
89 if (value)
90 *value = bucket->value;
91 return true;
92 }
93
94 void
p11_dict_iterate(p11_dict * dict,p11_dictiter * iter)95 p11_dict_iterate (p11_dict *dict,
96 p11_dictiter *iter)
97 {
98 iter->dict = dict;
99 iter->index = 0;
100 iter->next = NULL;
101 }
102
103 static dictbucket **
lookup_or_create_bucket(p11_dict * dict,const void * key,bool create)104 lookup_or_create_bucket (p11_dict *dict,
105 const void *key,
106 bool create)
107 {
108 dictbucket **bucketp;
109 unsigned int hash;
110
111 /* Perform the hashing */
112 hash = dict->hash_func (key);
113
114 /* scan linked list */
115 for (bucketp = &dict->buckets[hash % dict->num_buckets];
116 *bucketp != NULL; bucketp = &(*bucketp)->next) {
117 if((*bucketp)->hashed == hash && dict->equal_func ((*bucketp)->key, key))
118 break;
119 }
120
121 if ((*bucketp) != NULL || !create)
122 return bucketp;
123
124 /* add a new entry for non-NULL val */
125 (*bucketp) = calloc (1, sizeof (dictbucket));
126
127 if (*bucketp != NULL) {
128 (*bucketp)->key = (void*)key;
129 (*bucketp)->hashed = hash;
130 dict->num_items++;
131 }
132
133 return bucketp;
134 }
135
136 void *
p11_dict_get(p11_dict * dict,const void * key)137 p11_dict_get (p11_dict *dict,
138 const void *key)
139 {
140 dictbucket **bucketp;
141
142 bucketp = lookup_or_create_bucket (dict, key, false);
143 if (bucketp && *bucketp)
144 return (void*)((*bucketp)->value);
145 else
146 return NULL;
147 }
148
149 bool
p11_dict_set(p11_dict * dict,void * key,void * val)150 p11_dict_set (p11_dict *dict,
151 void *key,
152 void *val)
153 {
154 dictbucket **bucketp;
155 p11_dictiter iter;
156 dictbucket *bucket;
157 dictbucket **new_buckets;
158 unsigned int num_buckets;
159
160 bucketp = lookup_or_create_bucket (dict, key, true);
161 if(bucketp && *bucketp) {
162
163 /* Destroy the previous key */
164 if ((*bucketp)->key && (*bucketp)->key != key && dict->key_destroy_func)
165 dict->key_destroy_func ((*bucketp)->key);
166
167 /* Destroy the previous value */
168 if ((*bucketp)->value && (*bucketp)->value != val && dict->value_destroy_func)
169 dict->value_destroy_func ((*bucketp)->value);
170
171 /* replace entry */
172 (*bucketp)->key = key;
173 (*bucketp)->value = val;
174
175 /* check that the collision rate isn't too high */
176 if (dict->num_items > dict->num_buckets) {
177 num_buckets = dict->num_buckets * 2 + 1;
178 new_buckets = (dictbucket **)calloc (num_buckets, sizeof (dictbucket *));
179
180 /* Ignore failures, maybe we can expand later */
181 if(new_buckets) {
182 p11_dict_iterate (dict, &iter);
183 while ((bucket = next_entry (&iter)) != NULL) {
184 unsigned int i = bucket->hashed % num_buckets;
185 bucket->next = new_buckets[i];
186 new_buckets[i] = bucket;
187 }
188
189 free (dict->buckets);
190 dict->buckets = new_buckets;
191 dict->num_buckets = num_buckets;
192 }
193 }
194
195 return true;
196 }
197
198 return_val_if_reached (false);
199 }
200
201 bool
p11_dict_steal(p11_dict * dict,const void * key,void ** stolen_key,void ** stolen_value)202 p11_dict_steal (p11_dict *dict,
203 const void *key,
204 void **stolen_key,
205 void **stolen_value)
206 {
207 dictbucket **bucketp;
208
209 bucketp = lookup_or_create_bucket (dict, key, false);
210 if (bucketp && *bucketp) {
211 dictbucket *old = *bucketp;
212 *bucketp = (*bucketp)->next;
213 --dict->num_items;
214 if (stolen_key)
215 *stolen_key = old->key;
216 if (stolen_value)
217 *stolen_value = old->value;
218 free (old);
219 return true;
220 }
221
222 return false;
223
224 }
225
226 bool
p11_dict_remove(p11_dict * dict,const void * key)227 p11_dict_remove (p11_dict *dict,
228 const void *key)
229 {
230 void *old_key;
231 void *old_value;
232
233 if (!p11_dict_steal (dict, key, &old_key, &old_value))
234 return false;
235
236 if (dict->key_destroy_func)
237 dict->key_destroy_func (old_key);
238 if (dict->value_destroy_func)
239 dict->value_destroy_func (old_value);
240 return true;
241 }
242
243 void
p11_dict_clear(p11_dict * dict)244 p11_dict_clear (p11_dict *dict)
245 {
246 dictbucket *bucket, *next;
247 unsigned int i;
248
249 /* Free all entries in the array */
250 for (i = 0; i < dict->num_buckets; ++i) {
251 bucket = dict->buckets[i];
252 while (bucket != NULL) {
253 next = bucket->next;
254 if (dict->key_destroy_func)
255 dict->key_destroy_func (bucket->key);
256 if (dict->value_destroy_func)
257 dict->value_destroy_func (bucket->value);
258 free (bucket);
259 bucket = next;
260 }
261 }
262
263 memset (dict->buckets, 0, dict->num_buckets * sizeof (dictbucket *));
264 dict->num_items = 0;
265 }
266
267 p11_dict *
p11_dict_new(p11_dict_hasher hash_func,p11_dict_equals equal_func,p11_destroyer key_destroy_func,p11_destroyer value_destroy_func)268 p11_dict_new (p11_dict_hasher hash_func,
269 p11_dict_equals equal_func,
270 p11_destroyer key_destroy_func,
271 p11_destroyer value_destroy_func)
272 {
273 p11_dict *dict;
274
275 assert (hash_func);
276 assert (equal_func);
277
278 dict = malloc (sizeof (p11_dict));
279 if (dict) {
280 dict->hash_func = hash_func;
281 dict->equal_func = equal_func;
282 dict->key_destroy_func = key_destroy_func;
283 dict->value_destroy_func = value_destroy_func;
284
285 dict->num_buckets = 9;
286 dict->buckets = (dictbucket **)calloc (dict->num_buckets, sizeof (dictbucket *));
287 if (!dict->buckets) {
288 free (dict);
289 return NULL;
290 }
291
292 dict->num_items = 0;
293 }
294
295 return dict;
296 }
297
298 void
p11_dict_free(p11_dict * dict)299 p11_dict_free (p11_dict *dict)
300 {
301 dictbucket *bucket;
302 p11_dictiter iter;
303
304 if (!dict)
305 return;
306
307 p11_dict_iterate (dict, &iter);
308 while ((bucket = next_entry (&iter)) != NULL) {
309 if (dict->key_destroy_func)
310 dict->key_destroy_func (bucket->key);
311 if (dict->value_destroy_func)
312 dict->value_destroy_func (bucket->value);
313 free (bucket);
314 }
315
316 if (dict->buckets)
317 free (dict->buckets);
318
319 free (dict);
320 }
321
322 unsigned int
p11_dict_size(p11_dict * dict)323 p11_dict_size (p11_dict *dict)
324 {
325 return dict->num_items;
326 }
327
328 unsigned int
p11_dict_str_hash(const void * string)329 p11_dict_str_hash (const void *string)
330 {
331 uint32_t hash;
332 p11_hash_murmur3 (&hash, string, strlen (string), NULL);
333 return hash;
334 }
335
336 bool
p11_dict_str_equal(const void * string_one,const void * string_two)337 p11_dict_str_equal (const void *string_one,
338 const void *string_two)
339 {
340 assert (string_one);
341 assert (string_two);
342
343 return strcmp (string_one, string_two) == 0;
344 }
345
346 unsigned int
p11_dict_ulongptr_hash(const void * to_ulong)347 p11_dict_ulongptr_hash (const void *to_ulong)
348 {
349 assert (to_ulong);
350 return (unsigned int)*((unsigned long*)to_ulong);
351 }
352
353 bool
p11_dict_ulongptr_equal(const void * ulong_one,const void * ulong_two)354 p11_dict_ulongptr_equal (const void *ulong_one,
355 const void *ulong_two)
356 {
357 assert (ulong_one);
358 assert (ulong_two);
359 return *((unsigned long*)ulong_one) == *((unsigned long*)ulong_two);
360 }
361
362 unsigned int
p11_dict_intptr_hash(const void * to_int)363 p11_dict_intptr_hash (const void *to_int)
364 {
365 assert (to_int);
366 return (unsigned int)*((int*)to_int);
367 }
368
369 bool
p11_dict_intptr_equal(const void * int_one,const void * int_two)370 p11_dict_intptr_equal (const void *int_one,
371 const void *int_two)
372 {
373 assert (int_one);
374 assert (int_two);
375 return *((int*)int_one) == *((int*)int_two);
376 }
377
378 unsigned int
p11_dict_direct_hash(const void * ptr)379 p11_dict_direct_hash (const void *ptr)
380 {
381 return (unsigned int)(size_t)ptr;
382 }
383
384 bool
p11_dict_direct_equal(const void * ptr_one,const void * ptr_two)385 p11_dict_direct_equal (const void *ptr_one,
386 const void *ptr_two)
387 {
388 return ptr_one == ptr_two;
389 }
390