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 <stddef.h>
22#include <stdint.h>
25#include "../types.h"
26#include "impl_types.h"
27
28/* NOLINTBEGIN(readability-identifier-naming) */
29
33// #define CCC_FHM_PORTABLE
34
37#if defined(__x86_64) && defined(__SSE2__) && !defined(CCC_FHM_PORTABLE)
41# define CCC_HAS_X86_SIMD
42#elif defined(__ARM_NEON__) && !defined(CCC_FHM_PORTABLE)
46# define CCC_HAS_ARM_SIMD
47#endif /* defined(__x86_64)&&defined(__SSE2__)&&!defined(CCC_FHM_PORTABLE) */
65typedef struct
66{
68 uint8_t v;
69} ccc_fhm_tag;
70
76enum : typeof((ccc_fhm_tag){}.v)
77{
78#if defined(CCC_HAS_X86_SIMD)
80 CCC_FHM_GROUP_SIZE = 16,
81#elif defined(CCC_HAS_ARM_SIMD)
83 CCC_FHM_GROUP_SIZE = 8,
84#else /* PORTABLE FALLBACK */
86 CCC_FHM_GROUP_SIZE = 8,
87#endif /* defined(CCC_HAS_X86_SIMD) */
88};
89
115struct ccc_fhmap
116{
118 void *data;
120 ccc_fhm_tag *tag;
122 size_t count;
124 size_t remain;
126 size_t mask;
128 size_t sizeof_type;
130 size_t key_offset;
132 ccc_any_key_eq_fn *eq_fn;
134 ccc_any_key_hash_fn *hash_fn;
136 ccc_any_alloc_fn *alloc_fn;
138 void *aux;
139};
140
143struct ccc_fhash_entry
144{
146 struct ccc_fhmap *h;
148 ccc_fhm_tag tag;
150 struct ccc_handl handle;
151};
152
158union ccc_fhmap_entry
159{
160 struct ccc_fhash_entry impl;
161};
162
166/*====================== Private Interface =========================*/
167
168struct ccc_fhash_entry ccc_impl_fhm_entry(struct ccc_fhmap *h, void const *key);
169void ccc_impl_fhm_insert(struct ccc_fhmap *h, void const *key_val_type,
170 ccc_fhm_tag m, size_t i);
171void ccc_impl_fhm_erase(struct ccc_fhmap *h, size_t i);
172void *ccc_impl_fhm_data_at(struct ccc_fhmap const *h, size_t i);
173void *ccc_impl_fhm_key_at(struct ccc_fhmap const *h, size_t i);
174void ccc_impl_fhm_set_insert(struct ccc_fhash_entry const *e);
175
176/*====================== Macro Implementations =========================*/
177
185#define ccc_impl_fhm_declare_fixed_map(fixed_map_type_name, key_val_type_name, \
186 capacity) \
187 static_assert((capacity) != 0, \
188 "fixed size map must have capacity greater than 0."); \
189 static_assert((capacity) >= CCC_FHM_GROUP_SIZE, \
190 "fixed size map must have capacity >= CCC_FHM_GROUP_SIZE " \
191 "(8 or 16 depending on platform)."); \
192 static_assert(((capacity) & ((capacity) - 1)) == 0, \
193 "fixed size map must be a power of 2 capacity (32, 64, " \
194 "128, 256, etc.)."); \
195 typedef struct \
196 { \
197 key_val_type_name data[(capacity) + 1]; \
198 ccc_fhm_tag tag[(capacity) + CCC_FHM_GROUP_SIZE]; \
199 }(fixed_map_type_name);
200
211#define ccc_impl_fhm_fixed_capacity(fixed_map_type_name) \
212 (sizeof((fixed_map_type_name){}.tag) - CCC_FHM_GROUP_SIZE)
213
230#define ccc_impl_fhm_init(impl_fixed_map_ptr, impl_any_type_name, \
231 impl_key_field, impl_hash_fn, impl_key_eq_fn, \
232 impl_alloc_fn, impl_aux_data, impl_capacity) \
233 { \
234 .data = (impl_fixed_map_ptr), \
235 .tag = NULL, \
236 .count = 0, \
237 .remain = (((impl_capacity) / (size_t)8) * (size_t)7), \
238 .mask = (((impl_capacity) > (size_t)0) ? ((impl_capacity) - (size_t)1) \
239 : (size_t)0), \
240 .sizeof_type = sizeof(impl_any_type_name), \
241 .key_offset = offsetof(impl_any_type_name, impl_key_field), \
242 .eq_fn = (impl_key_eq_fn), \
243 .hash_fn = (impl_hash_fn), \
244 .alloc_fn = (impl_alloc_fn), \
245 .aux = (impl_aux_data), \
246 }
247
248/*======================== Construct In Place =========================*/
249
253#define ccc_impl_fhm_and_modify_w(flat_hash_map_entry_ptr, type_name, \
254 closure_over_T...) \
255 (__extension__({ \
256 __auto_type impl_fhm_mod_ent_ptr = (flat_hash_map_entry_ptr); \
257 struct ccc_fhash_entry impl_fhm_mod_with_ent \
258 = {.handle = {.stats = CCC_ENTRY_ARG_ERROR}}; \
259 if (impl_fhm_mod_ent_ptr) \
260 { \
261 impl_fhm_mod_with_ent = impl_fhm_mod_ent_ptr->impl; \
262 if (impl_fhm_mod_with_ent.handle.stats & CCC_ENTRY_OCCUPIED) \
263 { \
264 type_name *const T = ccc_impl_fhm_data_at( \
265 impl_fhm_mod_with_ent.h, impl_fhm_mod_with_ent.handle.i); \
266 if (T) \
267 { \
268 closure_over_T \
269 } \
270 } \
271 } \
272 impl_fhm_mod_with_ent; \
273 }))
274
279#define ccc_impl_fhm_or_insert_w(flat_hash_map_entry_ptr, lazy_key_value...) \
280 (__extension__({ \
281 __auto_type impl_fhm_or_ins_ent_ptr = (flat_hash_map_entry_ptr); \
282 typeof(lazy_key_value) *impl_fhm_or_ins_res = NULL; \
283 if (impl_fhm_or_ins_ent_ptr) \
284 { \
285 struct ccc_fhash_entry *impl_fhm_or_ins_entry \
286 = &impl_fhm_or_ins_ent_ptr->impl; \
287 if (!(impl_fhm_or_ins_entry->handle.stats \
288 & CCC_ENTRY_INSERT_ERROR)) \
289 { \
290 impl_fhm_or_ins_res \
291 = ccc_impl_fhm_data_at(impl_fhm_or_ins_entry->h, \
292 impl_fhm_or_ins_entry->handle.i); \
293 if (impl_fhm_or_ins_entry->handle.stats == CCC_ENTRY_VACANT) \
294 { \
295 *impl_fhm_or_ins_res = lazy_key_value; \
296 ccc_impl_fhm_set_insert(impl_fhm_or_ins_entry); \
297 } \
298 } \
299 } \
300 impl_fhm_or_ins_res; \
301 }))
302
305#define ccc_impl_fhm_insert_entry_w(flat_hash_map_entry_ptr, \
306 lazy_key_value...) \
307 (__extension__({ \
308 __auto_type impl_fhm_ins_ent_ptr = (flat_hash_map_entry_ptr); \
309 typeof(lazy_key_value) *impl_fhm_ins_ent_res = NULL; \
310 if (impl_fhm_ins_ent_ptr) \
311 { \
312 struct ccc_fhash_entry *impl_fhm_ins_entry \
313 = &impl_fhm_ins_ent_ptr->impl; \
314 if (!(impl_fhm_ins_entry->handle.stats & CCC_ENTRY_INSERT_ERROR)) \
315 { \
316 impl_fhm_ins_ent_res = ccc_impl_fhm_data_at( \
317 impl_fhm_ins_entry->h, impl_fhm_ins_entry->handle.i); \
318 *impl_fhm_ins_ent_res = lazy_key_value; \
319 if (impl_fhm_ins_entry->handle.stats == CCC_ENTRY_VACANT) \
320 { \
321 ccc_impl_fhm_set_insert(impl_fhm_ins_entry); \
322 } \
323 } \
324 } \
325 impl_fhm_ins_ent_res; \
326 }))
327
331#define ccc_impl_fhm_try_insert_w(flat_hash_map_ptr, key, lazy_value...) \
332 (__extension__({ \
333 struct ccc_fhmap *impl_flat_hash_map_ptr = (flat_hash_map_ptr); \
334 struct ccc_ent impl_fhm_try_insert_res \
335 = {.stats = CCC_ENTRY_ARG_ERROR}; \
336 if (impl_flat_hash_map_ptr) \
337 { \
338 __auto_type impl_fhm_key = key; \
339 struct ccc_fhash_entry impl_fhm_try_ins_ent = ccc_impl_fhm_entry( \
340 impl_flat_hash_map_ptr, (void *)&impl_fhm_key); \
341 if ((impl_fhm_try_ins_ent.handle.stats & CCC_ENTRY_OCCUPIED) \
342 || (impl_fhm_try_ins_ent.handle.stats \
343 & CCC_ENTRY_INSERT_ERROR)) \
344 { \
345 impl_fhm_try_insert_res = (struct ccc_ent){ \
346 .e = ccc_impl_fhm_data_at(impl_fhm_try_ins_ent.h, \
347 impl_fhm_try_ins_ent.handle.i), \
348 .stats = impl_fhm_try_ins_ent.handle.stats, \
349 }; \
350 } \
351 else \
352 { \
353 impl_fhm_try_insert_res = (struct ccc_ent){ \
354 .e = ccc_impl_fhm_data_at(impl_fhm_try_ins_ent.h, \
355 impl_fhm_try_ins_ent.handle.i), \
356 .stats = CCC_ENTRY_VACANT, \
357 }; \
358 *((typeof(lazy_value) *)impl_fhm_try_insert_res.e) \
359 = lazy_value; \
360 *((typeof(impl_fhm_key) *)ccc_impl_fhm_key_at( \
361 impl_fhm_try_ins_ent.h, impl_fhm_try_ins_ent.handle.i)) \
362 = impl_fhm_key; \
363 ccc_impl_fhm_set_insert(&impl_fhm_try_ins_ent); \
364 } \
365 } \
366 impl_fhm_try_insert_res; \
367 }))
368
373#define ccc_impl_fhm_insert_or_assign_w(flat_hash_map_ptr, key, lazy_value...) \
374 (__extension__({ \
375 struct ccc_fhmap *impl_flat_hash_map_ptr = (flat_hash_map_ptr); \
376 struct ccc_ent impl_fhm_insert_or_assign_res \
377 = {.stats = CCC_ENTRY_ARG_ERROR}; \
378 if (impl_flat_hash_map_ptr) \
379 { \
380 impl_fhm_insert_or_assign_res.stats = CCC_ENTRY_INSERT_ERROR; \
381 __auto_type impl_fhm_key = key; \
382 struct ccc_fhash_entry impl_fhm_ins_or_assign_ent \
383 = ccc_impl_fhm_entry(impl_flat_hash_map_ptr, \
384 (void *)&impl_fhm_key); \
385 if (!(impl_fhm_ins_or_assign_ent.handle.stats \
386 & CCC_ENTRY_INSERT_ERROR)) \
387 { \
388 impl_fhm_insert_or_assign_res = (struct ccc_ent){ \
389 .e = ccc_impl_fhm_data_at( \
390 impl_fhm_ins_or_assign_ent.h, \
391 impl_fhm_ins_or_assign_ent.handle.i), \
392 .stats = impl_fhm_ins_or_assign_ent.handle.stats, \
393 }; \
394 *((typeof(lazy_value) *)impl_fhm_insert_or_assign_res.e) \
395 = lazy_value; \
396 *((typeof(impl_fhm_key) *)ccc_impl_fhm_key_at( \
397 impl_fhm_ins_or_assign_ent.h, \
398 impl_fhm_ins_or_assign_ent.handle.i)) \
399 = impl_fhm_key; \
400 if (impl_fhm_ins_or_assign_ent.handle.stats \
401 == CCC_ENTRY_VACANT) \
402 { \
403 ccc_impl_fhm_set_insert(&impl_fhm_ins_or_assign_ent); \
404 } \
405 } \
406 } \
407 impl_fhm_insert_or_assign_res; \
408 }))
409
410/* NOLINTEND(readability-identifier-naming) */
411
412#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:65
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