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