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
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
|
#ifndef CHEESEMAP_
#define CHEESEMAP_
#ifdef __cplusplus
extern "C" {
#endif
////////////////////////////////
// options and includes
//
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
_Noreturn void CM_OPT_PANIC_NAME(const char* file, uint32_t line,
const char* fmt, ...);
#define cm_assert(cond) \
do { \
if (!(cond)) \
CM_OPT_PANIC_NAME(__FILE__, __LINE__, "cm_assertion failed: %s", #cond); \
} while (0)
#ifdef CM_OPT_ENABLE_SSE2
#include <emmintrin.h>
typedef __m128i group_t;
typedef uint16_t bitmask_t;
#define CM_GROUP_SIZE 16
#define CM_NO_FALLBACK
#endif
#ifndef CM_NO_FALLBACK
typedef uintptr_t group_t;
typedef group_t bitmask_t;
#define CM_GROUP_SIZE __SIZEOF_POINTER__
#endif
////////////////////////////////
// cheesemap callback functions
//
typedef uint64_t cm_hash_t;
/* hash and compare methods */
typedef cm_hash_t (*cm_hash_fn)(const uint8_t* key, uint8_t* user);
typedef bool (*cm_compare_fn)(const uint8_t* key1, const uint8_t* key2,
uint8_t* user);
/* allocator methods */
typedef void* (*cm_alloc_fn)(uintptr_t size, uint8_t* user);
typedef void (*cm_dealloc_fn)(void* ptr, uint8_t* user);
////////////////////////////////
// raw cheesemap implementation
//
// layout:
// [entries...][control bits...][mirror first CM_GROUP_SIZE bits]
enum {
// cheesemap config
CM_INITIAL_CAPACITY = CM_GROUP_SIZE,
CM_LOAD_DENOM = 8,
CM_LOAD_NUM = 7,
//
// ctrl ops
// -1 as i8, all bits set, top bit = 1
CM_CTRL_EMPTY = 0xFF, // 0b1111_1111
// -128 as i8, top bit = 1
CM_CTRL_DELETED = 0x80, // 0b1000_0000
// FULL entries have top bit = 0, lower 7 bits are H2 hash
CM_H2_MASK = 0x7F, // 0b0111_1111
// Mask to get bottom bit
CM_CTRL_END = 0x01, // 0b0000_0001
// Number of fingerprint bytes
CM_FP_SIZE = 7,
//
// aux
// Size of a word in bits
CM_WORD_WIDTH = sizeof(uintptr_t) * CHAR_BIT,
};
extern const uint8_t CM_CTRL_STATIC_EMPTY[CM_GROUP_SIZE];
struct cm_type {
uintptr_t key_size;
uintptr_t value_size;
uintptr_t value_offset;
uintptr_t entry_size;
};
#define cm_type_construct(key_size, value_size, value_offset, entry_size) \
((struct cm_type){key_size, value_size, value_offset, entry_size})
struct cheesemap_raw {
// number of buckets as mask
uintptr_t bucket_mask;
// number of entries in the map
uintptr_t count;
// number of entry left until resize
uintptr_t growth_left;
// pointer to the control bytes
uint8_t* ctrl;
};
#define cm_raw_new() \
((struct cheesemap_raw){.ctrl = (uint8_t*)CM_CTRL_STATIC_EMPTY})
bool cm_raw_new_with(struct cheesemap_raw* map, cm_alloc_fn alloc,
uint8_t* user, const struct cm_type* type,
uintptr_t initial_capacity);
void cm_raw_drop(struct cheesemap_raw* map, cm_dealloc_fn dealloc,
uint8_t* user, const struct cm_type* type);
bool cm_raw_reserve(struct cheesemap_raw* map, cm_hash_fn hash,
cm_alloc_fn alloc, cm_dealloc_fn dealloc, uint8_t* user,
const struct cm_type* type, uintptr_t additional);
bool cm_raw_lookup(const struct cheesemap_raw* map, cm_hash_fn hash,
cm_compare_fn compare, uint8_t* user,
const struct cm_type* type, const uint8_t* key,
uint8_t** out_value);
bool cm_raw_remove(struct cheesemap_raw* map, cm_hash_fn hash,
cm_compare_fn compare, uint8_t* user,
const struct cm_type* type, const uint8_t* key,
uint8_t* out_value);
bool cm_raw_insert(struct cheesemap_raw* map, cm_hash_fn hash,
cm_alloc_fn alloc, cm_dealloc_fn dealloc, uint8_t* user,
const struct cm_type* type, const uint8_t* key,
const uint8_t* value);
////////////////////////////////
// cheesemap implementation
//
struct cheesemap {
struct cm_type type;
uint8_t* user;
cm_hash_fn hash;
cm_compare_fn compare;
cm_alloc_fn alloc;
cm_dealloc_fn dealloc;
struct cheesemap_raw raw;
};
#define cm_construct(type, user, hash, compare, alloc, dealloc, raw) \
((struct cheesemap){type, user, hash, compare, alloc, dealloc, raw})
void cm_new(struct cheesemap* map, uintptr_t key_size, uintptr_t key_align,
uintptr_t value_size, uintptr_t value_align, uint8_t* user,
cm_hash_fn hash, cm_compare_fn compare, cm_alloc_fn alloc,
cm_dealloc_fn dealloc);
void cm_drop(struct cheesemap* map);
bool cm_insert(struct cheesemap* map, const uint8_t* key, const uint8_t* value);
bool cm_lookup(const struct cheesemap* map, const uint8_t* key,
uint8_t** out_value);
bool cm_remove(struct cheesemap* map, const uint8_t* key, uint8_t* out_value);
bool cm_reserve(struct cheesemap* map, uintptr_t additional);
////////////////////////////////
// cheesemap convenience macros
//
#define cm_new_(map, K, V, user, hash_fn, cmp_fn, alloc_fn, dealloc_fn) \
cm_new(map, sizeof(K), _Alignof(K), sizeof(V), _Alignof(V), user, hash_fn, \
cmp_fn, alloc_fn, dealloc_fn)
#define cm_lookup_(map, key, out_val) \
cm_lookup(map, (const uint8_t*)&(key), (uint8_t**)(out_val))
#define cm_insert_(map, key, val) \
cm_insert(map, (const uint8_t*)&(key), (const uint8_t*)&(val))
#define cm_remove_(map, key, out_val) \
cm_remove(map, (const uint8_t*)&(key), (uint8_t*)(out_val))
////////////////////////////////
// cheesemap iterators
//
struct cheesemap_raw_iter {
bitmask_t curr_mask;
uintptr_t curr_index;
uint8_t* n_ctrl;
uint8_t* n_entry;
uint8_t* end;
};
void cm_raw_iter_init(struct cheesemap_raw_iter* iter,
const struct cheesemap_raw* map,
const struct cm_type* type, uintptr_t start_index);
bool cm_raw_iter_next(struct cheesemap_raw_iter* iter,
const struct cm_type* type, uintptr_t* out_index);
struct cheesemap_iter {
uintptr_t entry_size, value_offset;
struct cheesemap_raw_iter raw;
};
void cm_iter_init(struct cheesemap_iter* iter, const struct cheesemap* map);
bool cm_iter_next(struct cheesemap_iter* iter, const struct cheesemap* map,
uint8_t** out_key, uint8_t** out_value);
#define cm_iter_next_(iter, map, out_key, out_val) \
cm_iter_next(iter, map, (uint8_t**)(out_key), (uint8_t**)(out_val))
#ifdef __cplusplus
}
#endif
#endif
|
