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
25/* NOLINTBEGIN(readability-identifier-naming) */
26
32struct CCC_Array_adaptive_map_node {
34 size_t branch[2];
35 union {
37 size_t parent;
39 size_t next_free;
40 };
41};
42
68struct CCC_Array_adaptive_map {
70 void *data;
72 struct CCC_Array_adaptive_map_node *nodes;
74 size_t capacity;
76 size_t count;
78 size_t root;
80 size_t free_list;
82 size_t sizeof_type;
84 size_t key_offset;
86 CCC_Key_comparator comparator;
87};
88
91struct CCC_Array_adaptive_map_handle {
93 struct CCC_Array_adaptive_map *map;
95 size_t index;
97 CCC_Order last_order;
99 CCC_Entry_status status;
100};
101
102/*=========================== Private Interface ===========================*/
103
105void
106CCC_private_array_adaptive_map_insert(struct CCC_Array_adaptive_map *, size_t);
108struct CCC_Array_adaptive_map_handle CCC_private_array_adaptive_map_handle(
109 struct CCC_Array_adaptive_map *, void const *key
110);
112void *CCC_private_array_adaptive_map_data_at(
113 struct CCC_Array_adaptive_map const *, size_t slot
114);
116void *CCC_private_array_adaptive_map_key_at(
117 struct CCC_Array_adaptive_map const *, size_t slot
118);
120size_t CCC_private_array_adaptive_map_allocate_slot(
121 struct CCC_Array_adaptive_map *, CCC_Allocator const *
122);
123
124/*======================== Initialization =========================*/
125
127#define CCC_private_array_adaptive_map_compound_literal_array_capacity( \
128 private_type_compound_literal_array \
129) \
130 (sizeof(private_type_compound_literal_array) \
131 / sizeof(*(private_type_compound_literal_array)))
132
134#define CCC_private_array_adaptive_map_default( \
135 private_type_name, private_key_node_field, private_comparator... \
136) \
137 (struct CCC_Array_adaptive_map) { \
138 .sizeof_type = sizeof(private_type_name), \
139 .key_offset = offsetof(private_type_name, private_key_node_field), \
140 .comparator = private_comparator, \
141 }
142
144#define CCC_private_array_adaptive_map_for( \
145 private_type_name, \
146 private_comparator, \
147 private_capacity, \
148 private_memory_pointer \
149) \
150 (struct CCC_Array_adaptive_map) { \
151 .data = (private_memory_pointer), .nodes = NULL, \
152 .capacity = (private_capacity), .count = 0, .root = 0, .free_list = 0, \
153 .sizeof_type = sizeof(private_type_name), \
154 .key_offset = offsetof(private_type_name, private_key_node_field), \
155 .comparator = (private_comparator), \
156 }
157
159#define CCC_private_array_adaptive_map_from( \
160 private_key_field, \
161 private_comparator, \
162 private_allocator, \
163 private_optional_cap, \
164 private_array_compound_literal... \
165) \
166 (struct { struct CCC_Array_adaptive_map private; }){(__extension__({ \
167 typeof(*private_array_compound_literal) \
168 *private_array_adaptive_map_initializer_list \
169 = private_array_compound_literal; \
170 struct CCC_Array_adaptive_map private_array_adaptive_map \
171 = CCC_private_array_adaptive_map_default( \
172 typeof(*private_array_adaptive_map_initializer_list), \
173 private_key_field, \
174 private_comparator \
175 ); \
176 size_t const private_array_adaptive_n \
177 = sizeof(private_array_compound_literal) \
178 / sizeof(*private_array_adaptive_map_initializer_list); \
179 size_t const private_cap = private_optional_cap; \
180 CCC_Allocator const *const private_array_adaptive_map_allocator \
181 = &(private_allocator); \
182 if (CCC_array_adaptive_map_reserve( \
183 &private_array_adaptive_map, \
184 (private_array_adaptive_n > private_cap \
185 ? private_array_adaptive_n \
186 : private_cap), \
187 private_array_adaptive_map_allocator \
188 ) \
189 == CCC_RESULT_OK) { \
190 for (size_t i = 0; i < private_array_adaptive_n; ++i) { \
191 struct CCC_Array_adaptive_map_handle \
192 private_array_adaptive_entry \
193 = CCC_private_array_adaptive_map_handle( \
194 &private_array_adaptive_map, \
195 ( \
196 void const * \
197 )&private_array_adaptive_map_initializer_list[i] \
198 .private_key_field \
199 ); \
200 CCC_Handle_index private_index \
201 = private_array_adaptive_entry.index; \
202 if (!(private_array_adaptive_entry.status \
203 & CCC_ENTRY_OCCUPIED)) { \
204 private_index \
205 = CCC_private_array_adaptive_map_allocate_slot( \
206 &private_array_adaptive_map, \
207 private_array_adaptive_map_allocator \
208 ); \
209 } \
210 *((typeof(*private_array_adaptive_map_initializer_list) *) \
211 CCC_private_array_adaptive_map_data_at( \
212 private_array_adaptive_entry.map, private_index \
213 )) = private_array_adaptive_map_initializer_list[i]; \
214 if (!(private_array_adaptive_entry.status \
215 & CCC_ENTRY_OCCUPIED)) { \
216 CCC_private_array_adaptive_map_insert( \
217 private_array_adaptive_entry.map, private_index \
218 ); \
219 } \
220 } \
221 } \
222 private_array_adaptive_map; \
223 }))}.private
224
226#define CCC_private_array_adaptive_map_with_capacity( \
227 private_type_name, \
228 private_key_field, \
229 private_comparator, \
230 private_allocator, \
231 private_cap \
232) \
233 (struct { struct CCC_Array_adaptive_map private; }){(__extension__({ \
234 struct CCC_Array_adaptive_map private_array_adaptive_map \
235 = CCC_private_array_adaptive_map_default( \
236 private_type_name, private_key_field, private_comparator \
237 ); \
238 (void)CCC_array_adaptive_map_reserve( \
239 &private_array_adaptive_map, private_cap, &(private_allocator) \
240 ); \
241 private_array_adaptive_map; \
242 }))}.private
243
247#define CCC_private_array_adaptive_map_storage_for( \
248 private_type_compound_literal_array, optional_storage_specifier... \
249) \
250 (optional_storage_specifier struct { \
251 static_assert( \
252 CCC_private_array_adaptive_map_compound_literal_array_capacity( \
253 private_type_compound_literal_array \
254 ) > 1, \
255 "fixed size map must have capacity greater than 1" \
256 ); \
257 typeof(*(private_type_compound_literal_array)) data \
258 [CCC_private_array_adaptive_map_compound_literal_array_capacity( \
259 private_type_compound_literal_array \
260 )]; \
261 struct CCC_Array_adaptive_map_node nodes \
262 [CCC_private_array_adaptive_map_compound_literal_array_capacity( \
263 private_type_compound_literal_array \
264 )]; \
265 }) { \
266 }
267
269#define CCC_private_array_adaptive_map_with_storage( \
270 private_key_node_field, \
271 private_comparator, \
272 private_compound_literal, \
273 private_optional_storage_specifier... \
274) \
275 (struct CCC_Array_adaptive_map) { \
276 .data = &CCC_private_array_adaptive_map_storage_for( \
277 private_compound_literal, private_optional_storage_specifier \
278 ), \
279 .nodes = NULL, \
280 .capacity \
281 = CCC_private_array_adaptive_map_compound_literal_array_capacity( \
282 private_compound_literal \
283 ), \
284 .count = 0, .root = 0, .free_list = 0, \
285 .sizeof_type = sizeof(*(private_compound_literal)), \
286 .key_offset = offsetof( \
287 typeof(*(private_compound_literal)), private_key_node_field \
288 ), \
289 .comparator = (private_comparator), \
290 }
291
293#define CCC_private_array_adaptive_map_as( \
294 array_adaptive_map_pointer, type_name, handle... \
295) \
296 ((type_name *)CCC_private_array_adaptive_map_data_at( \
297 (array_adaptive_map_pointer), (handle) \
298 ))
299
300/*================== Core Macro Implementations =====================*/
301
303#define CCC_private_array_adaptive_map_and_modify_with( \
304 array_adaptive_map_handle_pointer, \
305 closure_parameter, \
306 closure_over_closure_parameter... \
307) \
308 (__extension__({ \
309 struct CCC_Array_adaptive_map_handle const *const \
310 private_array_adaptive_map_mod_hndl_pointer \
311 = (array_adaptive_map_handle_pointer); \
312 struct CCC_Array_adaptive_map_handle \
313 private_array_adaptive_map_mod_hndl \
314 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
315 if (private_array_adaptive_map_mod_hndl_pointer) { \
316 private_array_adaptive_map_mod_hndl \
317 = *private_array_adaptive_map_mod_hndl_pointer; \
318 if (private_array_adaptive_map_mod_hndl.status \
319 & CCC_ENTRY_OCCUPIED) { \
320 closure_parameter = CCC_private_array_adaptive_map_data_at( \
321 private_array_adaptive_map_mod_hndl.map, \
322 private_array_adaptive_map_mod_hndl.index \
323 ); \
324 closure_over_closure_parameter \
325 } \
326 } \
327 private_array_adaptive_map_mod_hndl; \
328 }))
329
331#define CCC_private_array_adaptive_map_or_insert_with( \
332 array_adaptive_map_handle_pointer, \
333 private_allocator_pointer, \
334 type_compound_literal... \
335) \
336 (__extension__({ \
337 struct CCC_Array_adaptive_map_handle const *const \
338 private_array_adaptive_map_or_ins_hndl_pointer \
339 = (array_adaptive_map_handle_pointer); \
340 CCC_Handle_index private_array_adaptive_map_or_ins_ret = 0; \
341 CCC_Allocator const *const private_array_adaptive_map_allocator \
342 = (private_allocator_pointer); \
343 if (private_array_adaptive_map_allocator \
344 && private_array_adaptive_map_or_ins_hndl_pointer) { \
345 if (private_array_adaptive_map_or_ins_hndl_pointer->status \
346 == CCC_ENTRY_OCCUPIED) { \
347 private_array_adaptive_map_or_ins_ret \
348 = private_array_adaptive_map_or_ins_hndl_pointer->index; \
349 } else { \
350 private_array_adaptive_map_or_ins_ret \
351 = CCC_private_array_adaptive_map_allocate_slot( \
352 private_array_adaptive_map_or_ins_hndl_pointer->map, \
353 private_array_adaptive_map_allocator \
354 ); \
355 if (private_array_adaptive_map_or_ins_ret) { \
356 *((typeof(type_compound_literal) *) \
357 CCC_private_array_adaptive_map_data_at( \
358 private_array_adaptive_map_or_ins_hndl_pointer \
359 ->map, \
360 private_array_adaptive_map_or_ins_ret \
361 )) = type_compound_literal; \
362 CCC_private_array_adaptive_map_insert( \
363 private_array_adaptive_map_or_ins_hndl_pointer->map, \
364 private_array_adaptive_map_or_ins_ret \
365 ); \
366 } \
367 } \
368 } \
369 private_array_adaptive_map_or_ins_ret; \
370 }))
371
373#define CCC_private_array_adaptive_map_insert_handle_with( \
374 array_adaptive_map_handle_pointer, \
375 private_allocator_pointer, \
376 type_compound_literal... \
377) \
378 (__extension__({ \
379 struct CCC_Array_adaptive_map_handle const *const \
380 private_array_adaptive_map_ins_hndl_pointer \
381 = (array_adaptive_map_handle_pointer); \
382 CCC_Handle_index private_array_adaptive_map_ins_hndl_ret = 0; \
383 CCC_Allocator const *const private_array_adaptive_map_allocator \
384 = (private_allocator_pointer); \
385 if (private_array_adaptive_map_allocator \
386 && private_array_adaptive_map_ins_hndl_pointer) { \
387 if (!(private_array_adaptive_map_ins_hndl_pointer->status \
388 & CCC_ENTRY_OCCUPIED)) { \
389 private_array_adaptive_map_ins_hndl_ret \
390 = CCC_private_array_adaptive_map_allocate_slot( \
391 private_array_adaptive_map_ins_hndl_pointer->map, \
392 private_array_adaptive_map_allocator \
393 ); \
394 if (private_array_adaptive_map_ins_hndl_ret) { \
395 *((typeof(type_compound_literal) *) \
396 CCC_private_array_adaptive_map_data_at( \
397 private_array_adaptive_map_ins_hndl_pointer \
398 ->map, \
399 private_array_adaptive_map_ins_hndl_ret \
400 )) = type_compound_literal; \
401 CCC_private_array_adaptive_map_insert( \
402 private_array_adaptive_map_ins_hndl_pointer->map, \
403 private_array_adaptive_map_ins_hndl_ret \
404 ); \
405 } \
406 } else if (private_array_adaptive_map_ins_hndl_pointer->status \
407 == CCC_ENTRY_OCCUPIED) { \
408 *((typeof(type_compound_literal) *) \
409 CCC_private_array_adaptive_map_data_at( \
410 private_array_adaptive_map_ins_hndl_pointer->map, \
411 private_array_adaptive_map_ins_hndl_pointer->index \
412 )) = type_compound_literal; \
413 private_array_adaptive_map_ins_hndl_ret \
414 = private_array_adaptive_map_ins_hndl_pointer->index; \
415 } \
416 } \
417 private_array_adaptive_map_ins_hndl_ret; \
418 }))
419
421#define CCC_private_array_adaptive_map_try_insert_with( \
422 array_adaptive_map_pointer, \
423 key, \
424 private_allocator_pointer, \
425 type_compound_literal... \
426) \
427 (__extension__({ \
428 struct CCC_Array_adaptive_map *const \
429 private_array_adaptive_map_try_ins_map_pointer \
430 = (array_adaptive_map_pointer); \
431 CCC_Handle private_array_adaptive_map_try_ins_hndl_ret \
432 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
433 CCC_Allocator const *const private_array_adaptive_map_allocator \
434 = (private_allocator_pointer); \
435 if (private_array_adaptive_map_allocator \
436 && private_array_adaptive_map_try_ins_map_pointer) { \
437 __auto_type private_array_adaptive_map_key = (key); \
438 struct CCC_Array_adaptive_map_handle \
439 private_array_adaptive_map_try_ins_hndl \
440 = CCC_private_array_adaptive_map_handle( \
441 private_array_adaptive_map_try_ins_map_pointer, \
442 (void *)&private_array_adaptive_map_key \
443 ); \
444 if (!(private_array_adaptive_map_try_ins_hndl.status \
445 & CCC_ENTRY_OCCUPIED)) { \
446 private_array_adaptive_map_try_ins_hndl_ret = (CCC_Handle){ \
447 .index = CCC_private_array_adaptive_map_allocate_slot( \
448 private_array_adaptive_map_try_ins_hndl.map, \
449 private_array_adaptive_map_allocator \
450 ), \
451 .status = CCC_ENTRY_INSERT_ERROR, \
452 }; \
453 if (private_array_adaptive_map_try_ins_hndl_ret.index) { \
454 *((typeof(type_compound_literal) *) \
455 CCC_private_array_adaptive_map_data_at( \
456 private_array_adaptive_map_try_ins_map_pointer, \
457 private_array_adaptive_map_try_ins_hndl_ret \
458 .index \
459 )) = type_compound_literal; \
460 *((typeof(private_array_adaptive_map_key) *) \
461 CCC_private_array_adaptive_map_key_at( \
462 private_array_adaptive_map_try_ins_hndl.map, \
463 private_array_adaptive_map_try_ins_hndl_ret \
464 .index \
465 )) = private_array_adaptive_map_key; \
466 CCC_private_array_adaptive_map_insert( \
467 private_array_adaptive_map_try_ins_hndl.map, \
468 private_array_adaptive_map_try_ins_hndl_ret.index \
469 ); \
470 private_array_adaptive_map_try_ins_hndl_ret.status \
471 = CCC_ENTRY_VACANT; \
472 } \
473 } else if (private_array_adaptive_map_try_ins_hndl.status \
474 == CCC_ENTRY_OCCUPIED) { \
475 private_array_adaptive_map_try_ins_hndl_ret = (CCC_Handle){ \
476 .index = private_array_adaptive_map_try_ins_hndl.index, \
477 .status = private_array_adaptive_map_try_ins_hndl.status}; \
478 } \
479 } \
480 private_array_adaptive_map_try_ins_hndl_ret; \
481 }))
482
484#define CCC_private_array_adaptive_map_insert_or_assign_with( \
485 array_adaptive_map_pointer, \
486 key, \
487 private_allocator_pointer, \
488 type_compound_literal... \
489) \
490 (__extension__({ \
491 struct CCC_Array_adaptive_map *const \
492 private_array_adaptive_map_ins_or_assign_map_pointer \
493 = (array_adaptive_map_pointer); \
494 CCC_Handle private_array_adaptive_map_ins_or_assign_hndl_ret \
495 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
496 CCC_Allocator const *const private_array_adaptive_map_allocator \
497 = (private_allocator_pointer); \
498 if (private_array_adaptive_map_allocator \
499 && private_array_adaptive_map_ins_or_assign_map_pointer) { \
500 __auto_type private_array_adaptive_map_key = (key); \
501 struct CCC_Array_adaptive_map_handle \
502 private_array_adaptive_map_ins_or_assign_hndl \
503 = CCC_private_array_adaptive_map_handle( \
504 private_array_adaptive_map_ins_or_assign_map_pointer, \
505 (void *)&private_array_adaptive_map_key \
506 ); \
507 if (!(private_array_adaptive_map_ins_or_assign_hndl.status \
508 & CCC_ENTRY_OCCUPIED)) { \
509 private_array_adaptive_map_ins_or_assign_hndl_ret \
510 = (CCC_Handle){ \
511 .index = CCC_private_array_adaptive_map_allocate_slot( \
512 private_array_adaptive_map_ins_or_assign_hndl.map, \
513 private_array_adaptive_map_allocator \
514 ), \
515 .status = CCC_ENTRY_INSERT_ERROR, \
516 }; \
517 if (private_array_adaptive_map_ins_or_assign_hndl_ret.index) { \
518 *((typeof(type_compound_literal) *) \
519 CCC_private_array_adaptive_map_data_at( \
520 private_array_adaptive_map_ins_or_assign_map_pointer, \
521 private_array_adaptive_map_ins_or_assign_hndl_ret \
522 .index \
523 )) = type_compound_literal; \
524 *((typeof(private_array_adaptive_map_key) *) \
525 CCC_private_array_adaptive_map_key_at( \
526 private_array_adaptive_map_ins_or_assign_hndl \
527 .map, \
528 private_array_adaptive_map_ins_or_assign_hndl_ret \
529 .index \
530 )) = private_array_adaptive_map_key; \
531 CCC_private_array_adaptive_map_insert( \
532 private_array_adaptive_map_ins_or_assign_hndl.map, \
533 private_array_adaptive_map_ins_or_assign_hndl_ret \
534 .index \
535 ); \
536 private_array_adaptive_map_ins_or_assign_hndl_ret.status \
537 = CCC_ENTRY_VACANT; \
538 } \
539 } else if (private_array_adaptive_map_ins_or_assign_hndl.status \
540 == CCC_ENTRY_OCCUPIED) { \
541 *((typeof(type_compound_literal) *) \
542 CCC_private_array_adaptive_map_data_at( \
543 private_array_adaptive_map_ins_or_assign_hndl.map, \
544 private_array_adaptive_map_ins_or_assign_hndl.index \
545 )) = type_compound_literal; \
546 private_array_adaptive_map_ins_or_assign_hndl_ret \
547 = (CCC_Handle){ \
548 .index \
549 = private_array_adaptive_map_ins_or_assign_hndl.index, \
550 .status \
551 = private_array_adaptive_map_ins_or_assign_hndl \
552 .status, \
553 }; \
554 *((typeof(private_array_adaptive_map_key) *) \
555 CCC_private_array_adaptive_map_key_at( \
556 private_array_adaptive_map_ins_or_assign_hndl.map, \
557 private_array_adaptive_map_ins_or_assign_hndl.index \
558 )) = private_array_adaptive_map_key; \
559 } \
560 } \
561 private_array_adaptive_map_ins_or_assign_hndl_ret; \
562 }))
563
564/* NOLINTEND(readability-identifier-naming) */
565
566#endif /* CCC_PRIVATE_ARRAY_ADAPTIVE_MAP_H */
CCC_Allocator
The type passed by reference to any container function that may need to allocate memory....
Definition: types.h:369
CCC_Array_adaptive_map_handle
Definition: private_array_adaptive_map.h:91
CCC_Array_adaptive_map_handle::last_order
CCC_Order last_order
Definition: private_array_adaptive_map.h:97
CCC_Array_adaptive_map_handle::status
CCC_Entry_status status
Definition: private_array_adaptive_map.h:99
CCC_Array_adaptive_map_handle::index
size_t index
Definition: private_array_adaptive_map.h:95
CCC_Array_adaptive_map_handle::map
struct CCC_Array_adaptive_map * map
Definition: private_array_adaptive_map.h:93
CCC_Array_adaptive_map_node
Definition: private_array_adaptive_map.h:32
CCC_Array_adaptive_map_node::branch
size_t branch[2]
Definition: private_array_adaptive_map.h:34
CCC_Array_adaptive_map_node::next_free
size_t next_free
Definition: private_array_adaptive_map.h:39
CCC_Array_adaptive_map_node::parent
size_t parent
Definition: private_array_adaptive_map.h:37
CCC_Array_adaptive_map
Definition: private_array_adaptive_map.h:68
CCC_Array_adaptive_map::free_list
size_t free_list
Definition: private_array_adaptive_map.h:80
CCC_Array_adaptive_map::count
size_t count
Definition: private_array_adaptive_map.h:76
CCC_Array_adaptive_map::data
void * data
Definition: private_array_adaptive_map.h:70
CCC_Array_adaptive_map::sizeof_type
size_t sizeof_type
Definition: private_array_adaptive_map.h:82
CCC_Array_adaptive_map::root
size_t root
Definition: private_array_adaptive_map.h:78
CCC_Array_adaptive_map::comparator
CCC_Key_comparator comparator
Definition: private_array_adaptive_map.h:86
CCC_Array_adaptive_map::nodes
struct CCC_Array_adaptive_map_node * nodes
Definition: private_array_adaptive_map.h:72
CCC_Array_adaptive_map::capacity
size_t capacity
Definition: private_array_adaptive_map.h:74
CCC_Array_adaptive_map::key_offset
size_t key_offset
Definition: private_array_adaptive_map.h:84
CCC_Key_comparator
The type passed by reference to any container function that may need to compare keys....
Definition: types.h:505
CCC_Order
CCC_Order
A three-way comparison for comparison functions.
Definition: types.h:213
CCC_Entry_status
CCC_Entry_status
The status monitoring and entry state once it is obtained.
Definition: types.h:112