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
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
|
#ifndef CHEESEMAP_
#define CHEESEMAP_
#ifdef __cplusplus
extern "C" {
#endif
////////////////////////////////
// options and includes
//
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
typedef uint8_t cm_u8;
typedef uint16_t cm_u16;
typedef uint32_t cm_u32;
typedef uint64_t cm_u64;
#if UINTPTR_MAX == UINT64_MAX
typedef cm_u64 cm_usize;
#elif UINTPTR_MAX == UINT32_MAX
typedef cm_u32 cm_usize;
#else
#error "unsupported uintptr_t width"
#endif
void CM_PANIC_SYM(const char* file, cm_u32 line, const char* fmt, ...);
#ifdef NDEBUG
#define cm_assert(cond)
#else
#define cm_assert(cond) \
do { \
if (!(cond)) \
CM_PANIC_SYM(__FILE__, __LINE__, "cm_assertion failed: %s", #cond); \
} while (0)
#endif
#ifdef CM_ENABLE_SSE2
#include <emmintrin.h>
typedef __m128i group_t;
typedef cm_u16 bitmask_t;
#define CM_GROUP_SIZE 16
#define CM_NO_FALLBACK
#endif
#ifndef CM_NO_FALLBACK
typedef cm_usize group_t;
typedef group_t bitmask_t;
#define CM_GROUP_SIZE __SIZEOF_POINTER__
#endif
////////////////////////////////
// cheesemap callback functions
//
typedef cm_u64 cm_hash_t;
/* hash and compare methods */
typedef cm_hash_t (*cm_hash_fn)(const cm_u8* key, cm_u8* user);
typedef bool (*cm_compare_fn)(const cm_u8* key1, const cm_u8* key2,
cm_u8* user);
/* allocator methods */
typedef cm_u8* (*cm_alloc_fn)(cm_usize size, cm_u8* user);
typedef void (*cm_dealloc_fn)(cm_u8* ptr, cm_u8* 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(cm_usize) * CHAR_BIT,
};
extern const cm_u8 CM_CTRL_STATIC_EMPTY[CM_GROUP_SIZE];
struct cm_type {
cm_usize key_size;
cm_usize value_size;
cm_usize value_offset;
cm_usize entry_size;
};
#define cm_type_new(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
cm_usize bucket_mask;
// number of entries in the map
cm_usize count;
// number of entry left until resize
cm_usize growth_left;
// pointer to the control bytes
cm_u8* ctrl;
};
#define cm_raw_new() \
((struct cheesemap_raw){.ctrl = (cm_u8*)CM_CTRL_STATIC_EMPTY})
bool cm_raw_new_with(struct cheesemap_raw* map, cm_alloc_fn alloc, cm_u8* user,
const struct cm_type* type, cm_usize initial_capacity);
void cm_raw_drop(struct cheesemap_raw* map, cm_dealloc_fn dealloc, cm_u8* 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, cm_u8* user,
const struct cm_type* type, cm_usize additional);
bool cm_raw_lookup(const struct cheesemap_raw* map, cm_hash_fn hash,
cm_compare_fn compare, cm_u8* user,
const struct cm_type* type, const cm_u8* key,
cm_u8** out_value);
bool cm_raw_remove(struct cheesemap_raw* map, cm_hash_fn hash,
cm_compare_fn compare, cm_u8* user,
const struct cm_type* type, const cm_u8* key,
cm_u8* out_value);
bool cm_raw_insert(struct cheesemap_raw* map, cm_hash_fn hash,
cm_alloc_fn alloc, cm_dealloc_fn dealloc, cm_u8* user,
const struct cm_type* type, const cm_u8* key,
const cm_u8* value);
////////////////////////////////
// cheesemap implementation
//
struct cheesemap {
struct cm_type type;
cm_u8* user;
cm_hash_fn hash;
cm_compare_fn compare;
cm_alloc_fn alloc;
cm_dealloc_fn dealloc;
struct cheesemap_raw raw;
};
#define cm_new_raw(type, user, hash, compare, alloc, dealloc, raw) \
((struct cheesemap){type, user, hash, compare, alloc, dealloc, raw})
void cm_new(struct cheesemap* map, cm_usize key_size, cm_usize key_align,
cm_usize value_size, cm_usize value_align, cm_u8* 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 cm_u8* key, const cm_u8* value);
bool cm_lookup(const struct cheesemap* map, const cm_u8* key,
cm_u8** out_value);
bool cm_remove(struct cheesemap* map, const cm_u8* key, cm_u8* out_value);
bool cm_reserve(struct cheesemap* map, cm_usize 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 cm_u8*)&(key), (cm_u8**)(out_val))
#define cm_insert_(map, key, val) \
cm_insert(map, (const cm_u8*)&(key), (const cm_u8*)&(val))
#define cm_remove_(map, key, out_val) \
cm_remove(map, (const cm_u8*)&(key), (cm_u8*)(out_val))
////////////////////////////////
// cheesemap iterators
//
struct cheesemap_raw_iter {
bitmask_t curr_mask;
cm_usize curr_index;
cm_u8* n_ctrl;
cm_u8* n_entry;
cm_u8* end;
};
void cm_raw_iter_init(struct cheesemap_raw_iter* iter,
const struct cheesemap_raw* map,
const struct cm_type* type, cm_usize start_index);
bool cm_raw_iter_next(struct cheesemap_raw_iter* iter,
const struct cm_type* type, cm_usize* out_index);
struct cheesemap_iter {
cm_usize 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,
cm_u8** out_key, cm_u8** out_value);
#define cm_iter_next_(iter, map, out_key, out_val) \
cm_iter_next(iter, map, (cm_u8**)(out_key), (cm_u8**)(out_val))
#ifdef __cplusplus
}
#endif
#endif
|
