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
131struct CCC_Array_tree_map
132{
134 void *data;
136 struct CCC_Array_tree_map_node *nodes;
138 unsigned *parity;
140 size_t root;
142 size_t free_list;
144 size_t capacity;
146 size_t count;
148 size_t sizeof_type;
150 size_t key_offset;
152 CCC_Key_comparator *compare;
154 CCC_Allocator *allocate;
156 void *context;
157};
158
160struct CCC_Array_tree_map_handle
161{
163 struct CCC_Array_tree_map *map;
165 size_t index;
167 CCC_Order last_order;
169 CCC_Entry_status status;
170};
171
173union CCC_Array_tree_map_handle_wrap
174{
176 struct CCC_Array_tree_map_handle private;
177};
178
179/*======================== Private Interface ==============================*/
180
182void *CCC_private_array_tree_map_data_at(struct CCC_Array_tree_map const *,
183 size_t);
185void *CCC_private_array_tree_map_key_at(struct CCC_Array_tree_map const *,
186 size_t);
188struct CCC_Array_tree_map_node *
189CCC_private_array_tree_map_node_at(struct CCC_Array_tree_map const *, size_t);
191struct CCC_Array_tree_map_handle
192CCC_private_array_tree_map_handle(struct CCC_Array_tree_map const *,
193 void const *);
195void CCC_private_array_tree_map_insert(struct CCC_Array_tree_map *, size_t,
196 CCC_Order, size_t);
198size_t CCC_private_array_tree_map_allocate_slot(struct CCC_Array_tree_map *);
199
200/*========================= Initialization =========================*/
201
205#define CCC_private_array_tree_map_blocks(private_cap) \
206 (((private_cap) \
207 + ((sizeof(*(struct CCC_Array_tree_map){}.parity) * CHAR_BIT) - 1)) \
208 / (sizeof(*(struct CCC_Array_tree_map){}.parity) * CHAR_BIT))
209
213#define CCC_private_array_tree_map_declare_fixed( \
214 private_fixed_map_type_name, private_key_val_type_name, private_capacity) \
215 static_assert((private_capacity) > 1, \
216 "fixed size map must have capacity greater than 1"); \
217 typedef struct \
218 { \
219 private_key_val_type_name data[(private_capacity)]; \
220 struct CCC_Array_tree_map_node nodes[(private_capacity)]; \
221 typeof(*(struct CCC_Array_tree_map){}.parity) \
222 parity[CCC_private_array_tree_map_blocks((private_capacity))]; \
223 }(private_fixed_map_type_name)
224
227#define CCC_private_array_tree_map_fixed_capacity(fixed_map_type_name) \
228 (sizeof((fixed_map_type_name){}.nodes) \
229 / sizeof(struct CCC_Array_tree_map_node))
230
236#define CCC_private_array_tree_map_initialize( \
237 private_memory_pointer, private_type_name, private_key_field, \
238 private_key_compare, private_allocate, private_context_data, \
239 private_capacity) \
240 { \
241 .data = (private_memory_pointer), \
242 .nodes = NULL, \
243 .parity = NULL, \
244 .capacity = (private_capacity), \
245 .count = 0, \
246 .root = 0, \
247 .free_list = 0, \
248 .sizeof_type = sizeof(private_type_name), \
249 .key_offset = offsetof(private_type_name, private_key_field), \
250 .compare = (private_key_compare), \
251 .allocate = (private_allocate), \
252 .context = (private_context_data), \
253 }
254
256#define CCC_private_array_tree_map_from( \
257 private_key_field, private_key_compare, private_allocate, \
258 private_context_data, private_optional_cap, \
259 private_array_compound_literal...) \
260 (__extension__({ \
261 typeof(*private_array_compound_literal) \
262 *private_array_tree_map_initializer_list \
263 = private_array_compound_literal; \
264 struct CCC_Array_tree_map private_array_tree_map \
265 = CCC_private_array_tree_map_initialize( \
266 NULL, typeof(*private_array_tree_map_initializer_list), \
267 private_key_field, private_key_compare, private_allocate, \
268 private_context_data, 0); \
269 size_t const private_array_tree_n \
270 = sizeof(private_array_compound_literal) \
271 / sizeof(*private_array_tree_map_initializer_list); \
272 size_t const private_cap = private_optional_cap; \
273 if (CCC_array_tree_map_reserve(&private_array_tree_map, \
274 (private_array_tree_n > private_cap \
275 ? private_array_tree_n \
276 : private_cap), \
277 private_allocate) \
278 == CCC_RESULT_OK) \
279 { \
280 for (size_t i = 0; i < private_array_tree_n; ++i) \
281 { \
282 struct CCC_Array_tree_map_handle private_array_tree_entry \
283 = CCC_private_array_tree_map_handle( \
284 &private_array_tree_map, \
285 (void const \
286 *)&private_array_tree_map_initializer_list[i] \
287 .private_key_field); \
288 CCC_Handle_index private_index \
289 = private_array_tree_entry.index; \
290 if (!(private_array_tree_entry.status & CCC_ENTRY_OCCUPIED)) \
291 { \
292 private_index = CCC_private_array_tree_map_allocate_slot( \
293 &private_array_tree_map); \
294 } \
295 *((typeof(*private_array_tree_map_initializer_list) *) \
296 CCC_private_array_tree_map_data_at( \
297 private_array_tree_entry.map, private_index)) \
298 = private_array_tree_map_initializer_list[i]; \
299 if (!(private_array_tree_entry.status & CCC_ENTRY_OCCUPIED)) \
300 { \
301 CCC_private_array_tree_map_insert( \
302 private_array_tree_entry.map, \
303 private_array_tree_entry.index, \
304 private_array_tree_entry.last_order, private_index); \
305 } \
306 } \
307 } \
308 private_array_tree_map; \
309 }))
310
311#define CCC_private_array_tree_map_with_capacity( \
312 private_type_name, private_key_field, private_key_compare, \
313 private_allocate, private_context_data, private_cap) \
314 (__extension__({ \
315 struct CCC_Array_tree_map private_array_tree_map \
316 = CCC_private_array_tree_map_initialize( \
317 NULL, private_type_name, private_key_field, \
318 private_key_compare, private_allocate, private_context_data, \
319 0); \
320 (void)CCC_array_tree_map_reserve(&private_array_tree_map, private_cap, \
321 private_allocate); \
322 private_array_tree_map; \
323 }))
324
326#define CCC_private_array_tree_map_with_compound_literal( \
327 private_key_node_field, private_key_order_fn, private_compound_literal) \
328 { \
329 .data = &(private_compound_literal), \
330 .nodes = NULL, \
331 .parity = NULL, \
332 .capacity = CCC_private_array_tree_map_fixed_capacity( \
333 typeof(private_compound_literal)), \
334 .count = 0, \
335 .root = 0, \
336 .free_list = 0, \
337 .sizeof_type = sizeof(*(private_compound_literal.data)) /*NOLINT*/, \
338 .key_offset \
339 = offsetof(typeof(*(private_compound_literal.data)) /*NOLINT*/, \
340 private_key_node_field), \
341 .compare = (private_key_order_fn), \
342 .allocate = NULL, \
343 .context = NULL, \
344 }
345
347#define CCC_private_array_tree_map_with_context_compound_literal( \
348 private_key_node_field, private_key_order_fn, private_context, \
349 private_compound_literal) \
350 { \
351 .data = &(private_compound_literal), \
352 .nodes = NULL, \
353 .parity = NULL, \
354 .capacity = CCC_private_array_tree_map_fixed_capacity( \
355 typeof(private_compound_literal)), \
356 .count = 0, \
357 .root = 0, \
358 .free_list = 0, \
359 .sizeof_type = sizeof(*(private_compound_literal.data)) /*NOLINT*/, \
360 .key_offset \
361 = offsetof(typeof(*(private_compound_literal.data)) /*NOLINT*/, \
362 private_key_node_field), \
363 .compare = (private_key_order_fn), \
364 .allocate = NULL, \
365 .context = (private_context), \
366 }
367
369#define CCC_private_array_tree_map_as(array_tree_map_pointer, type_name, \
370 handle...) \
371 ((type_name *)CCC_private_array_tree_map_data_at((array_tree_map_pointer), \
372 (handle)))
373
374/*================== Core Macro Implementations =====================*/
375
377#define CCC_private_array_tree_map_and_modify_with( \
378 array_tree_map_array_pointer, type_name, closure_over_T...) \
379 (__extension__({ \
380 __auto_type private_array_tree_map_hndl_pointer \
381 = (array_tree_map_array_pointer); \
382 struct CCC_Array_tree_map_handle private_array_tree_map_mod_hndl \
383 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
384 if (private_array_tree_map_hndl_pointer) \
385 { \
386 private_array_tree_map_mod_hndl \
387 = private_array_tree_map_hndl_pointer->private; \
388 if (private_array_tree_map_mod_hndl.status & CCC_ENTRY_OCCUPIED) \
389 { \
390 type_name *const T = CCC_private_array_tree_map_data_at( \
391 private_array_tree_map_mod_hndl.map, \
392 private_array_tree_map_mod_hndl.index); \
393 if (T) \
394 { \
395 closure_over_T \
396 } \
397 } \
398 } \
399 private_array_tree_map_mod_hndl; \
400 }))
401
403#define CCC_private_array_tree_map_or_insert_with( \
404 array_tree_map_array_pointer, type_compound_literal...) \
405 (__extension__({ \
406 __auto_type private_or_ins_array_pointer \
407 = (array_tree_map_array_pointer); \
408 CCC_Handle_index private_array_tree_map_or_ins_ret = 0; \
409 if (private_or_ins_array_pointer) \
410 { \
411 if (private_or_ins_array_pointer->private.status \
412 == CCC_ENTRY_OCCUPIED) \
413 { \
414 private_array_tree_map_or_ins_ret \
415 = private_or_ins_array_pointer->private.index; \
416 } \
417 else \
418 { \
419 private_array_tree_map_or_ins_ret \
420 = CCC_private_array_tree_map_allocate_slot( \
421 private_or_ins_array_pointer->private.map); \
422 if (private_array_tree_map_or_ins_ret) \
423 { \
424 *((typeof(type_compound_literal) *) \
425 CCC_private_array_tree_map_data_at( \
426 private_or_ins_array_pointer->private.map, \
427 private_array_tree_map_or_ins_ret)) \
428 = type_compound_literal; \
429 CCC_private_array_tree_map_insert( \
430 private_or_ins_array_pointer->private.map, \
431 private_or_ins_array_pointer->private.index, \
432 private_or_ins_array_pointer->private.last_order, \
433 private_array_tree_map_or_ins_ret); \
434 } \
435 } \
436 } \
437 private_array_tree_map_or_ins_ret; \
438 }))
439
441#define CCC_private_array_tree_map_insert_array_with( \
442 array_tree_map_array_pointer, type_compound_literal...) \
443 (__extension__({ \
444 __auto_type private_ins_array_pointer \
445 = (array_tree_map_array_pointer); \
446 CCC_Handle_index private_array_tree_map_ins_hndl_ret = 0; \
447 if (private_ins_array_pointer) \
448 { \
449 if (!(private_ins_array_pointer->private.status \
450 & CCC_ENTRY_OCCUPIED)) \
451 { \
452 private_array_tree_map_ins_hndl_ret \
453 = CCC_private_array_tree_map_allocate_slot( \
454 private_ins_array_pointer->private.map); \
455 if (private_array_tree_map_ins_hndl_ret) \
456 { \
457 *((typeof(type_compound_literal) *) \
458 CCC_private_array_tree_map_data_at( \
459 private_ins_array_pointer->private.map, \
460 private_array_tree_map_ins_hndl_ret)) \
461 = type_compound_literal; \
462 CCC_private_array_tree_map_insert( \
463 private_ins_array_pointer->private.map, \
464 private_ins_array_pointer->private.index, \
465 private_ins_array_pointer->private.last_order, \
466 private_array_tree_map_ins_hndl_ret); \
467 } \
468 } \
469 else if (private_ins_array_pointer->private.status \
470 == CCC_ENTRY_OCCUPIED) \
471 { \
472 private_array_tree_map_ins_hndl_ret \
473 = private_ins_array_pointer->private.index; \
474 *((typeof(type_compound_literal) *) \
475 CCC_private_array_tree_map_data_at( \
476 private_ins_array_pointer->private.map, \
477 private_array_tree_map_ins_hndl_ret)) \
478 = type_compound_literal; \
479 } \
480 } \
481 private_array_tree_map_ins_hndl_ret; \
482 }))
483
485#define CCC_private_array_tree_map_try_insert_with( \
486 array_tree_map_pointer, key, type_compound_literal...) \
487 (__extension__({ \
488 __auto_type private_try_ins_map_pointer = (array_tree_map_pointer); \
489 struct CCC_Handle private_array_tree_map_try_ins_hndl_ret \
490 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
491 if (private_try_ins_map_pointer) \
492 { \
493 __auto_type private_array_tree_map_key = (key); \
494 struct CCC_Array_tree_map_handle \
495 private_array_tree_map_try_ins_hndl \
496 = CCC_private_array_tree_map_handle( \
497 private_try_ins_map_pointer, \
498 (void *)&private_array_tree_map_key); \
499 if (!(private_array_tree_map_try_ins_hndl.status \
500 & CCC_ENTRY_OCCUPIED)) \
501 { \
502 private_array_tree_map_try_ins_hndl_ret = (struct CCC_Handle){ \
503 .index = CCC_private_array_tree_map_allocate_slot( \
504 private_array_tree_map_try_ins_hndl.map), \
505 .status = CCC_ENTRY_INSERT_ERROR, \
506 }; \
507 if (private_array_tree_map_try_ins_hndl_ret.index) \
508 { \
509 *((typeof(type_compound_literal) *) \
510 CCC_private_array_tree_map_data_at( \
511 private_try_ins_map_pointer, \
512 private_array_tree_map_try_ins_hndl_ret.index)) \
513 = type_compound_literal; \
514 *((typeof(private_array_tree_map_key) *) \
515 CCC_private_array_tree_map_key_at( \
516 private_try_ins_map_pointer, \
517 private_array_tree_map_try_ins_hndl_ret.index)) \
518 = private_array_tree_map_key; \
519 CCC_private_array_tree_map_insert( \
520 private_array_tree_map_try_ins_hndl.map, \
521 private_array_tree_map_try_ins_hndl.index, \
522 private_array_tree_map_try_ins_hndl.last_order, \
523 private_array_tree_map_try_ins_hndl_ret.index); \
524 private_array_tree_map_try_ins_hndl_ret.status \
525 = CCC_ENTRY_VACANT; \
526 } \
527 } \
528 else if (private_array_tree_map_try_ins_hndl.status \
529 == CCC_ENTRY_OCCUPIED) \
530 { \
531 private_array_tree_map_try_ins_hndl_ret = (struct CCC_Handle){ \
532 .index = private_array_tree_map_try_ins_hndl.index, \
533 .status = private_array_tree_map_try_ins_hndl.status, \
534 }; \
535 } \
536 } \
537 private_array_tree_map_try_ins_hndl_ret; \
538 }))
539
541#define CCC_private_array_tree_map_insert_or_assign_with( \
542 array_tree_map_pointer, key, type_compound_literal...) \
543 (__extension__({ \
544 __auto_type private_ins_or_assign_map_pointer \
545 = (array_tree_map_pointer); \
546 struct CCC_Handle private_array_tree_map_ins_or_assign_hndl_ret \
547 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
548 if (private_ins_or_assign_map_pointer) \
549 { \
550 __auto_type private_array_tree_map_key = (key); \
551 struct CCC_Array_tree_map_handle \
552 private_array_tree_map_ins_or_assign_hndl \
553 = CCC_private_array_tree_map_handle( \
554 private_ins_or_assign_map_pointer, \
555 (void *)&private_array_tree_map_key); \
556 if (!(private_array_tree_map_ins_or_assign_hndl.status \
557 & CCC_ENTRY_OCCUPIED)) \
558 { \
559 private_array_tree_map_ins_or_assign_hndl_ret \
560 = (struct CCC_Handle){ \
561 .index = CCC_private_array_tree_map_allocate_slot( \
562 private_array_tree_map_ins_or_assign_hndl.map), \
563 .status = CCC_ENTRY_INSERT_ERROR, \
564 }; \
565 if (private_array_tree_map_ins_or_assign_hndl_ret.index) \
566 { \
567 *((typeof(type_compound_literal) *) \
568 CCC_private_array_tree_map_data_at( \
569 private_array_tree_map_ins_or_assign_hndl.map, \
570 private_array_tree_map_ins_or_assign_hndl_ret \
571 .index)) \
572 = type_compound_literal; \
573 *((typeof(private_array_tree_map_key) *) \
574 CCC_private_array_tree_map_key_at( \
575 private_array_tree_map_ins_or_assign_hndl.map, \
576 private_array_tree_map_ins_or_assign_hndl_ret \
577 .index)) \
578 = private_array_tree_map_key; \
579 CCC_private_array_tree_map_insert( \
580 private_array_tree_map_ins_or_assign_hndl.map, \
581 private_array_tree_map_ins_or_assign_hndl.index, \
582 private_array_tree_map_ins_or_assign_hndl.last_order, \
583 private_array_tree_map_ins_or_assign_hndl_ret.index); \
584 private_array_tree_map_ins_or_assign_hndl_ret.status \
585 = CCC_ENTRY_VACANT; \
586 } \
587 } \
588 else if (private_array_tree_map_ins_or_assign_hndl.status \
589 == CCC_ENTRY_OCCUPIED) \
590 { \
591 *((typeof(type_compound_literal) *) \
592 CCC_private_array_tree_map_data_at( \
593 private_array_tree_map_ins_or_assign_hndl.map, \
594 private_array_tree_map_ins_or_assign_hndl.index)) \
595 = type_compound_literal; \
596 private_array_tree_map_ins_or_assign_hndl_ret \
597 = (struct CCC_Handle){ \
598 .index \
599 = private_array_tree_map_ins_or_assign_hndl.index, \
600 .status \
601 = private_array_tree_map_ins_or_assign_hndl.status, \
602 }; \
603 *((typeof(private_array_tree_map_key) *) \
604 CCC_private_array_tree_map_key_at( \
605 private_array_tree_map_ins_or_assign_hndl.map, \
606 private_array_tree_map_ins_or_assign_hndl.index)) \
607 = private_array_tree_map_key; \
608 } \
609 } \
610 private_array_tree_map_ins_or_assign_hndl_ret; \
611 }))
612
613/* NOLINTEND(readability-identifier-naming) */
614
615#endif /* CCC_PRIVATE_ARRAY_TREE_MAP_H */
CCC_Array_tree_map_handle
Definition: private_array_tree_map.h:161
CCC_Array_tree_map_handle::last_order
CCC_Order last_order
Definition: private_array_tree_map.h:167
CCC_Array_tree_map_handle::index
size_t index
Definition: private_array_tree_map.h:165
CCC_Array_tree_map_handle::map
struct CCC_Array_tree_map * map
Definition: private_array_tree_map.h:163
CCC_Array_tree_map_handle::status
CCC_Entry_status status
Definition: private_array_tree_map.h:169
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:132
CCC_Array_tree_map::data
void * data
Definition: private_array_tree_map.h:134
CCC_Array_tree_map::parity
unsigned * parity
Definition: private_array_tree_map.h:138
CCC_Array_tree_map::sizeof_type
size_t sizeof_type
Definition: private_array_tree_map.h:148
CCC_Array_tree_map::count
size_t count
Definition: private_array_tree_map.h:146
CCC_Array_tree_map::capacity
size_t capacity
Definition: private_array_tree_map.h:144
CCC_Array_tree_map::root
size_t root
Definition: private_array_tree_map.h:140
CCC_Array_tree_map::free_list
size_t free_list
Definition: private_array_tree_map.h:142
CCC_Array_tree_map::context
void * context
Definition: private_array_tree_map.h:156
CCC_Array_tree_map::nodes
struct CCC_Array_tree_map_node * nodes
Definition: private_array_tree_map.h:136
CCC_Array_tree_map::allocate
CCC_Allocator * allocate
Definition: private_array_tree_map.h:154
CCC_Array_tree_map::key_offset
size_t key_offset
Definition: private_array_tree_map.h:150
CCC_Array_tree_map::compare
CCC_Key_comparator * compare
Definition: private_array_tree_map.h:152
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:174
CCC_Array_tree_map_handle_wrap::private
struct CCC_Array_tree_map_handle private
Definition: private_array_tree_map.h:176