1 #include "hashmap.h"
2 #include <string.h>
3
4 struct ext2fs_hashmap {
5 uint32_t size;
6 uint32_t(*hash)(const void *key, size_t len);
7 void(*free)(void*);
8 struct ext2fs_hashmap_entry *first;
9 struct ext2fs_hashmap_entry *last;
10 #if __GNUC_PREREQ (4, 8)
11 #pragma GCC diagnostic push
12 #pragma GCC diagnostic ignored "-Wpedantic"
13 #endif
14 struct ext2fs_hashmap_entry *entries[0];
15 #if __GNUC_PREREQ (4, 8)
16 #pragma GCC diagnostic pop
17 #endif
18 };
19
ext2fs_djb2_hash(const void * str,size_t size)20 uint32_t ext2fs_djb2_hash(const void *str, size_t size)
21 {
22 int c;
23 const char *s = str;
24 uint32_t hash = 5381;
25
26 while (size-- > 0) {
27 c = *s++;
28 hash = ((hash << 5) + hash) + c;
29 }
30 return hash;
31 }
32
ext2fs_hashmap_create(uint32_t (* hash_fct)(const void *,size_t),void (* free_fct)(void *),size_t size)33 struct ext2fs_hashmap *ext2fs_hashmap_create(
34 uint32_t(*hash_fct)(const void*, size_t),
35 void(*free_fct)(void*), size_t size)
36 {
37 struct ext2fs_hashmap *h = calloc(sizeof(struct ext2fs_hashmap) +
38 sizeof(struct ext2fs_hashmap_entry) * size, 1);
39 if (!h)
40 return NULL;
41
42 h->size = size;
43 h->free = free_fct;
44 h->hash = hash_fct;
45 h->first = h->last = NULL;
46 return h;
47 }
48
ext2fs_hashmap_add(struct ext2fs_hashmap * h,void * data,const void * key,size_t key_len)49 int ext2fs_hashmap_add(struct ext2fs_hashmap *h,
50 void *data, const void *key, size_t key_len)
51 {
52 uint32_t hash = h->hash(key, key_len) % h->size;
53 struct ext2fs_hashmap_entry *e = malloc(sizeof(*e));
54
55 if (!e)
56 return -1;
57
58 e->data = data;
59 e->key = key;
60 e->key_len = key_len;
61 e->next = h->entries[hash];
62 h->entries[hash] = e;
63
64 e->list_prev = NULL;
65 e->list_next = h->first;
66 if (h->first)
67 h->first->list_prev = e;
68 h->first = e;
69 if (!h->last)
70 h->last = e;
71
72 return 0;
73 }
74
ext2fs_hashmap_lookup(struct ext2fs_hashmap * h,const void * key,size_t key_len)75 void *ext2fs_hashmap_lookup(struct ext2fs_hashmap *h, const void *key,
76 size_t key_len)
77 {
78 struct ext2fs_hashmap_entry *iter;
79 uint32_t hash = h->hash(key, key_len) % h->size;
80
81 for (iter = h->entries[hash]; iter; iter = iter->next)
82 if (iter->key_len == key_len && !memcmp(iter->key, key, key_len))
83 return iter->data;
84 return NULL;
85 }
86
ext2fs_hashmap_iter_in_order(struct ext2fs_hashmap * h,struct ext2fs_hashmap_entry ** it)87 void *ext2fs_hashmap_iter_in_order(struct ext2fs_hashmap *h,
88 struct ext2fs_hashmap_entry **it)
89 {
90 *it = *it ? (*it)->list_next : h->first;
91 return *it ? (*it)->data : NULL;
92 }
93
ext2fs_hashmap_free(struct ext2fs_hashmap * h)94 void ext2fs_hashmap_free(struct ext2fs_hashmap *h)
95 {
96 size_t i;
97
98 for (i = 0; i < h->size; ++i) {
99 struct ext2fs_hashmap_entry *it = h->entries[i];
100 while (it) {
101 struct ext2fs_hashmap_entry *tmp = it->next;
102 if (h->free)
103 h->free(it->data);
104 free(it);
105 it = tmp;
106 }
107 }
108 free(h);
109 }
110