C Container Collection (CCC)
Loading...
Searching...
No Matches
private_flat_hash_map.h
Go to the documentation of this file.
1
33#ifndef CCC_PRIVATE_FLAT_HASH_MAP_H
34#define CCC_PRIVATE_FLAT_HASH_MAP_H
35
37#include <assert.h>
38#include <stdalign.h>
39#include <stddef.h>
40#include <stdint.h>
43#include "../types.h"
44#include "private_types.h"
45
46/* NOLINTBEGIN(readability-identifier-naming) */
47
50#if defined(__x86_64) && defined(__SSE2__) \
51 && !defined(CCC_FLAT_HASH_MAP_PORTABLE)
55# define CCC_HAS_X86_SIMD
56#elif defined(__ARM_NEON__) && !defined(CCC_FLAT_HASH_MAP_PORTABLE)
60# define CCC_HAS_ARM_SIMD
61#endif /* defined(__x86_64)&&defined(__SSE2__)&&!defined(CCC_FLAT_HASH_MAP_PORTABLE) \
62 */
80struct CCC_Flat_hash_map_tag
81{
83 uint8_t v;
84};
85
91enum : typeof((struct CCC_Flat_hash_map_tag){}.v)
92{
93#ifdef CCC_HAS_X86_SIMD
95 CCC_FLAT_HASH_MAP_GROUP_COUNT = 16,
96#elifdef CCC_HAS_ARM_SIMD
98 CCC_FLAT_HASH_MAP_GROUP_COUNT = 8,
99#else /* PORTABLE FALLBACK */
101 CCC_FLAT_HASH_MAP_GROUP_COUNT = 8,
102#endif /* defined(CCC_HAS_X86_SIMD) */
103};
104
141struct CCC_Flat_hash_map
142{
144 void *data;
146 struct CCC_Flat_hash_map_tag *tag;
148 size_t count;
150 size_t remain;
152 size_t mask;
154 size_t sizeof_type;
156 size_t key_offset;
158 CCC_Key_comparator *compare;
160 CCC_Key_hasher *hash;
162 CCC_Allocator *allocate;
164 void *context;
165};
166
169struct CCC_Flat_hash_map_entry
170{
172 struct CCC_Flat_hash_map *map;
174 size_t index;
176 struct CCC_Flat_hash_map_tag tag;
178 enum CCC_Entry_status status;
179};
180
187union CCC_Flat_hash_map_entry_wrap
188{
190 struct CCC_Flat_hash_map_entry private;
191};
192
193/*====================== Private Interface =========================*/
194
196struct CCC_Flat_hash_map_entry
197CCC_private_flat_hash_map_entry(struct CCC_Flat_hash_map *, void const *);
199void CCC_private_flat_hash_map_insert(struct CCC_Flat_hash_map *, void const *,
200 struct CCC_Flat_hash_map_tag, size_t);
202void CCC_private_flat_hash_map_erase(struct CCC_Flat_hash_map *, size_t);
204void *CCC_private_flat_hash_map_data_at(struct CCC_Flat_hash_map const *,
205 size_t);
207void *CCC_private_flat_hash_map_key_at(struct CCC_Flat_hash_map const *,
208 size_t);
210void
211CCC_private_flat_hash_map_set_insert(struct CCC_Flat_hash_map_entry const *);
212
213/*====================== Macro Implementations =========================*/
214
229#define CCC_private_flat_hash_map_declare_fixed_map( \
230 fixed_map_type_name, key_val_type_name, capacity) \
231 static_assert((capacity) > 0, \
232 "fixed size map must have capacity greater than 0"); \
233 static_assert( \
234 (capacity) >= CCC_FLAT_HASH_MAP_GROUP_COUNT, \
235 "fixed size map must have capacity >= CCC_FLAT_HASH_MAP_GROUP_COUNT " \
236 "(8 or 16 depending on platform)"); \
237 static_assert(((capacity) & ((capacity) - 1)) == 0, \
238 "fixed size map must be a power of 2 capacity (32, 64, " \
239 "128, 256, etc.)"); \
240 typedef struct \
241 { \
242 key_val_type_name data[(capacity) + 1]; \
243 alignas(CCC_FLAT_HASH_MAP_GROUP_COUNT) struct CCC_Flat_hash_map_tag \
244 tag[(capacity) + CCC_FLAT_HASH_MAP_GROUP_COUNT]; \
245 }(fixed_map_type_name)
246
257#define CCC_private_flat_hash_map_fixed_capacity(fixed_map_type_name) \
258 (sizeof((fixed_map_type_name){}.tag) - CCC_FLAT_HASH_MAP_GROUP_COUNT)
259
276#define CCC_private_flat_hash_map_initialize( \
277 private_fixed_map_pointer, private_type_name, private_key_field, \
278 private_hash, private_key_compare, private_allocate, private_context_data, \
279 private_capacity) \
280 { \
281 .data = (private_fixed_map_pointer), \
282 .tag = NULL, \
283 .count = 0, \
284 .remain = (((private_capacity) / (size_t)8) * (size_t)7), \
285 .mask \
286 = (((private_capacity) > (size_t)0) ? ((private_capacity) - (size_t)1) \
287 : (size_t)0), \
288 .sizeof_type = sizeof(private_type_name), \
289 .key_offset = offsetof(private_type_name, private_key_field), \
290 .compare = (private_key_compare), \
291 .hash = (private_hash), \
292 .allocate = (private_allocate), \
293 .context = (private_context_data), \
294 }
295
297#define CCC_private_flat_hash_map_from( \
298 private_key_field, private_hash, private_key_compare, private_allocate, \
299 private_context_data, private_optional_cap, \
300 private_array_compound_literal...) \
301 (__extension__({ \
302 typeof(*private_array_compound_literal) \
303 *private_flat_hash_map_initializer_list \
304 = private_array_compound_literal; \
305 struct CCC_Flat_hash_map private_map \
306 = CCC_private_flat_hash_map_initialize( \
307 NULL, typeof(*private_flat_hash_map_initializer_list), \
308 private_key_field, private_hash, private_key_compare, \
309 private_allocate, private_context_data, 0); \
310 size_t const private_n \
311 = sizeof(private_array_compound_literal) \
312 / sizeof(*private_flat_hash_map_initializer_list); \
313 size_t const private_cap = private_optional_cap; \
314 if (CCC_flat_hash_map_reserve( \
315 &private_map, \
316 (private_n > private_cap ? private_n : private_cap), \
317 private_allocate) \
318 == CCC_RESULT_OK) \
319 { \
320 for (size_t i = 0; i < private_n; ++i) \
321 { \
322 struct CCC_Flat_hash_map_entry private_ent \
323 = CCC_private_flat_hash_map_entry( \
324 &private_map, \
325 (void const \
326 *)&private_flat_hash_map_initializer_list[i] \
327 .private_key_field); \
328 *((typeof(*private_flat_hash_map_initializer_list) *) \
329 CCC_private_flat_hash_map_data_at(private_ent.map, \
330 private_ent.index)) \
331 = private_flat_hash_map_initializer_list[i]; \
332 if (private_ent.status == CCC_ENTRY_VACANT) \
333 { \
334 CCC_private_flat_hash_map_set_insert(&private_ent); \
335 } \
336 } \
337 } \
338 private_map; \
339 }))
340
342#define CCC_private_flat_hash_map_with_capacity( \
343 private_type_name, private_key_field, private_hash, private_key_compare, \
344 private_allocate, private_context_data, private_cap) \
345 (__extension__({ \
346 struct CCC_Flat_hash_map private_map \
347 = CCC_private_flat_hash_map_initialize( \
348 NULL, private_type_name, private_key_field, private_hash, \
349 private_key_compare, private_allocate, private_context_data, \
350 0); \
351 (void)CCC_flat_hash_map_reserve(&private_map, private_cap, \
352 private_allocate); \
353 private_map; \
354 }))
355
356/*======================== Construct In Place =========================*/
357
361#define CCC_private_flat_hash_map_and_modify_with( \
362 Flat_hash_map_entry_pointer, type_name, closure_over_T...) \
363 (__extension__({ \
364 __auto_type private_flat_hash_map_mod_ent_pointer \
365 = (Flat_hash_map_entry_pointer); \
366 struct CCC_Flat_hash_map_entry private_flat_hash_map_mod_with_ent \
367 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
368 if (private_flat_hash_map_mod_ent_pointer) \
369 { \
370 private_flat_hash_map_mod_with_ent \
371 = private_flat_hash_map_mod_ent_pointer->private; \
372 if (private_flat_hash_map_mod_with_ent.status \
373 & CCC_ENTRY_OCCUPIED) \
374 { \
375 type_name *const T = CCC_private_flat_hash_map_data_at( \
376 private_flat_hash_map_mod_with_ent.map, \
377 private_flat_hash_map_mod_with_ent.index); \
378 if (T) \
379 { \
380 closure_over_T \
381 } \
382 } \
383 } \
384 private_flat_hash_map_mod_with_ent; \
385 }))
386
391#define CCC_private_flat_hash_map_or_insert_with(Flat_hash_map_entry_pointer, \
392 type_compound_literal...) \
393 (__extension__({ \
394 __auto_type private_flat_hash_map_or_ins_ent_pointer \
395 = (Flat_hash_map_entry_pointer); \
396 typeof(type_compound_literal) *private_flat_hash_map_or_ins_res \
397 = NULL; \
398 if (private_flat_hash_map_or_ins_ent_pointer) \
399 { \
400 if (!(private_flat_hash_map_or_ins_ent_pointer->private.status \
401 & CCC_ENTRY_INSERT_ERROR)) \
402 { \
403 private_flat_hash_map_or_ins_res \
404 = CCC_private_flat_hash_map_data_at( \
405 private_flat_hash_map_or_ins_ent_pointer->private.map, \
406 private_flat_hash_map_or_ins_ent_pointer->private \
407 .index); \
408 if (private_flat_hash_map_or_ins_ent_pointer->private.status \
409 == CCC_ENTRY_VACANT) \
410 { \
411 *private_flat_hash_map_or_ins_res = type_compound_literal; \
412 CCC_private_flat_hash_map_set_insert( \
413 &private_flat_hash_map_or_ins_ent_pointer->private); \
414 } \
415 } \
416 } \
417 private_flat_hash_map_or_ins_res; \
418 }))
419
423#define CCC_private_flat_hash_map_insert_entry_with( \
424 Flat_hash_map_entry_pointer, type_compound_literal...) \
425 (__extension__({ \
426 __auto_type private_flat_hash_map_ins_ent_pointer \
427 = (Flat_hash_map_entry_pointer); \
428 typeof(type_compound_literal) *private_flat_hash_map_ins_ent_res \
429 = NULL; \
430 if (private_flat_hash_map_ins_ent_pointer) \
431 { \
432 if (!(private_flat_hash_map_ins_ent_pointer->private.status \
433 & CCC_ENTRY_INSERT_ERROR)) \
434 { \
435 private_flat_hash_map_ins_ent_res \
436 = CCC_private_flat_hash_map_data_at( \
437 private_flat_hash_map_ins_ent_pointer->private.map, \
438 private_flat_hash_map_ins_ent_pointer->private.index); \
439 *private_flat_hash_map_ins_ent_res = type_compound_literal; \
440 if (private_flat_hash_map_ins_ent_pointer->private.status \
441 == CCC_ENTRY_VACANT) \
442 { \
443 CCC_private_flat_hash_map_set_insert( \
444 &private_flat_hash_map_ins_ent_pointer->private); \
445 } \
446 } \
447 } \
448 private_flat_hash_map_ins_ent_res; \
449 }))
450
454#define CCC_private_flat_hash_map_try_insert_with(flat_hash_map_pointer, key, \
455 type_compound_literal...) \
456 (__extension__({ \
457 struct CCC_Flat_hash_map *private_flat_hash_map_pointer \
458 = (flat_hash_map_pointer); \
459 struct CCC_Entry private_flat_hash_map_try_insert_res \
460 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
461 if (private_flat_hash_map_pointer) \
462 { \
463 __auto_type private_flat_hash_map_key = key; \
464 struct CCC_Flat_hash_map_entry private_flat_hash_map_try_ins_ent \
465 = CCC_private_flat_hash_map_entry( \
466 private_flat_hash_map_pointer, \
467 (void *)&private_flat_hash_map_key); \
468 if ((private_flat_hash_map_try_ins_ent.status \
469 & CCC_ENTRY_OCCUPIED) \
470 || (private_flat_hash_map_try_ins_ent.status \
471 & CCC_ENTRY_INSERT_ERROR)) \
472 { \
473 private_flat_hash_map_try_insert_res = (struct CCC_Entry){ \
474 .type = CCC_private_flat_hash_map_data_at( \
475 private_flat_hash_map_try_ins_ent.map, \
476 private_flat_hash_map_try_ins_ent.index), \
477 .status = private_flat_hash_map_try_ins_ent.status, \
478 }; \
479 } \
480 else \
481 { \
482 private_flat_hash_map_try_insert_res = (struct CCC_Entry){ \
483 .type = CCC_private_flat_hash_map_data_at( \
484 private_flat_hash_map_try_ins_ent.map, \
485 private_flat_hash_map_try_ins_ent.index), \
486 .status = CCC_ENTRY_VACANT, \
487 }; \
488 *((typeof(type_compound_literal) *) \
489 private_flat_hash_map_try_insert_res.type) \
490 = type_compound_literal; \
491 *((typeof(private_flat_hash_map_key) *) \
492 CCC_private_flat_hash_map_key_at( \
493 private_flat_hash_map_try_ins_ent.map, \
494 private_flat_hash_map_try_ins_ent.index)) \
495 = private_flat_hash_map_key; \
496 CCC_private_flat_hash_map_set_insert( \
497 &private_flat_hash_map_try_ins_ent); \
498 } \
499 } \
500 private_flat_hash_map_try_insert_res; \
501 }))
502
507#define CCC_private_flat_hash_map_insert_or_assign_with( \
508 flat_hash_map_pointer, key, type_compound_literal...) \
509 (__extension__({ \
510 struct CCC_Flat_hash_map *private_flat_hash_map_pointer \
511 = (flat_hash_map_pointer); \
512 struct CCC_Entry private_flat_hash_map_insert_or_assign_res \
513 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
514 if (private_flat_hash_map_pointer) \
515 { \
516 private_flat_hash_map_insert_or_assign_res.status \
517 = CCC_ENTRY_INSERT_ERROR; \
518 __auto_type private_flat_hash_map_key = key; \
519 struct CCC_Flat_hash_map_entry \
520 private_flat_hash_map_ins_or_assign_ent \
521 = CCC_private_flat_hash_map_entry( \
522 private_flat_hash_map_pointer, \
523 (void *)&private_flat_hash_map_key); \
524 if (!(private_flat_hash_map_ins_or_assign_ent.status \
525 & CCC_ENTRY_INSERT_ERROR)) \
526 { \
527 private_flat_hash_map_insert_or_assign_res \
528 = (struct CCC_Entry){ \
529 .type = CCC_private_flat_hash_map_data_at( \
530 private_flat_hash_map_ins_or_assign_ent.map, \
531 private_flat_hash_map_ins_or_assign_ent.index), \
532 .status \
533 = private_flat_hash_map_ins_or_assign_ent.status, \
534 }; \
535 *((typeof(type_compound_literal) *) \
536 private_flat_hash_map_insert_or_assign_res.type) \
537 = type_compound_literal; \
538 *((typeof(private_flat_hash_map_key) *) \
539 CCC_private_flat_hash_map_key_at( \
540 private_flat_hash_map_ins_or_assign_ent.map, \
541 private_flat_hash_map_ins_or_assign_ent.index)) \
542 = private_flat_hash_map_key; \
543 if (private_flat_hash_map_ins_or_assign_ent.status \
544 == CCC_ENTRY_VACANT) \
545 { \
546 CCC_private_flat_hash_map_set_insert( \
547 &private_flat_hash_map_ins_or_assign_ent); \
548 } \
549 } \
550 } \
551 private_flat_hash_map_insert_or_assign_res; \
552 }))
553
554/* NOLINTEND(readability-identifier-naming) */
555
556#endif /* CCC_PRIVATE_FLAT_HASH_MAP_H */
CCC_private_flat_hash_map_erase
void CCC_private_flat_hash_map_erase(struct CCC_Flat_hash_map *, size_t)
CCC_private_flat_hash_map_insert
void CCC_private_flat_hash_map_insert(struct CCC_Flat_hash_map *, void const *, struct CCC_Flat_hash_map_tag, size_t)
CCC_private_flat_hash_map_entry
struct CCC_Flat_hash_map_entry CCC_private_flat_hash_map_entry(struct CCC_Flat_hash_map *, void const *)
CCC_private_flat_hash_map_data_at
void * CCC_private_flat_hash_map_data_at(struct CCC_Flat_hash_map const *, size_t)
CCC_private_flat_hash_map_key_at
void * CCC_private_flat_hash_map_key_at(struct CCC_Flat_hash_map const *, size_t)
CCC_private_flat_hash_map_set_insert
void CCC_private_flat_hash_map_set_insert(struct CCC_Flat_hash_map_entry const *)
CCC_FLAT_HASH_MAP_GROUP_COUNT
enum @6 CCC_FLAT_HASH_MAP_GROUP_COUNT
CCC_Flat_hash_map_entry
Definition: private_flat_hash_map.h:170
CCC_Flat_hash_map_entry::index
size_t index
Definition: private_flat_hash_map.h:174
CCC_Flat_hash_map_entry::tag
struct CCC_Flat_hash_map_tag tag
Definition: private_flat_hash_map.h:176
CCC_Flat_hash_map_entry::status
enum CCC_Entry_status status
Definition: private_flat_hash_map.h:178
CCC_Flat_hash_map_entry::map
struct CCC_Flat_hash_map * map
Definition: private_flat_hash_map.h:172
CCC_Flat_hash_map_tag
Definition: private_flat_hash_map.h:81
CCC_Flat_hash_map_tag::v
uint8_t v
Definition: private_flat_hash_map.h:83
CCC_Flat_hash_map
Definition: private_flat_hash_map.h:142
CCC_Flat_hash_map::compare
CCC_Key_comparator * compare
Definition: private_flat_hash_map.h:158
CCC_Flat_hash_map::context
void * context
Definition: private_flat_hash_map.h:164
CCC_Flat_hash_map::remain
size_t remain
Definition: private_flat_hash_map.h:150
CCC_Flat_hash_map::tag
struct CCC_Flat_hash_map_tag * tag
Definition: private_flat_hash_map.h:146
CCC_Flat_hash_map::sizeof_type
size_t sizeof_type
Definition: private_flat_hash_map.h:154
CCC_Flat_hash_map::key_offset
size_t key_offset
Definition: private_flat_hash_map.h:156
CCC_Flat_hash_map::mask
size_t mask
Definition: private_flat_hash_map.h:152
CCC_Flat_hash_map::data
void * data
Definition: private_flat_hash_map.h:144
CCC_Flat_hash_map::count
size_t count
Definition: private_flat_hash_map.h:148
CCC_Flat_hash_map::hash
CCC_Key_hasher * hash
Definition: private_flat_hash_map.h:160
CCC_Flat_hash_map::allocate
CCC_Allocator * allocate
Definition: private_flat_hash_map.h:162
CCC_Key_comparator
CCC_Order CCC_Key_comparator(CCC_Key_comparator_context)
A callback function for three-way comparing two stored keys.
Definition: types.h:383
CCC_Allocator
void * CCC_Allocator(CCC_Allocator_context)
An allocation function at the core of all containers.
Definition: types.h:340
CCC_Key_hasher
uint64_t CCC_Key_hasher(CCC_Key_context)
A callback function to hash the key type used in a container.
Definition: types.h:389
CCC_Flat_hash_map_entry_wrap
Definition: private_flat_hash_map.h:188
CCC_Flat_hash_map_entry_wrap::private
struct CCC_Flat_hash_map_entry private
Definition: private_flat_hash_map.h:190