C Container Collection (CCC)
Loading...
Searching...
No Matches
impl_realtime_ordered_map.h
1
16#ifndef CCC_IMPL_REALTIME_ORDERED_MAP_H
17#define CCC_IMPL_REALTIME_ORDERED_MAP_H
18
20#include <stddef.h>
21#include <stdint.h>
24#include "../types.h"
25#include "impl_types.h"
26
27/* NOLINTBEGIN(readability-identifier-naming) */
28
31struct ccc_romap_elem
32{
34 struct ccc_romap_elem *branch[2];
36 struct ccc_romap_elem *parent;
38 uint8_t parity;
39};
40
53struct ccc_romap
54{
56 struct ccc_romap_elem *root;
58 struct ccc_romap_elem end;
60 size_t count;
62 size_t key_offset;
64 size_t node_elem_offset;
66 size_t sizeof_type;
68 ccc_any_alloc_fn *alloc;
70 ccc_any_key_cmp_fn *cmp;
72 void *aux;
73};
74
78struct ccc_rtree_entry
79{
81 struct ccc_romap *rom;
85 ccc_threeway_cmp last_cmp;
87 struct ccc_ent entry;
88};
89
93union ccc_romap_entry
94{
96 struct ccc_rtree_entry impl;
97};
98
99/*========================= Private Interface ============================*/
100
102void *ccc_impl_rom_key_in_slot(struct ccc_romap const *rom, void const *slot);
104struct ccc_romap_elem *ccc_impl_romap_elem_in_slot(struct ccc_romap const *rom,
105 void const *slot);
107struct ccc_rtree_entry ccc_impl_rom_entry(struct ccc_romap const *rom,
108 void const *key);
110void *ccc_impl_rom_insert(struct ccc_romap *rom, struct ccc_romap_elem *parent,
111 ccc_threeway_cmp last_cmp,
112 struct ccc_romap_elem *out_handle);
113
114/*========================== Initialization ===========================*/
115
117#define ccc_impl_rom_init(impl_map_name, impl_struct_name, \
118 impl_node_elem_field, impl_key_elem_field, \
119 impl_key_cmp_fn, impl_alloc_fn, impl_aux_data) \
120 { \
121 .root = &(impl_map_name).end, \
122 .end = {.parity = 1, \
123 .parent = &(impl_map_name).end, \
124 .branch = {&(impl_map_name).end, &(impl_map_name).end}}, \
125 .count = 0, \
126 .key_offset = offsetof(impl_struct_name, impl_key_elem_field), \
127 .node_elem_offset = offsetof(impl_struct_name, impl_node_elem_field), \
128 .sizeof_type = sizeof(impl_struct_name), \
129 .alloc = (impl_alloc_fn), \
130 .cmp = (impl_key_cmp_fn), \
131 .aux = (impl_aux_data), \
132 }
133
134/*================== Helper Macros for Repeated Logic =================*/
135
137#define ccc_impl_rom_new(realtime_ordered_map_entry) \
138 (__extension__({ \
139 void *impl_rom_ins_alloc_ret = NULL; \
140 if ((realtime_ordered_map_entry)->rom->alloc) \
141 { \
142 impl_rom_ins_alloc_ret \
143 = (realtime_ordered_map_entry) \
144 ->rom->alloc( \
145 NULL, \
146 (realtime_ordered_map_entry)->rom->sizeof_type, \
147 (realtime_ordered_map_entry)->rom->aux); \
148 } \
149 impl_rom_ins_alloc_ret; \
150 }))
151
153#define ccc_impl_rom_insert_key_val(realtime_ordered_map_entry, new_mem, \
154 lazy_key_value...) \
155 (__extension__({ \
156 if (new_mem) \
157 { \
158 *new_mem = lazy_key_value; \
159 new_mem = ccc_impl_rom_insert( \
160 (realtime_ordered_map_entry)->rom, \
161 ccc_impl_romap_elem_in_slot( \
162 (realtime_ordered_map_entry)->rom, \
163 (realtime_ordered_map_entry)->entry.e), \
164 (realtime_ordered_map_entry)->last_cmp, \
165 ccc_impl_romap_elem_in_slot((realtime_ordered_map_entry)->rom, \
166 new_mem)); \
167 } \
168 }))
169
171#define ccc_impl_rom_insert_and_copy_key( \
172 rom_insert_entry, rom_insert_entry_ret, key, lazy_value...) \
173 (__extension__({ \
174 typeof(lazy_value) *impl_rom_new_ins_base \
175 = ccc_impl_rom_new((&rom_insert_entry)); \
176 rom_insert_entry_ret = (struct ccc_ent){ \
177 .e = impl_rom_new_ins_base, \
178 .stats = CCC_ENTRY_INSERT_ERROR, \
179 }; \
180 if (impl_rom_new_ins_base) \
181 { \
182 *impl_rom_new_ins_base = lazy_value; \
183 *((typeof(key) *)ccc_impl_rom_key_in_slot(rom_insert_entry.rom, \
184 impl_rom_new_ins_base)) \
185 = key; \
186 (void)ccc_impl_rom_insert( \
187 rom_insert_entry.rom, \
188 ccc_impl_romap_elem_in_slot(rom_insert_entry.rom, \
189 rom_insert_entry.entry.e), \
190 rom_insert_entry.last_cmp, \
191 ccc_impl_romap_elem_in_slot(rom_insert_entry.rom, \
192 impl_rom_new_ins_base)); \
193 } \
194 }))
195
196/*================== Core Macro Implementations =====================*/
197
199#define ccc_impl_rom_and_modify_w(realtime_ordered_map_entry_ptr, type_name, \
200 closure_over_T...) \
201 (__extension__({ \
202 __auto_type impl_rom_ent_ptr = (realtime_ordered_map_entry_ptr); \
203 struct ccc_rtree_entry impl_rom_mod_ent \
204 = {.entry = {.stats = CCC_ENTRY_ARG_ERROR}}; \
205 if (impl_rom_ent_ptr) \
206 { \
207 impl_rom_mod_ent = impl_rom_ent_ptr->impl; \
208 if (impl_rom_mod_ent.entry.stats & CCC_ENTRY_OCCUPIED) \
209 { \
210 type_name *const T = impl_rom_mod_ent.entry.e; \
211 if (T) \
212 { \
213 closure_over_T \
214 } \
215 } \
216 } \
217 impl_rom_mod_ent; \
218 }))
219
221#define ccc_impl_rom_or_insert_w(realtime_ordered_map_entry_ptr, \
222 lazy_key_value...) \
223 (__extension__({ \
224 __auto_type impl_or_ins_entry_ptr = (realtime_ordered_map_entry_ptr); \
225 typeof(lazy_key_value) *impl_rom_or_ins_ret = NULL; \
226 if (impl_or_ins_entry_ptr) \
227 { \
228 if (impl_or_ins_entry_ptr->impl.entry.stats == CCC_ENTRY_OCCUPIED) \
229 { \
230 impl_rom_or_ins_ret = impl_or_ins_entry_ptr->impl.entry.e; \
231 } \
232 else \
233 { \
234 impl_rom_or_ins_ret \
235 = ccc_impl_rom_new(&impl_or_ins_entry_ptr->impl); \
236 ccc_impl_rom_insert_key_val(&impl_or_ins_entry_ptr->impl, \
237 impl_rom_or_ins_ret, \
238 lazy_key_value); \
239 } \
240 } \
241 impl_rom_or_ins_ret; \
242 }))
243
245#define ccc_impl_rom_insert_entry_w(realtime_ordered_map_entry_ptr, \
246 lazy_key_value...) \
247 (__extension__({ \
248 __auto_type impl_ins_entry_ptr = (realtime_ordered_map_entry_ptr); \
249 typeof(lazy_key_value) *impl_rom_ins_ent_ret = NULL; \
250 if (impl_ins_entry_ptr) \
251 { \
252 if (!(impl_ins_entry_ptr->impl.entry.stats & CCC_ENTRY_OCCUPIED)) \
253 { \
254 impl_rom_ins_ent_ret \
255 = ccc_impl_rom_new(&impl_ins_entry_ptr->impl); \
256 ccc_impl_rom_insert_key_val(&impl_ins_entry_ptr->impl, \
257 impl_rom_ins_ent_ret, \
258 lazy_key_value); \
259 } \
260 else if (impl_ins_entry_ptr->impl.entry.stats \
261 == CCC_ENTRY_OCCUPIED) \
262 { \
263 struct ccc_romap_elem impl_ins_ent_saved \
264 = *ccc_impl_romap_elem_in_slot( \
265 impl_ins_entry_ptr->impl.rom, \
266 impl_ins_entry_ptr->impl.entry.e); \
267 *((typeof(impl_rom_ins_ent_ret)) \
268 impl_ins_entry_ptr->impl.entry.e) \
269 = lazy_key_value; \
270 *ccc_impl_romap_elem_in_slot(impl_ins_entry_ptr->impl.rom, \
271 impl_ins_entry_ptr->impl.entry.e) \
272 = impl_ins_ent_saved; \
273 impl_rom_ins_ent_ret = impl_ins_entry_ptr->impl.entry.e; \
274 } \
275 } \
276 impl_rom_ins_ent_ret; \
277 }))
278
280#define ccc_impl_rom_try_insert_w(realtime_ordered_map_ptr, key, \
281 lazy_value...) \
282 (__extension__({ \
283 struct ccc_romap *const impl_try_ins_map_ptr \
284 = (realtime_ordered_map_ptr); \
285 struct ccc_ent impl_rom_try_ins_ent_ret \
286 = {.stats = CCC_ENTRY_ARG_ERROR}; \
287 if (impl_try_ins_map_ptr) \
288 { \
289 __auto_type impl_rom_key = (key); \
290 struct ccc_rtree_entry impl_rom_try_ins_ent = ccc_impl_rom_entry( \
291 impl_try_ins_map_ptr, (void *)&impl_rom_key); \
292 if (!(impl_rom_try_ins_ent.entry.stats & CCC_ENTRY_OCCUPIED)) \
293 { \
294 ccc_impl_rom_insert_and_copy_key(impl_rom_try_ins_ent, \
295 impl_rom_try_ins_ent_ret, \
296 impl_rom_key, lazy_value); \
297 } \
298 else if (impl_rom_try_ins_ent.entry.stats == CCC_ENTRY_OCCUPIED) \
299 { \
300 impl_rom_try_ins_ent_ret = impl_rom_try_ins_ent.entry; \
301 } \
302 } \
303 impl_rom_try_ins_ent_ret; \
304 }))
305
307#define ccc_impl_rom_insert_or_assign_w(realtime_ordered_map_ptr, key, \
308 lazy_value...) \
309 (__extension__({ \
310 struct ccc_romap *const impl_ins_or_assign_map_ptr \
311 = (realtime_ordered_map_ptr); \
312 struct ccc_ent impl_rom_ins_or_assign_ent_ret \
313 = {.stats = CCC_ENTRY_ARG_ERROR}; \
314 if (impl_ins_or_assign_map_ptr) \
315 { \
316 __auto_type impl_rom_key = (key); \
317 struct ccc_rtree_entry impl_rom_ins_or_assign_ent \
318 = ccc_impl_rom_entry(impl_ins_or_assign_map_ptr, \
319 (void *)&impl_rom_key); \
320 if (!(impl_rom_ins_or_assign_ent.entry.stats \
321 & CCC_ENTRY_OCCUPIED)) \
322 { \
323 ccc_impl_rom_insert_and_copy_key( \
324 impl_rom_ins_or_assign_ent, \
325 impl_rom_ins_or_assign_ent_ret, impl_rom_key, lazy_value); \
326 } \
327 else if (impl_rom_ins_or_assign_ent.entry.stats \
328 == CCC_ENTRY_OCCUPIED) \
329 { \
330 struct ccc_romap_elem impl_ins_ent_saved \
331 = *ccc_impl_romap_elem_in_slot( \
332 impl_rom_ins_or_assign_ent.rom, \
333 impl_rom_ins_or_assign_ent.entry.e); \
334 *((typeof(lazy_value) *)impl_rom_ins_or_assign_ent.entry.e) \
335 = lazy_value; \
336 *ccc_impl_romap_elem_in_slot( \
337 impl_rom_ins_or_assign_ent.rom, \
338 impl_rom_ins_or_assign_ent.entry.e) \
339 = impl_ins_ent_saved; \
340 impl_rom_ins_or_assign_ent_ret \
341 = impl_rom_ins_or_assign_ent.entry; \
342 *((typeof(impl_rom_key) *)ccc_impl_rom_key_in_slot( \
343 impl_rom_ins_or_assign_ent.rom, \
344 impl_rom_ins_or_assign_ent_ret.e)) \
345 = impl_rom_key; \
346 } \
347 } \
348 impl_rom_ins_or_assign_ent_ret; \
349 }))
350
351/* NOLINTEND(readability-identifier-naming) */
352
353#endif /* CCC_IMPL_REALTIME__ORDERED_MAP_H */
ccc_romap_entry
union ccc_romap_entry ccc_romap_entry
A container specific entry used to implement the Entry Interface.
Definition: realtime_ordered_map.h:69
ccc_romap_elem
struct ccc_romap_elem ccc_romap_elem
The intrusive element of the user defined struct being stored in the map.
Definition: realtime_ordered_map.h:63
ccc_any_alloc_fn
void * ccc_any_alloc_fn(void *ptr, size_t size, void *aux)
An allocation function at the core of all containers.
Definition: types.h:312
ccc_any_key_cmp_fn
ccc_threeway_cmp ccc_any_key_cmp_fn(ccc_any_key_cmp)
A callback function for three-way comparing two stored keys.
Definition: types.h:362
ccc_threeway_cmp
ccc_threeway_cmp
A three-way comparison for comparison functions.
Definition: types.h:153