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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
|
#include "cheesemap.h"
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
static inline uintptr_t cm_ctz(uintptr_t val) {
assert(val != 0);
#if defined(__GNUC__) || defined(__clang__)
#if UINTPTR_MAX == UINT64_MAX
return (uintptr_t)__builtin_ctzll(val);
#elif UINTPTR_MAX == UINT32_MAX
return (uintptr_t)__builtin_ctz(val);
#else
#error "unknown word width"
#endif
#else
#error "ctz not implemented for this compiler"
#endif
}
struct sequence {
uintptr_t pos;
uintptr_t stride;
};
#define sequence_init(pos, stride) ((struct sequence){pos, stride})
static inline void cm_sequence_next(struct sequence* sequence,
uintptr_t bucket_mask) {
assert(sequence != NULL);
assert(sequence->stride <= bucket_mask);
sequence->stride += CM_GROUP_SIZE;
sequence->pos += sequence->stride;
sequence->pos &= bucket_mask;
}
/* ctrl ops */
static inline bool cm_ctrl_is_special(uint8_t v) { return v & CM_CTRL_DELETED; }
static inline bool cm_ctrl_is_empty(uint8_t v) {
assert(cm_ctrl_is_special(v) == true);
return (v & CM_CTRL_END) != 0;
}
/* group ops */
static inline group_t cm_group_load(const uint8_t* ctrl);
static inline bitmask_t cm_group_empty_or_deleted(group_t group);
/* scalar implementation */
static inline group_t cm_group_repeat(uint8_t v) {
return (group_t)v * (((group_t)-1) / (uint8_t)~0);
}
static inline group_t cm_group_load(const uint8_t* ctrl) {
assert(ctrl != NULL);
group_t v;
memcpy(&v, ctrl, sizeof(v));
return v;
}
static inline bitmask_t cm_group_empty_or_deleted(group_t group) {
return group & cm_group_repeat(CM_CTRL_DELETED);
}
/* static ctrl's */
const uint8_t CM_CTRL_STATIC_EMPTY[CM_GROUP_SIZE] = {[0 ... CM_GROUP_SIZE - 1] =
CM_CTRL_EMPTY};
/* hashmap implementation */
static inline uint8_t* cm_raw_elem_at(const struct cheesemap_raw* map,
uintptr_t index, uintptr_t entry_size) {
assert(map != NULL);
assert(map->bucket_mask + 1 > index);
return map->ctrl - entry_size * index;
}
static inline uint8_t* cm_raw_origin(const struct cheesemap_raw* map,
uintptr_t entry_size) {
assert(map != NULL);
return cm_raw_elem_at(map, map->bucket_mask + 1, entry_size);
}
static inline void cm_raw_ctrl_set(struct cheesemap_raw* map, uintptr_t index,
uint8_t ctrl) {
assert(map != NULL);
uintptr_t index2 =
((index - CM_GROUP_SIZE) & map->bucket_mask) + CM_GROUP_SIZE;
map->ctrl[index] = ctrl;
map->ctrl[index2] = ctrl;
}
static bool cm_raw_find_insert_index_in_group(const struct cheesemap_raw* map,
const group_t* group,
const struct sequence* seq,
uintptr_t* out_index) {
assert(map != NULL);
assert(group != NULL && seq != NULL);
assert(out_index != NULL);
bitmask_t mask = cm_group_empty_or_deleted(*group);
if (mask == 0) return false;
uintptr_t bit = cm_ctz(mask);
*out_index = (seq->pos + bit) & map->bucket_mask;
return true;
}
static uintptr_t cm_raw_find_insert_index(const struct cheesemap_raw* map,
cm_hash_t hash) {
assert(map != NULL);
struct sequence seq = sequence_init(cm_h1(hash) & map->bucket_mask, 0);
while (true) {
uint8_t* ctrl = &map->ctrl[seq.pos];
group_t group = cm_group_load(ctrl);
uintptr_t index;
if (cm_raw_find_insert_index_in_group(map, &group, &seq, &index))
return index;
cm_sequence_next(&seq, map->bucket_mask);
}
}
static void cm_raw_insert_at(struct cheesemap_raw* map, cm_hash_t hash,
uintptr_t index, uintptr_t key_size,
const uint8_t* key, uintptr_t value_size,
const uint8_t* value) {
assert(map != NULL);
assert(value != NULL);
uint8_t old_ctrl = map->ctrl[index];
map->growth_left -= cm_ctrl_is_empty(old_ctrl);
cm_raw_ctrl_set(map, index, cm_h2(hash));
uint8_t* elem = cm_raw_elem_at(map, index, key_size + value_size);
memcpy(elem, key, key_size);
elem += key_size;
memcpy(elem, value, value_size);
map->count += 1;
}
bool cm_raw_insert(struct cheesemap_raw* map, const struct cheesemap_fns* fns,
uintptr_t key_size, const uint8_t* key, uintptr_t value_size,
const uint8_t* value) {
assert(map != NULL && fns != NULL);
assert(key != NULL && value != NULL);
cm_hash_t hash = fns->hash(key, fns->map_usr);
uintptr_t index = cm_raw_find_insert_index(map, hash);
uint8_t old_ctrl = map->ctrl[index];
if (map->growth_left == 0 && cm_ctrl_is_empty(old_ctrl)) {
// TODO: do resize
}
cm_raw_insert_at(map, hash, index, key_size, key, value_size, value);
return true;
}
void cm_raw_drop(struct cheesemap_raw* map, uintptr_t key_size,
uintptr_t value_size, const struct cheesemap_fns* fns) {
assert(map != NULL);
assert(fns != NULL);
if (map->ctrl == CM_CTRL_STATIC_EMPTY || map->ctrl == NULL) return;
uint8_t* origin = cm_raw_origin(map, key_size + value_size);
fns->free(origin, fns->mem_usr);
*map = cm_raw_new();
}
void cm_new(struct cheesemap* map, uintptr_t key_size, uintptr_t value_size,
uint8_t* mem_usr, cm_malloc_fn malloc, cm_free_fn free,
uint8_t* map_usr, cm_hash_fn hash, cm_compare_fn compare) {
assert(map != NULL);
assert(malloc != NULL && free != NULL);
assert(hash != NULL && compare != NULL);
struct cheesemap_fns fns = {
mem_usr, map_usr, //
malloc, free, //
hash, compare, //
};
*map = (struct cheesemap){key_size, value_size, fns, cm_raw_new()};
}
|
