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