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 struct ccc_rtree_entry *impl_rom_or_ins_ent \
229 = &impl_or_ins_entry_ptr->impl; \
230 if (impl_rom_or_ins_ent->entry.stats == CCC_ENTRY_OCCUPIED) \
231 { \
232 impl_rom_or_ins_ret = impl_rom_or_ins_ent->entry.e; \
233 } \
234 else \
235 { \
236 impl_rom_or_ins_ret = ccc_impl_rom_new(impl_rom_or_ins_ent); \
237 ccc_impl_rom_insert_key_val( \
238 impl_rom_or_ins_ent, impl_rom_or_ins_ret, 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 struct ccc_rtree_entry *impl_rom_ins_ent \
253 = &impl_ins_entry_ptr->impl; \
254 if (!(impl_rom_ins_ent->entry.stats & CCC_ENTRY_OCCUPIED)) \
255 { \
256 impl_rom_ins_ent_ret = ccc_impl_rom_new(impl_rom_ins_ent); \
257 ccc_impl_rom_insert_key_val( \
258 impl_rom_ins_ent, impl_rom_ins_ent_ret, lazy_key_value); \
259 } \
260 else if (impl_rom_ins_ent->entry.stats == CCC_ENTRY_OCCUPIED) \
261 { \
262 struct ccc_romap_elem impl_ins_ent_saved \
263 = *ccc_impl_romap_elem_in_slot(impl_rom_ins_ent->rom, \
264 impl_rom_ins_ent->entry.e); \
265 *((typeof(impl_rom_ins_ent_ret))impl_rom_ins_ent->entry.e) \
266 = lazy_key_value; \
267 *ccc_impl_romap_elem_in_slot(impl_rom_ins_ent->rom, \
268 impl_rom_ins_ent->entry.e) \
269 = impl_ins_ent_saved; \
270 impl_rom_ins_ent_ret = impl_rom_ins_ent->entry.e; \
271 } \
272 } \
273 impl_rom_ins_ent_ret; \
274 }))
275
277#define ccc_impl_rom_try_insert_w(realtime_ordered_map_ptr, key, \
278 lazy_value...) \
279 (__extension__({ \
280 struct ccc_romap *const impl_try_ins_map_ptr \
281 = (realtime_ordered_map_ptr); \
282 struct ccc_ent impl_rom_try_ins_ent_ret \
283 = {.stats = CCC_ENTRY_ARG_ERROR}; \
284 if (impl_try_ins_map_ptr) \
285 { \
286 __auto_type impl_rom_key = (key); \
287 struct ccc_rtree_entry impl_rom_try_ins_ent = ccc_impl_rom_entry( \
288 impl_try_ins_map_ptr, (void *)&impl_rom_key); \
289 if (!(impl_rom_try_ins_ent.entry.stats & CCC_ENTRY_OCCUPIED)) \
290 { \
291 ccc_impl_rom_insert_and_copy_key(impl_rom_try_ins_ent, \
292 impl_rom_try_ins_ent_ret, \
293 impl_rom_key, lazy_value); \
294 } \
295 else if (impl_rom_try_ins_ent.entry.stats == CCC_ENTRY_OCCUPIED) \
296 { \
297 impl_rom_try_ins_ent_ret = impl_rom_try_ins_ent.entry; \
298 } \
299 } \
300 impl_rom_try_ins_ent_ret; \
301 }))
302
304#define ccc_impl_rom_insert_or_assign_w(realtime_ordered_map_ptr, key, \
305 lazy_value...) \
306 (__extension__({ \
307 struct ccc_romap *const impl_ins_or_assign_map_ptr \
308 = (realtime_ordered_map_ptr); \
309 struct ccc_ent impl_rom_ins_or_assign_ent_ret \
310 = {.stats = CCC_ENTRY_ARG_ERROR}; \
311 if (impl_ins_or_assign_map_ptr) \
312 { \
313 __auto_type impl_rom_key = (key); \
314 struct ccc_rtree_entry impl_rom_ins_or_assign_ent \
315 = ccc_impl_rom_entry(impl_ins_or_assign_map_ptr, \
316 (void *)&impl_rom_key); \
317 if (!(impl_rom_ins_or_assign_ent.entry.stats \
318 & CCC_ENTRY_OCCUPIED)) \
319 { \
320 ccc_impl_rom_insert_and_copy_key( \
321 impl_rom_ins_or_assign_ent, \
322 impl_rom_ins_or_assign_ent_ret, impl_rom_key, lazy_value); \
323 } \
324 else if (impl_rom_ins_or_assign_ent.entry.stats \
325 == CCC_ENTRY_OCCUPIED) \
326 { \
327 struct ccc_romap_elem impl_ins_ent_saved \
328 = *ccc_impl_romap_elem_in_slot( \
329 impl_rom_ins_or_assign_ent.rom, \
330 impl_rom_ins_or_assign_ent.entry.e); \
331 *((typeof(lazy_value) *)impl_rom_ins_or_assign_ent.entry.e) \
332 = lazy_value; \
333 *ccc_impl_romap_elem_in_slot( \
334 impl_rom_ins_or_assign_ent.rom, \
335 impl_rom_ins_or_assign_ent.entry.e) \
336 = impl_ins_ent_saved; \
337 impl_rom_ins_or_assign_ent_ret \
338 = impl_rom_ins_or_assign_ent.entry; \
339 *((typeof(impl_rom_key) *)ccc_impl_rom_key_in_slot( \
340 impl_rom_ins_or_assign_ent.rom, \
341 impl_rom_ins_or_assign_ent_ret.e)) \
342 = impl_rom_key; \
343 } \
344 } \
345 impl_rom_ins_or_assign_ent_ret; \
346 }))
347
348/* NOLINTEND(readability-identifier-naming) */
349
350#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