C Container Collection (CCC)
Loading...
Searching...
No Matches
private_array_adaptive_map.h
1
16#ifndef CCC_PRIVATE_ARRAY_ADAPTIVE_MAP_H
17#define CCC_PRIVATE_ARRAY_ADAPTIVE_MAP_H
18
20#include <stddef.h>
23#include "../types.h"
24#include "private_types.h" /* NOLINT */
25
26/* NOLINTBEGIN(readability-identifier-naming) */
27
33struct CCC_Array_adaptive_map_node
34{
36 size_t branch[2];
37 union
38 {
40 size_t parent;
42 size_t next_free;
43 };
44};
45
69struct CCC_Array_adaptive_map
70{
72 void *data;
74 struct CCC_Array_adaptive_map_node *nodes;
76 size_t capacity;
78 size_t count;
80 size_t root;
82 size_t free_list;
84 size_t sizeof_type;
86 size_t key_offset;
88 CCC_Key_comparator *compare;
90 CCC_Allocator *allocate;
92 void *context;
93};
94
97struct CCC_Array_adaptive_map_handle
98{
100 struct CCC_Array_adaptive_map *map;
102 size_t index;
104 CCC_Order last_order;
106 CCC_Entry_status status;
107};
108
113union CCC_Array_adaptive_map_handle_wrap
114{
116 struct CCC_Array_adaptive_map_handle private;
117};
118
119/*=========================== Private Interface ===========================*/
120
122void CCC_private_array_adaptive_map_insert(struct CCC_Array_adaptive_map *,
123 size_t);
125struct CCC_Array_adaptive_map_handle
126CCC_private_array_adaptive_map_handle(struct CCC_Array_adaptive_map *,
127 void const *key);
129void *
130CCC_private_array_adaptive_map_data_at(struct CCC_Array_adaptive_map const *,
131 size_t slot);
133void *
134CCC_private_array_adaptive_map_key_at(struct CCC_Array_adaptive_map const *,
135 size_t slot);
137size_t
138CCC_private_array_adaptive_map_allocate_slot(struct CCC_Array_adaptive_map *);
139
140/*======================== Initialization =========================*/
141
144#define CCC_private_array_adaptive_map_declare_fixed( \
145 private_fixed_map_type_name, private_key_val_type_name, private_capacity) \
146 static_assert((private_capacity) > 1, \
147 "fixed size map must have capacity greater than 1"); \
148 typedef struct \
149 { \
150 private_key_val_type_name data[(private_capacity)]; \
151 struct CCC_Array_adaptive_map_node nodes[(private_capacity)]; \
152 }(private_fixed_map_type_name)
153
156#define CCC_private_array_adaptive_map_fixed_capacity(fixed_map_type_name) \
157 (sizeof((fixed_map_type_name){}.nodes) \
158 / sizeof(struct CCC_Array_adaptive_map_node))
159
161#define CCC_private_array_adaptive_map_initialize( \
162 private_memory_pointer, private_type_name, private_key_node_field, \
163 private_key_order_fn, private_allocate, private_context_data, \
164 private_capacity) \
165 { \
166 .data = (private_memory_pointer), \
167 .nodes = NULL, \
168 .capacity = (private_capacity), \
169 .count = 0, \
170 .root = 0, \
171 .free_list = 0, \
172 .sizeof_type = sizeof(private_type_name), \
173 .key_offset = offsetof(private_type_name, private_key_node_field), \
174 .compare = (private_key_order_fn), \
175 .allocate = (private_allocate), \
176 .context = (private_context_data), \
177 }
178
180#define CCC_private_array_adaptive_map_from( \
181 private_key_field, private_key_compare, private_allocate, \
182 private_context_data, private_optional_cap, \
183 private_array_compound_literal...) \
184 (__extension__({ \
185 typeof(*private_array_compound_literal) \
186 *private_array_adaptive_map_initializer_list \
187 = private_array_compound_literal; \
188 struct CCC_Array_adaptive_map private_array_adaptive_map \
189 = CCC_private_array_adaptive_map_initialize( \
190 NULL, typeof(*private_array_adaptive_map_initializer_list), \
191 private_key_field, private_key_compare, private_allocate, \
192 private_context_data, 0); \
193 size_t const private_array_adaptive_n \
194 = sizeof(private_array_compound_literal) \
195 / sizeof(*private_array_adaptive_map_initializer_list); \
196 size_t const private_cap = private_optional_cap; \
197 if (CCC_array_adaptive_map_reserve( \
198 &private_array_adaptive_map, \
199 (private_array_adaptive_n > private_cap \
200 ? private_array_adaptive_n \
201 : private_cap), \
202 private_allocate) \
203 == CCC_RESULT_OK) \
204 { \
205 for (size_t i = 0; i < private_array_adaptive_n; ++i) \
206 { \
207 struct CCC_Array_adaptive_map_handle \
208 private_array_adaptive_entry \
209 = CCC_private_array_adaptive_map_handle( \
210 &private_array_adaptive_map, \
211 (void const \
212 *)&private_array_adaptive_map_initializer_list[i] \
213 .private_key_field); \
214 CCC_Handle_index private_index \
215 = private_array_adaptive_entry.index; \
216 if (!(private_array_adaptive_entry.status \
217 & CCC_ENTRY_OCCUPIED)) \
218 { \
219 private_index \
220 = CCC_private_array_adaptive_map_allocate_slot( \
221 &private_array_adaptive_map); \
222 } \
223 *((typeof(*private_array_adaptive_map_initializer_list) *) \
224 CCC_private_array_adaptive_map_data_at( \
225 private_array_adaptive_entry.map, private_index)) \
226 = private_array_adaptive_map_initializer_list[i]; \
227 if (!(private_array_adaptive_entry.status \
228 & CCC_ENTRY_OCCUPIED)) \
229 { \
230 CCC_private_array_adaptive_map_insert( \
231 private_array_adaptive_entry.map, private_index); \
232 } \
233 } \
234 } \
235 private_array_adaptive_map; \
236 }))
237
238#define CCC_private_array_adaptive_map_with_capacity( \
239 private_type_name, private_key_field, private_key_compare, \
240 private_allocate, private_context_data, private_cap) \
241 (__extension__({ \
242 struct CCC_Array_adaptive_map private_array_adaptive_map \
243 = CCC_private_array_adaptive_map_initialize( \
244 NULL, private_type_name, private_key_field, \
245 private_key_compare, private_allocate, private_context_data, \
246 0); \
247 (void)CCC_array_adaptive_map_reserve(&private_array_adaptive_map, \
248 private_cap, private_allocate); \
249 private_array_adaptive_map; \
250 }))
251
253#define CCC_private_array_adaptive_map_with_compound_literal( \
254 private_key_node_field, private_key_order_fn, private_compound_literal) \
255 { \
256 .data = &(private_compound_literal), \
257 .nodes = NULL, \
258 .capacity = CCC_private_array_adaptive_map_fixed_capacity( \
259 typeof(private_compound_literal)), \
260 .count = 0, \
261 .root = 0, \
262 .free_list = 0, \
263 .sizeof_type = sizeof(*(private_compound_literal.data)) /*NOLINT*/, \
264 .key_offset \
265 = offsetof(typeof(*(private_compound_literal.data)) /*NOLINT*/, \
266 private_key_node_field), \
267 .compare = (private_key_order_fn), \
268 .allocate = NULL, \
269 .context = NULL, \
270 }
271
273#define CCC_private_array_adaptive_map_with_context_compound_literal( \
274 private_key_node_field, private_key_order_fn, private_context, \
275 private_compound_literal) \
276 { \
277 .data = &(private_compound_literal), \
278 .nodes = NULL, \
279 .capacity = CCC_private_array_adaptive_map_fixed_capacity( \
280 typeof(private_compound_literal)), \
281 .count = 0, \
282 .root = 0, \
283 .free_list = 0, \
284 .sizeof_type = sizeof(*(private_compound_literal.data)) /*NOLINT*/, \
285 .key_offset \
286 = offsetof(typeof(*(private_compound_literal.data)) /*NOLINT*/, \
287 private_key_node_field), \
288 .compare = (private_key_order_fn), \
289 .allocate = NULL, \
290 .context = (private_context), \
291 }
292
294#define CCC_private_array_adaptive_map_as(array_adaptive_map_pointer, \
295 type_name, handle...) \
296 ((type_name *)CCC_private_array_adaptive_map_data_at( \
297 (array_adaptive_map_pointer), (handle)))
298
299/*================== Core Macro Implementations =====================*/
300
302#define CCC_private_array_adaptive_map_and_modify_with( \
303 array_adaptive_map_array_pointer, type_name, closure_over_T...) \
304 (__extension__({ \
305 __auto_type private_array_adaptive_map_mod_hndl_pointer \
306 = (array_adaptive_map_array_pointer); \
307 struct CCC_Array_adaptive_map_handle \
308 private_array_adaptive_map_mod_hndl \
309 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
310 if (private_array_adaptive_map_mod_hndl_pointer) \
311 { \
312 private_array_adaptive_map_mod_hndl \
313 = private_array_adaptive_map_mod_hndl_pointer->private; \
314 if (private_array_adaptive_map_mod_hndl.status \
315 & CCC_ENTRY_OCCUPIED) \
316 { \
317 type_name *const T = CCC_private_array_adaptive_map_data_at( \
318 private_array_adaptive_map_mod_hndl.map, \
319 private_array_adaptive_map_mod_hndl.index); \
320 if (T) \
321 { \
322 closure_over_T \
323 } \
324 } \
325 } \
326 private_array_adaptive_map_mod_hndl; \
327 }))
328
330#define CCC_private_array_adaptive_map_or_insert_with( \
331 array_adaptive_map_array_pointer, type_compound_literal...) \
332 (__extension__({ \
333 __auto_type private_array_adaptive_map_or_ins_hndl_pointer \
334 = (array_adaptive_map_array_pointer); \
335 CCC_Handle_index private_array_adaptive_map_or_ins_ret = 0; \
336 if (private_array_adaptive_map_or_ins_hndl_pointer) \
337 { \
338 if (private_array_adaptive_map_or_ins_hndl_pointer->private.status \
339 == CCC_ENTRY_OCCUPIED) \
340 { \
341 private_array_adaptive_map_or_ins_ret \
342 = private_array_adaptive_map_or_ins_hndl_pointer->private \
343 .index; \
344 } \
345 else \
346 { \
347 private_array_adaptive_map_or_ins_ret \
348 = CCC_private_array_adaptive_map_allocate_slot( \
349 private_array_adaptive_map_or_ins_hndl_pointer \
350 ->private.map); \
351 if (private_array_adaptive_map_or_ins_ret) \
352 { \
353 *((typeof(type_compound_literal) *) \
354 CCC_private_array_adaptive_map_data_at( \
355 private_array_adaptive_map_or_ins_hndl_pointer \
356 ->private.map, \
357 private_array_adaptive_map_or_ins_ret)) \
358 = type_compound_literal; \
359 CCC_private_array_adaptive_map_insert( \
360 private_array_adaptive_map_or_ins_hndl_pointer \
361 ->private.map, \
362 private_array_adaptive_map_or_ins_ret); \
363 } \
364 } \
365 } \
366 private_array_adaptive_map_or_ins_ret; \
367 }))
368
370#define CCC_private_array_adaptive_map_insert_array_with( \
371 array_adaptive_map_array_pointer, type_compound_literal...) \
372 (__extension__({ \
373 __auto_type private_array_adaptive_map_ins_hndl_pointer \
374 = (array_adaptive_map_array_pointer); \
375 CCC_Handle_index private_array_adaptive_map_ins_hndl_ret = 0; \
376 if (private_array_adaptive_map_ins_hndl_pointer) \
377 { \
378 if (!(private_array_adaptive_map_ins_hndl_pointer->private.status \
379 & CCC_ENTRY_OCCUPIED)) \
380 { \
381 private_array_adaptive_map_ins_hndl_ret \
382 = CCC_private_array_adaptive_map_allocate_slot( \
383 private_array_adaptive_map_ins_hndl_pointer->private \
384 .map); \
385 if (private_array_adaptive_map_ins_hndl_ret) \
386 { \
387 *((typeof(type_compound_literal) *) \
388 CCC_private_array_adaptive_map_data_at( \
389 private_array_adaptive_map_ins_hndl_pointer \
390 ->private.map, \
391 private_array_adaptive_map_ins_hndl_ret)) \
392 = type_compound_literal; \
393 CCC_private_array_adaptive_map_insert( \
394 private_array_adaptive_map_ins_hndl_pointer->private \
395 .map, \
396 private_array_adaptive_map_ins_hndl_ret); \
397 } \
398 } \
399 else if (private_array_adaptive_map_ins_hndl_pointer->private \
400 .status \
401 == CCC_ENTRY_OCCUPIED) \
402 { \
403 *((typeof(type_compound_literal) *) \
404 CCC_private_array_adaptive_map_data_at( \
405 private_array_adaptive_map_ins_hndl_pointer->private \
406 .map, \
407 private_array_adaptive_map_ins_hndl_pointer->private \
408 .index)) \
409 = type_compound_literal; \
410 private_array_adaptive_map_ins_hndl_ret \
411 = private_array_adaptive_map_ins_hndl_pointer->private \
412 .index; \
413 } \
414 } \
415 private_array_adaptive_map_ins_hndl_ret; \
416 }))
417
419#define CCC_private_array_adaptive_map_try_insert_with( \
420 array_adaptive_map_pointer, key, type_compound_literal...) \
421 (__extension__({ \
422 __auto_type private_array_adaptive_map_try_ins_map_pointer \
423 = (array_adaptive_map_pointer); \
424 struct CCC_Handle private_array_adaptive_map_try_ins_hndl_ret \
425 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
426 if (private_array_adaptive_map_try_ins_map_pointer) \
427 { \
428 __auto_type private_array_adaptive_map_key = (key); \
429 struct CCC_Array_adaptive_map_handle \
430 private_array_adaptive_map_try_ins_hndl \
431 = CCC_private_array_adaptive_map_handle( \
432 private_array_adaptive_map_try_ins_map_pointer, \
433 (void *)&private_array_adaptive_map_key); \
434 if (!(private_array_adaptive_map_try_ins_hndl.status \
435 & CCC_ENTRY_OCCUPIED)) \
436 { \
437 private_array_adaptive_map_try_ins_hndl_ret \
438 = (struct CCC_Handle){ \
439 .index = CCC_private_array_adaptive_map_allocate_slot( \
440 private_array_adaptive_map_try_ins_hndl.map), \
441 .status = CCC_ENTRY_INSERT_ERROR, \
442 }; \
443 if (private_array_adaptive_map_try_ins_hndl_ret.index) \
444 { \
445 *((typeof(type_compound_literal) *) \
446 CCC_private_array_adaptive_map_data_at( \
447 private_array_adaptive_map_try_ins_map_pointer, \
448 private_array_adaptive_map_try_ins_hndl_ret \
449 .index)) \
450 = type_compound_literal; \
451 *((typeof(private_array_adaptive_map_key) *) \
452 CCC_private_array_adaptive_map_key_at( \
453 private_array_adaptive_map_try_ins_hndl.map, \
454 private_array_adaptive_map_try_ins_hndl_ret \
455 .index)) \
456 = private_array_adaptive_map_key; \
457 CCC_private_array_adaptive_map_insert( \
458 private_array_adaptive_map_try_ins_hndl.map, \
459 private_array_adaptive_map_try_ins_hndl_ret.index); \
460 private_array_adaptive_map_try_ins_hndl_ret.status \
461 = CCC_ENTRY_VACANT; \
462 } \
463 } \
464 else if (private_array_adaptive_map_try_ins_hndl.status \
465 == CCC_ENTRY_OCCUPIED) \
466 { \
467 private_array_adaptive_map_try_ins_hndl_ret \
468 = (struct CCC_Handle){ \
469 .index \
470 = private_array_adaptive_map_try_ins_hndl.index, \
471 .status \
472 = private_array_adaptive_map_try_ins_hndl.status}; \
473 } \
474 } \
475 private_array_adaptive_map_try_ins_hndl_ret; \
476 }))
477
479#define CCC_private_array_adaptive_map_insert_or_assign_with( \
480 array_adaptive_map_pointer, key, type_compound_literal...) \
481 (__extension__({ \
482 __auto_type private_array_adaptive_map_ins_or_assign_map_pointer \
483 = (array_adaptive_map_pointer); \
484 struct CCC_Handle private_array_adaptive_map_ins_or_assign_hndl_ret \
485 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
486 if (private_array_adaptive_map_ins_or_assign_map_pointer) \
487 { \
488 __auto_type private_array_adaptive_map_key = (key); \
489 struct CCC_Array_adaptive_map_handle \
490 private_array_adaptive_map_ins_or_assign_hndl \
491 = CCC_private_array_adaptive_map_handle( \
492 private_array_adaptive_map_ins_or_assign_map_pointer, \
493 (void *)&private_array_adaptive_map_key); \
494 if (!(private_array_adaptive_map_ins_or_assign_hndl.status \
495 & CCC_ENTRY_OCCUPIED)) \
496 { \
497 private_array_adaptive_map_ins_or_assign_hndl_ret \
498 = (struct CCC_Handle){ \
499 .index = CCC_private_array_adaptive_map_allocate_slot( \
500 private_array_adaptive_map_ins_or_assign_hndl \
501 .map), \
502 .status = CCC_ENTRY_INSERT_ERROR, \
503 }; \
504 if (private_array_adaptive_map_ins_or_assign_hndl_ret.index) \
505 { \
506 *((typeof(type_compound_literal) *) \
507 CCC_private_array_adaptive_map_data_at( \
508 private_array_adaptive_map_ins_or_assign_map_pointer, \
509 private_array_adaptive_map_ins_or_assign_hndl_ret \
510 .index)) \
511 = type_compound_literal; \
512 *((typeof(private_array_adaptive_map_key) *) \
513 CCC_private_array_adaptive_map_key_at( \
514 private_array_adaptive_map_ins_or_assign_hndl \
515 .map, \
516 private_array_adaptive_map_ins_or_assign_hndl_ret \
517 .index)) \
518 = private_array_adaptive_map_key; \
519 CCC_private_array_adaptive_map_insert( \
520 private_array_adaptive_map_ins_or_assign_hndl.map, \
521 private_array_adaptive_map_ins_or_assign_hndl_ret \
522 .index); \
523 private_array_adaptive_map_ins_or_assign_hndl_ret.status \
524 = CCC_ENTRY_VACANT; \
525 } \
526 } \
527 else if (private_array_adaptive_map_ins_or_assign_hndl.status \
528 == CCC_ENTRY_OCCUPIED) \
529 { \
530 *((typeof(type_compound_literal) *) \
531 CCC_private_array_adaptive_map_data_at( \
532 private_array_adaptive_map_ins_or_assign_hndl.map, \
533 private_array_adaptive_map_ins_or_assign_hndl \
534 .index)) \
535 = type_compound_literal; \
536 private_array_adaptive_map_ins_or_assign_hndl_ret \
537 = (struct CCC_Handle){ \
538 .index \
539 = private_array_adaptive_map_ins_or_assign_hndl.index, \
540 .status \
541 = private_array_adaptive_map_ins_or_assign_hndl \
542 .status, \
543 }; \
544 *((typeof(private_array_adaptive_map_key) *) \
545 CCC_private_array_adaptive_map_key_at( \
546 private_array_adaptive_map_ins_or_assign_hndl.map, \
547 private_array_adaptive_map_ins_or_assign_hndl \
548 .index)) \
549 = private_array_adaptive_map_key; \
550 } \
551 } \
552 private_array_adaptive_map_ins_or_assign_hndl_ret; \
553 }))
554
555/* NOLINTEND(readability-identifier-naming) */
556
557#endif /* CCC_PRIVATE_ARRAY_ADAPTIVE_MAP_H */
CCC_Array_adaptive_map_handle
Definition: private_array_adaptive_map.h:98
CCC_Array_adaptive_map_handle::last_order
CCC_Order last_order
Definition: private_array_adaptive_map.h:104
CCC_Array_adaptive_map_handle::status
CCC_Entry_status status
Definition: private_array_adaptive_map.h:106
CCC_Array_adaptive_map_handle::index
size_t index
Definition: private_array_adaptive_map.h:102
CCC_Array_adaptive_map_handle::map
struct CCC_Array_adaptive_map * map
Definition: private_array_adaptive_map.h:100
CCC_Array_adaptive_map_node
Definition: private_array_adaptive_map.h:34
CCC_Array_adaptive_map_node::branch
size_t branch[2]
Definition: private_array_adaptive_map.h:36
CCC_Array_adaptive_map_node::next_free
size_t next_free
Definition: private_array_adaptive_map.h:42
CCC_Array_adaptive_map_node::parent
size_t parent
Definition: private_array_adaptive_map.h:40
CCC_Array_adaptive_map
Definition: private_array_adaptive_map.h:70
CCC_Array_adaptive_map::free_list
size_t free_list
Definition: private_array_adaptive_map.h:82
CCC_Array_adaptive_map::count
size_t count
Definition: private_array_adaptive_map.h:78
CCC_Array_adaptive_map::data
void * data
Definition: private_array_adaptive_map.h:72
CCC_Array_adaptive_map::context
void * context
Definition: private_array_adaptive_map.h:92
CCC_Array_adaptive_map::compare
CCC_Key_comparator * compare
Definition: private_array_adaptive_map.h:88
CCC_Array_adaptive_map::sizeof_type
size_t sizeof_type
Definition: private_array_adaptive_map.h:84
CCC_Array_adaptive_map::root
size_t root
Definition: private_array_adaptive_map.h:80
CCC_Array_adaptive_map::nodes
struct CCC_Array_adaptive_map_node * nodes
Definition: private_array_adaptive_map.h:74
CCC_Array_adaptive_map::allocate
CCC_Allocator * allocate
Definition: private_array_adaptive_map.h:90
CCC_Array_adaptive_map::capacity
size_t capacity
Definition: private_array_adaptive_map.h:76
CCC_Array_adaptive_map::key_offset
size_t key_offset
Definition: private_array_adaptive_map.h:86
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_adaptive_map_handle_wrap
Definition: private_array_adaptive_map.h:114
CCC_Array_adaptive_map_handle_wrap::private
struct CCC_Array_adaptive_map_handle private
Definition: private_array_adaptive_map.h:116