C Container Collection (CCC)
Loading...
Searching...
No Matches
private_adaptive_map.h
Go to the documentation of this file.
1
28#ifndef CCC_PRIVATE_ADAPTIVE_MAP_H
29#define CCC_PRIVATE_ADAPTIVE_MAP_H
30
32#include <stddef.h>
35#include "../types.h"
36
37/* NOLINTBEGIN(readability-identifier-naming) */
38
42struct CCC_Adaptive_map_node {
44 struct CCC_Adaptive_map_node *branch[2];
46 struct CCC_Adaptive_map_node *parent;
47};
48
56struct CCC_Adaptive_map {
58 struct CCC_Adaptive_map_node *root;
60 size_t count;
62 size_t sizeof_type;
64 size_t type_intruder_offset;
66 size_t key_offset;
68 CCC_Key_comparator comparator;
69};
70
85struct CCC_Adaptive_map_entry {
87 struct CCC_Adaptive_map *map;
89 CCC_Entry entry;
90};
91
92/*========================== Private Interface ============================*/
93
95void *CCC_private_adaptive_map_key_in_slot(
96 struct CCC_Adaptive_map const *, void const *
97);
99struct CCC_Adaptive_map_node *CCC_private_adaptive_map_node_in_slot(
100 struct CCC_Adaptive_map const *, void const *
101);
103struct CCC_Adaptive_map_entry
104CCC_private_adaptive_map_entry(struct CCC_Adaptive_map *, void const *);
106void *CCC_private_adaptive_map_insert(
107 struct CCC_Adaptive_map *, struct CCC_Adaptive_map_node *
108);
109
110/*====================== Macro Implementations ========================*/
111
113#define CCC_private_adaptive_map_default( \
114 private_struct_name, \
115 private_node_node_field, \
116 private_key_node_field, \
117 private_comparator... \
118) \
119 (struct CCC_Adaptive_map) { \
120 .sizeof_type = sizeof(private_struct_name), \
121 .type_intruder_offset \
122 = offsetof(private_struct_name, private_node_node_field), \
123 .key_offset = offsetof(private_struct_name, private_key_node_field), \
124 .comparator = private_comparator, \
125 }
126
128#define CCC_private_adaptive_map_for( \
129 private_struct_name, \
130 private_node_node_field, \
131 private_key_node_field, \
132 private_comparator... \
133) \
134 (struct CCC_Adaptive_map) { \
135 .root = NULL, .count = 0, .sizeof_type = sizeof(private_struct_name), \
136 .type_intruder_offset \
137 = offsetof(private_struct_name, private_node_node_field), \
138 .key_offset = offsetof(private_struct_name, private_key_node_field), \
139 .comparator = private_comparator, \
140 }
141
143#define CCC_private_adaptive_map_from( \
144 private_type_intruder_field_name, \
145 private_key_field_name, \
146 private_comparator, \
147 private_allocator, \
148 private_destructor, \
149 private_compound_literal_array... \
150) \
151 (struct { struct CCC_Adaptive_map private; }){(__extension__({ \
152 typeof(*private_compound_literal_array) \
153 *private_adaptive_map_type_array = private_compound_literal_array; \
154 struct CCC_Adaptive_map private_map \
155 = CCC_private_adaptive_map_default( \
156 typeof(*private_adaptive_map_type_array), \
157 private_type_intruder_field_name, \
158 private_key_field_name, \
159 private_comparator \
160 ); \
161 CCC_Allocator const private_adaptive_map_allocator \
162 = private_allocator; \
163 if (private_adaptive_map_allocator.allocate) { \
164 size_t const private_count \
165 = sizeof(private_compound_literal_array) \
166 / sizeof(*private_adaptive_map_type_array); \
167 for (size_t private_i = 0; private_i < private_count; \
168 ++private_i) { \
169 struct CCC_Adaptive_map_entry private_adaptive_map_entry \
170 = CCC_private_adaptive_map_entry( \
171 &private_map, \
172 (void *)&private_adaptive_map_type_array[private_i] \
173 .private_key_field_name \
174 ); \
175 if (!(private_adaptive_map_entry.entry.status \
176 & CCC_ENTRY_OCCUPIED)) { \
177 typeof(*private_adaptive_map_type_array) *const \
178 private_new_slot \
179 = private_adaptive_map_allocator.allocate(( \
180 CCC_Allocator_arguments \
181 ){ \
182 .input = NULL, \
183 .bytes = private_map.sizeof_type, \
184 .context = private_adaptive_map_allocator.context, \
185 }); \
186 if (!private_new_slot) { \
187 (void)CCC_adaptive_map_clear( \
188 &private_map, \
189 &(private_destructor), \
190 &private_adaptive_map_allocator \
191 ); \
192 break; \
193 } \
194 *private_new_slot \
195 = private_adaptive_map_type_array[private_i]; \
196 CCC_private_adaptive_map_insert( \
197 &private_map, \
198 CCC_private_adaptive_map_node_in_slot( \
199 &private_map, private_new_slot \
200 ) \
201 ); \
202 } else { \
203 struct CCC_Adaptive_map_node private_node_saved \
204 = *CCC_private_adaptive_map_node_in_slot( \
205 &private_map, \
206 private_adaptive_map_entry.entry.type \
207 ); \
208 *((typeof(*private_adaptive_map_type_array) *) \
209 private_adaptive_map_entry.entry.type) \
210 = private_adaptive_map_type_array[private_i]; \
211 *CCC_private_adaptive_map_node_in_slot( \
212 &private_map, private_adaptive_map_entry.entry.type \
213 ) = private_node_saved; \
214 } \
215 } \
216 } \
217 private_map; \
218 }))}.private
219
221#define CCC_private_adaptive_map_new(adaptive_map_entry, private_allocator) \
222 (__extension__({ \
223 void *private_adaptive_map_ins_allocate_ret = NULL; \
224 if ((private_allocator)->allocate) { \
225 private_adaptive_map_ins_allocate_ret \
226 = (private_allocator) \
227 ->allocate((CCC_Allocator_arguments){ \
228 .input = NULL, \
229 .bytes = (adaptive_map_entry)->map->sizeof_type, \
230 .context = (private_allocator)->context, \
231 }); \
232 } \
233 private_adaptive_map_ins_allocate_ret; \
234 }))
235
237#define CCC_private_adaptive_map_insert_key_val( \
238 adaptive_map_entry, new_data, type_compound_literal... \
239) \
240 (__extension__({ \
241 if (new_data) { \
242 *new_data = type_compound_literal; \
243 new_data = CCC_private_adaptive_map_insert( \
244 (adaptive_map_entry)->map, \
245 CCC_private_adaptive_map_node_in_slot( \
246 (adaptive_map_entry)->map, new_data \
247 ) \
248 ); \
249 } \
250 }))
251
253#define CCC_private_adaptive_map_insert_and_copy_key( \
254 om_insert_entry, \
255 om_insert_entry_ret, \
256 key, \
257 private_allocator, \
258 type_compound_literal... \
259) \
260 (__extension__({ \
261 typeof(type_compound_literal) *private_adaptive_map_new_ins_base \
262 = CCC_private_adaptive_map_new( \
263 (&om_insert_entry), private_allocator \
264 ); \
265 om_insert_entry_ret = (CCC_Entry){ \
266 .type = private_adaptive_map_new_ins_base, \
267 .status = CCC_ENTRY_INSERT_ERROR, \
268 }; \
269 if (private_adaptive_map_new_ins_base) { \
270 om_insert_entry_ret.status = CCC_ENTRY_VACANT; \
271 *((typeof(type_compound_literal) *) \
272 private_adaptive_map_new_ins_base) = type_compound_literal; \
273 *((typeof(key) *)CCC_private_adaptive_map_key_in_slot( \
274 om_insert_entry.map, private_adaptive_map_new_ins_base \
275 )) = key; \
276 (void)CCC_private_adaptive_map_insert( \
277 om_insert_entry.map, \
278 CCC_private_adaptive_map_node_in_slot( \
279 om_insert_entry.map, private_adaptive_map_new_ins_base \
280 ) \
281 ); \
282 } \
283 }))
284
285/*===================== Core Macro Implementations ==================*/
286
288#define CCC_private_adaptive_map_and_modify_with( \
289 adaptive_map_entry_pointer, \
290 closure_parameter, \
291 closure_over_closure_parameter... \
292) \
293 (__extension__({ \
294 struct CCC_Adaptive_map_entry const *const \
295 private_adaptive_map_ent_pointer = (adaptive_map_entry_pointer); \
296 struct CCC_Adaptive_map_entry private_adaptive_map_mod_ent \
297 = {.entry = {.status = CCC_ENTRY_ARGUMENT_ERROR}}; \
298 if (private_adaptive_map_ent_pointer) { \
299 private_adaptive_map_mod_ent = *private_adaptive_map_ent_pointer; \
300 if (private_adaptive_map_mod_ent.entry.status \
301 & CCC_ENTRY_OCCUPIED) { \
302 closure_parameter = private_adaptive_map_mod_ent.entry.type; \
303 closure_over_closure_parameter \
304 } \
305 } \
306 private_adaptive_map_mod_ent; \
307 }))
308
310#define CCC_private_adaptive_map_or_insert_with( \
311 adaptive_map_entry_pointer, \
312 private_allocator_pointer, \
313 type_compound_literal... \
314) \
315 (__extension__({ \
316 struct CCC_Adaptive_map_entry const *const \
317 private_or_ins_entry_pointer = (adaptive_map_entry_pointer); \
318 typeof(type_compound_literal) *private_or_ins_ret = NULL; \
319 CCC_Allocator const *const private_adaptive_map_allocator \
320 = (private_allocator_pointer); \
321 if (private_adaptive_map_allocator && private_or_ins_entry_pointer) { \
322 if (private_or_ins_entry_pointer->entry.status \
323 == CCC_ENTRY_OCCUPIED) { \
324 private_or_ins_ret = private_or_ins_entry_pointer->entry.type; \
325 } else { \
326 private_or_ins_ret = CCC_private_adaptive_map_new( \
327 private_or_ins_entry_pointer, \
328 private_adaptive_map_allocator \
329 ); \
330 CCC_private_adaptive_map_insert_key_val( \
331 private_or_ins_entry_pointer, \
332 private_or_ins_ret, \
333 type_compound_literal \
334 ); \
335 } \
336 } \
337 private_or_ins_ret; \
338 }))
339
341#define CCC_private_adaptive_map_insert_entry_with( \
342 adaptive_map_entry_pointer, \
343 private_allocator_pointer, \
344 type_compound_literal... \
345) \
346 (__extension__({ \
347 struct CCC_Adaptive_map_entry const *const private_ins_entry_pointer \
348 = (adaptive_map_entry_pointer); \
349 typeof(type_compound_literal) *private_adaptive_map_ins_ent_ret \
350 = NULL; \
351 CCC_Allocator const *const private_adaptive_map_allocator \
352 = (private_allocator_pointer); \
353 if (private_adaptive_map_allocator && private_ins_entry_pointer) { \
354 if (!(private_ins_entry_pointer->entry.status \
355 & CCC_ENTRY_OCCUPIED)) { \
356 private_adaptive_map_ins_ent_ret \
357 = CCC_private_adaptive_map_new( \
358 private_ins_entry_pointer, \
359 private_adaptive_map_allocator \
360 ); \
361 CCC_private_adaptive_map_insert_key_val( \
362 private_ins_entry_pointer, \
363 private_adaptive_map_ins_ent_ret, \
364 type_compound_literal \
365 ); \
366 } else if (private_ins_entry_pointer->entry.status \
367 == CCC_ENTRY_OCCUPIED) { \
368 struct CCC_Adaptive_map_node private_ins_ent_saved \
369 = *CCC_private_adaptive_map_node_in_slot( \
370 private_ins_entry_pointer->map, \
371 private_ins_entry_pointer->entry.type \
372 ); \
373 *((typeof(type_compound_literal) *) \
374 private_ins_entry_pointer->entry.type) \
375 = type_compound_literal; \
376 *CCC_private_adaptive_map_node_in_slot( \
377 private_ins_entry_pointer->map, \
378 private_ins_entry_pointer->entry.type \
379 ) = private_ins_ent_saved; \
380 private_adaptive_map_ins_ent_ret \
381 = private_ins_entry_pointer->entry.type; \
382 } \
383 } \
384 private_adaptive_map_ins_ent_ret; \
385 }))
386
388#define CCC_private_adaptive_map_try_insert_with( \
389 adaptive_map_pointer, \
390 key, \
391 private_allocator_pointer, \
392 type_compound_literal... \
393) \
394 (__extension__({ \
395 struct CCC_Adaptive_map *const private_try_ins_map_pointer \
396 = (adaptive_map_pointer); \
397 CCC_Entry private_adaptive_map_try_ins_ent_ret \
398 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
399 CCC_Allocator const *const private_adaptive_map_allocator \
400 = (private_allocator_pointer); \
401 if (private_adaptive_map_allocator && private_try_ins_map_pointer) { \
402 __auto_type private_adaptive_map_key = (key); \
403 struct CCC_Adaptive_map_entry private_adaptive_map_try_ins_ent \
404 = CCC_private_adaptive_map_entry( \
405 private_try_ins_map_pointer, \
406 (void *)&private_adaptive_map_key \
407 ); \
408 if (!(private_adaptive_map_try_ins_ent.entry.status \
409 & CCC_ENTRY_OCCUPIED)) { \
410 CCC_private_adaptive_map_insert_and_copy_key( \
411 private_adaptive_map_try_ins_ent, \
412 private_adaptive_map_try_ins_ent_ret, \
413 private_adaptive_map_key, \
414 private_adaptive_map_allocator, \
415 type_compound_literal \
416 ); \
417 } else if (private_adaptive_map_try_ins_ent.entry.status \
418 == CCC_ENTRY_OCCUPIED) { \
419 private_adaptive_map_try_ins_ent_ret \
420 = private_adaptive_map_try_ins_ent.entry; \
421 } \
422 } \
423 private_adaptive_map_try_ins_ent_ret; \
424 }))
425
427#define CCC_private_adaptive_map_insert_or_assign_with( \
428 adaptive_map_pointer, \
429 key, \
430 private_allocator_pointer, \
431 type_compound_literal... \
432) \
433 (__extension__({ \
434 struct CCC_Adaptive_map *const private_ins_or_assign_map_pointer \
435 = (adaptive_map_pointer); \
436 CCC_Entry private_adaptive_map_ins_or_assign_ent_ret \
437 = {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
438 CCC_Allocator const *const private_adaptive_map_allocator \
439 = (private_allocator_pointer); \
440 if (private_adaptive_map_allocator \
441 && private_ins_or_assign_map_pointer) { \
442 __auto_type private_adaptive_map_key = (key); \
443 struct CCC_Adaptive_map_entry \
444 private_adaptive_map_ins_or_assign_ent \
445 = CCC_private_adaptive_map_entry( \
446 private_ins_or_assign_map_pointer, \
447 (void *)&private_adaptive_map_key \
448 ); \
449 if (!(private_adaptive_map_ins_or_assign_ent.entry.status \
450 & CCC_ENTRY_OCCUPIED)) { \
451 CCC_private_adaptive_map_insert_and_copy_key( \
452 private_adaptive_map_ins_or_assign_ent, \
453 private_adaptive_map_ins_or_assign_ent_ret, \
454 private_adaptive_map_key, \
455 private_adaptive_map_allocator, \
456 type_compound_literal \
457 ); \
458 } else if (private_adaptive_map_ins_or_assign_ent.entry.status \
459 == CCC_ENTRY_OCCUPIED) { \
460 struct CCC_Adaptive_map_node private_ins_ent_saved \
461 = *CCC_private_adaptive_map_node_in_slot( \
462 private_adaptive_map_ins_or_assign_ent.map, \
463 private_adaptive_map_ins_or_assign_ent.entry.type \
464 ); \
465 *((typeof(type_compound_literal) *) \
466 private_adaptive_map_ins_or_assign_ent.entry.type) \
467 = type_compound_literal; \
468 *CCC_private_adaptive_map_node_in_slot( \
469 private_adaptive_map_ins_or_assign_ent.map, \
470 private_adaptive_map_ins_or_assign_ent.entry.type \
471 ) = private_ins_ent_saved; \
472 private_adaptive_map_ins_or_assign_ent_ret \
473 = private_adaptive_map_ins_or_assign_ent.entry; \
474 *((typeof(private_adaptive_map_key) *) \
475 CCC_private_adaptive_map_key_in_slot( \
476 private_ins_or_assign_map_pointer, \
477 private_adaptive_map_ins_or_assign_ent_ret.type \
478 )) = private_adaptive_map_key; \
479 } \
480 } \
481 private_adaptive_map_ins_or_assign_ent_ret; \
482 }))
483
484/* NOLINTEND(readability-identifier-naming) */
485
486#endif /* CCC_PRIVATE_ADAPTIVE_MAP_H */
CCC_private_adaptive_map_insert
void * CCC_private_adaptive_map_insert(struct CCC_Adaptive_map *, struct CCC_Adaptive_map_node *)
CCC_private_adaptive_map_entry
struct CCC_Adaptive_map_entry CCC_private_adaptive_map_entry(struct CCC_Adaptive_map *, void const *)
CCC_private_adaptive_map_key_in_slot
void * CCC_private_adaptive_map_key_in_slot(struct CCC_Adaptive_map const *, void const *)
CCC_private_adaptive_map_node_in_slot
struct CCC_Adaptive_map_node * CCC_private_adaptive_map_node_in_slot(struct CCC_Adaptive_map const *, void const *)
CCC_Adaptive_map_entry
Definition: private_adaptive_map.h:85
CCC_Adaptive_map_entry::entry
CCC_Entry entry
Definition: private_adaptive_map.h:89
CCC_Adaptive_map_entry::map
struct CCC_Adaptive_map * map
Definition: private_adaptive_map.h:87
CCC_Adaptive_map_node
Definition: private_adaptive_map.h:42
CCC_Adaptive_map_node::branch
struct CCC_Adaptive_map_node * branch[2]
Definition: private_adaptive_map.h:44
CCC_Adaptive_map_node::parent
struct CCC_Adaptive_map_node * parent
Definition: private_adaptive_map.h:46
CCC_Adaptive_map
Definition: private_adaptive_map.h:56
CCC_Adaptive_map::type_intruder_offset
size_t type_intruder_offset
Definition: private_adaptive_map.h:64
CCC_Adaptive_map::count
size_t count
Definition: private_adaptive_map.h:60
CCC_Adaptive_map::key_offset
size_t key_offset
Definition: private_adaptive_map.h:66
CCC_Adaptive_map::root
struct CCC_Adaptive_map_node * root
Definition: private_adaptive_map.h:58
CCC_Adaptive_map::sizeof_type
size_t sizeof_type
Definition: private_adaptive_map.h:62
CCC_Adaptive_map::comparator
CCC_Key_comparator comparator
Definition: private_adaptive_map.h:68
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:505