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_array_pointer, \
305 closure_parameter, \
306 closure_over_closure_parameter... \
307) \
308 (__extension__({ \
309 __auto_type private_array_adaptive_map_mod_hndl_pointer \
310 = (array_adaptive_map_array_pointer); \
311 struct CCC_Array_adaptive_map_handle \
312 private_array_adaptive_map_mod_hndl \
313 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
314 if (private_array_adaptive_map_mod_hndl_pointer) { \
315 private_array_adaptive_map_mod_hndl \
316 = *private_array_adaptive_map_mod_hndl_pointer; \
317 if (private_array_adaptive_map_mod_hndl.status \
318 & CCC_ENTRY_OCCUPIED) { \
319 closure_parameter = CCC_private_array_adaptive_map_data_at( \
320 private_array_adaptive_map_mod_hndl.map, \
321 private_array_adaptive_map_mod_hndl.index \
322 ); \
323 closure_over_closure_parameter \
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, \
332 private_allocator_pointer, \
333 type_compound_literal... \
334) \
335 (__extension__({ \
336 __auto_type private_array_adaptive_map_or_ins_hndl_pointer \
337 = (array_adaptive_map_array_pointer); \
338 CCC_Handle_index private_array_adaptive_map_or_ins_ret = 0; \
339 CCC_Allocator const *const private_array_adaptive_map_allocator \
340 = (private_allocator_pointer); \
341 if (private_array_adaptive_map_allocator \
342 && private_array_adaptive_map_or_ins_hndl_pointer) { \
343 if (private_array_adaptive_map_or_ins_hndl_pointer->status \
344 == CCC_ENTRY_OCCUPIED) { \
345 private_array_adaptive_map_or_ins_ret \
346 = private_array_adaptive_map_or_ins_hndl_pointer->index; \
347 } else { \
348 private_array_adaptive_map_or_ins_ret \
349 = CCC_private_array_adaptive_map_allocate_slot( \
350 private_array_adaptive_map_or_ins_hndl_pointer->map, \
351 private_array_adaptive_map_allocator \
352 ); \
353 if (private_array_adaptive_map_or_ins_ret) { \
354 *((typeof(type_compound_literal) *) \
355 CCC_private_array_adaptive_map_data_at( \
356 private_array_adaptive_map_or_ins_hndl_pointer \
357 ->map, \
358 private_array_adaptive_map_or_ins_ret \
359 )) = type_compound_literal; \
360 CCC_private_array_adaptive_map_insert( \
361 private_array_adaptive_map_or_ins_hndl_pointer->map, \
362 private_array_adaptive_map_or_ins_ret \
363 ); \
364 } \
365 } \
366 } \
367 private_array_adaptive_map_or_ins_ret; \
368 }))
369
371#define CCC_private_array_adaptive_map_insert_handle_with( \
372 array_adaptive_map_array_pointer, \
373 private_allocator_pointer, \
374 type_compound_literal... \
375) \
376 (__extension__({ \
377 __auto_type private_array_adaptive_map_ins_hndl_pointer \
378 = (array_adaptive_map_array_pointer); \
379 CCC_Handle_index private_array_adaptive_map_ins_hndl_ret = 0; \
380 CCC_Allocator const *const private_array_adaptive_map_allocator \
381 = (private_allocator_pointer); \
382 if (private_array_adaptive_map_allocator \
383 && private_array_adaptive_map_ins_hndl_pointer) { \
384 if (!(private_array_adaptive_map_ins_hndl_pointer->status \
385 & CCC_ENTRY_OCCUPIED)) { \
386 private_array_adaptive_map_ins_hndl_ret \
387 = CCC_private_array_adaptive_map_allocate_slot( \
388 private_array_adaptive_map_ins_hndl_pointer->map, \
389 private_array_adaptive_map_allocator \
390 ); \
391 if (private_array_adaptive_map_ins_hndl_ret) { \
392 *((typeof(type_compound_literal) *) \
393 CCC_private_array_adaptive_map_data_at( \
394 private_array_adaptive_map_ins_hndl_pointer \
395 ->map, \
396 private_array_adaptive_map_ins_hndl_ret \
397 )) = type_compound_literal; \
398 CCC_private_array_adaptive_map_insert( \
399 private_array_adaptive_map_ins_hndl_pointer->map, \
400 private_array_adaptive_map_ins_hndl_ret \
401 ); \
402 } \
403 } else if (private_array_adaptive_map_ins_hndl_pointer->status \
404 == CCC_ENTRY_OCCUPIED) { \
405 *((typeof(type_compound_literal) *) \
406 CCC_private_array_adaptive_map_data_at( \
407 private_array_adaptive_map_ins_hndl_pointer->map, \
408 private_array_adaptive_map_ins_hndl_pointer->index \
409 )) = type_compound_literal; \
410 private_array_adaptive_map_ins_hndl_ret \
411 = private_array_adaptive_map_ins_hndl_pointer->index; \
412 } \
413 } \
414 private_array_adaptive_map_ins_hndl_ret; \
415 }))
416
418#define CCC_private_array_adaptive_map_try_insert_with( \
419 array_adaptive_map_pointer, \
420 key, \
421 private_allocator_pointer, \
422 type_compound_literal... \
423) \
424 (__extension__({ \
425 __auto_type private_array_adaptive_map_try_ins_map_pointer \
426 = (array_adaptive_map_pointer); \
427 CCC_Handle private_array_adaptive_map_try_ins_hndl_ret \
428 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
429 CCC_Allocator const *const private_array_adaptive_map_allocator \
430 = (private_allocator_pointer); \
431 if (private_array_adaptive_map_allocator \
432 && private_array_adaptive_map_try_ins_map_pointer) { \
433 __auto_type private_array_adaptive_map_key = (key); \
434 struct CCC_Array_adaptive_map_handle \
435 private_array_adaptive_map_try_ins_hndl \
436 = CCC_private_array_adaptive_map_handle( \
437 private_array_adaptive_map_try_ins_map_pointer, \
438 (void *)&private_array_adaptive_map_key \
439 ); \
440 if (!(private_array_adaptive_map_try_ins_hndl.status \
441 & CCC_ENTRY_OCCUPIED)) { \
442 private_array_adaptive_map_try_ins_hndl_ret = (CCC_Handle){ \
443 .index = CCC_private_array_adaptive_map_allocate_slot( \
444 private_array_adaptive_map_try_ins_hndl.map, \
445 private_array_adaptive_map_allocator \
446 ), \
447 .status = CCC_ENTRY_INSERT_ERROR, \
448 }; \
449 if (private_array_adaptive_map_try_ins_hndl_ret.index) { \
450 *((typeof(type_compound_literal) *) \
451 CCC_private_array_adaptive_map_data_at( \
452 private_array_adaptive_map_try_ins_map_pointer, \
453 private_array_adaptive_map_try_ins_hndl_ret \
454 .index \
455 )) = type_compound_literal; \
456 *((typeof(private_array_adaptive_map_key) *) \
457 CCC_private_array_adaptive_map_key_at( \
458 private_array_adaptive_map_try_ins_hndl.map, \
459 private_array_adaptive_map_try_ins_hndl_ret \
460 .index \
461 )) = private_array_adaptive_map_key; \
462 CCC_private_array_adaptive_map_insert( \
463 private_array_adaptive_map_try_ins_hndl.map, \
464 private_array_adaptive_map_try_ins_hndl_ret.index \
465 ); \
466 private_array_adaptive_map_try_ins_hndl_ret.status \
467 = CCC_ENTRY_VACANT; \
468 } \
469 } else if (private_array_adaptive_map_try_ins_hndl.status \
470 == CCC_ENTRY_OCCUPIED) { \
471 private_array_adaptive_map_try_ins_hndl_ret = (CCC_Handle){ \
472 .index = private_array_adaptive_map_try_ins_hndl.index, \
473 .status = private_array_adaptive_map_try_ins_hndl.status}; \
474 } \
475 } \
476 private_array_adaptive_map_try_ins_hndl_ret; \
477 }))
478
480#define CCC_private_array_adaptive_map_insert_or_assign_with( \
481 array_adaptive_map_pointer, \
482 key, \
483 private_allocator_pointer, \
484 type_compound_literal... \
485) \
486 (__extension__({ \
487 __auto_type private_array_adaptive_map_ins_or_assign_map_pointer \
488 = (array_adaptive_map_pointer); \
489 CCC_Handle private_array_adaptive_map_ins_or_assign_hndl_ret \
490 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
491 CCC_Allocator const *const private_array_adaptive_map_allocator \
492 = (private_allocator_pointer); \
493 if (private_array_adaptive_map_allocator \
494 && private_array_adaptive_map_ins_or_assign_map_pointer) { \
495 __auto_type private_array_adaptive_map_key = (key); \
496 struct CCC_Array_adaptive_map_handle \
497 private_array_adaptive_map_ins_or_assign_hndl \
498 = CCC_private_array_adaptive_map_handle( \
499 private_array_adaptive_map_ins_or_assign_map_pointer, \
500 (void *)&private_array_adaptive_map_key \
501 ); \
502 if (!(private_array_adaptive_map_ins_or_assign_hndl.status \
503 & CCC_ENTRY_OCCUPIED)) { \
504 private_array_adaptive_map_ins_or_assign_hndl_ret \
505 = (CCC_Handle){ \
506 .index = CCC_private_array_adaptive_map_allocate_slot( \
507 private_array_adaptive_map_ins_or_assign_hndl.map, \
508 private_array_adaptive_map_allocator \
509 ), \
510 .status = CCC_ENTRY_INSERT_ERROR, \
511 }; \
512 if (private_array_adaptive_map_ins_or_assign_hndl_ret.index) { \
513 *((typeof(type_compound_literal) *) \
514 CCC_private_array_adaptive_map_data_at( \
515 private_array_adaptive_map_ins_or_assign_map_pointer, \
516 private_array_adaptive_map_ins_or_assign_hndl_ret \
517 .index \
518 )) = type_compound_literal; \
519 *((typeof(private_array_adaptive_map_key) *) \
520 CCC_private_array_adaptive_map_key_at( \
521 private_array_adaptive_map_ins_or_assign_hndl \
522 .map, \
523 private_array_adaptive_map_ins_or_assign_hndl_ret \
524 .index \
525 )) = private_array_adaptive_map_key; \
526 CCC_private_array_adaptive_map_insert( \
527 private_array_adaptive_map_ins_or_assign_hndl.map, \
528 private_array_adaptive_map_ins_or_assign_hndl_ret \
529 .index \
530 ); \
531 private_array_adaptive_map_ins_or_assign_hndl_ret.status \
532 = CCC_ENTRY_VACANT; \
533 } \
534 } else if (private_array_adaptive_map_ins_or_assign_hndl.status \
535 == CCC_ENTRY_OCCUPIED) { \
536 *((typeof(type_compound_literal) *) \
537 CCC_private_array_adaptive_map_data_at( \
538 private_array_adaptive_map_ins_or_assign_hndl.map, \
539 private_array_adaptive_map_ins_or_assign_hndl.index \
540 )) = type_compound_literal; \
541 private_array_adaptive_map_ins_or_assign_hndl_ret \
542 = (CCC_Handle){ \
543 .index \
544 = private_array_adaptive_map_ins_or_assign_hndl.index, \
545 .status \
546 = private_array_adaptive_map_ins_or_assign_hndl \
547 .status, \
548 }; \
549 *((typeof(private_array_adaptive_map_key) *) \
550 CCC_private_array_adaptive_map_key_at( \
551 private_array_adaptive_map_ins_or_assign_hndl.map, \
552 private_array_adaptive_map_ins_or_assign_hndl.index \
553 )) = private_array_adaptive_map_key; \
554 } \
555 } \
556 private_array_adaptive_map_ins_or_assign_hndl_ret; \
557 }))
558
559/* NOLINTEND(readability-identifier-naming) */
560
561#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:376
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:512
CCC_Order
CCC_Order
A three-way comparison for comparison functions.
Definition: types.h:214
CCC_Entry_status
CCC_Entry_status
The status monitoring and entry state once it is obtained.
Definition: types.h:112