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
32#if defined(__x86_64) && defined(__SSE2__) && !defined(CCC_FHM_PORTABLE)
36# define CCC_HAS_X86_SIMD
37#elif defined(__ARM_NEON__) && !defined(CCC_FHM_PORTABLE)
41# define CCC_HAS_ARM_SIMD
42#endif /* defined(__x86_64)&&defined(__SSE2__)&&!defined(CCC_FHM_PORTABLE) */
60typedef struct
61{
63 uint8_t v;
64} ccc_fhm_tag;
65
71enum : typeof((ccc_fhm_tag){}.v)
72{
73#if defined(CCC_HAS_X86_SIMD)
75 CCC_FHM_GROUP_SIZE = 16,
76#elif defined(CCC_HAS_ARM_SIMD)
78 CCC_FHM_GROUP_SIZE = 8,
79#else /* PORTABLE FALLBACK */
81 CCC_FHM_GROUP_SIZE = 8,
82#endif /* defined(CCC_HAS_X86_SIMD) */
83};
84
110struct ccc_fhmap
111{
113 void *data;
115 ccc_fhm_tag *tag;
117 size_t count;
119 size_t remain;
121 size_t mask;
123 size_t sizeof_type;
125 size_t key_offset;
127 ccc_any_key_eq_fn *eq_fn;
129 ccc_any_key_hash_fn *hash_fn;
131 ccc_any_alloc_fn *alloc_fn;
133 void *aux;
134};
135
138struct ccc_fhash_entry
139{
141 struct ccc_fhmap *h;
143 size_t i;
145 ccc_fhm_tag tag;
147 enum ccc_entry_status stats;
148};
149
155union ccc_fhmap_entry
156{
157 struct ccc_fhash_entry impl;
158};
159
163/*====================== Private Interface =========================*/
164
165struct ccc_fhash_entry ccc_impl_fhm_entry(struct ccc_fhmap *h, void const *key);
166void ccc_impl_fhm_insert(struct ccc_fhmap *h, void const *key_val_type,
167 ccc_fhm_tag m, size_t i);
168void ccc_impl_fhm_erase(struct ccc_fhmap *h, size_t i);
169void *ccc_impl_fhm_data_at(struct ccc_fhmap const *h, size_t i);
170void *ccc_impl_fhm_key_at(struct ccc_fhmap const *h, size_t i);
171void ccc_impl_fhm_set_insert(struct ccc_fhash_entry const *e);
172
173/*====================== Macro Implementations =========================*/
174
182#define ccc_impl_fhm_declare_fixed_map(fixed_map_type_name, key_val_type_name, \
183 capacity) \
184 static_assert((capacity) > 0, \
185 "fixed size map must have capacity greater than 0"); \
186 static_assert((capacity) >= CCC_FHM_GROUP_SIZE, \
187 "fixed size map must have capacity >= CCC_FHM_GROUP_SIZE " \
188 "(8 or 16 depending on platform)"); \
189 static_assert(((capacity) & ((capacity) - 1)) == 0, \
190 "fixed size map must be a power of 2 capacity (32, 64, " \
191 "128, 256, etc.)"); \
192 typedef struct \
193 { \
194 key_val_type_name data[(capacity) + 1]; \
195 ccc_fhm_tag tag[(capacity) + CCC_FHM_GROUP_SIZE]; \
196 }(fixed_map_type_name)
197
208#define ccc_impl_fhm_fixed_capacity(fixed_map_type_name) \
209 (sizeof((fixed_map_type_name){}.tag) - CCC_FHM_GROUP_SIZE)
210
227#define ccc_impl_fhm_init(impl_fixed_map_ptr, impl_any_type_name, \
228 impl_key_field, impl_hash_fn, impl_key_eq_fn, \
229 impl_alloc_fn, impl_aux_data, impl_capacity) \
230 { \
231 .data = (impl_fixed_map_ptr), \
232 .tag = NULL, \
233 .count = 0, \
234 .remain = (((impl_capacity) / (size_t)8) * (size_t)7), \
235 .mask = (((impl_capacity) > (size_t)0) ? ((impl_capacity) - (size_t)1) \
236 : (size_t)0), \
237 .sizeof_type = sizeof(impl_any_type_name), \
238 .key_offset = offsetof(impl_any_type_name, impl_key_field), \
239 .eq_fn = (impl_key_eq_fn), \
240 .hash_fn = (impl_hash_fn), \
241 .alloc_fn = (impl_alloc_fn), \
242 .aux = (impl_aux_data), \
243 }
244
245/*======================== Construct In Place =========================*/
246
250#define ccc_impl_fhm_and_modify_w(flat_hash_map_entry_ptr, type_name, \
251 closure_over_T...) \
252 (__extension__({ \
253 __auto_type impl_fhm_mod_ent_ptr = (flat_hash_map_entry_ptr); \
254 struct ccc_fhash_entry impl_fhm_mod_with_ent \
255 = {.stats = CCC_ENTRY_ARG_ERROR}; \
256 if (impl_fhm_mod_ent_ptr) \
257 { \
258 impl_fhm_mod_with_ent = impl_fhm_mod_ent_ptr->impl; \
259 if (impl_fhm_mod_with_ent.stats & CCC_ENTRY_OCCUPIED) \
260 { \
261 type_name *const T = ccc_impl_fhm_data_at( \
262 impl_fhm_mod_with_ent.h, impl_fhm_mod_with_ent.i); \
263 if (T) \
264 { \
265 closure_over_T \
266 } \
267 } \
268 } \
269 impl_fhm_mod_with_ent; \
270 }))
271
276#define ccc_impl_fhm_or_insert_w(flat_hash_map_entry_ptr, lazy_key_value...) \
277 (__extension__({ \
278 __auto_type impl_fhm_or_ins_ent_ptr = (flat_hash_map_entry_ptr); \
279 typeof(lazy_key_value) *impl_fhm_or_ins_res = NULL; \
280 if (impl_fhm_or_ins_ent_ptr) \
281 { \
282 if (!(impl_fhm_or_ins_ent_ptr->impl.stats \
283 & CCC_ENTRY_INSERT_ERROR)) \
284 { \
285 impl_fhm_or_ins_res \
286 = ccc_impl_fhm_data_at(impl_fhm_or_ins_ent_ptr->impl.h, \
287 impl_fhm_or_ins_ent_ptr->impl.i); \
288 if (impl_fhm_or_ins_ent_ptr->impl.stats == CCC_ENTRY_VACANT) \
289 { \
290 *impl_fhm_or_ins_res = lazy_key_value; \
291 ccc_impl_fhm_set_insert(&impl_fhm_or_ins_ent_ptr->impl); \
292 } \
293 } \
294 } \
295 impl_fhm_or_ins_res; \
296 }))
297
300#define ccc_impl_fhm_insert_entry_w(flat_hash_map_entry_ptr, \
301 lazy_key_value...) \
302 (__extension__({ \
303 __auto_type impl_fhm_ins_ent_ptr = (flat_hash_map_entry_ptr); \
304 typeof(lazy_key_value) *impl_fhm_ins_ent_res = NULL; \
305 if (impl_fhm_ins_ent_ptr) \
306 { \
307 if (!(impl_fhm_ins_ent_ptr->impl.stats & CCC_ENTRY_INSERT_ERROR)) \
308 { \
309 impl_fhm_ins_ent_res \
310 = ccc_impl_fhm_data_at(impl_fhm_ins_ent_ptr->impl.h, \
311 impl_fhm_ins_ent_ptr->impl.i); \
312 *impl_fhm_ins_ent_res = lazy_key_value; \
313 if (impl_fhm_ins_ent_ptr->impl.stats == CCC_ENTRY_VACANT) \
314 { \
315 ccc_impl_fhm_set_insert(&impl_fhm_ins_ent_ptr->impl); \
316 } \
317 } \
318 } \
319 impl_fhm_ins_ent_res; \
320 }))
321
325#define ccc_impl_fhm_try_insert_w(flat_hash_map_ptr, key, lazy_value...) \
326 (__extension__({ \
327 struct ccc_fhmap *impl_flat_hash_map_ptr = (flat_hash_map_ptr); \
328 struct ccc_ent impl_fhm_try_insert_res \
329 = {.stats = CCC_ENTRY_ARG_ERROR}; \
330 if (impl_flat_hash_map_ptr) \
331 { \
332 __auto_type impl_fhm_key = key; \
333 struct ccc_fhash_entry impl_fhm_try_ins_ent = ccc_impl_fhm_entry( \
334 impl_flat_hash_map_ptr, (void *)&impl_fhm_key); \
335 if ((impl_fhm_try_ins_ent.stats & CCC_ENTRY_OCCUPIED) \
336 || (impl_fhm_try_ins_ent.stats & CCC_ENTRY_INSERT_ERROR)) \
337 { \
338 impl_fhm_try_insert_res = (struct ccc_ent){ \
339 .e = ccc_impl_fhm_data_at(impl_fhm_try_ins_ent.h, \
340 impl_fhm_try_ins_ent.i), \
341 .stats = impl_fhm_try_ins_ent.stats, \
342 }; \
343 } \
344 else \
345 { \
346 impl_fhm_try_insert_res = (struct ccc_ent){ \
347 .e = ccc_impl_fhm_data_at(impl_fhm_try_ins_ent.h, \
348 impl_fhm_try_ins_ent.i), \
349 .stats = CCC_ENTRY_VACANT, \
350 }; \
351 *((typeof(lazy_value) *)impl_fhm_try_insert_res.e) \
352 = lazy_value; \
353 *((typeof(impl_fhm_key) *)ccc_impl_fhm_key_at( \
354 impl_fhm_try_ins_ent.h, impl_fhm_try_ins_ent.i)) \
355 = impl_fhm_key; \
356 ccc_impl_fhm_set_insert(&impl_fhm_try_ins_ent); \
357 } \
358 } \
359 impl_fhm_try_insert_res; \
360 }))
361
366#define ccc_impl_fhm_insert_or_assign_w(flat_hash_map_ptr, key, lazy_value...) \
367 (__extension__({ \
368 struct ccc_fhmap *impl_flat_hash_map_ptr = (flat_hash_map_ptr); \
369 struct ccc_ent impl_fhm_insert_or_assign_res \
370 = {.stats = CCC_ENTRY_ARG_ERROR}; \
371 if (impl_flat_hash_map_ptr) \
372 { \
373 impl_fhm_insert_or_assign_res.stats = CCC_ENTRY_INSERT_ERROR; \
374 __auto_type impl_fhm_key = key; \
375 struct ccc_fhash_entry impl_fhm_ins_or_assign_ent \
376 = ccc_impl_fhm_entry(impl_flat_hash_map_ptr, \
377 (void *)&impl_fhm_key); \
378 if (!(impl_fhm_ins_or_assign_ent.stats & CCC_ENTRY_INSERT_ERROR)) \
379 { \
380 impl_fhm_insert_or_assign_res = (struct ccc_ent){ \
381 .e = ccc_impl_fhm_data_at(impl_fhm_ins_or_assign_ent.h, \
382 impl_fhm_ins_or_assign_ent.i), \
383 .stats = impl_fhm_ins_or_assign_ent.stats, \
384 }; \
385 *((typeof(lazy_value) *)impl_fhm_insert_or_assign_res.e) \
386 = lazy_value; \
387 *((typeof(impl_fhm_key) *)ccc_impl_fhm_key_at( \
388 impl_fhm_ins_or_assign_ent.h, \
389 impl_fhm_ins_or_assign_ent.i)) \
390 = impl_fhm_key; \
391 if (impl_fhm_ins_or_assign_ent.stats == CCC_ENTRY_VACANT) \
392 { \
393 ccc_impl_fhm_set_insert(&impl_fhm_ins_or_assign_ent); \
394 } \
395 } \
396 } \
397 impl_fhm_insert_or_assign_res; \
398 }))
399
400/* NOLINTEND(readability-identifier-naming) */
401
402#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