C Container Collection (CCC)
Loading...
Searching...
No Matches
private_array_tree_map.h
1
16#ifndef CCC_PRIVATE_ARRAY_TREE_MAP_H
17#define CCC_PRIVATE_ARRAY_TREE_MAP_H
18
20#include <limits.h>
21#include <stddef.h>
22#include <stdint.h>
25#include "../types.h"
26#include "private_types.h" /* NOLINT */
27
28/* NOLINTBEGIN(readability-identifier-naming) */
29
35struct CCC_Array_tree_map_node
36{
38 size_t branch[2];
39 union
40 {
42 size_t parent;
44 size_t next_free;
45 };
46};
47
136struct CCC_Array_tree_map
137{
139 void *data;
141 struct CCC_Array_tree_map_node *nodes;
143 unsigned *parity;
145 size_t root;
147 size_t free_list;
149 size_t capacity;
151 size_t count;
153 size_t sizeof_type;
155 size_t key_offset;
157 CCC_Key_comparator *compare;
159 CCC_Allocator *allocate;
161 void *context;
162};
163
165struct CCC_Array_tree_map_handle
166{
168 struct CCC_Array_tree_map *map;
170 size_t index;
172 CCC_Order last_order;
174 CCC_Entry_status status;
175};
176
178union CCC_Array_tree_map_handle_wrap
179{
181 struct CCC_Array_tree_map_handle private;
182};
183
184/*======================== Private Interface ==============================*/
185
187void *CCC_private_array_tree_map_data_at(struct CCC_Array_tree_map const *,
188 size_t);
190void *CCC_private_array_tree_map_key_at(struct CCC_Array_tree_map const *,
191 size_t);
193struct CCC_Array_tree_map_node *
194CCC_private_array_tree_map_node_at(struct CCC_Array_tree_map const *, size_t);
196struct CCC_Array_tree_map_handle
197CCC_private_array_tree_map_handle(struct CCC_Array_tree_map const *,
198 void const *);
200void CCC_private_array_tree_map_insert(struct CCC_Array_tree_map *, size_t,
201 CCC_Order, size_t);
203size_t CCC_private_array_tree_map_allocate_slot(struct CCC_Array_tree_map *);
204
205/*========================= Initialization =========================*/
206
210#define CCC_private_array_tree_map_blocks(private_cap) \
211 (((private_cap) \
212 + ((sizeof(*(struct CCC_Array_tree_map){}.parity) * CHAR_BIT) - 1)) \
213 / (sizeof(*(struct CCC_Array_tree_map){}.parity) * CHAR_BIT))
214
218#define CCC_private_array_tree_map_declare_fixed( \
219 private_fixed_map_type_name, private_key_val_type_name, private_capacity) \
220 static_assert((private_capacity) > 1, \
221 "fixed size map must have capacity greater than 1"); \
222 typedef struct \
223 { \
224 private_key_val_type_name data[(private_capacity)]; \
225 struct CCC_Array_tree_map_node nodes[(private_capacity)]; \
226 typeof(*(struct CCC_Array_tree_map){}.parity) \
227 parity[CCC_private_array_tree_map_blocks((private_capacity))]; \
228 }(private_fixed_map_type_name)
229
232#define CCC_private_array_tree_map_fixed_capacity(fixed_map_type_name) \
233 (sizeof((fixed_map_type_name){}.nodes) \
234 / sizeof(struct CCC_Array_tree_map_node))
235
241#define CCC_private_array_tree_map_initialize( \
242 private_type_name, private_key_field, private_key_compare, \
243 private_allocate, private_context_data, private_capacity, \
244 private_memory_pointer) \
245 { \
246 .data = (private_memory_pointer), \
247 .nodes = NULL, \
248 .parity = NULL, \
249 .capacity = (private_capacity), \
250 .count = 0, \
251 .root = 0, \
252 .free_list = 0, \
253 .sizeof_type = sizeof(private_type_name), \
254 .key_offset = offsetof(private_type_name, private_key_field), \
255 .compare = (private_key_compare), \
256 .allocate = (private_allocate), \
257 .context = (private_context_data), \
258 }
259
261#define CCC_private_array_tree_map_from( \
262 private_key_field, private_key_compare, private_allocate, \
263 private_context_data, private_optional_cap, \
264 private_array_compound_literal...) \
265 (__extension__({ \
266 typeof(*private_array_compound_literal) \
267 *private_array_tree_map_initializer_list \
268 = private_array_compound_literal; \
269 struct CCC_Array_tree_map private_array_tree_map \
270 = CCC_private_array_tree_map_initialize( \
271 typeof(*private_array_tree_map_initializer_list), \
272 private_key_field, private_key_compare, private_allocate, \
273 private_context_data, 0, NULL); \
274 size_t const private_array_tree_n \
275 = sizeof(private_array_compound_literal) \
276 / sizeof(*private_array_tree_map_initializer_list); \
277 size_t const private_cap = private_optional_cap; \
278 if (CCC_array_tree_map_reserve(&private_array_tree_map, \
279 (private_array_tree_n > private_cap \
280 ? private_array_tree_n \
281 : private_cap), \
282 private_allocate) \
283 == CCC_RESULT_OK) \
284 { \
285 for (size_t i = 0; i < private_array_tree_n; ++i) \
286 { \
287 struct CCC_Array_tree_map_handle private_array_tree_entry \
288 = CCC_private_array_tree_map_handle( \
289 &private_array_tree_map, \
290 (void const \
291 *)&private_array_tree_map_initializer_list[i] \
292 .private_key_field); \
293 CCC_Handle_index private_index \
294 = private_array_tree_entry.index; \
295 if (!(private_array_tree_entry.status & CCC_ENTRY_OCCUPIED)) \
296 { \
297 private_index = CCC_private_array_tree_map_allocate_slot( \
298 &private_array_tree_map); \
299 } \
300 *((typeof(*private_array_tree_map_initializer_list) *) \
301 CCC_private_array_tree_map_data_at( \
302 private_array_tree_entry.map, private_index)) \
303 = private_array_tree_map_initializer_list[i]; \
304 if (!(private_array_tree_entry.status & CCC_ENTRY_OCCUPIED)) \
305 { \
306 CCC_private_array_tree_map_insert( \
307 private_array_tree_entry.map, \
308 private_array_tree_entry.index, \
309 private_array_tree_entry.last_order, private_index); \
310 } \
311 } \
312 } \
313 private_array_tree_map; \
314 }))
315
316#define CCC_private_array_tree_map_with_capacity( \
317 private_type_name, private_key_field, private_key_compare, \
318 private_allocate, private_context_data, private_cap) \
319 (__extension__({ \
320 struct CCC_Array_tree_map private_array_tree_map \
321 = CCC_private_array_tree_map_initialize( \
322 private_type_name, private_key_field, private_key_compare, \
323 private_allocate, private_context_data, 0, NULL); \
324 (void)CCC_array_tree_map_reserve(&private_array_tree_map, private_cap, \
325 private_allocate); \
326 private_array_tree_map; \
327 }))
328
330#define CCC_private_array_tree_map_with_compound_literal( \
331 private_key_node_field, private_key_order_fn, private_compound_literal) \
332 { \
333 .data = &(private_compound_literal), \
334 .nodes = NULL, \
335 .parity = NULL, \
336 .capacity = CCC_private_array_tree_map_fixed_capacity( \
337 typeof(private_compound_literal)), \
338 .count = 0, \
339 .root = 0, \
340 .free_list = 0, \
341 .sizeof_type = sizeof(*(private_compound_literal.data)) /*NOLINT*/, \
342 .key_offset \
343 = offsetof(typeof(*(private_compound_literal.data)) /*NOLINT*/, \
344 private_key_node_field), \
345 .compare = (private_key_order_fn), \
346 .allocate = NULL, \
347 .context = NULL, \
348 }
349
351#define CCC_private_array_tree_map_with_context_compound_literal( \
352 private_key_node_field, private_key_order_fn, private_context, \
353 private_compound_literal) \
354 { \
355 .data = &(private_compound_literal), \
356 .nodes = NULL, \
357 .parity = NULL, \
358 .capacity = CCC_private_array_tree_map_fixed_capacity( \
359 typeof(private_compound_literal)), \
360 .count = 0, \
361 .root = 0, \
362 .free_list = 0, \
363 .sizeof_type = sizeof(*(private_compound_literal.data)) /*NOLINT*/, \
364 .key_offset \
365 = offsetof(typeof(*(private_compound_literal.data)) /*NOLINT*/, \
366 private_key_node_field), \
367 .compare = (private_key_order_fn), \
368 .allocate = NULL, \
369 .context = (private_context), \
370 }
371
373#define CCC_private_array_tree_map_with_allocator( \
374 private_type_name, private_key_field, private_key_compare, \
375 private_allocate) \
376 { \
377 .data = NULL, \
378 .nodes = NULL, \
379 .parity = NULL, \
380 .capacity = 0, \
381 .count = 0, \
382 .root = 0, \
383 .free_list = 0, \
384 .sizeof_type = sizeof(private_type_name), \
385 .key_offset = offsetof(private_type_name, private_key_field), \
386 .compare = (private_key_compare), \
387 .allocate = (private_allocate), \
388 .context = NULL, \
389 }
390
392#define CCC_private_array_tree_map_with_context_allocator( \
393 private_type_name, private_key_field, private_key_compare, \
394 private_allocate, private_context) \
395 { \
396 .data = NULL, \
397 .nodes = NULL, \
398 .parity = NULL, \
399 .capacity = 0, \
400 .count = 0, \
401 .root = 0, \
402 .free_list = 0, \
403 .sizeof_type = sizeof(private_type_name), \
404 .key_offset = offsetof(private_type_name, private_key_field), \
405 .compare = (private_key_compare), \
406 .allocate = (private_allocate), \
407 .context = (private_context), \
408 }
409
411#define CCC_private_array_tree_map_as(array_tree_map_pointer, type_name, \
412 handle...) \
413 ((type_name *)CCC_private_array_tree_map_data_at((array_tree_map_pointer), \
414 (handle)))
415
416/*================== Core Macro Implementations =====================*/
417
419#define CCC_private_array_tree_map_and_modify_with( \
420 array_tree_map_array_pointer, type_name, closure_over_T...) \
421 (__extension__({ \
422 __auto_type private_array_tree_map_hndl_pointer \
423 = (array_tree_map_array_pointer); \
424 struct CCC_Array_tree_map_handle private_array_tree_map_mod_hndl \
425 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
426 if (private_array_tree_map_hndl_pointer) \
427 { \
428 private_array_tree_map_mod_hndl \
429 = private_array_tree_map_hndl_pointer->private; \
430 if (private_array_tree_map_mod_hndl.status & CCC_ENTRY_OCCUPIED) \
431 { \
432 type_name *const T = CCC_private_array_tree_map_data_at( \
433 private_array_tree_map_mod_hndl.map, \
434 private_array_tree_map_mod_hndl.index); \
435 if (T) \
436 { \
437 closure_over_T \
438 } \
439 } \
440 } \
441 private_array_tree_map_mod_hndl; \
442 }))
443
445#define CCC_private_array_tree_map_or_insert_with( \
446 array_tree_map_array_pointer, type_compound_literal...) \
447 (__extension__({ \
448 __auto_type private_or_ins_array_pointer \
449 = (array_tree_map_array_pointer); \
450 CCC_Handle_index private_array_tree_map_or_ins_ret = 0; \
451 if (private_or_ins_array_pointer) \
452 { \
453 if (private_or_ins_array_pointer->private.status \
454 == CCC_ENTRY_OCCUPIED) \
455 { \
456 private_array_tree_map_or_ins_ret \
457 = private_or_ins_array_pointer->private.index; \
458 } \
459 else \
460 { \
461 private_array_tree_map_or_ins_ret \
462 = CCC_private_array_tree_map_allocate_slot( \
463 private_or_ins_array_pointer->private.map); \
464 if (private_array_tree_map_or_ins_ret) \
465 { \
466 *((typeof(type_compound_literal) *) \
467 CCC_private_array_tree_map_data_at( \
468 private_or_ins_array_pointer->private.map, \
469 private_array_tree_map_or_ins_ret)) \
470 = type_compound_literal; \
471 CCC_private_array_tree_map_insert( \
472 private_or_ins_array_pointer->private.map, \
473 private_or_ins_array_pointer->private.index, \
474 private_or_ins_array_pointer->private.last_order, \
475 private_array_tree_map_or_ins_ret); \
476 } \
477 } \
478 } \
479 private_array_tree_map_or_ins_ret; \
480 }))
481
483#define CCC_private_array_tree_map_insert_array_with( \
484 array_tree_map_array_pointer, type_compound_literal...) \
485 (__extension__({ \
486 __auto_type private_ins_array_pointer \
487 = (array_tree_map_array_pointer); \
488 CCC_Handle_index private_array_tree_map_ins_hndl_ret = 0; \
489 if (private_ins_array_pointer) \
490 { \
491 if (!(private_ins_array_pointer->private.status \
492 & CCC_ENTRY_OCCUPIED)) \
493 { \
494 private_array_tree_map_ins_hndl_ret \
495 = CCC_private_array_tree_map_allocate_slot( \
496 private_ins_array_pointer->private.map); \
497 if (private_array_tree_map_ins_hndl_ret) \
498 { \
499 *((typeof(type_compound_literal) *) \
500 CCC_private_array_tree_map_data_at( \
501 private_ins_array_pointer->private.map, \
502 private_array_tree_map_ins_hndl_ret)) \
503 = type_compound_literal; \
504 CCC_private_array_tree_map_insert( \
505 private_ins_array_pointer->private.map, \
506 private_ins_array_pointer->private.index, \
507 private_ins_array_pointer->private.last_order, \
508 private_array_tree_map_ins_hndl_ret); \
509 } \
510 } \
511 else if (private_ins_array_pointer->private.status \
512 == CCC_ENTRY_OCCUPIED) \
513 { \
514 private_array_tree_map_ins_hndl_ret \
515 = private_ins_array_pointer->private.index; \
516 *((typeof(type_compound_literal) *) \
517 CCC_private_array_tree_map_data_at( \
518 private_ins_array_pointer->private.map, \
519 private_array_tree_map_ins_hndl_ret)) \
520 = type_compound_literal; \
521 } \
522 } \
523 private_array_tree_map_ins_hndl_ret; \
524 }))
525
527#define CCC_private_array_tree_map_try_insert_with( \
528 array_tree_map_pointer, key, type_compound_literal...) \
529 (__extension__({ \
530 __auto_type private_try_ins_map_pointer = (array_tree_map_pointer); \
531 struct CCC_Handle private_array_tree_map_try_ins_hndl_ret \
532 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
533 if (private_try_ins_map_pointer) \
534 { \
535 __auto_type private_array_tree_map_key = (key); \
536 struct CCC_Array_tree_map_handle \
537 private_array_tree_map_try_ins_hndl \
538 = CCC_private_array_tree_map_handle( \
539 private_try_ins_map_pointer, \
540 (void *)&private_array_tree_map_key); \
541 if (!(private_array_tree_map_try_ins_hndl.status \
542 & CCC_ENTRY_OCCUPIED)) \
543 { \
544 private_array_tree_map_try_ins_hndl_ret = (struct CCC_Handle){ \
545 .index = CCC_private_array_tree_map_allocate_slot( \
546 private_array_tree_map_try_ins_hndl.map), \
547 .status = CCC_ENTRY_INSERT_ERROR, \
548 }; \
549 if (private_array_tree_map_try_ins_hndl_ret.index) \
550 { \
551 *((typeof(type_compound_literal) *) \
552 CCC_private_array_tree_map_data_at( \
553 private_try_ins_map_pointer, \
554 private_array_tree_map_try_ins_hndl_ret.index)) \
555 = type_compound_literal; \
556 *((typeof(private_array_tree_map_key) *) \
557 CCC_private_array_tree_map_key_at( \
558 private_try_ins_map_pointer, \
559 private_array_tree_map_try_ins_hndl_ret.index)) \
560 = private_array_tree_map_key; \
561 CCC_private_array_tree_map_insert( \
562 private_array_tree_map_try_ins_hndl.map, \
563 private_array_tree_map_try_ins_hndl.index, \
564 private_array_tree_map_try_ins_hndl.last_order, \
565 private_array_tree_map_try_ins_hndl_ret.index); \
566 private_array_tree_map_try_ins_hndl_ret.status \
567 = CCC_ENTRY_VACANT; \
568 } \
569 } \
570 else if (private_array_tree_map_try_ins_hndl.status \
571 == CCC_ENTRY_OCCUPIED) \
572 { \
573 private_array_tree_map_try_ins_hndl_ret = (struct CCC_Handle){ \
574 .index = private_array_tree_map_try_ins_hndl.index, \
575 .status = private_array_tree_map_try_ins_hndl.status, \
576 }; \
577 } \
578 } \
579 private_array_tree_map_try_ins_hndl_ret; \
580 }))
581
583#define CCC_private_array_tree_map_insert_or_assign_with( \
584 array_tree_map_pointer, key, type_compound_literal...) \
585 (__extension__({ \
586 __auto_type private_ins_or_assign_map_pointer \
587 = (array_tree_map_pointer); \
588 struct CCC_Handle private_array_tree_map_ins_or_assign_hndl_ret \
589 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
590 if (private_ins_or_assign_map_pointer) \
591 { \
592 __auto_type private_array_tree_map_key = (key); \
593 struct CCC_Array_tree_map_handle \
594 private_array_tree_map_ins_or_assign_hndl \
595 = CCC_private_array_tree_map_handle( \
596 private_ins_or_assign_map_pointer, \
597 (void *)&private_array_tree_map_key); \
598 if (!(private_array_tree_map_ins_or_assign_hndl.status \
599 & CCC_ENTRY_OCCUPIED)) \
600 { \
601 private_array_tree_map_ins_or_assign_hndl_ret \
602 = (struct CCC_Handle){ \
603 .index = CCC_private_array_tree_map_allocate_slot( \
604 private_array_tree_map_ins_or_assign_hndl.map), \
605 .status = CCC_ENTRY_INSERT_ERROR, \
606 }; \
607 if (private_array_tree_map_ins_or_assign_hndl_ret.index) \
608 { \
609 *((typeof(type_compound_literal) *) \
610 CCC_private_array_tree_map_data_at( \
611 private_array_tree_map_ins_or_assign_hndl.map, \
612 private_array_tree_map_ins_or_assign_hndl_ret \
613 .index)) \
614 = type_compound_literal; \
615 *((typeof(private_array_tree_map_key) *) \
616 CCC_private_array_tree_map_key_at( \
617 private_array_tree_map_ins_or_assign_hndl.map, \
618 private_array_tree_map_ins_or_assign_hndl_ret \
619 .index)) \
620 = private_array_tree_map_key; \
621 CCC_private_array_tree_map_insert( \
622 private_array_tree_map_ins_or_assign_hndl.map, \
623 private_array_tree_map_ins_or_assign_hndl.index, \
624 private_array_tree_map_ins_or_assign_hndl.last_order, \
625 private_array_tree_map_ins_or_assign_hndl_ret.index); \
626 private_array_tree_map_ins_or_assign_hndl_ret.status \
627 = CCC_ENTRY_VACANT; \
628 } \
629 } \
630 else if (private_array_tree_map_ins_or_assign_hndl.status \
631 == CCC_ENTRY_OCCUPIED) \
632 { \
633 *((typeof(type_compound_literal) *) \
634 CCC_private_array_tree_map_data_at( \
635 private_array_tree_map_ins_or_assign_hndl.map, \
636 private_array_tree_map_ins_or_assign_hndl.index)) \
637 = type_compound_literal; \
638 private_array_tree_map_ins_or_assign_hndl_ret \
639 = (struct CCC_Handle){ \
640 .index \
641 = private_array_tree_map_ins_or_assign_hndl.index, \
642 .status \
643 = private_array_tree_map_ins_or_assign_hndl.status, \
644 }; \
645 *((typeof(private_array_tree_map_key) *) \
646 CCC_private_array_tree_map_key_at( \
647 private_array_tree_map_ins_or_assign_hndl.map, \
648 private_array_tree_map_ins_or_assign_hndl.index)) \
649 = private_array_tree_map_key; \
650 } \
651 } \
652 private_array_tree_map_ins_or_assign_hndl_ret; \
653 }))
654
655/* NOLINTEND(readability-identifier-naming) */
656
657#endif /* CCC_PRIVATE_ARRAY_TREE_MAP_H */
CCC_Array_tree_map_handle
Definition: private_array_tree_map.h:166
CCC_Array_tree_map_handle::last_order
CCC_Order last_order
Definition: private_array_tree_map.h:172
CCC_Array_tree_map_handle::index
size_t index
Definition: private_array_tree_map.h:170
CCC_Array_tree_map_handle::map
struct CCC_Array_tree_map * map
Definition: private_array_tree_map.h:168
CCC_Array_tree_map_handle::status
CCC_Entry_status status
Definition: private_array_tree_map.h:174
CCC_Array_tree_map_node
Definition: private_array_tree_map.h:36
CCC_Array_tree_map_node::parent
size_t parent
Definition: private_array_tree_map.h:42
CCC_Array_tree_map_node::branch
size_t branch[2]
Definition: private_array_tree_map.h:38
CCC_Array_tree_map_node::next_free
size_t next_free
Definition: private_array_tree_map.h:44
CCC_Array_tree_map
Definition: private_array_tree_map.h:137
CCC_Array_tree_map::data
void * data
Definition: private_array_tree_map.h:139
CCC_Array_tree_map::parity
unsigned * parity
Definition: private_array_tree_map.h:143
CCC_Array_tree_map::sizeof_type
size_t sizeof_type
Definition: private_array_tree_map.h:153
CCC_Array_tree_map::count
size_t count
Definition: private_array_tree_map.h:151
CCC_Array_tree_map::capacity
size_t capacity
Definition: private_array_tree_map.h:149
CCC_Array_tree_map::root
size_t root
Definition: private_array_tree_map.h:145
CCC_Array_tree_map::free_list
size_t free_list
Definition: private_array_tree_map.h:147
CCC_Array_tree_map::context
void * context
Definition: private_array_tree_map.h:161
CCC_Array_tree_map::nodes
struct CCC_Array_tree_map_node * nodes
Definition: private_array_tree_map.h:141
CCC_Array_tree_map::allocate
CCC_Allocator * allocate
Definition: private_array_tree_map.h:159
CCC_Array_tree_map::key_offset
size_t key_offset
Definition: private_array_tree_map.h:155
CCC_Array_tree_map::compare
CCC_Key_comparator * compare
Definition: private_array_tree_map.h:157
CCC_Order
CCC_Order
A three-way comparison for comparison functions.
Definition: types.h:171
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_Array_tree_map_handle_wrap
Definition: private_array_tree_map.h:179
CCC_Array_tree_map_handle_wrap::private
struct CCC_Array_tree_map_handle private
Definition: private_array_tree_map.h:181