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