C Container Collection (CCC)
Loading...
Searching...
No Matches
impl_flat_hash_map.h
1
16#ifndef CCC_IMPL_FLAT_HASH_MAP_H
17#define CCC_IMPL_FLAT_HASH_MAP_H
18
20#include <assert.h>
21#include <stdalign.h>
22#include <stddef.h>
23#include <stdint.h>
26#include "../types.h"
27#include "impl_types.h"
28
29/* NOLINTBEGIN(readability-identifier-naming) */
30
33#if defined(__x86_64) && defined(__SSE2__) && !defined(CCC_FHM_PORTABLE)
37# define CCC_HAS_X86_SIMD
38#elif defined(__ARM_NEON__) && !defined(CCC_FHM_PORTABLE)
42# define CCC_HAS_ARM_SIMD
43#endif /* defined(__x86_64)&&defined(__SSE2__)&&!defined(CCC_FHM_PORTABLE) */
61typedef struct
62{
64 uint8_t v;
65} ccc_fhm_tag;
66
72enum : typeof((ccc_fhm_tag){}.v)
73{
74#if defined(CCC_HAS_X86_SIMD)
76 CCC_FHM_GROUP_SIZE = 16,
77#elif defined(CCC_HAS_ARM_SIMD)
79 CCC_FHM_GROUP_SIZE = 8,
80#else /* PORTABLE FALLBACK */
82 CCC_FHM_GROUP_SIZE = 8,
83#endif /* defined(CCC_HAS_X86_SIMD) */
84};
85
122struct ccc_fhmap
123{
125 void *data;
127 ccc_fhm_tag *tag;
129 size_t count;
131 size_t remain;
133 size_t mask;
135 size_t sizeof_type;
137 size_t key_offset;
139 ccc_any_key_eq_fn *eq_fn;
141 ccc_any_key_hash_fn *hash_fn;
143 ccc_any_alloc_fn *alloc_fn;
145 void *aux;
146};
147
150struct ccc_fhash_entry
151{
153 struct ccc_fhmap *h;
155 size_t i;
157 ccc_fhm_tag tag;
159 enum ccc_entry_status stats;
160};
161
167union ccc_fhmap_entry
168{
169 struct ccc_fhash_entry impl;
170};
171
175/*====================== Private Interface =========================*/
176
177struct ccc_fhash_entry ccc_impl_fhm_entry(struct ccc_fhmap *h, void const *key);
178void ccc_impl_fhm_insert(struct ccc_fhmap *h, void const *key_val_type,
179 ccc_fhm_tag m, size_t i);
180void ccc_impl_fhm_erase(struct ccc_fhmap *h, size_t i);
181void *ccc_impl_fhm_data_at(struct ccc_fhmap const *h, size_t i);
182void *ccc_impl_fhm_key_at(struct ccc_fhmap const *h, size_t i);
183void ccc_impl_fhm_set_insert(struct ccc_fhash_entry const *e);
184
185/*====================== Macro Implementations =========================*/
186
201#define ccc_impl_fhm_declare_fixed_map(fixed_map_type_name, key_val_type_name, \
202 capacity) \
203 static_assert((capacity) > 0, \
204 "fixed size map must have capacity greater than 0"); \
205 static_assert((capacity) >= CCC_FHM_GROUP_SIZE, \
206 "fixed size map must have capacity >= CCC_FHM_GROUP_SIZE " \
207 "(8 or 16 depending on platform)"); \
208 static_assert(((capacity) & ((capacity) - 1)) == 0, \
209 "fixed size map must be a power of 2 capacity (32, 64, " \
210 "128, 256, etc.)"); \
211 typedef struct \
212 { \
213 key_val_type_name data[(capacity) + 1]; \
214 alignas(CCC_FHM_GROUP_SIZE) \
215 ccc_fhm_tag tag[(capacity) + CCC_FHM_GROUP_SIZE]; \
216 }(fixed_map_type_name)
217
228#define ccc_impl_fhm_fixed_capacity(fixed_map_type_name) \
229 (sizeof((fixed_map_type_name){}.tag) - CCC_FHM_GROUP_SIZE)
230
247#define ccc_impl_fhm_init(impl_fixed_map_ptr, impl_any_type_name, \
248 impl_key_field, impl_hash_fn, impl_key_eq_fn, \
249 impl_alloc_fn, impl_aux_data, impl_capacity) \
250 { \
251 .data = (impl_fixed_map_ptr), \
252 .tag = NULL, \
253 .count = 0, \
254 .remain = (((impl_capacity) / (size_t)8) * (size_t)7), \
255 .mask = (((impl_capacity) > (size_t)0) ? ((impl_capacity) - (size_t)1) \
256 : (size_t)0), \
257 .sizeof_type = sizeof(impl_any_type_name), \
258 .key_offset = offsetof(impl_any_type_name, impl_key_field), \
259 .eq_fn = (impl_key_eq_fn), \
260 .hash_fn = (impl_hash_fn), \
261 .alloc_fn = (impl_alloc_fn), \
262 .aux = (impl_aux_data), \
263 }
264
265/*======================== Construct In Place =========================*/
266
270#define ccc_impl_fhm_and_modify_w(flat_hash_map_entry_ptr, type_name, \
271 closure_over_T...) \
272 (__extension__({ \
273 __auto_type impl_fhm_mod_ent_ptr = (flat_hash_map_entry_ptr); \
274 struct ccc_fhash_entry impl_fhm_mod_with_ent \
275 = {.stats = CCC_ENTRY_ARG_ERROR}; \
276 if (impl_fhm_mod_ent_ptr) \
277 { \
278 impl_fhm_mod_with_ent = impl_fhm_mod_ent_ptr->impl; \
279 if (impl_fhm_mod_with_ent.stats & CCC_ENTRY_OCCUPIED) \
280 { \
281 type_name *const T = ccc_impl_fhm_data_at( \
282 impl_fhm_mod_with_ent.h, impl_fhm_mod_with_ent.i); \
283 if (T) \
284 { \
285 closure_over_T \
286 } \
287 } \
288 } \
289 impl_fhm_mod_with_ent; \
290 }))
291
296#define ccc_impl_fhm_or_insert_w(flat_hash_map_entry_ptr, lazy_key_value...) \
297 (__extension__({ \
298 __auto_type impl_fhm_or_ins_ent_ptr = (flat_hash_map_entry_ptr); \
299 typeof(lazy_key_value) *impl_fhm_or_ins_res = NULL; \
300 if (impl_fhm_or_ins_ent_ptr) \
301 { \
302 if (!(impl_fhm_or_ins_ent_ptr->impl.stats \
303 & CCC_ENTRY_INSERT_ERROR)) \
304 { \
305 impl_fhm_or_ins_res \
306 = ccc_impl_fhm_data_at(impl_fhm_or_ins_ent_ptr->impl.h, \
307 impl_fhm_or_ins_ent_ptr->impl.i); \
308 if (impl_fhm_or_ins_ent_ptr->impl.stats == CCC_ENTRY_VACANT) \
309 { \
310 *impl_fhm_or_ins_res = lazy_key_value; \
311 ccc_impl_fhm_set_insert(&impl_fhm_or_ins_ent_ptr->impl); \
312 } \
313 } \
314 } \
315 impl_fhm_or_ins_res; \
316 }))
317
320#define ccc_impl_fhm_insert_entry_w(flat_hash_map_entry_ptr, \
321 lazy_key_value...) \
322 (__extension__({ \
323 __auto_type impl_fhm_ins_ent_ptr = (flat_hash_map_entry_ptr); \
324 typeof(lazy_key_value) *impl_fhm_ins_ent_res = NULL; \
325 if (impl_fhm_ins_ent_ptr) \
326 { \
327 if (!(impl_fhm_ins_ent_ptr->impl.stats & CCC_ENTRY_INSERT_ERROR)) \
328 { \
329 impl_fhm_ins_ent_res \
330 = ccc_impl_fhm_data_at(impl_fhm_ins_ent_ptr->impl.h, \
331 impl_fhm_ins_ent_ptr->impl.i); \
332 *impl_fhm_ins_ent_res = lazy_key_value; \
333 if (impl_fhm_ins_ent_ptr->impl.stats == CCC_ENTRY_VACANT) \
334 { \
335 ccc_impl_fhm_set_insert(&impl_fhm_ins_ent_ptr->impl); \
336 } \
337 } \
338 } \
339 impl_fhm_ins_ent_res; \
340 }))
341
345#define ccc_impl_fhm_try_insert_w(flat_hash_map_ptr, key, lazy_value...) \
346 (__extension__({ \
347 struct ccc_fhmap *impl_flat_hash_map_ptr = (flat_hash_map_ptr); \
348 struct ccc_ent impl_fhm_try_insert_res \
349 = {.stats = CCC_ENTRY_ARG_ERROR}; \
350 if (impl_flat_hash_map_ptr) \
351 { \
352 __auto_type impl_fhm_key = key; \
353 struct ccc_fhash_entry impl_fhm_try_ins_ent = ccc_impl_fhm_entry( \
354 impl_flat_hash_map_ptr, (void *)&impl_fhm_key); \
355 if ((impl_fhm_try_ins_ent.stats & CCC_ENTRY_OCCUPIED) \
356 || (impl_fhm_try_ins_ent.stats & CCC_ENTRY_INSERT_ERROR)) \
357 { \
358 impl_fhm_try_insert_res = (struct ccc_ent){ \
359 .e = ccc_impl_fhm_data_at(impl_fhm_try_ins_ent.h, \
360 impl_fhm_try_ins_ent.i), \
361 .stats = impl_fhm_try_ins_ent.stats, \
362 }; \
363 } \
364 else \
365 { \
366 impl_fhm_try_insert_res = (struct ccc_ent){ \
367 .e = ccc_impl_fhm_data_at(impl_fhm_try_ins_ent.h, \
368 impl_fhm_try_ins_ent.i), \
369 .stats = CCC_ENTRY_VACANT, \
370 }; \
371 *((typeof(lazy_value) *)impl_fhm_try_insert_res.e) \
372 = lazy_value; \
373 *((typeof(impl_fhm_key) *)ccc_impl_fhm_key_at( \
374 impl_fhm_try_ins_ent.h, impl_fhm_try_ins_ent.i)) \
375 = impl_fhm_key; \
376 ccc_impl_fhm_set_insert(&impl_fhm_try_ins_ent); \
377 } \
378 } \
379 impl_fhm_try_insert_res; \
380 }))
381
386#define ccc_impl_fhm_insert_or_assign_w(flat_hash_map_ptr, key, lazy_value...) \
387 (__extension__({ \
388 struct ccc_fhmap *impl_flat_hash_map_ptr = (flat_hash_map_ptr); \
389 struct ccc_ent impl_fhm_insert_or_assign_res \
390 = {.stats = CCC_ENTRY_ARG_ERROR}; \
391 if (impl_flat_hash_map_ptr) \
392 { \
393 impl_fhm_insert_or_assign_res.stats = CCC_ENTRY_INSERT_ERROR; \
394 __auto_type impl_fhm_key = key; \
395 struct ccc_fhash_entry impl_fhm_ins_or_assign_ent \
396 = ccc_impl_fhm_entry(impl_flat_hash_map_ptr, \
397 (void *)&impl_fhm_key); \
398 if (!(impl_fhm_ins_or_assign_ent.stats & CCC_ENTRY_INSERT_ERROR)) \
399 { \
400 impl_fhm_insert_or_assign_res = (struct ccc_ent){ \
401 .e = ccc_impl_fhm_data_at(impl_fhm_ins_or_assign_ent.h, \
402 impl_fhm_ins_or_assign_ent.i), \
403 .stats = impl_fhm_ins_or_assign_ent.stats, \
404 }; \
405 *((typeof(lazy_value) *)impl_fhm_insert_or_assign_res.e) \
406 = lazy_value; \
407 *((typeof(impl_fhm_key) *)ccc_impl_fhm_key_at( \
408 impl_fhm_ins_or_assign_ent.h, \
409 impl_fhm_ins_or_assign_ent.i)) \
410 = impl_fhm_key; \
411 if (impl_fhm_ins_or_assign_ent.stats == CCC_ENTRY_VACANT) \
412 { \
413 ccc_impl_fhm_set_insert(&impl_fhm_ins_or_assign_ent); \
414 } \
415 } \
416 } \
417 impl_fhm_insert_or_assign_res; \
418 }))
419
420/* NOLINTEND(readability-identifier-naming) */
421
422#endif /* CCC_IMPL_FLAT_HASH_MAP_H */
ccc_fhmap_entry
union ccc_fhmap_entry ccc_fhmap_entry
A container specific entry used to implement the Entry Interface.
Definition: flat_hash_map.h:76
ccc_any_alloc_fn
void * ccc_any_alloc_fn(void *ptr, size_t size, void *aux)
An allocation function at the core of all containers.
Definition: types.h:312
ccc_any_key_eq_fn
ccc_tribool ccc_any_key_eq_fn(ccc_any_key_cmp)
A callback function to determining equality between two stored keys.
Definition: types.h:355
ccc_any_key_hash_fn
uint64_t ccc_any_key_hash_fn(ccc_any_key to_hash)
A callback function to hash the key type used in a container.
Definition: types.h:368