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"
43
44/* NOLINTBEGIN(readability-identifier-naming) */
45
48#if defined(__x86_64) && defined(__SSE2__) \
49 && !defined(CCC_FLAT_HASH_MAP_PORTABLE)
53# define CCC_HAS_X86_SIMD
54#elif defined(__ARM_NEON__) && !defined(CCC_FLAT_HASH_MAP_PORTABLE)
58# define CCC_HAS_ARM_SIMD
59#endif /* defined(__x86_64)&&defined(__SSE2__)&&!defined(CCC_FLAT_HASH_MAP_PORTABLE) \
60 */
78struct CCC_Flat_hash_map_tag {
80 uint8_t v;
81};
82
88enum : typeof((struct CCC_Flat_hash_map_tag){}.v) {
89#ifdef CCC_HAS_X86_SIMD
91 CCC_FLAT_HASH_MAP_GROUP_COUNT = 16,
92#elifdef CCC_HAS_ARM_SIMD
94 CCC_FLAT_HASH_MAP_GROUP_COUNT = 8,
95#else /* PORTABLE FALLBACK */
97 CCC_FLAT_HASH_MAP_GROUP_COUNT = 8,
98#endif /* defined(CCC_HAS_X86_SIMD) */
99};
100
137struct CCC_Flat_hash_map {
139 void *data;
141 struct CCC_Flat_hash_map_tag *tag;
143 size_t count;
145 size_t remain;
147 size_t mask;
149 size_t sizeof_type;
151 size_t key_offset;
153 CCC_Hasher hasher;
154};
155
158struct CCC_Flat_hash_map_entry {
160 struct CCC_Flat_hash_map *map;
162 size_t index;
164 struct CCC_Flat_hash_map_tag tag;
166 CCC_Entry_status status;
167};
168
169/*====================== Private Interface =========================*/
170
172struct CCC_Flat_hash_map_entry CCC_private_flat_hash_map_entry(
173 struct CCC_Flat_hash_map *, void const *, CCC_Allocator const *
174);
176void *
177CCC_private_flat_hash_map_data_at(struct CCC_Flat_hash_map const *, size_t);
179void *
180CCC_private_flat_hash_map_key_at(struct CCC_Flat_hash_map const *, size_t);
182void
183CCC_private_flat_hash_map_set_insert(struct CCC_Flat_hash_map_entry const *);
184
185/*====================== Macro Implementations =========================*/
186
188#define CCC_private_flat_hash_map_compound_literal_array_capacity( \
189 private_type_compound_literal_array \
190) \
191 (sizeof(private_type_compound_literal_array) \
192 / sizeof(*(private_type_compound_literal_array)))
193
199#define CCC_private_flat_hash_map_storage_for( \
200 private_type_compound_literal_array, optional_storage_specifier... \
201) \
202 (optional_storage_specifier struct { \
203 static_assert( \
204 CCC_private_flat_hash_map_compound_literal_array_capacity( \
205 private_type_compound_literal_array \
206 ) >= CCC_FLAT_HASH_MAP_GROUP_COUNT, \
207 "fixed size map must have capacity >= " \
208 "CCC_FLAT_HASH_MAP_GROUP_COUNT " \
209 "(8 or 16 depending on platform)" \
210 ); \
211 static_assert( \
212 (CCC_private_flat_hash_map_compound_literal_array_capacity( \
213 private_type_compound_literal_array \
214 ) \
215 & (CCC_private_flat_hash_map_compound_literal_array_capacity( \
216 private_type_compound_literal_array \
217 ) \
218 - 1)) \
219 == 0, \
220 "fixed size map must be a power of 2 capacity (32, 64, " \
221 "128, 256, etc.)" \
222 ); \
223 typeof(*(private_type_compound_literal_array)) data \
224 [CCC_private_flat_hash_map_compound_literal_array_capacity( \
225 private_type_compound_literal_array \
226 ) \
227 + 1]; \
228 alignas(CCC_FLAT_HASH_MAP_GROUP_COUNT) struct CCC_Flat_hash_map_tag \
229 tag[CCC_private_flat_hash_map_compound_literal_array_capacity( \
230 private_type_compound_literal_array \
231 ) \
232 + CCC_FLAT_HASH_MAP_GROUP_COUNT]; \
233 }) { \
234 }
235
237#define CCC_private_flat_hash_map_default( \
238 private_type_name, private_key_field, private_hasher... \
239) \
240 (struct CCC_Flat_hash_map) { \
241 .sizeof_type = sizeof(private_type_name), \
242 .key_offset = offsetof(private_type_name, private_key_field), \
243 .hasher = private_hasher, \
244 }
245
263#define CCC_private_flat_hash_map_for( \
264 private_type_name, \
265 private_key_field, \
266 private_hasher, \
267 private_capacity, \
268 private_map_pointer \
269) \
270 (struct CCC_Flat_hash_map) { \
271 .data = (private_map_pointer), .tag = NULL, .count = 0, \
272 .remain = (((private_capacity) / (size_t)8) * (size_t)7), \
273 .mask \
274 = (((private_capacity) > (size_t)0) \
275 ? ((private_capacity) - (size_t)1) \
276 : (size_t)0), \
277 .sizeof_type = sizeof(private_type_name), \
278 .key_offset = offsetof(private_type_name, private_key_field), \
279 .hasher = (private_hasher), \
280 }
281
283#define CCC_private_flat_hash_map_from( \
284 private_key_field, \
285 private_hasher, \
286 private_allocator, \
287 private_optional_cap, \
288 private_array_compound_literal... \
289) \
290 (struct { struct CCC_Flat_hash_map private; }){(__extension__({ \
291 typeof(*private_array_compound_literal) \
292 *private_flat_hash_map_initializer_list \
293 = private_array_compound_literal; \
294 struct CCC_Flat_hash_map private_map \
295 = CCC_private_flat_hash_map_default( \
296 typeof(*private_flat_hash_map_initializer_list), \
297 private_key_field, \
298 private_hasher \
299 ); \
300 size_t const private_n \
301 = sizeof(private_array_compound_literal) \
302 / sizeof(*private_flat_hash_map_initializer_list); \
303 size_t const private_cap = private_optional_cap; \
304 CCC_Allocator const *const private_flat_hash_map_allocator \
305 = &(private_allocator); \
306 if (CCC_flat_hash_map_reserve( \
307 &private_map, \
308 (private_n > private_cap ? private_n : private_cap), \
309 private_flat_hash_map_allocator \
310 ) \
311 == CCC_RESULT_OK) { \
312 for (size_t i = 0; i < private_n; ++i) { \
313 struct CCC_Flat_hash_map_entry private_ent \
314 = CCC_private_flat_hash_map_entry( \
315 &private_map, \
316 ( \
317 void const * \
318 )&private_flat_hash_map_initializer_list[i] \
319 .private_key_field, \
320 private_flat_hash_map_allocator \
321 ); \
322 *((typeof(*private_flat_hash_map_initializer_list) *) \
323 CCC_private_flat_hash_map_data_at( \
324 private_ent.map, private_ent.index \
325 )) = private_flat_hash_map_initializer_list[i]; \
326 if (private_ent.status == CCC_ENTRY_VACANT) { \
327 CCC_private_flat_hash_map_set_insert(&private_ent); \
328 } \
329 } \
330 } \
331 private_map; \
332 }))}.private
333
335#define CCC_private_flat_hash_map_with_capacity( \
336 private_type_name, \
337 private_key_field, \
338 private_hasher, \
339 private_allocator, \
340 private_cap \
341) \
342 (struct { struct CCC_Flat_hash_map private; }){(__extension__({ \
343 struct CCC_Flat_hash_map private_map \
344 = CCC_private_flat_hash_map_default( \
345 private_type_name, private_key_field, private_hasher \
346 ); \
347 (void)CCC_flat_hash_map_reserve( \
348 &private_map, private_cap, &(private_allocator) \
349 ); \
350 private_map; \
351 }))}.private
352
354#define CCC_private_flat_hash_map_with_storage( \
355 private_key_field, \
356 private_hasher, \
357 private_compound_literal, \
358 private_optional_storage_specifier... \
359) \
360 (struct CCC_Flat_hash_map) { \
361 .data = &CCC_private_flat_hash_map_storage_for( \
362 private_compound_literal, private_optional_storage_specifier \
363 ), \
364 .tag = NULL, .count = 0, \
365 .remain \
366 = ((CCC_private_flat_hash_map_compound_literal_array_capacity( \
367 private_compound_literal \
368 ) \
369 / (size_t)8) \
370 * (size_t)7), \
371 .mask = CCC_private_flat_hash_map_compound_literal_array_capacity( \
372 private_compound_literal \
373 ) \
374 - (size_t)1, \
375 .sizeof_type = sizeof(*(private_compound_literal)), \
376 .key_offset = offsetof( \
377 typeof(*(private_compound_literal)), private_key_field \
378 ), \
379 .hasher = (private_hasher), \
380 }
381
382/*======================== Construct In Place =========================*/
383
387#define CCC_private_flat_hash_map_and_modify_with( \
388 flat_hash_map_entry_pointer, \
389 closure_parameter, \
390 closure_over_closure_parameter... \
391) \
392 (__extension__({ \
393 __auto_type private_flat_hash_map_mod_ent_pointer \
394 = (flat_hash_map_entry_pointer); \
395 struct CCC_Flat_hash_map_entry private_flat_hash_map_mod_with_ent \
396 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
397 if (private_flat_hash_map_mod_ent_pointer) { \
398 private_flat_hash_map_mod_with_ent \
399 = *private_flat_hash_map_mod_ent_pointer; \
400 if (private_flat_hash_map_mod_with_ent.status \
401 & CCC_ENTRY_OCCUPIED) { \
402 closure_parameter = CCC_private_flat_hash_map_data_at( \
403 private_flat_hash_map_mod_with_ent.map, \
404 private_flat_hash_map_mod_with_ent.index \
405 ); \
406 closure_over_closure_parameter \
407 } \
408 } \
409 private_flat_hash_map_mod_with_ent; \
410 }))
411
416#define CCC_private_flat_hash_map_or_insert_with( \
417 flat_hash_map_entry_pointer, type_compound_literal... \
418) \
419 (__extension__({ \
420 __auto_type private_flat_hash_map_or_ins_ent_pointer \
421 = (flat_hash_map_entry_pointer); \
422 typeof(type_compound_literal) *private_flat_hash_map_or_ins_res \
423 = NULL; \
424 if (private_flat_hash_map_or_ins_ent_pointer) { \
425 if (!(private_flat_hash_map_or_ins_ent_pointer->status \
426 & CCC_ENTRY_INSERT_ERROR)) { \
427 private_flat_hash_map_or_ins_res \
428 = CCC_private_flat_hash_map_data_at( \
429 private_flat_hash_map_or_ins_ent_pointer->map, \
430 private_flat_hash_map_or_ins_ent_pointer->index \
431 ); \
432 if (private_flat_hash_map_or_ins_ent_pointer->status \
433 == CCC_ENTRY_VACANT) { \
434 *private_flat_hash_map_or_ins_res = type_compound_literal; \
435 CCC_private_flat_hash_map_set_insert( \
436 private_flat_hash_map_or_ins_ent_pointer \
437 ); \
438 } \
439 } \
440 } \
441 private_flat_hash_map_or_ins_res; \
442 }))
443
447#define CCC_private_flat_hash_map_insert_entry_with( \
448 flat_hash_map_entry_pointer, type_compound_literal... \
449) \
450 (__extension__({ \
451 __auto_type private_flat_hash_map_ins_ent_pointer \
452 = (flat_hash_map_entry_pointer); \
453 typeof(type_compound_literal) *private_flat_hash_map_ins_ent_res \
454 = NULL; \
455 if (private_flat_hash_map_ins_ent_pointer) { \
456 if (!(private_flat_hash_map_ins_ent_pointer->status \
457 & CCC_ENTRY_INSERT_ERROR)) { \
458 private_flat_hash_map_ins_ent_res \
459 = CCC_private_flat_hash_map_data_at( \
460 private_flat_hash_map_ins_ent_pointer->map, \
461 private_flat_hash_map_ins_ent_pointer->index \
462 ); \
463 *private_flat_hash_map_ins_ent_res = type_compound_literal; \
464 if (private_flat_hash_map_ins_ent_pointer->status \
465 == CCC_ENTRY_VACANT) { \
466 CCC_private_flat_hash_map_set_insert( \
467 private_flat_hash_map_ins_ent_pointer \
468 ); \
469 } \
470 } \
471 } \
472 private_flat_hash_map_ins_ent_res; \
473 }))
474
478#define CCC_private_flat_hash_map_try_insert_with( \
479 flat_hash_map_pointer, \
480 key, \
481 private_allocator_pointer, \
482 type_compound_literal... \
483) \
484 (__extension__({ \
485 struct CCC_Flat_hash_map *private_flat_hash_map_pointer \
486 = (flat_hash_map_pointer); \
487 CCC_Entry private_flat_hash_map_try_insert_res \
488 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
489 if (private_flat_hash_map_pointer) { \
490 __auto_type private_flat_hash_map_key = key; \
491 struct CCC_Flat_hash_map_entry private_flat_hash_map_try_ins_ent \
492 = CCC_private_flat_hash_map_entry( \
493 private_flat_hash_map_pointer, \
494 (void *)&private_flat_hash_map_key, \
495 private_allocator_pointer \
496 ); \
497 if ((private_flat_hash_map_try_ins_ent.status \
498 & CCC_ENTRY_OCCUPIED) \
499 || (private_flat_hash_map_try_ins_ent.status \
500 & CCC_ENTRY_INSERT_ERROR)) { \
501 private_flat_hash_map_try_insert_res = (CCC_Entry){ \
502 .type = CCC_private_flat_hash_map_data_at( \
503 private_flat_hash_map_try_ins_ent.map, \
504 private_flat_hash_map_try_ins_ent.index \
505 ), \
506 .status = private_flat_hash_map_try_ins_ent.status, \
507 }; \
508 } else { \
509 private_flat_hash_map_try_insert_res = (CCC_Entry){ \
510 .type = CCC_private_flat_hash_map_data_at( \
511 private_flat_hash_map_try_ins_ent.map, \
512 private_flat_hash_map_try_ins_ent.index \
513 ), \
514 .status = CCC_ENTRY_VACANT, \
515 }; \
516 *((typeof(type_compound_literal) *) \
517 private_flat_hash_map_try_insert_res.type) \
518 = type_compound_literal; \
519 *((typeof(private_flat_hash_map_key) *) \
520 CCC_private_flat_hash_map_key_at( \
521 private_flat_hash_map_try_ins_ent.map, \
522 private_flat_hash_map_try_ins_ent.index \
523 )) = private_flat_hash_map_key; \
524 CCC_private_flat_hash_map_set_insert( \
525 &private_flat_hash_map_try_ins_ent \
526 ); \
527 } \
528 } \
529 private_flat_hash_map_try_insert_res; \
530 }))
531
536#define CCC_private_flat_hash_map_insert_or_assign_with( \
537 flat_hash_map_pointer, \
538 key, \
539 private_allocator_pointer, \
540 type_compound_literal... \
541) \
542 (__extension__({ \
543 struct CCC_Flat_hash_map *private_flat_hash_map_pointer \
544 = (flat_hash_map_pointer); \
545 CCC_Entry private_flat_hash_map_insert_or_assign_res \
546 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
547 if (private_flat_hash_map_pointer) { \
548 private_flat_hash_map_insert_or_assign_res.status \
549 = CCC_ENTRY_INSERT_ERROR; \
550 __auto_type private_flat_hash_map_key = key; \
551 struct CCC_Flat_hash_map_entry \
552 private_flat_hash_map_ins_or_assign_ent \
553 = CCC_private_flat_hash_map_entry( \
554 private_flat_hash_map_pointer, \
555 (void *)&private_flat_hash_map_key, \
556 private_allocator_pointer \
557 ); \
558 if (!(private_flat_hash_map_ins_or_assign_ent.status \
559 & CCC_ENTRY_INSERT_ERROR)) { \
560 private_flat_hash_map_insert_or_assign_res = (CCC_Entry){ \
561 .type = CCC_private_flat_hash_map_data_at( \
562 private_flat_hash_map_ins_or_assign_ent.map, \
563 private_flat_hash_map_ins_or_assign_ent.index \
564 ), \
565 .status = private_flat_hash_map_ins_or_assign_ent.status, \
566 }; \
567 *((typeof(type_compound_literal) *) \
568 private_flat_hash_map_insert_or_assign_res.type) \
569 = type_compound_literal; \
570 *((typeof(private_flat_hash_map_key) *) \
571 CCC_private_flat_hash_map_key_at( \
572 private_flat_hash_map_ins_or_assign_ent.map, \
573 private_flat_hash_map_ins_or_assign_ent.index \
574 )) = private_flat_hash_map_key; \
575 if (private_flat_hash_map_ins_or_assign_ent.status \
576 == CCC_ENTRY_VACANT) { \
577 CCC_private_flat_hash_map_set_insert( \
578 &private_flat_hash_map_ins_or_assign_ent \
579 ); \
580 } \
581 } \
582 } \
583 private_flat_hash_map_insert_or_assign_res; \
584 }))
585
586/* NOLINTEND(readability-identifier-naming) */
587
588#endif /* CCC_PRIVATE_FLAT_HASH_MAP_H */
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_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:376
CCC_Flat_hash_map_entry
Definition: private_flat_hash_map.h:158
CCC_Flat_hash_map_entry::index
size_t index
Definition: private_flat_hash_map.h:162
CCC_Flat_hash_map_entry::tag
struct CCC_Flat_hash_map_tag tag
Definition: private_flat_hash_map.h:164
CCC_Flat_hash_map_entry::status
CCC_Entry_status status
Definition: private_flat_hash_map.h:166
CCC_Flat_hash_map_entry::map
struct CCC_Flat_hash_map * map
Definition: private_flat_hash_map.h:160
CCC_Flat_hash_map_tag
Definition: private_flat_hash_map.h:78
CCC_Flat_hash_map_tag::v
uint8_t v
Definition: private_flat_hash_map.h:80
CCC_Flat_hash_map
Definition: private_flat_hash_map.h:137
CCC_Flat_hash_map::remain
size_t remain
Definition: private_flat_hash_map.h:145
CCC_Flat_hash_map::tag
struct CCC_Flat_hash_map_tag * tag
Definition: private_flat_hash_map.h:141
CCC_Flat_hash_map::sizeof_type
size_t sizeof_type
Definition: private_flat_hash_map.h:149
CCC_Flat_hash_map::key_offset
size_t key_offset
Definition: private_flat_hash_map.h:151
CCC_Flat_hash_map::mask
size_t mask
Definition: private_flat_hash_map.h:147
CCC_Flat_hash_map::data
void * data
Definition: private_flat_hash_map.h:139
CCC_Flat_hash_map::count
size_t count
Definition: private_flat_hash_map.h:143
CCC_Flat_hash_map::hasher
CCC_Hasher hasher
Definition: private_flat_hash_map.h:153
CCC_Hasher
The type passed by reference to a hash map that needs a hash function and key comparison function....
Definition: types.h:550
CCC_Entry_status
CCC_Entry_status
The status monitoring and entry state once it is obtained.
Definition: types.h:112