1 /* Copyright (C) 2013-2016, The Regents of The University of Michigan.
2 All rights reserved.
3 This software was developed in the APRIL Robotics Lab under the
4 direction of Edwin Olson, ebolson@umich.edu. This software may be
5 available under alternative licensing terms; contact the address above.
6 Redistribution and use in source and binary forms, with or without
7 modification, are permitted provided that the following conditions are met:
8 1. Redistributions of source code must retain the above copyright notice, this
9 list of conditions and the following disclaimer.
10 2. Redistributions in binary form must reproduce the above copyright notice,
11 this list of conditions and the following disclaimer in the documentation
12 and/or other materials provided with the distribution.
13 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
14 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
15 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
16 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
17 ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
18 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
19 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
20 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
21 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
22 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
23 The views and conclusions contained in the software and documentation are those
24 of the authors and should not be interpreted as representing official policies,
25 either expressed or implied, of the Regents of The University of Michigan.
26 */
27
28 #include <stdio.h>
29 #include <stdlib.h>
30 #include <string.h>
31 #include <assert.h>
32
33 #include "zhash.h"
34
35 // force a rehash when our capacity is less than this many times the size
36 #define ZHASH_FACTOR_CRITICAL 2
37
38 // When resizing, how much bigger do we want to be? (should be greater than _CRITICAL)
39 #define ZHASH_FACTOR_REALLOC 4
40
41 struct zhash
42 {
43 size_t keysz, valuesz;
44 int entrysz; // valid byte (1) + keysz + values
45
46 uint32_t(*hash)(const void *a);
47
48 // returns 1 if equal
49 int(*equals)(const void *a, const void *b);
50
51 int size; // # of items in hash table
52
53 char *entries; // each entry of size entrysz;
54 int nentries; // how many entries are allocated? Never 0.
55 };
56
zhash_create_capacity(size_t keysz,size_t valuesz,uint32_t (* hash)(const void * a),int (* equals)(const void * a,const void * b),int capacity)57 zhash_t *zhash_create_capacity(size_t keysz, size_t valuesz,
58 uint32_t(*hash)(const void *a), int(*equals)(const void *a, const void*b),
59 int capacity)
60 {
61 assert(hash != NULL);
62 assert(equals != NULL);
63
64 // resize...
65 int _nentries = ZHASH_FACTOR_REALLOC * capacity;
66 if (_nentries < 8)
67 _nentries = 8;
68
69 // to a power of 2.
70 int nentries = _nentries;
71 if ((nentries & (nentries - 1)) != 0) {
72 nentries = 8;
73 while (nentries < _nentries)
74 nentries *= 2;
75 }
76
77 zhash_t *zh = (zhash_t*) calloc(1, sizeof(zhash_t));
78 zh->keysz = keysz;
79 zh->valuesz = valuesz;
80 zh->hash = hash;
81 zh->equals = equals;
82 zh->nentries = nentries;
83
84 zh->entrysz = static_cast<int>(1 + zh->keysz + zh->valuesz);
85
86 zh->entries = (char *)calloc(zh->nentries, zh->entrysz);
87 zh->nentries = nentries;
88
89 return zh;
90 }
91
zhash_create(size_t keysz,size_t valuesz,uint32_t (* hash)(const void * a),int (* equals)(const void * a,const void * b))92 zhash_t *zhash_create(size_t keysz, size_t valuesz,
93 uint32_t(*hash)(const void *a), int(*equals)(const void *a, const void *b))
94 {
95 return zhash_create_capacity(keysz, valuesz, hash, equals, 8);
96 }
97
zhash_destroy(zhash_t * zh)98 void zhash_destroy(zhash_t *zh)
99 {
100 if (zh == NULL)
101 return;
102
103 free(zh->entries);
104 free(zh);
105 }
106
zhash_size(const zhash_t * zh)107 int zhash_size(const zhash_t *zh)
108 {
109 return zh->size;
110 }
111
zhash_clear(zhash_t * zh)112 void zhash_clear(zhash_t *zh)
113 {
114 memset(zh->entries, 0, zh->nentries * zh->entrysz);
115 zh->size = 0;
116 }
117
zhash_get_volatile(const zhash_t * zh,const void * key,void * out_value)118 int zhash_get_volatile(const zhash_t *zh, const void *key, void *out_value)
119 {
120 uint32_t code = zh->hash(key);
121 uint32_t entry_idx = code & (zh->nentries - 1);
122
123 while (zh->entries[entry_idx * zh->entrysz]) {
124 void *this_key = &zh->entries[entry_idx * zh->entrysz + 1];
125 if (zh->equals(key, this_key)) {
126 *((void**) out_value) = &zh->entries[entry_idx * zh->entrysz + 1 + zh->keysz];
127 return 1;
128 }
129
130 entry_idx = (entry_idx + 1) & (zh->nentries - 1);
131 }
132
133 return 0;
134 }
135
zhash_get(const zhash_t * zh,const void * key,void * out_value)136 int zhash_get(const zhash_t *zh, const void *key, void *out_value)
137 {
138 void *tmp;
139 if (zhash_get_volatile(zh, key, &tmp)) {
140 memcpy(out_value, tmp, zh->valuesz);
141 return 1;
142 }
143
144 return 0;
145 }
146
zhash_put(zhash_t * zh,const void * key,const void * value,void * oldkey,void * oldvalue)147 int zhash_put(zhash_t *zh, const void *key, const void *value, void *oldkey, void *oldvalue)
148 {
149 uint32_t code = zh->hash(key);
150 uint32_t entry_idx = code & (zh->nentries - 1);
151
152 while (zh->entries[entry_idx * zh->entrysz]) {
153 void *this_key = &zh->entries[entry_idx * zh->entrysz + 1];
154 void *this_value = &zh->entries[entry_idx * zh->entrysz + 1 + zh->keysz];
155
156 if (zh->equals(key, this_key)) {
157 // replace
158 if (oldkey)
159 memcpy(oldkey, this_key, zh->keysz);
160 if (oldvalue)
161 memcpy(oldvalue, this_value, zh->valuesz);
162 memcpy(this_key, key, zh->keysz);
163 memcpy(this_value, value, zh->valuesz);
164 zh->entries[entry_idx * zh->entrysz] = 1; // mark valid
165 return 1;
166 }
167
168 entry_idx = (entry_idx + 1) & (zh->nentries - 1);
169 }
170
171 // add the entry
172 zh->entries[entry_idx * zh->entrysz] = 1;
173 memcpy(&zh->entries[entry_idx * zh->entrysz + 1], key, zh->keysz);
174 memcpy(&zh->entries[entry_idx * zh->entrysz + 1 + zh->keysz], value, zh->valuesz);
175 zh->size++;
176
177 if (zh->nentries < ZHASH_FACTOR_CRITICAL * zh->size) {
178 zhash_t *newhash = zhash_create_capacity(zh->keysz, zh->valuesz,
179 zh->hash, zh->equals,
180 zh->size);
181
182 for (int entry_idx = 0; entry_idx < zh->nentries; entry_idx++) {
183
184 if (zh->entries[entry_idx * zh->entrysz]) {
185 void *this_key = &zh->entries[entry_idx * zh->entrysz + 1];
186 void *this_value = &zh->entries[entry_idx * zh->entrysz + 1 + zh->keysz];
187 if (zhash_put(newhash, this_key, this_value, NULL, NULL))
188 assert(0); // shouldn't already be present.
189 }
190 }
191
192 // play switch-a-roo
193 zhash_t tmp;
194 memcpy(&tmp, zh, sizeof(zhash_t));
195 memcpy(zh, newhash, sizeof(zhash_t));
196 memcpy(newhash, &tmp, sizeof(zhash_t));
197 zhash_destroy(newhash);
198 }
199
200 return 0;
201 }
202
zhash_remove(zhash_t * zh,const void * key,void * old_key,void * old_value)203 int zhash_remove(zhash_t *zh, const void *key, void *old_key, void *old_value)
204 {
205 uint32_t code = zh->hash(key);
206 uint32_t entry_idx = code & (zh->nentries - 1);
207
208 while (zh->entries[entry_idx * zh->entrysz]) {
209 void *this_key = &zh->entries[entry_idx * zh->entrysz + 1];
210 void *this_value = &zh->entries[entry_idx * zh->entrysz + 1 + zh->keysz];
211
212 if (zh->equals(key, this_key)) {
213 if (old_key)
214 memcpy(old_key, this_key, zh->keysz);
215 if (old_value)
216 memcpy(old_value, this_value, zh->valuesz);
217
218 // mark this entry as available
219 zh->entries[entry_idx * zh->entrysz] = 0;
220 zh->size--;
221
222 // reinsert any consecutive entries that follow
223 while (1) {
224 entry_idx = (entry_idx + 1) & (zh->nentries - 1);
225
226 if (zh->entries[entry_idx * zh->entrysz]) {
227 // completely remove this entry
228 char *tmp = (char *)malloc(sizeof(char)*zh->entrysz);
229 memcpy(tmp, &zh->entries[entry_idx * zh->entrysz], zh->entrysz);
230 zh->entries[entry_idx * zh->entrysz] = 0;
231 zh->size--;
232 // reinsert it
233 if (zhash_put(zh, &tmp[1], &tmp[1+zh->keysz], NULL, NULL))
234 assert(0);
235 free(tmp);
236 } else {
237 break;
238 }
239 }
240 return 1;
241 }
242
243 entry_idx = (entry_idx + 1) & (zh->nentries - 1);
244 }
245
246 return 0;
247 }
248
zhash_copy(const zhash_t * zh)249 zhash_t *zhash_copy(const zhash_t *zh)
250 {
251 zhash_t *newhash = zhash_create_capacity(zh->keysz, zh->valuesz,
252 zh->hash, zh->equals,
253 zh->size);
254
255 for (int entry_idx = 0; entry_idx < zh->nentries; entry_idx++) {
256 if (zh->entries[entry_idx * zh->entrysz]) {
257 void *this_key = &zh->entries[entry_idx * zh->entrysz + 1];
258 void *this_value = &zh->entries[entry_idx * zh->entrysz + 1 + zh->keysz];
259 if (zhash_put(newhash, this_key, this_value, NULL, NULL))
260 assert(0); // shouldn't already be present.
261 }
262 }
263
264 return newhash;
265 }
266
zhash_contains(const zhash_t * zh,const void * key)267 int zhash_contains(const zhash_t *zh, const void *key)
268 {
269 void *tmp;
270 return zhash_get_volatile(zh, key, &tmp);
271 }
272
zhash_iterator_init(zhash_t * zh,zhash_iterator_t * zit)273 void zhash_iterator_init(zhash_t *zh, zhash_iterator_t *zit)
274 {
275 zit->zh = zh;
276 zit->czh = zh;
277 zit->last_entry = -1;
278 }
279
zhash_iterator_init_const(const zhash_t * zh,zhash_iterator_t * zit)280 void zhash_iterator_init_const(const zhash_t *zh, zhash_iterator_t *zit)
281 {
282 zit->zh = NULL;
283 zit->czh = zh;
284 zit->last_entry = -1;
285 }
286
zhash_iterator_next_volatile(zhash_iterator_t * zit,void * outkey,void * outvalue)287 int zhash_iterator_next_volatile(zhash_iterator_t *zit, void *outkey, void *outvalue)
288 {
289 const zhash_t *zh = zit->czh;
290
291 while (1) {
292 if (zit->last_entry + 1 >= zh->nentries)
293 return 0;
294
295 zit->last_entry++;
296
297 if (zh->entries[zit->last_entry * zh->entrysz]) {
298 void *this_key = &zh->entries[zit->last_entry * zh->entrysz + 1];
299 void *this_value = &zh->entries[zit->last_entry * zh->entrysz + 1 + zh->keysz];
300
301 if (outkey != NULL)
302 *((void**) outkey) = this_key;
303 if (outvalue != NULL)
304 *((void**) outvalue) = this_value;
305
306 return 1;
307 }
308 }
309 }
310
zhash_iterator_next(zhash_iterator_t * zit,void * outkey,void * outvalue)311 int zhash_iterator_next(zhash_iterator_t *zit, void *outkey, void *outvalue)
312 {
313 const zhash_t *zh = zit->czh;
314
315 void *outkeyp, *outvaluep;
316
317 if (!zhash_iterator_next_volatile(zit, &outkeyp, &outvaluep))
318 return 0;
319
320 if (outkey != NULL)
321 memcpy(outkey, outkeyp, zh->keysz);
322 if (outvalue != NULL)
323 memcpy(outvalue, outvaluep, zh->valuesz);
324
325 return 1;
326 }
327
zhash_iterator_remove(zhash_iterator_t * zit)328 void zhash_iterator_remove(zhash_iterator_t *zit)
329 {
330 assert(zit->zh); // can't call _remove on a iterator with const zhash
331 zhash_t *zh = zit->zh;
332
333 zh->entries[zit->last_entry * zh->entrysz] = 0;
334 zh->size--;
335
336 // re-insert following entries
337 int entry_idx = (zit->last_entry + 1) & (zh->nentries - 1);
338 while (zh->entries[entry_idx *zh->entrysz]) {
339 // completely remove this entry
340 char *tmp = (char *)malloc(sizeof(char)*zh->entrysz);
341 memcpy(tmp, &zh->entries[entry_idx * zh->entrysz], zh->entrysz);
342 zh->entries[entry_idx * zh->entrysz] = 0;
343 zh->size--;
344
345 // reinsert it
346 if (zhash_put(zh, &tmp[1], &tmp[1+zh->keysz], NULL, NULL))
347 assert(0);
348 free(tmp);
349
350 entry_idx = (entry_idx + 1) & (zh->nentries - 1);
351 }
352
353 zit->last_entry--;
354 }
355
zhash_map_keys(zhash_t * zh,void (* f)(void *))356 void zhash_map_keys(zhash_t *zh, void (*f)(void *))
357 {
358 assert(zh != NULL);
359 if (f == NULL)
360 return;
361
362 zhash_iterator_t itr;
363 zhash_iterator_init(zh, &itr);
364
365 void *key, *value;
366
367 while(zhash_iterator_next_volatile(&itr, &key, &value)) {
368 f(key);
369 }
370 }
371
zhash_vmap_keys(zhash_t * zh,void (* f)(void *))372 void zhash_vmap_keys(zhash_t * zh, void (*f)(void *))
373 {
374 assert(zh != NULL);
375 if (f == NULL)
376 return;
377
378 zhash_iterator_t itr;
379 zhash_iterator_init(zh, &itr);
380
381 void *key, *value;
382
383 while(zhash_iterator_next_volatile(&itr, &key, &value)) {
384 void *p = *(void**) key;
385 f(p);
386 }
387 }
388
zhash_map_values(zhash_t * zh,void (* f)(void *))389 void zhash_map_values(zhash_t * zh, void (*f)(void *))
390 {
391 assert(zh != NULL);
392 if (f == NULL)
393 return;
394
395 zhash_iterator_t itr;
396 zhash_iterator_init(zh, &itr);
397
398 void *key, *value;
399 while(zhash_iterator_next_volatile(&itr, &key, &value)) {
400 f(value);
401 }
402 }
403
zhash_vmap_values(zhash_t * zh,void (* f)(void *))404 void zhash_vmap_values(zhash_t * zh, void (*f)(void *))
405 {
406 assert(zh != NULL);
407 if (f == NULL)
408 return;
409
410 zhash_iterator_t itr;
411 zhash_iterator_init(zh, &itr);
412
413 void *key, *value;
414 while(zhash_iterator_next_volatile(&itr, &key, &value)) {
415 void *p = *(void**) value;
416 f(p);
417 }
418 }
419
zhash_keys(const zhash_t * zh)420 zarray_t *zhash_keys(const zhash_t *zh)
421 {
422 assert(zh != NULL);
423
424 zarray_t *za = zarray_create(zh->keysz);
425
426 zhash_iterator_t itr;
427 zhash_iterator_init_const(zh, &itr);
428
429 void *key, *value;
430 while(zhash_iterator_next_volatile(&itr, &key, &value)) {
431 zarray_add(za, key);
432 }
433
434 return za;
435 }
436
zhash_values(const zhash_t * zh)437 zarray_t *zhash_values(const zhash_t *zh)
438 {
439 assert(zh != NULL);
440
441 zarray_t *za = zarray_create(zh->valuesz);
442
443 zhash_iterator_t itr;
444 zhash_iterator_init_const(zh, &itr);
445
446 void *key, *value;
447 while(zhash_iterator_next_volatile(&itr, &key, &value)) {
448 zarray_add(za, value);
449 }
450
451 return za;
452 }
453
454
zhash_uint32_hash(const void * _a)455 uint32_t zhash_uint32_hash(const void *_a)
456 {
457 assert(_a != NULL);
458
459 uint32_t a = *((uint32_t*) _a);
460 return a;
461 }
462
zhash_uint32_equals(const void * _a,const void * _b)463 int zhash_uint32_equals(const void *_a, const void *_b)
464 {
465 assert(_a != NULL);
466 assert(_b != NULL);
467
468 uint32_t a = *((uint32_t*) _a);
469 uint32_t b = *((uint32_t*) _b);
470
471 return a==b;
472 }
473
zhash_uint64_hash(const void * _a)474 uint32_t zhash_uint64_hash(const void *_a)
475 {
476 assert(_a != NULL);
477
478 uint64_t a = *((uint64_t*) _a);
479 return (uint32_t) (a ^ (a >> 32));
480 }
481
zhash_uint64_equals(const void * _a,const void * _b)482 int zhash_uint64_equals(const void *_a, const void *_b)
483 {
484 assert(_a != NULL);
485 assert(_b != NULL);
486
487 uint64_t a = *((uint64_t*) _a);
488 uint64_t b = *((uint64_t*) _b);
489
490 return a==b;
491 }
492
493
494 union uintpointer
495 {
496 const void *p;
497 uint32_t i;
498 };
499
zhash_ptr_hash(const void * a)500 uint32_t zhash_ptr_hash(const void *a)
501 {
502 assert(a != NULL);
503
504 union uintpointer ip;
505 ip.p = * (void**)a;
506
507 // compute a hash from the lower 32 bits of the pointer (on LE systems)
508 uint32_t hash = ip.i;
509 hash ^= (hash >> 7);
510
511 return hash;
512 }
513
514
zhash_ptr_equals(const void * a,const void * b)515 int zhash_ptr_equals(const void *a, const void *b)
516 {
517 assert(a != NULL);
518 assert(b != NULL);
519
520 const void * ptra = * (void**)a;
521 const void * ptrb = * (void**)b;
522 return ptra == ptrb;
523 }
524
525
zhash_str_equals(const void * _a,const void * _b)526 int zhash_str_equals(const void *_a, const void *_b)
527 {
528 assert(_a != NULL);
529 assert(_b != NULL);
530
531 char *a = * (char**)_a;
532 char *b = * (char**)_b;
533
534 return !strcmp(a, b);
535 }
536
zhash_str_hash(const void * _a)537 uint32_t zhash_str_hash(const void *_a)
538 {
539 assert(_a != NULL);
540
541 char *a = * (char**)_a;
542
543 int32_t hash = 0;
544 while (*a != 0) {
545 hash = (hash << 7) + (hash >> 23);
546 hash += *a;
547 a++;
548 }
549
550 return (uint32_t) hash;
551 }
552
553
zhash_debug(zhash_t * zh)554 void zhash_debug(zhash_t *zh)
555 {
556 for (int entry_idx = 0; entry_idx < zh->nentries; entry_idx++) {
557 char *k, *v;
558 memcpy(&k, &zh->entries[entry_idx * zh->entrysz + 1], sizeof(char*));
559 memcpy(&v, &zh->entries[entry_idx * zh->entrysz + 1 + zh->keysz], sizeof(char*));
560 printf("%d: %d, %s => %s\n", entry_idx, zh->entries[entry_idx * zh->entrysz], k, v);
561 }
562 }
563