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