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
|
#ifndef CHEESEMAP
#define CHEESEMAP
#ifdef __cplusplus
extern "C" {
#endif
////////////////////////////////
// options and includes
//
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include CM_OPT_ASSERT_PATH
#ifndef assert
#error "assert is not defined"
#endif
typedef uintptr_t group_t;
typedef group_t bitmask_t;
enum {
CM_GROUP_SIZE = sizeof(group_t),
};
////////////////////////////////
// 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);
////////////////////////////////
// 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,
};
static inline uintptr_t cm_h1(cm_hash_t hash) {
return (uintptr_t)(hash >> CM_FP_SIZE);
}
static inline uint8_t cm_h2(cm_hash_t hash) {
uintptr_t top = hash >> (sizeof(cm_hash_t) * CHAR_BIT - CM_FP_SIZE);
return (uint8_t)(top & CM_H2_MASK);
}
extern const uint8_t CM_CTRL_STATIC_EMPTY[CM_GROUP_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, uintptr_t entry_size,
uintptr_t initial_capacity);
void cm_raw_drop(struct cheesemap_raw* map, uintptr_t entry_size);
bool cm_raw_reserve(struct cheesemap_raw* map, cm_hash_fn hash, uint8_t* user,
uintptr_t entry_size, uintptr_t additional);
bool cm_raw_lookup(const struct cheesemap_raw* map, cm_hash_fn hash,
cm_compare_fn compare, uint8_t* user, uintptr_t entry_size,
uintptr_t value_offset, 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, uintptr_t entry_size,
uintptr_t value_offset, uintptr_t value_size,
const uint8_t* key, uint8_t* out_value);
bool cm_raw_insert(struct cheesemap_raw* map, cm_hash_fn hash, uint8_t* user,
uintptr_t entry_size, uintptr_t key_size,
uintptr_t value_offset, uintptr_t value_size,
const uint8_t* key, const uint8_t* value);
////////////////////////////////
// cheesemap implementation
//
struct cheesemap {
uintptr_t key_size, value_size;
uintptr_t value_offset, entry_size;
uint8_t* user;
cm_hash_fn hash;
cm_compare_fn compare;
struct cheesemap_raw 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);
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) \
cm_new(map, sizeof(K), _Alignof(K), sizeof(V), _Alignof(V), user, hash_fn, \
cmp_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, uintptr_t entry_size,
uintptr_t start_index);
bool cm_raw_iter_next(struct cheesemap_raw_iter* iter, uintptr_t entry_size,
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);
#ifdef __cplusplus
}
#endif
#endif
|
