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
143struct CCC_Flat_hash_map
144{
146 void *data;
148 struct CCC_Flat_hash_map_tag *tag;
150 size_t count;
152 size_t remain;
154 size_t mask;
156 size_t sizeof_type;
158 size_t key_offset;
160 CCC_Key_comparator *compare;
162 CCC_Key_hasher *hash;
164 CCC_Allocator *allocate;
166 void *context;
167};
168
171struct CCC_Flat_hash_map_entry
172{
174 struct CCC_Flat_hash_map *map;
176 size_t index;
178 struct CCC_Flat_hash_map_tag tag;
180 enum CCC_Entry_status status;
181};
182
189union CCC_Flat_hash_map_entry_wrap
190{
192 struct CCC_Flat_hash_map_entry private;
193};
194
195/*====================== Private Interface =========================*/
196
198struct CCC_Flat_hash_map_entry
199CCC_private_flat_hash_map_entry(struct CCC_Flat_hash_map *, void const *);
201void CCC_private_flat_hash_map_insert(struct CCC_Flat_hash_map *, void const *,
202 struct CCC_Flat_hash_map_tag, size_t);
204void CCC_private_flat_hash_map_erase(struct CCC_Flat_hash_map *, size_t);
206void *CCC_private_flat_hash_map_data_at(struct CCC_Flat_hash_map const *,
207 size_t);
209void *CCC_private_flat_hash_map_key_at(struct CCC_Flat_hash_map const *,
210 size_t);
212void
213CCC_private_flat_hash_map_set_insert(struct CCC_Flat_hash_map_entry const *);
214
215/*====================== Macro Implementations =========================*/
216
231#define CCC_private_flat_hash_map_declare_fixed(fixed_map_type_name, \
232 key_val_type_name, capacity) \
233 static_assert((capacity) > 0, \
234 "fixed size map must have capacity greater than 0"); \
235 static_assert( \
236 (capacity) >= CCC_FLAT_HASH_MAP_GROUP_COUNT, \
237 "fixed size map must have capacity >= CCC_FLAT_HASH_MAP_GROUP_COUNT " \
238 "(8 or 16 depending on platform)"); \
239 static_assert(((capacity) & ((capacity) - 1)) == 0, \
240 "fixed size map must be a power of 2 capacity (32, 64, " \
241 "128, 256, etc.)"); \
242 typedef struct \
243 { \
244 key_val_type_name data[(capacity) + 1]; \
245 alignas(CCC_FLAT_HASH_MAP_GROUP_COUNT) struct CCC_Flat_hash_map_tag \
246 tag[(capacity) + CCC_FLAT_HASH_MAP_GROUP_COUNT]; \
247 }(fixed_map_type_name)
248
259#define CCC_private_flat_hash_map_fixed_capacity(fixed_map_type_name) \
260 (sizeof((fixed_map_type_name){}.tag) - CCC_FLAT_HASH_MAP_GROUP_COUNT)
261
278#define CCC_private_flat_hash_map_initialize( \
279 private_type_name, private_key_field, private_hash, private_key_compare, \
280 private_allocate, private_context_data, private_capacity, \
281 private_fixed_map_pointer) \
282 { \
283 .data = (private_fixed_map_pointer), \
284 .tag = NULL, \
285 .count = 0, \
286 .remain = (((private_capacity) / (size_t)8) * (size_t)7), \
287 .mask \
288 = (((private_capacity) > (size_t)0) ? ((private_capacity) - (size_t)1) \
289 : (size_t)0), \
290 .sizeof_type = sizeof(private_type_name), \
291 .key_offset = offsetof(private_type_name, private_key_field), \
292 .compare = (private_key_compare), \
293 .hash = (private_hash), \
294 .allocate = (private_allocate), \
295 .context = (private_context_data), \
296 }
297
299#define CCC_private_flat_hash_map_from( \
300 private_key_field, private_hash, private_key_compare, private_allocate, \
301 private_context_data, private_optional_cap, \
302 private_array_compound_literal...) \
303 (__extension__({ \
304 typeof(*private_array_compound_literal) \
305 *private_flat_hash_map_initializer_list \
306 = private_array_compound_literal; \
307 struct CCC_Flat_hash_map private_map \
308 = CCC_private_flat_hash_map_initialize( \
309 typeof(*private_flat_hash_map_initializer_list), \
310 private_key_field, private_hash, private_key_compare, \
311 private_allocate, private_context_data, 0, NULL); \
312 size_t const private_n \
313 = sizeof(private_array_compound_literal) \
314 / sizeof(*private_flat_hash_map_initializer_list); \
315 size_t const private_cap = private_optional_cap; \
316 if (CCC_flat_hash_map_reserve( \
317 &private_map, \
318 (private_n > private_cap ? private_n : private_cap), \
319 private_allocate) \
320 == CCC_RESULT_OK) \
321 { \
322 for (size_t i = 0; i < private_n; ++i) \
323 { \
324 struct CCC_Flat_hash_map_entry private_ent \
325 = CCC_private_flat_hash_map_entry( \
326 &private_map, \
327 (void const \
328 *)&private_flat_hash_map_initializer_list[i] \
329 .private_key_field); \
330 *((typeof(*private_flat_hash_map_initializer_list) *) \
331 CCC_private_flat_hash_map_data_at(private_ent.map, \
332 private_ent.index)) \
333 = private_flat_hash_map_initializer_list[i]; \
334 if (private_ent.status == CCC_ENTRY_VACANT) \
335 { \
336 CCC_private_flat_hash_map_set_insert(&private_ent); \
337 } \
338 } \
339 } \
340 private_map; \
341 }))
342
344#define CCC_private_flat_hash_map_with_capacity( \
345 private_type_name, private_key_field, private_hash, private_key_compare, \
346 private_allocate, private_context_data, private_cap) \
347 (__extension__({ \
348 struct CCC_Flat_hash_map private_map \
349 = CCC_private_flat_hash_map_initialize( \
350 private_type_name, private_key_field, private_hash, \
351 private_key_compare, private_allocate, private_context_data, \
352 0, NULL); \
353 (void)CCC_flat_hash_map_reserve(&private_map, private_cap, \
354 private_allocate); \
355 private_map; \
356 }))
357
359#define CCC_private_flat_hash_map_with_compound_literal( \
360 private_key_field, private_hash, private_key_compare, \
361 private_compound_literal) \
362 { \
363 .data = &(private_compound_literal), \
364 .tag = NULL, \
365 .count = 0, \
366 .remain = ((CCC_private_flat_hash_map_fixed_capacity( \
367 typeof(private_compound_literal)) \
368 / (size_t)8) \
369 * (size_t)7), \
370 .mask = ((CCC_private_flat_hash_map_fixed_capacity( \
371 typeof(private_compound_literal)) \
372 > (size_t)0) \
373 ? (CCC_private_flat_hash_map_fixed_capacity( \
374 typeof(private_compound_literal)) \
375 - (size_t)1) \
376 : (size_t)0), \
377 .sizeof_type = sizeof(*(private_compound_literal.data)), /*NOLINT*/ \
378 .key_offset \
379 = offsetof(typeof(*(private_compound_literal.data)), /*NOLINT*/ \
380 private_key_field), \
381 .compare = (private_key_compare), \
382 .hash = (private_hash), \
383 .allocate = NULL, \
384 .context = NULL, \
385 }
386
388#define CCC_private_flat_hash_map_with_context_compound_literal( \
389 private_key_field, private_hash, private_key_compare, private_context, \
390 private_compound_literal) \
391 { \
392 .data = &(private_compound_literal), \
393 .tag = NULL, \
394 .count = 0, \
395 .remain = ((CCC_private_flat_hash_map_fixed_capacity( \
396 typeof(private_compound_literal)) \
397 / (size_t)8) \
398 * (size_t)7), \
399 .mask = ((CCC_private_flat_hash_map_fixed_capacity( \
400 typeof(private_compound_literal)) \
401 > (size_t)0) \
402 ? (CCC_private_flat_hash_map_fixed_capacity( \
403 typeof(private_compound_literal)) \
404 - (size_t)1) \
405 : (size_t)0), \
406 .sizeof_type = sizeof(*(private_compound_literal.data)), /*NOLINT*/ \
407 .key_offset \
408 = offsetof(typeof(*(private_compound_literal.data)), /*NOLINT*/ \
409 private_key_field), \
410 .compare = (private_key_compare), \
411 .hash = (private_hash), \
412 .allocate = NULL, \
413 .context = (private_context), \
414 }
415
417#define CCC_private_flat_hash_map_with_allocator( \
418 private_type_name, private_key_field, private_hash, private_key_compare, \
419 private_allocate) \
420 { \
421 .data = NULL, \
422 .tag = NULL, \
423 .count = 0, \
424 .remain = 0, \
425 .mask = 0, \
426 .sizeof_type = sizeof(private_type_name), \
427 .key_offset = offsetof(private_type_name, private_key_field), \
428 .compare = (private_key_compare), \
429 .hash = (private_hash), \
430 .allocate = (private_allocate), \
431 .context = NULL, \
432 }
433
435#define CCC_private_flat_hash_map_with_context_allocator( \
436 private_type_name, private_key_field, private_hash, private_key_compare, \
437 private_allocate, private_context) \
438 { \
439 .data = NULL, \
440 .tag = NULL, \
441 .count = 0, \
442 .remain = 0, \
443 .mask = 0, \
444 .sizeof_type = sizeof(private_type_name), \
445 .key_offset = offsetof(private_type_name, private_key_field), \
446 .compare = (private_key_compare), \
447 .hash = (private_hash), \
448 .allocate = (private_allocate), \
449 .context = (private_context), \
450 }
451
452/*======================== Construct In Place =========================*/
453
457#define CCC_private_flat_hash_map_and_modify_with( \
458 Flat_hash_map_entry_pointer, type_name, closure_over_T...) \
459 (__extension__({ \
460 __auto_type private_flat_hash_map_mod_ent_pointer \
461 = (Flat_hash_map_entry_pointer); \
462 struct CCC_Flat_hash_map_entry private_flat_hash_map_mod_with_ent \
463 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
464 if (private_flat_hash_map_mod_ent_pointer) \
465 { \
466 private_flat_hash_map_mod_with_ent \
467 = private_flat_hash_map_mod_ent_pointer->private; \
468 if (private_flat_hash_map_mod_with_ent.status \
469 & CCC_ENTRY_OCCUPIED) \
470 { \
471 type_name *const T = CCC_private_flat_hash_map_data_at( \
472 private_flat_hash_map_mod_with_ent.map, \
473 private_flat_hash_map_mod_with_ent.index); \
474 if (T) \
475 { \
476 closure_over_T \
477 } \
478 } \
479 } \
480 private_flat_hash_map_mod_with_ent; \
481 }))
482
487#define CCC_private_flat_hash_map_or_insert_with(Flat_hash_map_entry_pointer, \
488 type_compound_literal...) \
489 (__extension__({ \
490 __auto_type private_flat_hash_map_or_ins_ent_pointer \
491 = (Flat_hash_map_entry_pointer); \
492 typeof(type_compound_literal) *private_flat_hash_map_or_ins_res \
493 = NULL; \
494 if (private_flat_hash_map_or_ins_ent_pointer) \
495 { \
496 if (!(private_flat_hash_map_or_ins_ent_pointer->private.status \
497 & CCC_ENTRY_INSERT_ERROR)) \
498 { \
499 private_flat_hash_map_or_ins_res \
500 = CCC_private_flat_hash_map_data_at( \
501 private_flat_hash_map_or_ins_ent_pointer->private.map, \
502 private_flat_hash_map_or_ins_ent_pointer->private \
503 .index); \
504 if (private_flat_hash_map_or_ins_ent_pointer->private.status \
505 == CCC_ENTRY_VACANT) \
506 { \
507 *private_flat_hash_map_or_ins_res = type_compound_literal; \
508 CCC_private_flat_hash_map_set_insert( \
509 &private_flat_hash_map_or_ins_ent_pointer->private); \
510 } \
511 } \
512 } \
513 private_flat_hash_map_or_ins_res; \
514 }))
515
519#define CCC_private_flat_hash_map_insert_entry_with( \
520 Flat_hash_map_entry_pointer, type_compound_literal...) \
521 (__extension__({ \
522 __auto_type private_flat_hash_map_ins_ent_pointer \
523 = (Flat_hash_map_entry_pointer); \
524 typeof(type_compound_literal) *private_flat_hash_map_ins_ent_res \
525 = NULL; \
526 if (private_flat_hash_map_ins_ent_pointer) \
527 { \
528 if (!(private_flat_hash_map_ins_ent_pointer->private.status \
529 & CCC_ENTRY_INSERT_ERROR)) \
530 { \
531 private_flat_hash_map_ins_ent_res \
532 = CCC_private_flat_hash_map_data_at( \
533 private_flat_hash_map_ins_ent_pointer->private.map, \
534 private_flat_hash_map_ins_ent_pointer->private.index); \
535 *private_flat_hash_map_ins_ent_res = type_compound_literal; \
536 if (private_flat_hash_map_ins_ent_pointer->private.status \
537 == CCC_ENTRY_VACANT) \
538 { \
539 CCC_private_flat_hash_map_set_insert( \
540 &private_flat_hash_map_ins_ent_pointer->private); \
541 } \
542 } \
543 } \
544 private_flat_hash_map_ins_ent_res; \
545 }))
546
550#define CCC_private_flat_hash_map_try_insert_with(flat_hash_map_pointer, key, \
551 type_compound_literal...) \
552 (__extension__({ \
553 struct CCC_Flat_hash_map *private_flat_hash_map_pointer \
554 = (flat_hash_map_pointer); \
555 struct CCC_Entry private_flat_hash_map_try_insert_res \
556 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
557 if (private_flat_hash_map_pointer) \
558 { \
559 __auto_type private_flat_hash_map_key = key; \
560 struct CCC_Flat_hash_map_entry private_flat_hash_map_try_ins_ent \
561 = CCC_private_flat_hash_map_entry( \
562 private_flat_hash_map_pointer, \
563 (void *)&private_flat_hash_map_key); \
564 if ((private_flat_hash_map_try_ins_ent.status \
565 & CCC_ENTRY_OCCUPIED) \
566 || (private_flat_hash_map_try_ins_ent.status \
567 & CCC_ENTRY_INSERT_ERROR)) \
568 { \
569 private_flat_hash_map_try_insert_res = (struct CCC_Entry){ \
570 .type = CCC_private_flat_hash_map_data_at( \
571 private_flat_hash_map_try_ins_ent.map, \
572 private_flat_hash_map_try_ins_ent.index), \
573 .status = private_flat_hash_map_try_ins_ent.status, \
574 }; \
575 } \
576 else \
577 { \
578 private_flat_hash_map_try_insert_res = (struct CCC_Entry){ \
579 .type = CCC_private_flat_hash_map_data_at( \
580 private_flat_hash_map_try_ins_ent.map, \
581 private_flat_hash_map_try_ins_ent.index), \
582 .status = CCC_ENTRY_VACANT, \
583 }; \
584 *((typeof(type_compound_literal) *) \
585 private_flat_hash_map_try_insert_res.type) \
586 = type_compound_literal; \
587 *((typeof(private_flat_hash_map_key) *) \
588 CCC_private_flat_hash_map_key_at( \
589 private_flat_hash_map_try_ins_ent.map, \
590 private_flat_hash_map_try_ins_ent.index)) \
591 = private_flat_hash_map_key; \
592 CCC_private_flat_hash_map_set_insert( \
593 &private_flat_hash_map_try_ins_ent); \
594 } \
595 } \
596 private_flat_hash_map_try_insert_res; \
597 }))
598
603#define CCC_private_flat_hash_map_insert_or_assign_with( \
604 flat_hash_map_pointer, key, type_compound_literal...) \
605 (__extension__({ \
606 struct CCC_Flat_hash_map *private_flat_hash_map_pointer \
607 = (flat_hash_map_pointer); \
608 struct CCC_Entry private_flat_hash_map_insert_or_assign_res \
609 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
610 if (private_flat_hash_map_pointer) \
611 { \
612 private_flat_hash_map_insert_or_assign_res.status \
613 = CCC_ENTRY_INSERT_ERROR; \
614 __auto_type private_flat_hash_map_key = key; \
615 struct CCC_Flat_hash_map_entry \
616 private_flat_hash_map_ins_or_assign_ent \
617 = CCC_private_flat_hash_map_entry( \
618 private_flat_hash_map_pointer, \
619 (void *)&private_flat_hash_map_key); \
620 if (!(private_flat_hash_map_ins_or_assign_ent.status \
621 & CCC_ENTRY_INSERT_ERROR)) \
622 { \
623 private_flat_hash_map_insert_or_assign_res \
624 = (struct CCC_Entry){ \
625 .type = CCC_private_flat_hash_map_data_at( \
626 private_flat_hash_map_ins_or_assign_ent.map, \
627 private_flat_hash_map_ins_or_assign_ent.index), \
628 .status \
629 = private_flat_hash_map_ins_or_assign_ent.status, \
630 }; \
631 *((typeof(type_compound_literal) *) \
632 private_flat_hash_map_insert_or_assign_res.type) \
633 = type_compound_literal; \
634 *((typeof(private_flat_hash_map_key) *) \
635 CCC_private_flat_hash_map_key_at( \
636 private_flat_hash_map_ins_or_assign_ent.map, \
637 private_flat_hash_map_ins_or_assign_ent.index)) \
638 = private_flat_hash_map_key; \
639 if (private_flat_hash_map_ins_or_assign_ent.status \
640 == CCC_ENTRY_VACANT) \
641 { \
642 CCC_private_flat_hash_map_set_insert( \
643 &private_flat_hash_map_ins_or_assign_ent); \
644 } \
645 } \
646 } \
647 private_flat_hash_map_insert_or_assign_res; \
648 }))
649
650/* NOLINTEND(readability-identifier-naming) */
651
652#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:172
CCC_Flat_hash_map_entry::index
size_t index
Definition: private_flat_hash_map.h:176
CCC_Flat_hash_map_entry::tag
struct CCC_Flat_hash_map_tag tag
Definition: private_flat_hash_map.h:178
CCC_Flat_hash_map_entry::status
enum CCC_Entry_status status
Definition: private_flat_hash_map.h:180
CCC_Flat_hash_map_entry::map
struct CCC_Flat_hash_map * map
Definition: private_flat_hash_map.h:174
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:144
CCC_Flat_hash_map::compare
CCC_Key_comparator * compare
Definition: private_flat_hash_map.h:160
CCC_Flat_hash_map::context
void * context
Definition: private_flat_hash_map.h:166
CCC_Flat_hash_map::remain
size_t remain
Definition: private_flat_hash_map.h:152
CCC_Flat_hash_map::tag
struct CCC_Flat_hash_map_tag * tag
Definition: private_flat_hash_map.h:148
CCC_Flat_hash_map::sizeof_type
size_t sizeof_type
Definition: private_flat_hash_map.h:156
CCC_Flat_hash_map::key_offset
size_t key_offset
Definition: private_flat_hash_map.h:158
CCC_Flat_hash_map::mask
size_t mask
Definition: private_flat_hash_map.h:154
CCC_Flat_hash_map::data
void * data
Definition: private_flat_hash_map.h:146
CCC_Flat_hash_map::count
size_t count
Definition: private_flat_hash_map.h:150
CCC_Flat_hash_map::hash
CCC_Key_hasher * hash
Definition: private_flat_hash_map.h:162
CCC_Flat_hash_map::allocate
CCC_Allocator * allocate
Definition: private_flat_hash_map.h:164
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:190
CCC_Flat_hash_map_entry_wrap::private
struct CCC_Flat_hash_map_entry private
Definition: private_flat_hash_map.h:192