1 #include "iwhmap.h"
2 #include "iwlog.h"
3 #include "murmur3.h"
4
5 #include <stdlib.h>
6 #include <string.h>
7 #include <errno.h>
8 #include <assert.h>
9
10 #define MIN_BUCKETS 64
11 #define STEPS 4
12
13 struct lru_node;
14
15 typedef struct entry {
16 void *key;
17 void *val;
18 struct lru_node *lru_node;
19 uint32_t hash;
20 } entry_t;
21
22 typedef struct {
23 entry_t *entries;
24 uint32_t used;
25 uint32_t total;
26 } bucket_t;
27
28 typedef struct lru_node {
29 struct lru_node *next;
30 struct lru_node *prev;
31 void *key;
32 } lru_node_t;
33
34 typedef struct _IWHMAP {
35 uint32_t count;
36 uint32_t buckets_mask;
37 bucket_t *buckets;
38
39 int (*cmp_fn)(const void*, const void*);
40 uint32_t (*hash_key_fn)(const void*);
41 void (*kv_free_fn)(void*, void*);
42
43 // LRU
44 struct lru_node *lru_first;
45 struct lru_node *lru_last;
46 iwhmap_lru_eviction_needed lru_ev;
47 void *lru_ev_user_data;
48
49 bool int_key_as_pointer_value;
50 } hmap_t;
51
_noop_kv_free(void * key,void * val)52 static void _noop_kv_free(void *key, void *val) {
53 }
54
_noop_uint64_kv_free(void * key,void * val)55 static void _noop_uint64_kv_free(void *key, void *val) {
56 if (key) {
57 free(key);
58 }
59 }
60
iwhmap_kv_free(void * key,void * val)61 void iwhmap_kv_free(void *key, void *val) {
62 free(key);
63 free(val);
64 }
65
_n_buckets(hmap_t * hm)66 IW_INLINE uint32_t _n_buckets(hmap_t *hm) {
67 return hm->buckets_mask + 1;
68 }
69
_ptr_cmp(const void * v1,const void * v2)70 static int _ptr_cmp(const void *v1, const void *v2) {
71 return v1 > v2 ? 1 : v1 < v2 ? -1 : 0;
72 }
73
_uint32_cmp(const void * v1,const void * v2)74 static int _uint32_cmp(const void *v1, const void *v2) {
75 intptr_t p1 = (intptr_t) v1;
76 intptr_t p2 = (intptr_t) v2;
77 return p1 > p2 ? 1 : p1 < p2 ? -1 : 0;
78 }
79
_uint64_cmp(const void * v1,const void * v2)80 static int _uint64_cmp(const void *v1, const void *v2) {
81 if (sizeof(uintptr_t) >= sizeof(uint64_t)) {
82 intptr_t p1 = (intptr_t) v1;
83 intptr_t p2 = (intptr_t) v2;
84 return p1 > p2 ? 1 : p1 < p2 ? -1 : 0;
85 } else {
86 uint64_t l1, l2;
87 memcpy(&l1, v1, sizeof(l1));
88 memcpy(&l2, v2, sizeof(l2));
89 return l1 > l2 ? 1 : l1 < l2 ? -1 : 0;
90 }
91 }
92
93 // https://gist.github.com/badboy/6267743
94 // https://nullprogram.com/blog/2018/07/31
95
_hash_uint32(uint32_t x)96 IW_INLINE uint32_t _hash_uint32(uint32_t x) {
97 x ^= x >> 17;
98 x *= UINT32_C(0xed5ad4bb);
99 x ^= x >> 11;
100 x *= UINT32_C(0xac4c1b51);
101 x ^= x >> 15;
102 x *= UINT32_C(0x31848bab);
103 x ^= x >> 14;
104 return x;
105 }
106
_hash_uint64(uint64_t x)107 IW_INLINE uint32_t _hash_uint64(uint64_t x) {
108 return _hash_uint32(x) ^ _hash_uint32(x >> 31);
109 }
110
_hash_uint64_key(const void * key)111 IW_INLINE uint32_t _hash_uint64_key(const void *key) {
112 if (sizeof(uintptr_t) >= sizeof(uint64_t)) {
113 return _hash_uint64((uint64_t) key);
114 } else {
115 uint64_t lv;
116 memcpy(&lv, key, sizeof(lv));
117 return _hash_uint64(lv);
118 }
119 }
120
_hash_uint32_key(const void * key)121 IW_INLINE uint32_t _hash_uint32_key(const void *key) {
122 return _hash_uint32((uintptr_t) key);
123 }
124
_hash_buf_key(const void * key)125 IW_INLINE uint32_t _hash_buf_key(const void *key) {
126 return murmur3(key, strlen(key));
127 }
128
iwhmap_create(int (* cmp_fn)(const void *,const void *),uint32_t (* hash_key_fn)(const void *),void (* kv_free_fn)(void *,void *))129 IWHMAP* iwhmap_create(
130 int (*cmp_fn)(const void*, const void*),
131 uint32_t (*hash_key_fn)(const void*),
132 void (*kv_free_fn)(void*, void*)
133 ) {
134 if (!hash_key_fn) {
135 return 0;
136 }
137 if (!cmp_fn) {
138 cmp_fn = _ptr_cmp;
139 }
140 if (!kv_free_fn) {
141 kv_free_fn = _noop_kv_free;
142 }
143
144 hmap_t *hm = malloc(sizeof(*hm));
145 if (!hm) {
146 return 0;
147 }
148 hm->buckets = calloc(MIN_BUCKETS, sizeof(hm->buckets[0]));
149 if (!hm->buckets) {
150 free(hm);
151 return 0;
152 }
153 hm->cmp_fn = cmp_fn;
154 hm->hash_key_fn = hash_key_fn;
155 hm->kv_free_fn = kv_free_fn;
156 hm->buckets_mask = MIN_BUCKETS - 1;
157 hm->count = 0;
158 hm->lru_first = hm->lru_last = 0;
159 hm->lru_ev = 0;
160 hm->lru_ev_user_data = 0;
161 hm->int_key_as_pointer_value = false;
162 return hm;
163 }
164
iwhmap_create_u64(void (* kv_free_fn)(void *,void *))165 IWHMAP* iwhmap_create_u64(void (*kv_free_fn)(void*, void*)) {
166 if (!kv_free_fn) {
167 kv_free_fn = _noop_uint64_kv_free;
168 }
169 hmap_t *hm = iwhmap_create(_uint64_cmp, _hash_uint64_key, kv_free_fn);
170 if (hm) {
171 if (sizeof(uintptr_t) >= sizeof(uint64_t)) {
172 hm->int_key_as_pointer_value = true;
173 }
174 }
175 return hm;
176 }
177
iwhmap_create_u32(void (* kv_free_fn)(void *,void *))178 IWHMAP* iwhmap_create_u32(void (*kv_free_fn)(void*, void*)) {
179 hmap_t *hm = iwhmap_create(_uint32_cmp, _hash_uint32_key, kv_free_fn);
180 if (hm) {
181 hm->int_key_as_pointer_value = true;
182 }
183 return hm;
184 }
185
iwhmap_create_str(void (* kv_free_fn)(void *,void *))186 IWHMAP* iwhmap_create_str(void (*kv_free_fn)(void*, void*)) {
187 return iwhmap_create((int (*)(const void*, const void*)) strcmp, _hash_buf_key, kv_free_fn);
188 }
189
_entry_find(IWHMAP * hm,const void * key,uint32_t hash)190 static entry_t* _entry_find(IWHMAP *hm, const void *key, uint32_t hash) {
191 bucket_t *bucket = hm->buckets + (hash & hm->buckets_mask);
192 entry_t *entry = bucket->entries;
193 for (entry_t *end = entry + bucket->used; entry < end; ++entry) {
194 if (hash == entry->hash && hm->cmp_fn(key, entry->key) == 0) {
195 return entry;
196 }
197 }
198 return 0;
199 }
200
_entry_add(IWHMAP * hm,void * key,uint32_t hash)201 static entry_t* _entry_add(IWHMAP *hm, void *key, uint32_t hash) {
202 entry_t *entry;
203 bucket_t *bucket = hm->buckets + (hash & hm->buckets_mask);
204
205 if (bucket->used + 1 >= bucket->total) {
206 if (UINT32_MAX - bucket->total < STEPS) {
207 errno = EOVERFLOW;
208 return 0;
209 }
210 uint32_t new_total = bucket->total + STEPS;
211 entry_t *new_entries = realloc(bucket->entries, new_total * sizeof(new_entries[0]));
212 if (!new_entries) {
213 return 0;
214 }
215 bucket->entries = new_entries;
216 bucket->total = new_total;
217 }
218 entry = bucket->entries;
219 for (entry_t *end = entry + bucket->used; entry < end; ++entry) {
220 // NOLINTNEXTLINE (clang-analyzer-core.UndefinedBinaryOperatorResult)
221 if ((hash == entry->hash) && (hm->cmp_fn(key, entry->key) == 0)) {
222 return entry;
223 }
224 }
225 ++bucket->used;
226 ++hm->count;
227
228 entry->hash = hash;
229 entry->key = 0;
230 entry->val = 0;
231 entry->lru_node = 0;
232
233 return entry;
234 }
235
_rehash(hmap_t * hm,uint32_t num_buckets)236 static void _rehash(hmap_t *hm, uint32_t num_buckets) {
237 bucket_t *buckets = calloc(num_buckets, sizeof(*buckets));
238 if (!buckets) {
239 return;
240 }
241 assert(!(num_buckets & (num_buckets - 1)));
242 assert(num_buckets != _n_buckets(hm));
243
244 bucket_t *bucket,
245 *bucket_end = hm->buckets + _n_buckets(hm);
246
247 hmap_t hm_copy = *hm;
248 hm_copy.count = 0;
249 hm_copy.buckets_mask = num_buckets - 1;
250 hm_copy.buckets = buckets;
251
252 for (bucket = hm->buckets; bucket < bucket_end; ++bucket) {
253 entry_t *entry_old = bucket->entries;
254 if (entry_old) {
255 entry_t *entry_old_end = entry_old + bucket->used;
256 for ( ; entry_old < entry_old_end; ++entry_old) {
257 entry_t *entry_new = _entry_add(&hm_copy, entry_old->key, entry_old->hash);
258 if (!entry_new) {
259 goto fail;
260 }
261 entry_new->key = entry_old->key;
262 entry_new->val = entry_old->val;
263 entry_new->lru_node = entry_old->lru_node;
264 }
265 }
266 }
267
268 for (bucket = hm->buckets; bucket < bucket_end; ++bucket) {
269 free(bucket->entries);
270 }
271 free(hm->buckets);
272
273 hm->buckets = buckets;
274 hm->buckets_mask = num_buckets - 1;
275
276 assert(hm->count == hm_copy.count);
277 return;
278
279 fail:
280 for (bucket_end = bucket, bucket = hm->buckets; bucket < bucket_end; ++bucket) {
281 free(bucket->entries);
282 }
283 free(buckets);
284 }
285
_lru_entry_update(IWHMAP * hm,entry_t * entry)286 static void _lru_entry_update(IWHMAP *hm, entry_t *entry) {
287 if (entry->lru_node) {
288 entry->lru_node->key = entry->key;
289 if (entry->lru_node->next) {
290 struct lru_node *prev = entry->lru_node->prev;
291 if (prev) {
292 prev->next = entry->lru_node->next;
293 } else {
294 hm->lru_first = entry->lru_node->next;
295 }
296 entry->lru_node->next->prev = prev;
297 hm->lru_last->next = entry->lru_node;
298 entry->lru_node->next = 0;
299 entry->lru_node->prev = hm->lru_last;
300 hm->lru_last = entry->lru_node;
301 }
302 } else {
303 entry->lru_node = malloc(sizeof(*entry->lru_node));
304 if (entry->lru_node) {
305 entry->lru_node->key = entry->key;
306 if (hm->lru_last) {
307 hm->lru_last->next = entry->lru_node;
308 entry->lru_node->next = 0;
309 entry->lru_node->prev = hm->lru_last;
310 hm->lru_last = entry->lru_node;
311 } else {
312 hm->lru_first = hm->lru_last = entry->lru_node;
313 entry->lru_node->next = entry->lru_node->prev = 0;
314 }
315 }
316 }
317 }
318
_lru_entry_remove(IWHMAP * hm,entry_t * entry)319 static void _lru_entry_remove(IWHMAP *hm, entry_t *entry) {
320 if (entry->lru_node->next) {
321 struct lru_node *prev = entry->lru_node->prev;
322 if (prev) {
323 prev->next = entry->lru_node->next;
324 } else {
325 hm->lru_first = entry->lru_node->next;
326 }
327 entry->lru_node->next->prev = prev;
328 } else if (entry->lru_node->prev) {
329 entry->lru_node->prev->next = 0;
330 hm->lru_last = entry->lru_node->prev;
331 } else {
332 hm->lru_last = hm->lru_first = 0;
333 }
334 free(entry->lru_node);
335 entry->lru_node = 0;
336 }
337
iwhmap_get(IWHMAP * hm,const void * key)338 void* iwhmap_get(IWHMAP *hm, const void *key) {
339 uint32_t hash = hm->hash_key_fn(key);
340 entry_t *entry = _entry_find(hm, key, hash);
341 if (entry) {
342 if (hm->lru_ev) {
343 _lru_entry_update(hm, entry);
344 }
345 return entry->val;
346 } else {
347 return 0;
348 }
349 }
350
_entry_remove(IWHMAP * hm,bucket_t * bucket,entry_t * entry)351 static void _entry_remove(IWHMAP *hm, bucket_t *bucket, entry_t *entry) {
352 if (entry->lru_node) {
353 _lru_entry_remove(hm, entry);
354 }
355
356 hm->kv_free_fn(hm->int_key_as_pointer_value ? 0 : entry->key, entry->val);
357
358 if (bucket->used > 1) {
359 entry_t *entry_last = bucket->entries + bucket->used - 1;
360 if (entry != entry_last) {
361 memcpy(entry, entry_last, sizeof(*entry));
362 }
363 }
364 --bucket->used;
365 --hm->count;
366
367 if ((hm->buckets_mask > MIN_BUCKETS - 1) && (hm->count < hm->buckets_mask / 2)) {
368 _rehash(hm, _n_buckets(hm) / 2);
369 } else {
370 uint32_t steps_used = bucket->used / STEPS;
371 uint32_t steps_total = bucket->total / STEPS;
372 if (steps_used + 1 < steps_total) {
373 entry_t *entries_new = realloc(bucket->entries, (steps_used + 1) * STEPS * sizeof(entries_new[0]));
374 if (entries_new) {
375 bucket->entries = entries_new;
376 bucket->total = (steps_used + 1) * STEPS;
377 }
378 }
379 }
380 }
381
iwhmap_remove(IWHMAP * hm,const void * key)382 bool iwhmap_remove(IWHMAP *hm, const void *key) {
383 uint32_t hash = hm->hash_key_fn(key);
384 bucket_t *bucket = hm->buckets + (hash & hm->buckets_mask);
385 entry_t *entry = _entry_find(hm, key, hash);
386 if (entry) {
387 _entry_remove(hm, bucket, entry);
388 return true;
389 } else {
390 return false;
391 }
392 }
393
iwhmap_remove_u64(IWHMAP * hm,uint64_t key)394 bool iwhmap_remove_u64(IWHMAP *hm, uint64_t key) {
395 if (hm->int_key_as_pointer_value) {
396 return iwhmap_remove(hm, (void*) (uintptr_t) key);
397 } else {
398 return iwhmap_remove(hm, &key);
399 }
400 }
401
iwhmap_remove_u32(IWHMAP * hm,uint32_t key)402 bool iwhmap_remove_u32(IWHMAP *hm, uint32_t key) {
403 return iwhmap_remove(hm, (void*) (uintptr_t) key);
404 }
405
iwhmap_put(IWHMAP * hm,void * key,void * val)406 iwrc iwhmap_put(IWHMAP *hm, void *key, void *val) {
407 uint32_t hash = hm->hash_key_fn(key);
408 entry_t *entry = _entry_add(hm, key, hash);
409 if (!entry) {
410 return iwrc_set_errno(IW_ERROR_ERRNO, errno);
411 }
412
413 hm->kv_free_fn(hm->int_key_as_pointer_value ? 0 : entry->key, entry->val);
414
415 entry->key = key;
416 entry->val = val;
417
418 if (hm->lru_ev) {
419 _lru_entry_update(hm, entry);
420 }
421
422 if (hm->count > hm->buckets_mask) {
423 _rehash(hm, _n_buckets(hm) * 2);
424 }
425
426 while (hm->lru_first && hm->lru_ev(hm, hm->lru_ev_user_data)) {
427 hash = hm->hash_key_fn(hm->lru_first->key);
428 bucket_t *bucket = hm->buckets + (hash & hm->buckets_mask);
429 entry = _entry_find(hm, hm->lru_first->key, hash);
430 assert(entry); // Should never be zero.
431 _entry_remove(hm, bucket, entry);
432 }
433
434 return 0;
435 }
436
iwhmap_put_str(IWHMAP * hm,const char * key_,void * val)437 iwrc iwhmap_put_str(IWHMAP *hm, const char *key_, void *val) {
438 char *key = strdup(key_);
439 if (!key) {
440 return iwrc_set_errno(IW_ERROR_ALLOC, errno);
441 }
442 iwrc rc = iwhmap_put(hm, key, val);
443 if (rc) {
444 free(key);
445 }
446 return rc;
447 }
448
iwhmap_rename(IWHMAP * hm,const void * key_old,void * key_new)449 iwrc iwhmap_rename(IWHMAP *hm, const void *key_old, void *key_new) {
450 uint32_t hash = hm->hash_key_fn(key_old);
451 entry_t *entry = _entry_find(hm, key_old, hash);
452 bucket_t *bucket = hm->buckets + (hash & hm->buckets_mask);
453
454 if (entry) {
455 void *val = entry->val;
456 entry->val = 0;
457 _entry_remove(hm, bucket, entry);
458 hash = hm->hash_key_fn(key_new);
459 entry = _entry_add(hm, key_new, hash);
460 if (!entry) {
461 return iwrc_set_errno(IW_ERROR_ERRNO, errno);
462 }
463 hm->kv_free_fn(hm->int_key_as_pointer_value ? 0 : entry->key, entry->val);
464
465 entry->key = key_new;
466 entry->val = val;
467
468 if (hm->lru_ev) {
469 _lru_entry_update(hm, entry);
470 }
471 }
472
473 return 0;
474 }
475
iwhmap_put_u32(IWHMAP * hm,uint32_t key,void * val)476 iwrc iwhmap_put_u32(IWHMAP *hm, uint32_t key, void *val) {
477 return iwhmap_put(hm, (void*) (uintptr_t) key, val);
478 }
479
iwhmap_put_u64(IWHMAP * hm,uint64_t key,void * val)480 iwrc iwhmap_put_u64(IWHMAP *hm, uint64_t key, void *val) {
481 if (hm->int_key_as_pointer_value) {
482 return iwhmap_put(hm, (void*) (uintptr_t) key, val);
483 } else {
484 uint64_t *kv = malloc(sizeof(*kv));
485 if (!kv) {
486 return iwrc_set_errno(IW_ERROR_ALLOC, errno);
487 }
488 memcpy(kv, &key, sizeof(*kv));
489 iwrc rc = iwhmap_put(hm, kv, val);
490 if (rc) {
491 free(kv);
492 }
493 return rc;
494 }
495 }
496
iwhmap_get_u64(IWHMAP * hm,uint64_t key)497 void* iwhmap_get_u64(IWHMAP *hm, uint64_t key) {
498 if (hm->int_key_as_pointer_value) {
499 return iwhmap_get(hm, (void*) (intptr_t) key);
500 } else {
501 return iwhmap_get(hm, &key);
502 }
503 }
504
iwhmap_get_u32(IWHMAP * hm,uint32_t key)505 void* iwhmap_get_u32(IWHMAP *hm, uint32_t key) {
506 return iwhmap_get(hm, (void*) (intptr_t) key);
507 }
508
iwhmap_count(IWHMAP * hm)509 uint32_t iwhmap_count(IWHMAP *hm) {
510 return hm->count;
511 }
512
iwhmap_iter_init(IWHMAP * hm,IWHMAP_ITER * iter)513 void iwhmap_iter_init(IWHMAP *hm, IWHMAP_ITER *iter) {
514 iter->hm = hm;
515 iter->entry = -1;
516 iter->bucket = 0;
517 iter->key = 0;
518 iter->val = 0;
519 }
520
iwhmap_iter_next(IWHMAP_ITER * iter)521 bool iwhmap_iter_next(IWHMAP_ITER *iter) {
522 if (!iter->hm) {
523 return false;
524 }
525 entry_t *entry;
526 bucket_t *bucket = iter->hm->buckets + iter->bucket;
527
528 ++iter->entry;
529 if ((uint32_t) iter->entry >= bucket->used) {
530 uint32_t n = _n_buckets(iter->hm);
531 iter->entry = 0;
532 for (++iter->bucket; iter->bucket < n; ++iter->bucket) {
533 bucket = iter->hm->buckets + iter->bucket;
534 if (bucket->used > 0) {
535 break;
536 }
537 }
538 if (iter->bucket >= n) {
539 return false;
540 }
541 }
542 entry = bucket->entries + iter->entry;
543 iter->key = entry->key;
544 iter->val = entry->val;
545 return true;
546 }
547
iwhmap_clear(IWHMAP * hm)548 void iwhmap_clear(IWHMAP *hm) {
549 if (!hm) {
550 return;
551 }
552 for (bucket_t *b = hm->buckets, *be = hm->buckets + _n_buckets(hm); b < be; ++b) {
553 for (entry_t *e = b->entries, *ee = b->entries + b->used; e < ee; ++e) {
554 hm->kv_free_fn(hm->int_key_as_pointer_value ? 0 : e->key, e->val);
555 }
556 free(b->entries);
557 b->used = 0;
558 b->total = 0;
559 b->entries = 0;
560 }
561 if (_n_buckets(hm) > MIN_BUCKETS) {
562 bucket_t *buckets_new = realloc(hm->buckets, sizeof(buckets_new[0]) * MIN_BUCKETS);
563 if (buckets_new) {
564 memset(buckets_new, 0, sizeof(buckets_new[0]) * MIN_BUCKETS);
565 hm->buckets = buckets_new;
566 hm->buckets_mask = MIN_BUCKETS - 1;
567 }
568 }
569 hm->count = 0;
570 }
571
iwhmap_destroy(IWHMAP * hm)572 void iwhmap_destroy(IWHMAP *hm) {
573 if (!hm) {
574 return;
575 }
576 for (bucket_t *b = hm->buckets, *be = hm->buckets + _n_buckets(hm); b < be; ++b) {
577 if (b->entries) {
578 for (entry_t *e = b->entries, *ee = b->entries + b->used; e < ee; ++e) {
579 hm->kv_free_fn(hm->int_key_as_pointer_value ? 0 : e->key, e->val);
580 }
581 free(b->entries);
582 }
583 }
584 for (lru_node_t *n = hm->lru_first; n; ) {
585 lru_node_t *nn = n->next;
586 free(n);
587 n = nn;
588 }
589 free(hm->buckets);
590 free(hm);
591 }
592
iwhmap_lru_eviction_max_count(IWHMAP * hm,void * max_count_val)593 bool iwhmap_lru_eviction_max_count(IWHMAP *hm, void *max_count_val) {
594 uint32_t max_count = (uintptr_t) max_count_val;
595 return iwhmap_count(hm) > max_count;
596 }
597
iwhmap_lru_init(IWHMAP * hm,iwhmap_lru_eviction_needed ev,void * ev_user_data)598 void iwhmap_lru_init(IWHMAP *hm, iwhmap_lru_eviction_needed ev, void *ev_user_data) {
599 hm->lru_ev = ev;
600 hm->lru_ev_user_data = ev_user_data;
601 }
602