C Container Collection (CCC)
Loading...
Searching...
No Matches
private_tree_map.h
1
16#ifndef CCC_PRIVATE_TREE_MAP_H
17#define CCC_PRIVATE_TREE_MAP_H
18
20#include <stddef.h>
21#include <stdint.h>
24#include "../types.h"
25
26/* NOLINTBEGIN(readability-identifier-naming) */
27
30struct CCC_Tree_map_node {
32 struct CCC_Tree_map_node *branch[2];
34 struct CCC_Tree_map_node *parent;
36 uint8_t parity;
37};
38
51struct CCC_Tree_map {
53 struct CCC_Tree_map_node *root;
55 size_t count;
57 size_t key_offset;
60 size_t type_intruder_offset;
62 size_t sizeof_type;
64 CCC_Key_comparator comparator;
65};
66
70struct CCC_Tree_map_entry {
72 struct CCC_Tree_map *map;
76 CCC_Order last_order;
78 CCC_Entry entry;
79};
80
81/*========================= Private Interface ============================*/
82
84void *
85CCC_private_tree_map_key_in_slot(struct CCC_Tree_map const *, void const *slot);
87struct CCC_Tree_map_node *CCC_private_tree_map_node_in_slot(
88 struct CCC_Tree_map const *, void const *slot
89);
91struct CCC_Tree_map_entry
92CCC_private_tree_map_entry(struct CCC_Tree_map const *, void const *key);
94void *CCC_private_tree_map_insert(
95 struct CCC_Tree_map *,
96 struct CCC_Tree_map_node *parent,
97 CCC_Order last_order,
98 struct CCC_Tree_map_node *type_output_intruder
99);
100
101/*========================== Initialization ===========================*/
102
104#define CCC_private_tree_map_for( \
105 private_struct_name, \
106 private_node_field, \
107 private_key_node_field, \
108 private_comparator... \
109) \
110 (struct CCC_Tree_map) { \
111 .root = NULL, .count = 0, \
112 .key_offset = offsetof(private_struct_name, private_key_node_field), \
113 .type_intruder_offset \
114 = offsetof(private_struct_name, private_node_field), \
115 .sizeof_type = sizeof(private_struct_name), \
116 .comparator = (private_comparator), \
117 }
118
120#define CCC_private_tree_map_default( \
121 private_struct_name, \
122 private_node_field, \
123 private_key_node_field, \
124 private_comparator... \
125) \
126 CCC_private_tree_map_for( \
127 private_struct_name, \
128 private_node_field, \
129 private_key_node_field, \
130 private_comparator \
131 )
132
134#define CCC_private_tree_map_from( \
135 private_type_intruder_field_name, \
136 private_key_field_name, \
137 private_comparator, \
138 private_allocator, \
139 private_destructor, \
140 private_compound_literal_array... \
141) \
142 (struct { struct CCC_Tree_map private; }){(__extension__({ \
143 typeof(*private_compound_literal_array) *private_tree_map_type_array \
144 = private_compound_literal_array; \
145 struct CCC_Tree_map private_map = CCC_private_tree_map_default( \
146 typeof(*private_tree_map_type_array), \
147 private_type_intruder_field_name, \
148 private_key_field_name, \
149 private_comparator \
150 ); \
151 CCC_Allocator const *const private_tree_map_allocator \
152 = &(private_allocator); \
153 if (private_tree_map_allocator->allocate) { \
154 size_t const private_count \
155 = sizeof(private_compound_literal_array) \
156 / sizeof(*private_tree_map_type_array); \
157 for (size_t private_i = 0; private_i < private_count; \
158 ++private_i) { \
159 struct CCC_Tree_map_entry private_tree_map_entry \
160 = CCC_private_tree_map_entry( \
161 &private_map, \
162 (void *)&private_tree_map_type_array[private_i] \
163 .private_key_field_name \
164 ); \
165 if (!(private_tree_map_entry.entry.status \
166 & CCC_ENTRY_OCCUPIED)) { \
167 typeof(*private_tree_map_type_array) *const \
168 private_new_slot \
169 = private_tree_map_allocator->allocate(( \
170 CCC_Allocator_arguments \
171 ){ \
172 .input = NULL, \
173 .bytes = private_map.sizeof_type, \
174 .context = private_tree_map_allocator->context, \
175 }); \
176 if (!private_new_slot) { \
177 (void)CCC_tree_map_clear( \
178 &private_map, \
179 &private_destructor, \
180 private_tree_map_allocator \
181 ); \
182 break; \
183 } \
184 *private_new_slot \
185 = private_tree_map_type_array[private_i]; \
186 CCC_private_tree_map_insert( \
187 &private_map, \
188 CCC_private_tree_map_node_in_slot( \
189 &private_map, private_tree_map_entry.entry.type \
190 ), \
191 private_tree_map_entry.last_order, \
192 CCC_private_tree_map_node_in_slot( \
193 &private_map, private_new_slot \
194 ) \
195 ); \
196 } else { \
197 struct CCC_Tree_map_node private_node_saved \
198 = *CCC_private_tree_map_node_in_slot( \
199 &private_map, private_tree_map_entry.entry.type \
200 ); \
201 *((typeof(*private_tree_map_type_array) *) \
202 private_tree_map_entry.entry.type) \
203 = private_tree_map_type_array[private_i]; \
204 *CCC_private_tree_map_node_in_slot( \
205 &private_map, private_tree_map_entry.entry.type \
206 ) = private_node_saved; \
207 } \
208 } \
209 } \
210 private_map; \
211 }))}.private
212
213/*================== Helper Macros for Repeated Logic =================*/
214
216#define CCC_private_tree_map_new( \
217 private_tree_map_entry, private_allocator_pointer \
218) \
219 (__extension__({ \
220 void *private_tree_map_ins_allocate_ret = NULL; \
221 if ((private_allocator_pointer)->allocate) { \
222 private_tree_map_ins_allocate_ret \
223 = (private_allocator_pointer) \
224 ->allocate((CCC_Allocator_arguments){ \
225 .input = NULL, \
226 .bytes = (private_tree_map_entry)->map->sizeof_type, \
227 .context = (private_allocator_pointer)->context, \
228 }); \
229 } \
230 private_tree_map_ins_allocate_ret; \
231 }))
232
234#define CCC_private_tree_map_insert_key_val( \
235 private_tree_map_entry, new_data, type_compound_literal... \
236) \
237 (__extension__({ \
238 if (new_data) { \
239 *new_data = type_compound_literal; \
240 new_data = CCC_private_tree_map_insert( \
241 (private_tree_map_entry)->map, \
242 CCC_private_tree_map_node_in_slot( \
243 (private_tree_map_entry)->map, \
244 (private_tree_map_entry)->entry.type \
245 ), \
246 (private_tree_map_entry)->last_order, \
247 CCC_private_tree_map_node_in_slot( \
248 (private_tree_map_entry)->map, new_data \
249 ) \
250 ); \
251 } \
252 }))
253
255#define CCC_private_tree_map_insert_and_copy_key( \
256 tree_map_insert_entry, \
257 tree_map_insert_entry_ret, \
258 key, \
259 private_allocator_pointer, \
260 type_compound_literal... \
261) \
262 (__extension__({ \
263 typeof(type_compound_literal) *private_tree_map_new_ins_base \
264 = CCC_private_tree_map_new( \
265 (&tree_map_insert_entry), private_allocator_pointer \
266 ); \
267 tree_map_insert_entry_ret = (CCC_Entry){ \
268 .type = private_tree_map_new_ins_base, \
269 .status = CCC_ENTRY_INSERT_ERROR, \
270 }; \
271 if (private_tree_map_new_ins_base) { \
272 tree_map_insert_entry_ret.status = CCC_ENTRY_VACANT; \
273 *private_tree_map_new_ins_base = type_compound_literal; \
274 *((typeof(key) *)CCC_private_tree_map_key_in_slot( \
275 tree_map_insert_entry.map, private_tree_map_new_ins_base \
276 )) = key; \
277 (void)CCC_private_tree_map_insert( \
278 tree_map_insert_entry.map, \
279 CCC_private_tree_map_node_in_slot( \
280 tree_map_insert_entry.map, \
281 tree_map_insert_entry.entry.type \
282 ), \
283 tree_map_insert_entry.last_order, \
284 CCC_private_tree_map_node_in_slot( \
285 tree_map_insert_entry.map, private_tree_map_new_ins_base \
286 ) \
287 ); \
288 } \
289 }))
290
291/*================== Core Macro Implementations =====================*/
292
294#define CCC_private_tree_map_and_modify_with( \
295 private_tree_map_entry_pointer, \
296 closure_parameter, \
297 closure_over_closure_parameter... \
298) \
299 (__extension__({ \
300 __auto_type private_tree_map_ent_pointer \
301 = (private_tree_map_entry_pointer); \
302 struct CCC_Tree_map_entry private_tree_map_mod_ent \
303 = {.entry = {.status = CCC_ENTRY_ARGUMENT_ERROR}}; \
304 if (private_tree_map_ent_pointer) { \
305 private_tree_map_mod_ent = *private_tree_map_ent_pointer; \
306 if (private_tree_map_mod_ent.entry.status & CCC_ENTRY_OCCUPIED) { \
307 closure_parameter = private_tree_map_mod_ent.entry.type; \
308 closure_over_closure_parameter \
309 } \
310 } \
311 private_tree_map_mod_ent; \
312 }))
313
315#define CCC_private_tree_map_or_insert_with( \
316 private_tree_map_entry_pointer, \
317 private_allocator_pointer, \
318 type_compound_literal... \
319) \
320 (__extension__({ \
321 __auto_type private_or_ins_entry_pointer \
322 = (private_tree_map_entry_pointer); \
323 typeof(type_compound_literal) *private_tree_map_or_ins_ret = NULL; \
324 CCC_Allocator const *const private_tree_map_allocator \
325 = (private_allocator_pointer); \
326 if (private_tree_map_allocator && private_or_ins_entry_pointer) { \
327 if (private_or_ins_entry_pointer->entry.status \
328 == CCC_ENTRY_OCCUPIED) { \
329 private_tree_map_or_ins_ret \
330 = private_or_ins_entry_pointer->entry.type; \
331 } else { \
332 private_tree_map_or_ins_ret = CCC_private_tree_map_new( \
333 private_or_ins_entry_pointer, private_tree_map_allocator \
334 ); \
335 CCC_private_tree_map_insert_key_val( \
336 private_or_ins_entry_pointer, \
337 private_tree_map_or_ins_ret, \
338 type_compound_literal \
339 ); \
340 } \
341 } \
342 private_tree_map_or_ins_ret; \
343 }))
344
346#define CCC_private_tree_map_insert_entry_with( \
347 private_tree_map_entry_pointer, \
348 private_allocator_pointer, \
349 type_compound_literal... \
350) \
351 (__extension__({ \
352 __auto_type private_ins_entry_pointer \
353 = (private_tree_map_entry_pointer); \
354 typeof(type_compound_literal) *private_tree_map_ins_ent_ret = NULL; \
355 CCC_Allocator const *const private_tree_map_allocator \
356 = (private_allocator_pointer); \
357 if (private_tree_map_allocator && private_ins_entry_pointer) { \
358 if (!(private_ins_entry_pointer->entry.status \
359 & CCC_ENTRY_OCCUPIED)) { \
360 private_tree_map_ins_ent_ret = CCC_private_tree_map_new( \
361 private_ins_entry_pointer, private_allocator_pointer \
362 ); \
363 CCC_private_tree_map_insert_key_val( \
364 private_ins_entry_pointer, \
365 private_tree_map_ins_ent_ret, \
366 type_compound_literal \
367 ); \
368 } else if (private_ins_entry_pointer->entry.status \
369 == CCC_ENTRY_OCCUPIED) { \
370 struct CCC_Tree_map_node private_ins_ent_saved \
371 = *CCC_private_tree_map_node_in_slot( \
372 private_ins_entry_pointer->map, \
373 private_ins_entry_pointer->entry.type \
374 ); \
375 *((typeof(private_tree_map_ins_ent_ret)) \
376 private_ins_entry_pointer->entry.type) \
377 = type_compound_literal; \
378 *CCC_private_tree_map_node_in_slot( \
379 private_ins_entry_pointer->map, \
380 private_ins_entry_pointer->entry.type \
381 ) = private_ins_ent_saved; \
382 private_tree_map_ins_ent_ret \
383 = private_ins_entry_pointer->entry.type; \
384 } \
385 } \
386 private_tree_map_ins_ent_ret; \
387 }))
388
390#define CCC_private_tree_map_try_insert_with( \
391 Tree_map_pointer, key, private_allocator_pointer, type_compound_literal... \
392) \
393 (__extension__({ \
394 struct CCC_Tree_map *const private_try_ins_map_pointer \
395 = (Tree_map_pointer); \
396 CCC_Entry private_tree_map_try_ins_ent_ret \
397 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
398 CCC_Allocator const *const private_tree_map_allocator \
399 = (private_allocator_pointer); \
400 if (private_tree_map_allocator && private_try_ins_map_pointer) { \
401 __auto_type private_tree_map_key = (key); \
402 struct CCC_Tree_map_entry private_tree_map_try_ins_ent \
403 = CCC_private_tree_map_entry( \
404 private_try_ins_map_pointer, (void *)&private_tree_map_key \
405 ); \
406 if (!(private_tree_map_try_ins_ent.entry.status \
407 & CCC_ENTRY_OCCUPIED)) { \
408 CCC_private_tree_map_insert_and_copy_key( \
409 private_tree_map_try_ins_ent, \
410 private_tree_map_try_ins_ent_ret, \
411 private_tree_map_key, \
412 private_tree_map_allocator, \
413 type_compound_literal \
414 ); \
415 } else if (private_tree_map_try_ins_ent.entry.status \
416 == CCC_ENTRY_OCCUPIED) { \
417 private_tree_map_try_ins_ent_ret \
418 = private_tree_map_try_ins_ent.entry; \
419 } \
420 } \
421 private_tree_map_try_ins_ent_ret; \
422 }))
423
425#define CCC_private_tree_map_insert_or_assign_with( \
426 Tree_map_pointer, key, private_allocator_pointer, type_compound_literal... \
427) \
428 (__extension__({ \
429 struct CCC_Tree_map *const private_ins_or_assign_map_pointer \
430 = (Tree_map_pointer); \
431 CCC_Entry private_tree_map_ins_or_assign_ent_ret \
432 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
433 CCC_Allocator const *const private_tree_map_allocator \
434 = (private_allocator_pointer); \
435 if (private_tree_map_allocator && private_ins_or_assign_map_pointer) { \
436 __auto_type private_tree_map_key = (key); \
437 struct CCC_Tree_map_entry private_tree_map_ins_or_assign_ent \
438 = CCC_private_tree_map_entry( \
439 private_ins_or_assign_map_pointer, \
440 (void *)&private_tree_map_key \
441 ); \
442 if (!(private_tree_map_ins_or_assign_ent.entry.status \
443 & CCC_ENTRY_OCCUPIED)) { \
444 CCC_private_tree_map_insert_and_copy_key( \
445 private_tree_map_ins_or_assign_ent, \
446 private_tree_map_ins_or_assign_ent_ret, \
447 private_tree_map_key, \
448 private_tree_map_allocator, \
449 type_compound_literal \
450 ); \
451 } else if (private_tree_map_ins_or_assign_ent.entry.status \
452 == CCC_ENTRY_OCCUPIED) { \
453 struct CCC_Tree_map_node private_ins_ent_saved \
454 = *CCC_private_tree_map_node_in_slot( \
455 private_tree_map_ins_or_assign_ent.map, \
456 private_tree_map_ins_or_assign_ent.entry.type \
457 ); \
458 *((typeof(type_compound_literal) *) \
459 private_tree_map_ins_or_assign_ent.entry.type) \
460 = type_compound_literal; \
461 *CCC_private_tree_map_node_in_slot( \
462 private_tree_map_ins_or_assign_ent.map, \
463 private_tree_map_ins_or_assign_ent.entry.type \
464 ) = private_ins_ent_saved; \
465 private_tree_map_ins_or_assign_ent_ret \
466 = private_tree_map_ins_or_assign_ent.entry; \
467 *((typeof(private_tree_map_key) *) \
468 CCC_private_tree_map_key_in_slot( \
469 private_tree_map_ins_or_assign_ent.map, \
470 private_tree_map_ins_or_assign_ent_ret.type \
471 )) = private_tree_map_key; \
472 } \
473 } \
474 private_tree_map_ins_or_assign_ent_ret; \
475 }))
476
477/* NOLINTEND(readability-identifier-naming) */
478
479#endif /* CCC_PRIVATE_REALTIME__ADAPTIVE_MAP_H */
CCC_Entry
An Occupied or Vacant position in a searchable container.
Definition: types.h:135
CCC_Key_comparator
The type passed by reference to any container function that may need to compare keys....
Definition: types.h:512
CCC_Tree_map_entry
Definition: private_tree_map.h:70
CCC_Tree_map_entry::entry
CCC_Entry entry
Definition: private_tree_map.h:78
CCC_Tree_map_entry::last_order
CCC_Order last_order
Definition: private_tree_map.h:76
CCC_Tree_map_entry::map
struct CCC_Tree_map * map
Definition: private_tree_map.h:72
CCC_Tree_map_node
Definition: private_tree_map.h:30
CCC_Tree_map_node::parity
uint8_t parity
Definition: private_tree_map.h:36
CCC_Tree_map_node::branch
struct CCC_Tree_map_node * branch[2]
Definition: private_tree_map.h:32
CCC_Tree_map_node::parent
struct CCC_Tree_map_node * parent
Definition: private_tree_map.h:34
CCC_Tree_map
Definition: private_tree_map.h:51
CCC_Tree_map::comparator
CCC_Key_comparator comparator
Definition: private_tree_map.h:64
CCC_Tree_map::count
size_t count
Definition: private_tree_map.h:55
CCC_Tree_map::root
struct CCC_Tree_map_node * root
Definition: private_tree_map.h:53
CCC_Tree_map::sizeof_type
size_t sizeof_type
Definition: private_tree_map.h:62
CCC_Tree_map::key_offset
size_t key_offset
Definition: private_tree_map.h:57
CCC_Tree_map::type_intruder_offset
size_t type_intruder_offset
Definition: private_tree_map.h:60
CCC_Order
CCC_Order
A three-way comparison for comparison functions.
Definition: types.h:214