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 <stdalign.h>
38#include <stddef.h>
39#include <stdint.h>
42#include "../types.h" /* IWYU pragma: keep */
43
44/* NOLINTBEGIN(readability-identifier-naming) */
45
48#if defined(__x86_64) && defined(__SSE2__) \
49 && !defined(CCC_FLAT_HASH_MAP_PORTABLE_ENABLED)
53# define CCC_HAS_X86_SIMD
54#elif defined(__ARM_NEON__) && !defined(CCC_FLAT_HASH_MAP_PORTABLE_ENABLED)
58# define CCC_HAS_ARM_SIMD
59#endif /* defined(__x86_64) && defined(__SSE2__) && \
60 !defined(CCC_FLAT_HASH_MAP_PORTABLE_ENABLED) */
80struct CCC_Flat_hash_map_tag {
82 uint8_t v;
83};
84
90enum : typeof((struct CCC_Flat_hash_map_tag){}.v) {
91#ifdef CCC_HAS_X86_SIMD
93 CCC_FLAT_HASH_MAP_GROUP_COUNT = 16,
94#elifdef CCC_HAS_ARM_SIMD
96 CCC_FLAT_HASH_MAP_GROUP_COUNT = 8,
97#else /* PORTABLE FALLBACK */
99 CCC_FLAT_HASH_MAP_GROUP_COUNT = 8,
100#endif /* defined(CCC_HAS_X86_SIMD) */
101};
102
152struct CCC_Flat_hash_map {
156 void *data;
159 struct CCC_Flat_hash_map_tag *tag;
161 size_t count;
163 size_t remain;
165 size_t mask;
167 size_t sizeof_type;
169 size_t alignof_type;
171 size_t key_offset;
173 CCC_Hasher hasher;
174};
175
178struct CCC_Flat_hash_map_entry {
180 struct CCC_Flat_hash_map *map;
182 size_t index;
184 struct CCC_Flat_hash_map_tag tag;
186 CCC_Entry_status status;
187};
188
189/*====================== Private Interface =========================*/
190
192struct CCC_Flat_hash_map_entry CCC_private_flat_hash_map_entry(
193 struct CCC_Flat_hash_map *, void const *, CCC_Allocator const *
194);
196void *
197CCC_private_flat_hash_map_data_at(struct CCC_Flat_hash_map const *, size_t);
199void *
200CCC_private_flat_hash_map_key_at(struct CCC_Flat_hash_map const *, size_t);
202void
203CCC_private_flat_hash_map_set_insert(struct CCC_Flat_hash_map_entry const *);
204
205/*====================== Macro Implementations =========================*/
206
208#define CCC_private_flat_hash_map_compound_literal_array_capacity( \
209 private_type_compound_literal_array \
210) \
211 (sizeof(private_type_compound_literal_array) \
212 / sizeof(*(private_type_compound_literal_array)))
213
219#define CCC_private_flat_hash_map_storage_for( \
220 private_type_compound_literal_array, optional_storage_specifier... \
221) \
222 (optional_storage_specifier struct { \
223 static_assert( \
224 CCC_private_flat_hash_map_compound_literal_array_capacity( \
225 private_type_compound_literal_array \
226 ) >= CCC_FLAT_HASH_MAP_GROUP_COUNT, \
227 "fixed size map must have capacity >= " \
228 "CCC_FLAT_HASH_MAP_GROUP_COUNT " \
229 "(8 or 16 depending on platform)" \
230 ); \
231 static_assert( \
232 (CCC_private_flat_hash_map_compound_literal_array_capacity( \
233 private_type_compound_literal_array \
234 ) \
235 & (CCC_private_flat_hash_map_compound_literal_array_capacity( \
236 private_type_compound_literal_array \
237 ) \
238 - 1)) \
239 == 0, \
240 "fixed size map must be a power of 2 capacity (32, 64, " \
241 "128, 256, etc.)" \
242 ); \
243 alignas( \
244 CCC_FLAT_HASH_MAP_GROUP_COUNT \
245 > alignof(*(private_type_compound_literal_array)) \
246 ? CCC_FLAT_HASH_MAP_GROUP_COUNT \
247 : alignof(*(private_type_compound_literal_array)) \
248 ) typeof(*(private_type_compound_literal_array)) data \
249 [CCC_private_flat_hash_map_compound_literal_array_capacity( \
250 private_type_compound_literal_array \
251 ) \
252 + 1]; \
253 alignas(CCC_FLAT_HASH_MAP_GROUP_COUNT) struct CCC_Flat_hash_map_tag \
254 tag[CCC_private_flat_hash_map_compound_literal_array_capacity( \
255 private_type_compound_literal_array \
256 ) \
257 + CCC_FLAT_HASH_MAP_GROUP_COUNT]; \
258 }) { \
259 }
260
262#define CCC_private_flat_hash_map_default( \
263 private_type_name, private_key_field, private_hasher... \
264) \
265 (struct CCC_Flat_hash_map) { \
266 .sizeof_type = sizeof(private_type_name), \
267 .alignof_type = alignof(private_type_name), \
268 .key_offset = offsetof(private_type_name, private_key_field), \
269 .hasher = private_hasher, \
270 }
271
289#define CCC_private_flat_hash_map_for( \
290 private_type_name, \
291 private_key_field, \
292 private_hasher, \
293 private_capacity, \
294 private_map_pointer \
295) \
296 (struct CCC_Flat_hash_map) { \
297 .data = (private_map_pointer), .tag = NULL, .count = 0, \
298 .remain = (((private_capacity) / (size_t)8) * (size_t)7), \
299 .mask \
300 = (((private_capacity) > (size_t)0) \
301 ? ((private_capacity) - (size_t)1) \
302 : (size_t)0), \
303 .sizeof_type = sizeof(private_type_name), \
304 .alignof_type = alignof(private_type_name), \
305 .key_offset = offsetof(private_type_name, private_key_field), \
306 .hasher = (private_hasher), \
307 }
308
310#define CCC_private_flat_hash_map_from( \
311 private_key_field, \
312 private_hasher, \
313 private_allocator, \
314 private_optional_cap, \
315 private_array_compound_literal... \
316) \
317 (struct { struct CCC_Flat_hash_map private; }){(__extension__({ \
318 typeof(*private_array_compound_literal) \
319 *private_flat_hash_map_initializer_list \
320 = private_array_compound_literal; \
321 struct CCC_Flat_hash_map private_map \
322 = CCC_private_flat_hash_map_default( \
323 typeof(*private_flat_hash_map_initializer_list), \
324 private_key_field, \
325 private_hasher \
326 ); \
327 size_t const private_n \
328 = sizeof(private_array_compound_literal) \
329 / sizeof(*private_flat_hash_map_initializer_list); \
330 size_t const private_cap = private_optional_cap; \
331 CCC_Allocator const *const private_flat_hash_map_allocator \
332 = &(private_allocator); \
333 if (CCC_flat_hash_map_reserve( \
334 &private_map, \
335 (private_n > private_cap ? private_n : private_cap), \
336 private_flat_hash_map_allocator \
337 ) \
338 == CCC_RESULT_OK) { \
339 for (size_t i = 0; i < private_n; ++i) { \
340 struct CCC_Flat_hash_map_entry private_ent \
341 = CCC_private_flat_hash_map_entry( \
342 &private_map, \
343 ( \
344 void const * \
345 )&private_flat_hash_map_initializer_list[i] \
346 .private_key_field, \
347 private_flat_hash_map_allocator \
348 ); \
349 *((typeof(*private_flat_hash_map_initializer_list) *) \
350 CCC_private_flat_hash_map_data_at( \
351 private_ent.map, private_ent.index \
352 )) = private_flat_hash_map_initializer_list[i]; \
353 if (private_ent.status == CCC_ENTRY_VACANT) { \
354 CCC_private_flat_hash_map_set_insert(&private_ent); \
355 } \
356 } \
357 } \
358 private_map; \
359 }))}.private
360
362#define CCC_private_flat_hash_map_with_capacity( \
363 private_type_name, \
364 private_key_field, \
365 private_hasher, \
366 private_allocator, \
367 private_cap \
368) \
369 (struct { struct CCC_Flat_hash_map private; }){(__extension__({ \
370 struct CCC_Flat_hash_map private_map \
371 = CCC_private_flat_hash_map_default( \
372 private_type_name, private_key_field, private_hasher \
373 ); \
374 (void)CCC_flat_hash_map_reserve( \
375 &private_map, private_cap, &(private_allocator) \
376 ); \
377 private_map; \
378 }))}.private
379
381#define CCC_private_flat_hash_map_with_storage( \
382 private_key_field, \
383 private_hasher, \
384 private_compound_literal, \
385 private_optional_storage_specifier... \
386) \
387 (struct CCC_Flat_hash_map) { \
388 .data = &CCC_private_flat_hash_map_storage_for( \
389 private_compound_literal, private_optional_storage_specifier \
390 ), \
391 .tag = NULL, .count = 0, \
392 .remain \
393 = ((CCC_private_flat_hash_map_compound_literal_array_capacity( \
394 private_compound_literal \
395 ) \
396 / (size_t)8) \
397 * (size_t)7), \
398 .mask = CCC_private_flat_hash_map_compound_literal_array_capacity( \
399 private_compound_literal \
400 ) \
401 - (size_t)1, \
402 .sizeof_type = sizeof(*(private_compound_literal)), \
403 .alignof_type = alignof(*(private_compound_literal)), \
404 .key_offset = offsetof( \
405 typeof(*(private_compound_literal)), private_key_field \
406 ), \
407 .hasher = (private_hasher), \
408 }
409
411#define CCC_private_flat_hash_map_with_allocator_storage( \
412 private_key_field, \
413 private_hasher, \
414 private_allocator, \
415 private_compound_literal \
416) \
417 (__extension__({ \
418 CCC_Allocator const *const private_allocator_pointer \
419 = &(private_allocator); \
420 void *private_data_base = NULL; \
421 if (private_allocator_pointer->allocate) { \
422 private_data_base = private_allocator_pointer->allocate( \
423 (CCC_Allocator_arguments){ \
424 .input = NULL, \
425 .bytes = sizeof(CCC_private_flat_hash_map_storage_for( \
426 private_compound_literal \
427 )), \
428 .alignment = CCC_FLAT_HASH_MAP_GROUP_COUNT \
429 > alignof(*(private_compound_literal)) \
430 ? CCC_FLAT_HASH_MAP_GROUP_COUNT \
431 : alignof(*(private_compound_literal)), \
432 .context = private_allocator_pointer->context, \
433 } \
434 ); \
435 } \
436 struct CCC_Flat_hash_map private_flat_hash_map = {}; \
437 if (private_data_base) { \
438 private_flat_hash_map = CCC_private_flat_hash_map_for( \
439 typeof(*(private_compound_literal)), \
440 private_key_field, \
441 private_hasher, \
442 CCC_private_flat_hash_map_compound_literal_array_capacity( \
443 private_compound_literal \
444 ), \
445 private_data_base \
446 ); \
447 } else { \
448 private_flat_hash_map = CCC_private_flat_hash_map_for( \
449 typeof(*(private_compound_literal)), \
450 private_key_field, \
451 private_hasher, \
452 0, \
453 NULL \
454 ); \
455 } \
456 private_flat_hash_map; \
457 }))
458
459/*======================== Construct In Place =========================*/
460
464#define CCC_private_flat_hash_map_and_modify_with( \
465 flat_hash_map_entry_pointer, \
466 closure_parameter, \
467 closure_over_closure_parameter... \
468) \
469 (__extension__({ \
470 struct CCC_Flat_hash_map_entry const *const \
471 private_flat_hash_map_mod_ent_pointer \
472 = (flat_hash_map_entry_pointer); \
473 struct CCC_Flat_hash_map_entry private_flat_hash_map_mod_with_ent \
474 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
475 if (private_flat_hash_map_mod_ent_pointer) { \
476 private_flat_hash_map_mod_with_ent \
477 = *private_flat_hash_map_mod_ent_pointer; \
478 if (private_flat_hash_map_mod_with_ent.status \
479 & CCC_ENTRY_OCCUPIED) { \
480 closure_parameter = CCC_private_flat_hash_map_data_at( \
481 private_flat_hash_map_mod_with_ent.map, \
482 private_flat_hash_map_mod_with_ent.index \
483 ); \
484 closure_over_closure_parameter \
485 } \
486 } \
487 private_flat_hash_map_mod_with_ent; \
488 }))
489
494#define CCC_private_flat_hash_map_or_insert_with( \
495 flat_hash_map_entry_pointer, type_compound_literal... \
496) \
497 (__extension__({ \
498 struct CCC_Flat_hash_map_entry const *const \
499 private_flat_hash_map_or_ins_ent_pointer \
500 = (flat_hash_map_entry_pointer); \
501 typeof(type_compound_literal) *private_flat_hash_map_or_ins_res \
502 = NULL; \
503 if (private_flat_hash_map_or_ins_ent_pointer) { \
504 if (!(private_flat_hash_map_or_ins_ent_pointer->status \
505 & CCC_ENTRY_INSERT_ERROR)) { \
506 private_flat_hash_map_or_ins_res \
507 = CCC_private_flat_hash_map_data_at( \
508 private_flat_hash_map_or_ins_ent_pointer->map, \
509 private_flat_hash_map_or_ins_ent_pointer->index \
510 ); \
511 if (private_flat_hash_map_or_ins_ent_pointer->status \
512 == CCC_ENTRY_VACANT) { \
513 *private_flat_hash_map_or_ins_res = type_compound_literal; \
514 CCC_private_flat_hash_map_set_insert( \
515 private_flat_hash_map_or_ins_ent_pointer \
516 ); \
517 } \
518 } \
519 } \
520 private_flat_hash_map_or_ins_res; \
521 }))
522
526#define CCC_private_flat_hash_map_insert_entry_with( \
527 flat_hash_map_entry_pointer, type_compound_literal... \
528) \
529 (__extension__({ \
530 struct CCC_Flat_hash_map_entry const *const \
531 private_flat_hash_map_ins_ent_pointer \
532 = (flat_hash_map_entry_pointer); \
533 typeof(type_compound_literal) *private_flat_hash_map_ins_ent_res \
534 = NULL; \
535 if (private_flat_hash_map_ins_ent_pointer) { \
536 if (!(private_flat_hash_map_ins_ent_pointer->status \
537 & CCC_ENTRY_INSERT_ERROR)) { \
538 private_flat_hash_map_ins_ent_res \
539 = CCC_private_flat_hash_map_data_at( \
540 private_flat_hash_map_ins_ent_pointer->map, \
541 private_flat_hash_map_ins_ent_pointer->index \
542 ); \
543 *private_flat_hash_map_ins_ent_res = type_compound_literal; \
544 if (private_flat_hash_map_ins_ent_pointer->status \
545 == CCC_ENTRY_VACANT) { \
546 CCC_private_flat_hash_map_set_insert( \
547 private_flat_hash_map_ins_ent_pointer \
548 ); \
549 } \
550 } \
551 } \
552 private_flat_hash_map_ins_ent_res; \
553 }))
554
558#define CCC_private_flat_hash_map_try_insert_with( \
559 flat_hash_map_pointer, \
560 key, \
561 private_allocator_pointer, \
562 type_compound_literal... \
563) \
564 (__extension__({ \
565 struct CCC_Flat_hash_map *private_flat_hash_map_pointer \
566 = (flat_hash_map_pointer); \
567 CCC_Entry private_flat_hash_map_try_insert_res \
568 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
569 if (private_flat_hash_map_pointer) { \
570 __auto_type private_flat_hash_map_key = key; \
571 struct CCC_Flat_hash_map_entry private_flat_hash_map_try_ins_ent \
572 = CCC_private_flat_hash_map_entry( \
573 private_flat_hash_map_pointer, \
574 (void *)&private_flat_hash_map_key, \
575 private_allocator_pointer \
576 ); \
577 if ((private_flat_hash_map_try_ins_ent.status \
578 & CCC_ENTRY_OCCUPIED) \
579 || (private_flat_hash_map_try_ins_ent.status \
580 & CCC_ENTRY_INSERT_ERROR)) { \
581 private_flat_hash_map_try_insert_res = (CCC_Entry){ \
582 .type = CCC_private_flat_hash_map_data_at( \
583 private_flat_hash_map_try_ins_ent.map, \
584 private_flat_hash_map_try_ins_ent.index \
585 ), \
586 .status = private_flat_hash_map_try_ins_ent.status, \
587 }; \
588 } else { \
589 private_flat_hash_map_try_insert_res = (CCC_Entry){ \
590 .type = CCC_private_flat_hash_map_data_at( \
591 private_flat_hash_map_try_ins_ent.map, \
592 private_flat_hash_map_try_ins_ent.index \
593 ), \
594 .status = CCC_ENTRY_VACANT, \
595 }; \
596 *((typeof(type_compound_literal) *) \
597 private_flat_hash_map_try_insert_res.type) \
598 = type_compound_literal; \
599 *((typeof(private_flat_hash_map_key) *) \
600 CCC_private_flat_hash_map_key_at( \
601 private_flat_hash_map_try_ins_ent.map, \
602 private_flat_hash_map_try_ins_ent.index \
603 )) = private_flat_hash_map_key; \
604 CCC_private_flat_hash_map_set_insert( \
605 &private_flat_hash_map_try_ins_ent \
606 ); \
607 } \
608 } \
609 private_flat_hash_map_try_insert_res; \
610 }))
611
616#define CCC_private_flat_hash_map_insert_or_assign_with( \
617 flat_hash_map_pointer, \
618 key, \
619 private_allocator_pointer, \
620 type_compound_literal... \
621) \
622 (__extension__({ \
623 struct CCC_Flat_hash_map *private_flat_hash_map_pointer \
624 = (flat_hash_map_pointer); \
625 CCC_Entry private_flat_hash_map_insert_or_assign_res \
626 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
627 if (private_flat_hash_map_pointer) { \
628 private_flat_hash_map_insert_or_assign_res.status \
629 = CCC_ENTRY_INSERT_ERROR; \
630 __auto_type private_flat_hash_map_key = key; \
631 struct CCC_Flat_hash_map_entry \
632 private_flat_hash_map_ins_or_assign_ent \
633 = CCC_private_flat_hash_map_entry( \
634 private_flat_hash_map_pointer, \
635 (void *)&private_flat_hash_map_key, \
636 private_allocator_pointer \
637 ); \
638 if (!(private_flat_hash_map_ins_or_assign_ent.status \
639 & CCC_ENTRY_INSERT_ERROR)) { \
640 private_flat_hash_map_insert_or_assign_res = (CCC_Entry){ \
641 .type = CCC_private_flat_hash_map_data_at( \
642 private_flat_hash_map_ins_or_assign_ent.map, \
643 private_flat_hash_map_ins_or_assign_ent.index \
644 ), \
645 .status = private_flat_hash_map_ins_or_assign_ent.status, \
646 }; \
647 *((typeof(type_compound_literal) *) \
648 private_flat_hash_map_insert_or_assign_res.type) \
649 = type_compound_literal; \
650 *((typeof(private_flat_hash_map_key) *) \
651 CCC_private_flat_hash_map_key_at( \
652 private_flat_hash_map_ins_or_assign_ent.map, \
653 private_flat_hash_map_ins_or_assign_ent.index \
654 )) = private_flat_hash_map_key; \
655 if (private_flat_hash_map_ins_or_assign_ent.status \
656 == CCC_ENTRY_VACANT) { \
657 CCC_private_flat_hash_map_set_insert( \
658 &private_flat_hash_map_ins_or_assign_ent \
659 ); \
660 } \
661 } \
662 } \
663 private_flat_hash_map_insert_or_assign_res; \
664 }))
665
666/* NOLINTEND(readability-identifier-naming) */
667
668#endif /* CCC_PRIVATE_FLAT_HASH_MAP_H */
CCC_FLAT_HASH_MAP_GROUP_COUNT
enum @4 CCC_FLAT_HASH_MAP_GROUP_COUNT
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_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_Allocator const *)
CCC_Allocator
The type passed by reference to any container function that may need to allocate memory....
Definition: types.h:384
CCC_Flat_hash_map_entry
Definition: private_flat_hash_map.h:178
CCC_Flat_hash_map_entry::index
size_t index
Definition: private_flat_hash_map.h:182
CCC_Flat_hash_map_entry::tag
struct CCC_Flat_hash_map_tag tag
Definition: private_flat_hash_map.h:184
CCC_Flat_hash_map_entry::status
CCC_Entry_status status
Definition: private_flat_hash_map.h:186
CCC_Flat_hash_map_entry::map
struct CCC_Flat_hash_map * map
Definition: private_flat_hash_map.h:180
CCC_Flat_hash_map_tag
Definition: private_flat_hash_map.h:80
CCC_Flat_hash_map_tag::v
uint8_t v
Definition: private_flat_hash_map.h:82
CCC_Flat_hash_map
Definition: private_flat_hash_map.h:152
CCC_Flat_hash_map::remain
size_t remain
Definition: private_flat_hash_map.h:163
CCC_Flat_hash_map::alignof_type
size_t alignof_type
Definition: private_flat_hash_map.h:169
CCC_Flat_hash_map::tag
struct CCC_Flat_hash_map_tag * tag
Definition: private_flat_hash_map.h:159
CCC_Flat_hash_map::sizeof_type
size_t sizeof_type
Definition: private_flat_hash_map.h:167
CCC_Flat_hash_map::key_offset
size_t key_offset
Definition: private_flat_hash_map.h:171
CCC_Flat_hash_map::mask
size_t mask
Definition: private_flat_hash_map.h:165
CCC_Flat_hash_map::data
void * data
Definition: private_flat_hash_map.h:156
CCC_Flat_hash_map::count
size_t count
Definition: private_flat_hash_map.h:161
CCC_Flat_hash_map::hasher
CCC_Hasher hasher
Definition: private_flat_hash_map.h:173
CCC_Hasher
The type passed by reference to a hash map that needs a hash function and key comparison function....
Definition: types.h:558
CCC_Entry_status
CCC_Entry_status
The status monitoring and entry state once it is obtained.
Definition: types.h:112