C Container Collection (CCC)
Loading...
Searching...
No Matches
impl_flat_hash_map.h
1#ifndef CCC_IMPL_FLAT_HASH_MAP_H
2#define CCC_IMPL_FLAT_HASH_MAP_H
3
5#include <assert.h>
6#include <stddef.h>
7#include <stdint.h>
8#include <string.h>
11#include "../buffer.h"
12#include "../types.h"
13#include "impl_types.h"
14
15/* NOLINTBEGIN(readability-identifier-naming) */
16
18enum : uint64_t
19{
20 CCC_FHM_EMPTY = 0,
21};
22
24struct ccc_fhmap_elem_
25{
26 uint64_t hash_;
27};
28
30struct ccc_fhmap_
31{
32 ccc_buffer buf_;
33 ccc_hash_fn *hash_fn_;
34 ccc_key_eq_fn *eq_fn_;
35 size_t key_offset_;
36 size_t hash_elem_offset_;
37};
38
40struct ccc_fhash_entry_
41{
42 struct ccc_fhmap_ *h_;
43 uint64_t hash_;
44 struct ccc_ent_ entry_;
45};
46
48union ccc_fhmap_entry_
49{
50 struct ccc_fhash_entry_ impl_;
51};
52
53/*====================== Private Interface ============================*/
54
56void ccc_impl_fhm_insert(struct ccc_fhmap_ *h, void const *e, uint64_t hash,
57 size_t cur_i);
59struct ccc_fhash_entry_ ccc_impl_fhm_entry(struct ccc_fhmap_ *h,
60 void const *key);
62struct ccc_fhmap_elem_ *ccc_impl_fhm_in_slot(struct ccc_fhmap_ const *h,
63 void const *slot);
65void *ccc_impl_fhm_key_in_slot(struct ccc_fhmap_ const *h, void const *slot);
67uint64_t *ccc_impl_fhm_hash_at(struct ccc_fhmap_ const *h, size_t i);
69size_t ccc_impl_fhm_increment(size_t capacity, size_t i);
70
71/*===================== Macro Implementations =========================*/
72
74#define ccc_impl_fhm_init(memory_ptr, fhash_elem_field, key_field, hash_fn, \
75 key_eq_fn, alloc_fn, aux, capacity) \
76 { \
77 .buf_ \
78 = (ccc_buffer)ccc_buf_init((memory_ptr), (alloc_fn), (aux), capacity), \
79 .hash_fn_ = (hash_fn), \
80 .eq_fn_ = (key_eq_fn), \
81 .key_offset_ = offsetof(typeof(*(memory_ptr)), key_field), \
82 .hash_elem_offset_ \
83 = offsetof(typeof(*(memory_ptr)), fhash_elem_field), \
84 }
85
88#define ccc_impl_fhm_swaps(swap_entry, lazy_key_value...) \
89 (__extension__({ \
90 size_t fhm_i_ \
91 = ccc_buf_i(&((swap_entry)->h_->buf_), (swap_entry)->entry_.e_) \
92 .count; \
93 if (*ccc_impl_fhm_hash_at((swap_entry)->h_, fhm_i_) == CCC_FHM_EMPTY) \
94 { \
95 *((typeof(lazy_key_value) *)ccc_buf_at(&((swap_entry)->h_->buf_), \
96 fhm_i_)) \
97 = lazy_key_value; \
98 *ccc_impl_fhm_hash_at((swap_entry)->h_, fhm_i_) \
99 = (swap_entry)->hash_; \
100 (void)ccc_buf_size_plus(&(swap_entry)->h_->buf_, 1); \
101 } \
102 else \
103 { \
104 typeof(lazy_key_value) fhm_cur_slot_ \
105 = *((typeof(fhm_cur_slot_) *)ccc_buf_at( \
106 &((swap_entry)->h_->buf_), fhm_i_)); \
107 *((typeof(fhm_cur_slot_) *)ccc_buf_at(&((swap_entry)->h_->buf_), \
108 fhm_i_)) \
109 = lazy_key_value; \
110 *ccc_impl_fhm_hash_at((swap_entry)->h_, fhm_i_) \
111 = (swap_entry)->hash_; \
112 fhm_i_ = ccc_impl_fhm_increment( \
113 ccc_buf_capacity(&(swap_entry)->h_->buf_).count, fhm_i_); \
114 ccc_impl_fhm_insert( \
115 (swap_entry)->h_, &fhm_cur_slot_, \
116 ccc_impl_fhm_in_slot((swap_entry)->h_, &fhm_cur_slot_)->hash_, \
117 fhm_i_); \
118 } \
119 (swap_entry)->entry_.e_; \
120 }))
121
122/*===================== Core Macro Implementations ==================*/
123
125#define ccc_impl_fhm_and_modify_w(flat_hash_map_entry_ptr, type_name, \
126 closure_over_T...) \
127 (__extension__({ \
128 __auto_type fhm_mod_ent_ptr_ = (flat_hash_map_entry_ptr); \
129 struct ccc_fhash_entry_ fhm_mod_with_ent_ \
130 = {.entry_ = {.stats_ = CCC_ENTRY_ARG_ERROR}}; \
131 if (fhm_mod_ent_ptr_) \
132 { \
133 fhm_mod_with_ent_ = fhm_mod_ent_ptr_->impl_; \
134 if (fhm_mod_with_ent_.entry_.stats_ == CCC_ENTRY_OCCUPIED) \
135 { \
136 type_name *const T = fhm_mod_with_ent_.entry_.e_; \
137 if (T) \
138 { \
139 closure_over_T \
140 } \
141 } \
142 } \
143 fhm_mod_with_ent_; \
144 }))
145
147#define ccc_impl_fhm_or_insert_w(flat_hash_map_entry_ptr, lazy_key_value...) \
148 (__extension__({ \
149 __auto_type fhm_or_ins_ent_ptr_ = (flat_hash_map_entry_ptr); \
150 typeof(lazy_key_value) *fhm_or_ins_res_ = NULL; \
151 if (fhm_or_ins_ent_ptr_) \
152 { \
153 struct ccc_fhash_entry_ *fhm_or_ins_entry_ \
154 = &fhm_or_ins_ent_ptr_->impl_; \
155 if (!(fhm_or_ins_entry_->entry_.stats_ & CCC_ENTRY_INSERT_ERROR)) \
156 { \
157 if (fhm_or_ins_entry_->entry_.stats_ & CCC_ENTRY_OCCUPIED) \
158 { \
159 fhm_or_ins_res_ = fhm_or_ins_entry_->entry_.e_; \
160 } \
161 else \
162 { \
163 fhm_or_ins_res_ = ccc_impl_fhm_swaps(fhm_or_ins_entry_, \
164 lazy_key_value); \
165 } \
166 } \
167 } \
168 fhm_or_ins_res_; \
169 }))
170
172#define ccc_impl_fhm_insert_entry_w(flat_hash_map_entry_ptr, \
173 lazy_key_value...) \
174 (__extension__({ \
175 __auto_type fhm_ins_ent_ptr_ = (flat_hash_map_entry_ptr); \
176 typeof(lazy_key_value) *fhm_res_ = NULL; \
177 if (fhm_ins_ent_ptr_) \
178 { \
179 struct ccc_fhash_entry_ *fhm_ins_ent_ = &fhm_ins_ent_ptr_->impl_; \
180 if (!(fhm_ins_ent_->entry_.stats_ & CCC_ENTRY_INSERT_ERROR)) \
181 { \
182 if (fhm_ins_ent_->entry_.stats_ & CCC_ENTRY_OCCUPIED) \
183 { \
184 fhm_ins_ent_->entry_.stats_ = CCC_ENTRY_OCCUPIED; \
185 *((typeof(fhm_res_))fhm_ins_ent_->entry_.e_) \
186 = lazy_key_value; \
187 ccc_impl_fhm_in_slot(fhm_ins_ent_->h_, \
188 fhm_ins_ent_->entry_.e_) \
189 ->hash_ \
190 = fhm_ins_ent_->hash_; \
191 fhm_res_ = fhm_ins_ent_->entry_.e_; \
192 } \
193 else \
194 { \
195 fhm_res_ \
196 = ccc_impl_fhm_swaps(fhm_ins_ent_, lazy_key_value); \
197 } \
198 } \
199 } \
200 fhm_res_; \
201 }))
202
204#define ccc_impl_fhm_try_insert_w(flat_hash_map_ptr, key, lazy_value...) \
205 (__extension__({ \
206 struct ccc_fhmap_ *flat_hash_map_ptr_ = (flat_hash_map_ptr); \
207 struct ccc_ent_ fhm_try_insert_res_ = {.stats_ = CCC_ENTRY_ARG_ERROR}; \
208 if (flat_hash_map_ptr_) \
209 { \
210 __auto_type fhm_key_ = key; \
211 struct ccc_fhash_entry_ fhm_try_ins_ent_ \
212 = ccc_impl_fhm_entry(flat_hash_map_ptr_, (void *)&fhm_key_); \
213 if ((fhm_try_ins_ent_.entry_.stats_ & CCC_ENTRY_OCCUPIED) \
214 || (fhm_try_ins_ent_.entry_.stats_ & CCC_ENTRY_INSERT_ERROR)) \
215 { \
216 fhm_try_insert_res_ = fhm_try_ins_ent_.entry_; \
217 } \
218 else \
219 { \
220 fhm_try_insert_res_ = (struct ccc_ent_){ \
221 ccc_impl_fhm_swaps((&fhm_try_ins_ent_), lazy_value), \
222 CCC_ENTRY_VACANT, \
223 }; \
224 *((typeof(fhm_key_) *)ccc_impl_fhm_key_in_slot( \
225 flat_hash_map_ptr_, fhm_try_insert_res_.e_)) \
226 = fhm_key_; \
227 } \
228 } \
229 fhm_try_insert_res_; \
230 }))
231
233#define ccc_impl_fhm_insert_or_assign_w(flat_hash_map_ptr, key, lazy_value...) \
234 (__extension__({ \
235 struct ccc_fhmap_ *flat_hash_map_ptr_ = (flat_hash_map_ptr); \
236 struct ccc_ent_ fhm_ins_or_assign_res_ \
237 = {.stats_ = CCC_ENTRY_ARG_ERROR}; \
238 if (flat_hash_map_ptr_) \
239 { \
240 __auto_type fhm_key_ = key; \
241 struct ccc_fhash_entry_ fhm_ins_or_assign_ent_ \
242 = ccc_impl_fhm_entry(flat_hash_map_ptr_, (void *)&fhm_key_); \
243 if (fhm_ins_or_assign_ent_.entry_.stats_ & CCC_ENTRY_OCCUPIED) \
244 { \
245 fhm_ins_or_assign_res_ = fhm_ins_or_assign_ent_.entry_; \
246 *((typeof(lazy_value) *)fhm_ins_or_assign_res_.e_) \
247 = lazy_value; \
248 *((typeof(fhm_key_) *)ccc_impl_fhm_key_in_slot( \
249 flat_hash_map_ptr_, fhm_ins_or_assign_res_.e_)) \
250 = fhm_key_; \
251 ccc_impl_fhm_in_slot(fhm_ins_or_assign_ent_.h_, \
252 fhm_ins_or_assign_ent_.entry_.e_) \
253 ->hash_ \
254 = fhm_ins_or_assign_ent_.hash_; \
255 } \
256 else if (fhm_ins_or_assign_ent_.entry_.stats_ \
257 & CCC_ENTRY_INSERT_ERROR) \
258 { \
259 fhm_ins_or_assign_res_.e_ = NULL; \
260 fhm_ins_or_assign_res_.stats_ = CCC_ENTRY_INSERT_ERROR; \
261 } \
262 else \
263 { \
264 fhm_ins_or_assign_res_ = (struct ccc_ent_){ \
265 ccc_impl_fhm_swaps((&fhm_ins_or_assign_ent_), lazy_value), \
266 CCC_ENTRY_VACANT, \
267 }; \
268 *((typeof(fhm_key_) *)ccc_impl_fhm_key_in_slot( \
269 flat_hash_map_ptr_, fhm_ins_or_assign_res_.e_)) \
270 = fhm_key_; \
271 } \
272 } \
273 fhm_ins_or_assign_res_; \
274 }))
275
276/* NOLINTEND(readability-identifier-naming) */
277
278#endif /* CCC_IMPL_FLAT_HASH_MAP_H */
ccc_buffer
struct ccc_buf_ ccc_buffer
A contiguous block of storage for elements of the same type.
Definition: buffer.h:50
ccc_hash_fn
uint64_t ccc_hash_fn(ccc_user_key to_hash)
A callback function to hash the key type used in a container.
Definition: types.h:339
ccc_key_eq_fn
ccc_tribool ccc_key_eq_fn(ccc_key_cmp)
A callback function to determining equality between two stored keys.
Definition: types.h:326