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#include "private_types.h"
26
27/* NOLINTBEGIN(readability-identifier-naming) */
28
31struct CCC_Tree_map_node
32{
34 struct CCC_Tree_map_node *branch[2];
36 struct CCC_Tree_map_node *parent;
38 uint8_t parity;
39};
40
53struct CCC_Tree_map
54{
56 struct CCC_Tree_map_node *root;
58 size_t count;
60 size_t key_offset;
63 size_t type_intruder_offset;
65 size_t sizeof_type;
67 CCC_Key_comparator *compare;
69 CCC_Allocator *allocate;
71 void *context;
72};
73
77struct CCC_Tree_map_entry
78{
80 struct CCC_Tree_map *map;
84 CCC_Order last_order;
86 struct CCC_Entry entry;
87};
88
93union CCC_Tree_map_entry_wrap
94{
96 struct CCC_Tree_map_entry private;
97};
98
99/*========================= Private Interface ============================*/
100
102void *CCC_private_tree_map_key_in_slot(struct CCC_Tree_map const *,
103 void const *slot);
105struct CCC_Tree_map_node *
106CCC_private_tree_map_node_in_slot(struct CCC_Tree_map const *,
107 void const *slot);
109struct CCC_Tree_map_entry
110CCC_private_tree_map_entry(struct CCC_Tree_map const *, void const *key);
112void *CCC_private_tree_map_insert(
113 struct CCC_Tree_map *, struct CCC_Tree_map_node *parent,
114 CCC_Order last_order, struct CCC_Tree_map_node *type_output_intruder);
115
116/*========================== Initialization ===========================*/
117
119#define CCC_private_tree_map_initialize( \
120 private_struct_name, private_node_node_field, private_key_node_field, \
121 private_key_order_fn, private_allocate, private_context_data) \
122 { \
123 .root = NULL, \
124 .count = 0, \
125 .key_offset = offsetof(private_struct_name, private_key_node_field), \
126 .type_intruder_offset \
127 = offsetof(private_struct_name, private_node_node_field), \
128 .sizeof_type = sizeof(private_struct_name), \
129 .compare = (private_key_order_fn), \
130 .allocate = (private_allocate), \
131 .context = (private_context_data), \
132 }
133
135#define CCC_private_tree_map_from( \
136 private_type_intruder_field_name, private_key_field_name, private_compare, \
137 private_allocate, private_destroy, private_context_data, \
138 private_compound_literal_array...) \
139 (__extension__({ \
140 typeof(*private_compound_literal_array) *private_tree_map_type_array \
141 = private_compound_literal_array; \
142 struct CCC_Tree_map private_map = CCC_private_tree_map_initialize( \
143 typeof(*private_tree_map_type_array), \
144 private_type_intruder_field_name, private_key_field_name, \
145 private_compare, private_allocate, private_context_data); \
146 if (private_map.allocate) \
147 { \
148 size_t const private_count \
149 = sizeof(private_compound_literal_array) \
150 / sizeof(*private_tree_map_type_array); \
151 for (size_t private_i = 0; private_i < private_count; ++private_i) \
152 { \
153 struct CCC_Tree_map_entry private_tree_map_entry \
154 = CCC_private_tree_map_entry( \
155 &private_map, \
156 (void *)&private_tree_map_type_array[private_i] \
157 .private_key_field_name); \
158 if (!(private_tree_map_entry.entry.status \
159 & CCC_ENTRY_OCCUPIED)) \
160 { \
161 typeof(*private_tree_map_type_array) *const \
162 private_new_slot \
163 = private_map.allocate((CCC_Allocator_context){ \
164 .input = NULL, \
165 .bytes = private_map.sizeof_type, \
166 .context = private_map.context, \
167 }); \
168 if (!private_new_slot) \
169 { \
170 (void)CCC_tree_map_clear(&private_map, \
171 private_destroy); \
172 break; \
173 } \
174 *private_new_slot \
175 = private_tree_map_type_array[private_i]; \
176 CCC_private_tree_map_insert( \
177 &private_map, \
178 CCC_private_tree_map_node_in_slot( \
179 &private_map, private_tree_map_entry.entry.type), \
180 private_tree_map_entry.last_order, \
181 CCC_private_tree_map_node_in_slot(&private_map, \
182 private_new_slot)); \
183 } \
184 else \
185 { \
186 struct CCC_Tree_map_node private_node_saved \
187 = *CCC_private_tree_map_node_in_slot( \
188 &private_map, private_tree_map_entry.entry.type); \
189 *((typeof(*private_tree_map_type_array) *) \
190 private_tree_map_entry.entry.type) \
191 = private_tree_map_type_array[private_i]; \
192 *CCC_private_tree_map_node_in_slot( \
193 &private_map, private_tree_map_entry.entry.type) \
194 = private_node_saved; \
195 } \
196 } \
197 } \
198 private_map; \
199 }))
200
201/*================== Helper Macros for Repeated Logic =================*/
202
204#define CCC_private_tree_map_new(Tree_map_entry) \
205 (__extension__({ \
206 void *private_tree_map_ins_allocate_ret = NULL; \
207 if ((Tree_map_entry)->map->allocate) \
208 { \
209 private_tree_map_ins_allocate_ret \
210 = (Tree_map_entry) \
211 ->map->allocate((CCC_Allocator_context){ \
212 .input = NULL, \
213 .bytes = (Tree_map_entry)->map->sizeof_type, \
214 .context = (Tree_map_entry)->map->context, \
215 }); \
216 } \
217 private_tree_map_ins_allocate_ret; \
218 }))
219
221#define CCC_private_tree_map_insert_key_val(Tree_map_entry, new_data, \
222 type_compound_literal...) \
223 (__extension__({ \
224 if (new_data) \
225 { \
226 *new_data = type_compound_literal; \
227 new_data = CCC_private_tree_map_insert( \
228 (Tree_map_entry)->map, \
229 CCC_private_tree_map_node_in_slot( \
230 (Tree_map_entry)->map, (Tree_map_entry)->entry.type), \
231 (Tree_map_entry)->last_order, \
232 CCC_private_tree_map_node_in_slot((Tree_map_entry)->map, \
233 new_data)); \
234 } \
235 }))
236
238#define CCC_private_tree_map_insert_and_copy_key( \
239 tree_map_insert_entry, tree_map_insert_entry_ret, key, \
240 type_compound_literal...) \
241 (__extension__({ \
242 typeof(type_compound_literal) *private_tree_map_new_ins_base \
243 = CCC_private_tree_map_new((&tree_map_insert_entry)); \
244 tree_map_insert_entry_ret = (struct CCC_Entry){ \
245 .type = private_tree_map_new_ins_base, \
246 .status = CCC_ENTRY_INSERT_ERROR, \
247 }; \
248 if (private_tree_map_new_ins_base) \
249 { \
250 *private_tree_map_new_ins_base = type_compound_literal; \
251 *((typeof(key) *)CCC_private_tree_map_key_in_slot( \
252 tree_map_insert_entry.map, private_tree_map_new_ins_base)) \
253 = key; \
254 (void)CCC_private_tree_map_insert( \
255 tree_map_insert_entry.map, \
256 CCC_private_tree_map_node_in_slot( \
257 tree_map_insert_entry.map, \
258 tree_map_insert_entry.entry.type), \
259 tree_map_insert_entry.last_order, \
260 CCC_private_tree_map_node_in_slot( \
261 tree_map_insert_entry.map, \
262 private_tree_map_new_ins_base)); \
263 } \
264 }))
265
266/*================== Core Macro Implementations =====================*/
267
269#define CCC_private_tree_map_and_modify_with(Tree_map_entry_pointer, \
270 type_name, closure_over_T...) \
271 (__extension__({ \
272 __auto_type private_tree_map_ent_pointer = (Tree_map_entry_pointer); \
273 struct CCC_Tree_map_entry private_tree_map_mod_ent \
274 = {.entry = {.status = CCC_ENTRY_ARGUMENT_ERROR}}; \
275 if (private_tree_map_ent_pointer) \
276 { \
277 private_tree_map_mod_ent = private_tree_map_ent_pointer->private; \
278 if (private_tree_map_mod_ent.entry.status & CCC_ENTRY_OCCUPIED) \
279 { \
280 type_name *const T = private_tree_map_mod_ent.entry.type; \
281 if (T) \
282 { \
283 closure_over_T \
284 } \
285 } \
286 } \
287 private_tree_map_mod_ent; \
288 }))
289
291#define CCC_private_tree_map_or_insert_with(Tree_map_entry_pointer, \
292 type_compound_literal...) \
293 (__extension__({ \
294 __auto_type private_or_ins_entry_pointer = (Tree_map_entry_pointer); \
295 typeof(type_compound_literal) *private_tree_map_or_ins_ret = NULL; \
296 if (private_or_ins_entry_pointer) \
297 { \
298 if (private_or_ins_entry_pointer->private.entry.status \
299 == CCC_ENTRY_OCCUPIED) \
300 { \
301 private_tree_map_or_ins_ret \
302 = private_or_ins_entry_pointer->private.entry.type; \
303 } \
304 else \
305 { \
306 private_tree_map_or_ins_ret = CCC_private_tree_map_new( \
307 &private_or_ins_entry_pointer->private); \
308 CCC_private_tree_map_insert_key_val( \
309 &private_or_ins_entry_pointer->private, \
310 private_tree_map_or_ins_ret, type_compound_literal); \
311 } \
312 } \
313 private_tree_map_or_ins_ret; \
314 }))
315
317#define CCC_private_tree_map_insert_entry_with(Tree_map_entry_pointer, \
318 type_compound_literal...) \
319 (__extension__({ \
320 __auto_type private_ins_entry_pointer = (Tree_map_entry_pointer); \
321 typeof(type_compound_literal) *private_tree_map_ins_ent_ret = NULL; \
322 if (private_ins_entry_pointer) \
323 { \
324 if (!(private_ins_entry_pointer->private.entry.status \
325 & CCC_ENTRY_OCCUPIED)) \
326 { \
327 private_tree_map_ins_ent_ret = CCC_private_tree_map_new( \
328 &private_ins_entry_pointer->private); \
329 CCC_private_tree_map_insert_key_val( \
330 &private_ins_entry_pointer->private, \
331 private_tree_map_ins_ent_ret, type_compound_literal); \
332 } \
333 else if (private_ins_entry_pointer->private.entry.status \
334 == CCC_ENTRY_OCCUPIED) \
335 { \
336 struct CCC_Tree_map_node private_ins_ent_saved \
337 = *CCC_private_tree_map_node_in_slot( \
338 private_ins_entry_pointer->private.map, \
339 private_ins_entry_pointer->private.entry.type); \
340 *((typeof(private_tree_map_ins_ent_ret)) \
341 private_ins_entry_pointer->private.entry.type) \
342 = type_compound_literal; \
343 *CCC_private_tree_map_node_in_slot( \
344 private_ins_entry_pointer->private.map, \
345 private_ins_entry_pointer->private.entry.type) \
346 = private_ins_ent_saved; \
347 private_tree_map_ins_ent_ret \
348 = private_ins_entry_pointer->private.entry.type; \
349 } \
350 } \
351 private_tree_map_ins_ent_ret; \
352 }))
353
355#define CCC_private_tree_map_try_insert_with(Tree_map_pointer, key, \
356 type_compound_literal...) \
357 (__extension__({ \
358 struct CCC_Tree_map *const private_try_ins_map_pointer \
359 = (Tree_map_pointer); \
360 struct CCC_Entry private_tree_map_try_ins_ent_ret \
361 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
362 if (private_try_ins_map_pointer) \
363 { \
364 __auto_type private_tree_map_key = (key); \
365 struct CCC_Tree_map_entry private_tree_map_try_ins_ent \
366 = CCC_private_tree_map_entry(private_try_ins_map_pointer, \
367 (void *)&private_tree_map_key); \
368 if (!(private_tree_map_try_ins_ent.entry.status \
369 & CCC_ENTRY_OCCUPIED)) \
370 { \
371 CCC_private_tree_map_insert_and_copy_key( \
372 private_tree_map_try_ins_ent, \
373 private_tree_map_try_ins_ent_ret, private_tree_map_key, \
374 type_compound_literal); \
375 } \
376 else if (private_tree_map_try_ins_ent.entry.status \
377 == CCC_ENTRY_OCCUPIED) \
378 { \
379 private_tree_map_try_ins_ent_ret \
380 = private_tree_map_try_ins_ent.entry; \
381 } \
382 } \
383 private_tree_map_try_ins_ent_ret; \
384 }))
385
387#define CCC_private_tree_map_insert_or_assign_with(Tree_map_pointer, key, \
388 type_compound_literal...) \
389 (__extension__({ \
390 struct CCC_Tree_map *const private_ins_or_assign_map_pointer \
391 = (Tree_map_pointer); \
392 struct CCC_Entry private_tree_map_ins_or_assign_ent_ret \
393 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
394 if (private_ins_or_assign_map_pointer) \
395 { \
396 __auto_type private_tree_map_key = (key); \
397 struct CCC_Tree_map_entry private_tree_map_ins_or_assign_ent \
398 = CCC_private_tree_map_entry( \
399 private_ins_or_assign_map_pointer, \
400 (void *)&private_tree_map_key); \
401 if (!(private_tree_map_ins_or_assign_ent.entry.status \
402 & CCC_ENTRY_OCCUPIED)) \
403 { \
404 CCC_private_tree_map_insert_and_copy_key( \
405 private_tree_map_ins_or_assign_ent, \
406 private_tree_map_ins_or_assign_ent_ret, \
407 private_tree_map_key, type_compound_literal); \
408 } \
409 else if (private_tree_map_ins_or_assign_ent.entry.status \
410 == CCC_ENTRY_OCCUPIED) \
411 { \
412 struct CCC_Tree_map_node private_ins_ent_saved \
413 = *CCC_private_tree_map_node_in_slot( \
414 private_tree_map_ins_or_assign_ent.map, \
415 private_tree_map_ins_or_assign_ent.entry.type); \
416 *((typeof(type_compound_literal) *) \
417 private_tree_map_ins_or_assign_ent.entry.type) \
418 = type_compound_literal; \
419 *CCC_private_tree_map_node_in_slot( \
420 private_tree_map_ins_or_assign_ent.map, \
421 private_tree_map_ins_or_assign_ent.entry.type) \
422 = private_ins_ent_saved; \
423 private_tree_map_ins_or_assign_ent_ret \
424 = private_tree_map_ins_or_assign_ent.entry; \
425 *((typeof(private_tree_map_key) *) \
426 CCC_private_tree_map_key_in_slot( \
427 private_tree_map_ins_or_assign_ent.map, \
428 private_tree_map_ins_or_assign_ent_ret.type)) \
429 = private_tree_map_key; \
430 } \
431 } \
432 private_tree_map_ins_or_assign_ent_ret; \
433 }))
434
435/* NOLINTEND(readability-identifier-naming) */
436
437#endif /* CCC_PRIVATE_REALTIME__ADAPTIVE_MAP_H */
CCC_Entry
Definition: private_types.h:53
CCC_Tree_map_entry
Definition: private_tree_map.h:78
CCC_Tree_map_entry::entry
struct CCC_Entry entry
Definition: private_tree_map.h:86
CCC_Tree_map_entry::last_order
CCC_Order last_order
Definition: private_tree_map.h:84
CCC_Tree_map_entry::map
struct CCC_Tree_map * map
Definition: private_tree_map.h:80
CCC_Tree_map_node
Definition: private_tree_map.h:32
CCC_Tree_map_node::parity
uint8_t parity
Definition: private_tree_map.h:38
CCC_Tree_map_node::branch
struct CCC_Tree_map_node * branch[2]
Definition: private_tree_map.h:34
CCC_Tree_map_node::parent
struct CCC_Tree_map_node * parent
Definition: private_tree_map.h:36
CCC_Tree_map
Definition: private_tree_map.h:54
CCC_Tree_map::context
void * context
Definition: private_tree_map.h:71
CCC_Tree_map::count
size_t count
Definition: private_tree_map.h:58
CCC_Tree_map::root
struct CCC_Tree_map_node * root
Definition: private_tree_map.h:56
CCC_Tree_map::allocate
CCC_Allocator * allocate
Definition: private_tree_map.h:69
CCC_Tree_map::sizeof_type
size_t sizeof_type
Definition: private_tree_map.h:65
CCC_Tree_map::key_offset
size_t key_offset
Definition: private_tree_map.h:60
CCC_Tree_map::type_intruder_offset
size_t type_intruder_offset
Definition: private_tree_map.h:63
CCC_Tree_map::compare
CCC_Key_comparator * compare
Definition: private_tree_map.h:67
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_Tree_map_entry_wrap
Definition: private_tree_map.h:94
CCC_Tree_map_entry_wrap::private
struct CCC_Tree_map_entry private
Definition: private_tree_map.h:96