-
Notifications
You must be signed in to change notification settings - Fork 0
/
hashmap.h
132 lines (123 loc) · 5.02 KB
/
hashmap.h
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#ifndef GEN_HASHMAP
#define GEN_HASHMAP
#include "macros.h"
#include <assert.h>
#include <stdlib.h>
#define keyval_t(key_t, val_t) CONCAT(CONCAT(key_t, _to_), val_t)
#define hashmap_t(key_t, val_t) struct CONCAT(hashmap_, keyval_t(key_t, val_t))
#define hashmap_deinit_fn(kv_t) CONCAT(hashmap_deinit_, kv_t)
#define hashmap_add_fn(kv_t) CONCAT(hashmap_add_, kv_t)
#define hashmap_del_fn(kv_t) CONCAT(hashmap_del_, kv_t)
#define hashmap_lookup_fn(kv_t) CONCAT(hashmap_lookup_, kv_t)
#define hashmap_at_fn(kv_t) CONCAT(hashmap_at_, kv_t)
#define hashmap_init(key_t, val_t, sz, sl) \
(hashmap_t(key_t, val_t)) { \
.arena = arena_init(size_t, sl), \
.list = nodelist_init(keyval_t(key_t, val_t), sz).pool \
}
#define hashmap_reserve(map_ref, sz) \
hashmap_type(nodelist_reserve_fn, \
(map_ref)->list.array.arena.ptr->elt)( \
&(map_ref)->list.array.arena, sz)
#define hashmap_associated(hashmap_fn, map_ref, ...) \
hashmap_type(hashmap_fn, (map_ref)->list.array.arena.ptr->elt)( \
map_ref __VA_OPT__(, ) __VA_ARGS__)
#define hashmap_trait(hashmap_fn, map, ...) \
hashmap_type(hashmap_fn, (map).list.array.arena.ptr->elt)( \
map __VA_OPT__(, ) __VA_ARGS__)
#define hashmap_deinit(map_ref) hashmap_associated(hashmap_deinit_fn, map_ref)
#define hashmap_add(map_ref, elt) \
hashmap_associated(hashmap_add_fn, map_ref, elt)
#define hashmap_del(map_ref, key) \
hashmap_associated(hashmap_del_fn, map_ref, key)
#define hashmap_lookup(map, key) hashmap_trait(hashmap_lookup_fn, map, key)
#define hashmap_at(map, key) (*hashmap_associated(hashmap_at_fn, map, key))
#define hashmap_declare(key_t, val_t) \
typedef struct { \
key_t key; \
val_t val; \
} keyval_t(key_t, val_t); \
nodelist_declare(keyval_t(key_t, val_t)) hashmap_t(key_t, val_t) { \
arena_t(size_t) arena; \
nodelist_pool_t(keyval_t(key_t, val_t)) list; \
}; \
void hashmap_deinit_fn(keyval_t(key_t, val_t))( \
hashmap_t(key_t, val_t) *); \
void hashmap_add_fn(keyval_t(key_t, val_t))(hashmap_t(key_t, val_t) *, \
keyval_t(key_t, val_t)); \
void hashmap_del_fn(keyval_t(key_t, val_t))(hashmap_t(key_t, val_t) *, \
key_t); \
val_t hashmap_lookup_fn(keyval_t(key_t, val_t))( \
hashmap_t(key_t, val_t), key_t); \
val_t * hashmap_at_fn(keyval_t(key_t, val_t))( \
hashmap_t(key_t, val_t) *, key_t);
#define hashmap_define(key_t, val_t) \
void hashmap_deinit_fn(keyval_t(key_t, val_t))( \
hashmap_t(key_t, val_t) * map) { \
if (!map) return; \
arena_deinit_fn(size_t)(&map->arena); \
arena_deinit_fn(node_t(keyval_t(key_t, val_t)))( \
&map->list.array.arena); \
*map = (hashmap_t(key_t, val_t)){0}; \
} \
void hashmap_add_fn(keyval_t(key_t, val_t))( \
hashmap_t(key_t, val_t) * map, keyval_t(key_t, val_t) elt) { \
size_t slot = \
hashmap_hash(elt.key) & (map->arena.storage - 1); \
nodelist_t(keyval_t(key_t, val_t)) node = { \
.head = arena_at(map->arena, slot), .pool = map->list}; \
nodelist_cons_fn(keyval_t(key_t, val_t))(&node, elt); \
map->list = node.pool; \
arena_at(map->arena, slot) = node.head; \
} \
void hashmap_del_fn(keyval_t(key_t, val_t))( \
hashmap_t(key_t, val_t) * map, key_t key) { \
size_t slot = hashmap_hash(key) & (map->arena.storage - 1); \
nodelist_t(keyval_t(key_t, val_t)) node = { \
.head = arena_at(map->arena, slot), .pool = map->list}; \
for (size_t prev = 0, head = node.head; head; \
prev = head, head = nodelist_link(node, head)) { \
if (nodelist_at(node, head).key == key) { \
nodelist_remove_fn(keyval_t(key_t, val_t))( \
&node, prev); \
map->list = node.pool; \
arena_at(map->arena, slot) = node.head; \
} \
} \
} \
val_t hashmap_lookup_fn(keyval_t(key_t, val_t))( \
hashmap_t(key_t, val_t) map, key_t key) { \
size_t slot = hashmap_hash(key) & (map.arena.storage - 1); \
nodelist_t(keyval_t(key_t, val_t)) node = { \
.head = arena_at(map.arena, slot), .pool = map.list}; \
for (size_t head = node.head; head; \
head = nodelist_link(node, head)) { \
if (nodelist_at(node, head).key == key) { \
return nodelist_at(node, head).val; \
} \
} \
return (val_t){0}; \
} \
val_t * hashmap_at_fn(keyval_t(key_t, val_t))( \
hashmap_t(key_t, val_t) * map, key_t key) { \
size_t slot = hashmap_hash(key) & (map->arena.storage - 1); \
nodelist_t(keyval_t(key_t, val_t)) node = { \
.head = arena_at(map->arena, slot), .pool = map->list}; \
for (size_t head = node.head; head; \
head = nodelist_link(node, head)) { \
if (nodelist_at(node, head).key == key) { \
return &nodelist_at(node, head).val; \
} \
} \
nodelist_cons_fn(keyval_t(key_t, val_t))( \
&node, (keyval_t(key_t, val_t)){.key = key}); \
map->list = node.pool; \
arena_at(map->arena, slot) = node.head; \
return &nodelist_at(node, node.head).val; \
} \
nodelist_define(keyval_t(key_t, val_t))
#define hashmap_deduced(key_t, val_t) \
static_assert(hashmap_type(sizeof, (keyval_t(key_t, val_t)){0}) == \
sizeof(keyval_t(key_t, val_t)), \
STRING(key_t) ":" STRING(val_t) " hashmap");
#endif // !GEN_HASHMAP