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(fixed_map_type_name, \
230 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
357#define CCC_private_flat_hash_map_with_compound_literal( \
358 private_key_field, private_hash, private_key_compare, \
359 private_compound_literal) \
360 { \
361 .data = &(private_compound_literal), \
362 .tag = NULL, \
363 .count = 0, \
364 .remain = ((CCC_private_flat_hash_map_fixed_capacity( \
365 typeof(private_compound_literal)) \
366 / (size_t)8) \
367 * (size_t)7), \
368 .mask = ((CCC_private_flat_hash_map_fixed_capacity( \
369 typeof(private_compound_literal)) \
370 > (size_t)0) \
371 ? (CCC_private_flat_hash_map_fixed_capacity( \
372 typeof(private_compound_literal)) \
373 - (size_t)1) \
374 : (size_t)0), \
375 .sizeof_type = sizeof(*(private_compound_literal.data)), /*NOLINT*/ \
376 .key_offset \
377 = offsetof(typeof(*(private_compound_literal.data)), /*NOLINT*/ \
378 private_key_field), \
379 .compare = (private_key_compare), \
380 .hash = (private_hash), \
381 .allocate = NULL, \
382 .context = NULL, \
383 }
384
386#define CCC_private_flat_hash_map_with_context_compound_literal( \
387 private_key_field, private_hash, private_key_compare, private_context, \
388 private_compound_literal) \
389 { \
390 .data = &(private_compound_literal), \
391 .tag = NULL, \
392 .count = 0, \
393 .remain = ((CCC_private_flat_hash_map_fixed_capacity( \
394 typeof(private_compound_literal)) \
395 / (size_t)8) \
396 * (size_t)7), \
397 .mask = ((CCC_private_flat_hash_map_fixed_capacity( \
398 typeof(private_compound_literal)) \
399 > (size_t)0) \
400 ? (CCC_private_flat_hash_map_fixed_capacity( \
401 typeof(private_compound_literal)) \
402 - (size_t)1) \
403 : (size_t)0), \
404 .sizeof_type = sizeof(*(private_compound_literal.data)), /*NOLINT*/ \
405 .key_offset \
406 = offsetof(typeof(*(private_compound_literal.data)), /*NOLINT*/ \
407 private_key_field), \
408 .compare = (private_key_compare), \
409 .hash = (private_hash), \
410 .allocate = NULL, \
411 .context = (private_context), \
412 }
413
414/*======================== Construct In Place =========================*/
415
419#define CCC_private_flat_hash_map_and_modify_with( \
420 Flat_hash_map_entry_pointer, type_name, closure_over_T...) \
421 (__extension__({ \
422 __auto_type private_flat_hash_map_mod_ent_pointer \
423 = (Flat_hash_map_entry_pointer); \
424 struct CCC_Flat_hash_map_entry private_flat_hash_map_mod_with_ent \
425 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
426 if (private_flat_hash_map_mod_ent_pointer) \
427 { \
428 private_flat_hash_map_mod_with_ent \
429 = private_flat_hash_map_mod_ent_pointer->private; \
430 if (private_flat_hash_map_mod_with_ent.status \
431 & CCC_ENTRY_OCCUPIED) \
432 { \
433 type_name *const T = CCC_private_flat_hash_map_data_at( \
434 private_flat_hash_map_mod_with_ent.map, \
435 private_flat_hash_map_mod_with_ent.index); \
436 if (T) \
437 { \
438 closure_over_T \
439 } \
440 } \
441 } \
442 private_flat_hash_map_mod_with_ent; \
443 }))
444
449#define CCC_private_flat_hash_map_or_insert_with(Flat_hash_map_entry_pointer, \
450 type_compound_literal...) \
451 (__extension__({ \
452 __auto_type private_flat_hash_map_or_ins_ent_pointer \
453 = (Flat_hash_map_entry_pointer); \
454 typeof(type_compound_literal) *private_flat_hash_map_or_ins_res \
455 = NULL; \
456 if (private_flat_hash_map_or_ins_ent_pointer) \
457 { \
458 if (!(private_flat_hash_map_or_ins_ent_pointer->private.status \
459 & CCC_ENTRY_INSERT_ERROR)) \
460 { \
461 private_flat_hash_map_or_ins_res \
462 = CCC_private_flat_hash_map_data_at( \
463 private_flat_hash_map_or_ins_ent_pointer->private.map, \
464 private_flat_hash_map_or_ins_ent_pointer->private \
465 .index); \
466 if (private_flat_hash_map_or_ins_ent_pointer->private.status \
467 == CCC_ENTRY_VACANT) \
468 { \
469 *private_flat_hash_map_or_ins_res = type_compound_literal; \
470 CCC_private_flat_hash_map_set_insert( \
471 &private_flat_hash_map_or_ins_ent_pointer->private); \
472 } \
473 } \
474 } \
475 private_flat_hash_map_or_ins_res; \
476 }))
477
481#define CCC_private_flat_hash_map_insert_entry_with( \
482 Flat_hash_map_entry_pointer, type_compound_literal...) \
483 (__extension__({ \
484 __auto_type private_flat_hash_map_ins_ent_pointer \
485 = (Flat_hash_map_entry_pointer); \
486 typeof(type_compound_literal) *private_flat_hash_map_ins_ent_res \
487 = NULL; \
488 if (private_flat_hash_map_ins_ent_pointer) \
489 { \
490 if (!(private_flat_hash_map_ins_ent_pointer->private.status \
491 & CCC_ENTRY_INSERT_ERROR)) \
492 { \
493 private_flat_hash_map_ins_ent_res \
494 = CCC_private_flat_hash_map_data_at( \
495 private_flat_hash_map_ins_ent_pointer->private.map, \
496 private_flat_hash_map_ins_ent_pointer->private.index); \
497 *private_flat_hash_map_ins_ent_res = type_compound_literal; \
498 if (private_flat_hash_map_ins_ent_pointer->private.status \
499 == CCC_ENTRY_VACANT) \
500 { \
501 CCC_private_flat_hash_map_set_insert( \
502 &private_flat_hash_map_ins_ent_pointer->private); \
503 } \
504 } \
505 } \
506 private_flat_hash_map_ins_ent_res; \
507 }))
508
512#define CCC_private_flat_hash_map_try_insert_with(flat_hash_map_pointer, key, \
513 type_compound_literal...) \
514 (__extension__({ \
515 struct CCC_Flat_hash_map *private_flat_hash_map_pointer \
516 = (flat_hash_map_pointer); \
517 struct CCC_Entry private_flat_hash_map_try_insert_res \
518 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
519 if (private_flat_hash_map_pointer) \
520 { \
521 __auto_type private_flat_hash_map_key = key; \
522 struct CCC_Flat_hash_map_entry private_flat_hash_map_try_ins_ent \
523 = CCC_private_flat_hash_map_entry( \
524 private_flat_hash_map_pointer, \
525 (void *)&private_flat_hash_map_key); \
526 if ((private_flat_hash_map_try_ins_ent.status \
527 & CCC_ENTRY_OCCUPIED) \
528 || (private_flat_hash_map_try_ins_ent.status \
529 & CCC_ENTRY_INSERT_ERROR)) \
530 { \
531 private_flat_hash_map_try_insert_res = (struct CCC_Entry){ \
532 .type = CCC_private_flat_hash_map_data_at( \
533 private_flat_hash_map_try_ins_ent.map, \
534 private_flat_hash_map_try_ins_ent.index), \
535 .status = private_flat_hash_map_try_ins_ent.status, \
536 }; \
537 } \
538 else \
539 { \
540 private_flat_hash_map_try_insert_res = (struct CCC_Entry){ \
541 .type = CCC_private_flat_hash_map_data_at( \
542 private_flat_hash_map_try_ins_ent.map, \
543 private_flat_hash_map_try_ins_ent.index), \
544 .status = CCC_ENTRY_VACANT, \
545 }; \
546 *((typeof(type_compound_literal) *) \
547 private_flat_hash_map_try_insert_res.type) \
548 = type_compound_literal; \
549 *((typeof(private_flat_hash_map_key) *) \
550 CCC_private_flat_hash_map_key_at( \
551 private_flat_hash_map_try_ins_ent.map, \
552 private_flat_hash_map_try_ins_ent.index)) \
553 = private_flat_hash_map_key; \
554 CCC_private_flat_hash_map_set_insert( \
555 &private_flat_hash_map_try_ins_ent); \
556 } \
557 } \
558 private_flat_hash_map_try_insert_res; \
559 }))
560
565#define CCC_private_flat_hash_map_insert_or_assign_with( \
566 flat_hash_map_pointer, key, type_compound_literal...) \
567 (__extension__({ \
568 struct CCC_Flat_hash_map *private_flat_hash_map_pointer \
569 = (flat_hash_map_pointer); \
570 struct CCC_Entry private_flat_hash_map_insert_or_assign_res \
571 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
572 if (private_flat_hash_map_pointer) \
573 { \
574 private_flat_hash_map_insert_or_assign_res.status \
575 = CCC_ENTRY_INSERT_ERROR; \
576 __auto_type private_flat_hash_map_key = key; \
577 struct CCC_Flat_hash_map_entry \
578 private_flat_hash_map_ins_or_assign_ent \
579 = CCC_private_flat_hash_map_entry( \
580 private_flat_hash_map_pointer, \
581 (void *)&private_flat_hash_map_key); \
582 if (!(private_flat_hash_map_ins_or_assign_ent.status \
583 & CCC_ENTRY_INSERT_ERROR)) \
584 { \
585 private_flat_hash_map_insert_or_assign_res \
586 = (struct CCC_Entry){ \
587 .type = CCC_private_flat_hash_map_data_at( \
588 private_flat_hash_map_ins_or_assign_ent.map, \
589 private_flat_hash_map_ins_or_assign_ent.index), \
590 .status \
591 = private_flat_hash_map_ins_or_assign_ent.status, \
592 }; \
593 *((typeof(type_compound_literal) *) \
594 private_flat_hash_map_insert_or_assign_res.type) \
595 = type_compound_literal; \
596 *((typeof(private_flat_hash_map_key) *) \
597 CCC_private_flat_hash_map_key_at( \
598 private_flat_hash_map_ins_or_assign_ent.map, \
599 private_flat_hash_map_ins_or_assign_ent.index)) \
600 = private_flat_hash_map_key; \
601 if (private_flat_hash_map_ins_or_assign_ent.status \
602 == CCC_ENTRY_VACANT) \
603 { \
604 CCC_private_flat_hash_map_set_insert( \
605 &private_flat_hash_map_ins_or_assign_ent); \
606 } \
607 } \
608 } \
609 private_flat_hash_map_insert_or_assign_res; \
610 }))
611
612/* NOLINTEND(readability-identifier-naming) */
613
614#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