C Container Collection (CCC)
Loading...
Searching...
No Matches
impl_realtime_ordered_map.h
1#ifndef CCC_IMPL_REALTIME_ORDERED_MAP_H
2#define CCC_IMPL_REALTIME_ORDERED_MAP_H
3
5#include <stddef.h>
6#include <stdint.h>
9#include "../types.h"
10#include "impl_types.h"
11
12/* NOLINTBEGIN(readability-identifier-naming) */
13
15typedef struct ccc_romap_elem_
16{
17 struct ccc_romap_elem_ *branch_[2];
18 struct ccc_romap_elem_ *parent_;
19 uint8_t parity_;
20} ccc_romap_elem_;
21
23struct ccc_romap_
24{
25 struct ccc_romap_elem_ *root_;
26 struct ccc_romap_elem_ end_;
27 size_t sz_;
28 size_t key_offset_;
29 size_t node_elem_offset_;
30 size_t elem_sz_;
31 ccc_alloc_fn *alloc_;
32 ccc_key_cmp_fn *cmp_;
33 void *aux_;
34};
35
37struct ccc_rtree_entry_
38{
39 struct ccc_romap_ *rom_;
40 ccc_threeway_cmp last_cmp_;
41 struct ccc_ent_ entry_;
42};
43
45union ccc_romap_entry_
46{
47 struct ccc_rtree_entry_ impl_;
48};
49
50/*========================= Private Interface ============================*/
51
53void *ccc_impl_rom_key_in_slot(struct ccc_romap_ const *rom, void const *slot);
55struct ccc_romap_elem_ *
56ccc_impl_romap_elem_in_slot(struct ccc_romap_ const *rom, void const *slot);
58struct ccc_rtree_entry_ ccc_impl_rom_entry(struct ccc_romap_ const *rom,
59 void const *key);
61void *ccc_impl_rom_insert(struct ccc_romap_ *rom,
62 struct ccc_romap_elem_ *parent,
63 ccc_threeway_cmp last_cmp,
64 struct ccc_romap_elem_ *out_handle);
65
66/*========================== Initialization ===========================*/
67
69#define ccc_impl_rom_init(map_name, struct_name, node_elem_field, \
70 key_elem_field, key_cmp_fn, alloc_fn, aux_data) \
71 { \
72 .root_ = &(map_name).end_, \
73 .end_ = {.parity_ = 1, \
74 .parent_ = &(map_name).end_, \
75 .branch_ = {&(map_name).end_, &(map_name).end_}}, \
76 .sz_ = 0, \
77 .key_offset_ = offsetof(struct_name, key_elem_field), \
78 .node_elem_offset_ = offsetof(struct_name, node_elem_field), \
79 .elem_sz_ = sizeof(struct_name), \
80 .alloc_ = (alloc_fn), \
81 .cmp_ = (key_cmp_fn), \
82 .aux_ = (aux_data), \
83 }
84
85/*================== Helper Macros for Repeated Logic =================*/
86
88#define ccc_impl_rom_new(realtime_ordered_map_entry) \
89 (__extension__({ \
90 void *rom_ins_alloc_ret_ = NULL; \
91 if ((realtime_ordered_map_entry)->rom_->alloc_) \
92 { \
93 rom_ins_alloc_ret_ \
94 = (realtime_ordered_map_entry) \
95 ->rom_->alloc_( \
96 NULL, (realtime_ordered_map_entry)->rom_->elem_sz_, \
97 (realtime_ordered_map_entry)->rom_->aux_); \
98 } \
99 rom_ins_alloc_ret_; \
100 }))
101
103#define ccc_impl_rom_insert_key_val(realtime_ordered_map_entry, new_mem, \
104 lazy_key_value...) \
105 (__extension__({ \
106 if (new_mem) \
107 { \
108 *new_mem = lazy_key_value; \
109 new_mem = ccc_impl_rom_insert( \
110 (realtime_ordered_map_entry)->rom_, \
111 ccc_impl_romap_elem_in_slot( \
112 (realtime_ordered_map_entry)->rom_, \
113 (realtime_ordered_map_entry)->entry_.e_), \
114 (realtime_ordered_map_entry)->last_cmp_, \
115 ccc_impl_romap_elem_in_slot( \
116 (realtime_ordered_map_entry)->rom_, new_mem)); \
117 } \
118 }))
119
121#define ccc_impl_rom_insert_and_copy_key( \
122 rom_insert_entry, rom_insert_entry_ret, key, lazy_value...) \
123 (__extension__({ \
124 typeof(lazy_value) *rom_new_ins_base_ \
125 = ccc_impl_rom_new((&rom_insert_entry)); \
126 rom_insert_entry_ret = (struct ccc_ent_){ \
127 .e_ = rom_new_ins_base_, \
128 .stats_ = CCC_ENTRY_INSERT_ERROR, \
129 }; \
130 if (rom_new_ins_base_) \
131 { \
132 *rom_new_ins_base_ = lazy_value; \
133 *((typeof(key) *)ccc_impl_rom_key_in_slot(rom_insert_entry.rom_, \
134 rom_new_ins_base_)) \
135 = key; \
136 (void)ccc_impl_rom_insert( \
137 rom_insert_entry.rom_, \
138 ccc_impl_romap_elem_in_slot(rom_insert_entry.rom_, \
139 rom_insert_entry.entry_.e_), \
140 rom_insert_entry.last_cmp_, \
141 ccc_impl_romap_elem_in_slot(rom_insert_entry.rom_, \
142 rom_new_ins_base_)); \
143 } \
144 }))
145
146/*================== Core Macro Implementations =====================*/
147
149#define ccc_impl_rom_and_modify_w(realtime_ordered_map_entry_ptr, type_name, \
150 closure_over_T...) \
151 (__extension__({ \
152 __auto_type rom_ent_ptr_ = (realtime_ordered_map_entry_ptr); \
153 struct ccc_rtree_entry_ rom_mod_ent_ \
154 = {.entry_ = {.stats_ = CCC_ENTRY_ARG_ERROR}}; \
155 if (rom_ent_ptr_) \
156 { \
157 rom_mod_ent_ = rom_ent_ptr_->impl_; \
158 if (rom_mod_ent_.entry_.stats_ & CCC_ENTRY_OCCUPIED) \
159 { \
160 type_name *const T = rom_mod_ent_.entry_.e_; \
161 if (T) \
162 { \
163 closure_over_T \
164 } \
165 } \
166 } \
167 rom_mod_ent_; \
168 }))
169
171#define ccc_impl_rom_or_insert_w(realtime_ordered_map_entry_ptr, \
172 lazy_key_value...) \
173 (__extension__({ \
174 __auto_type or_ins_entry_ptr_ = (realtime_ordered_map_entry_ptr); \
175 typeof(lazy_key_value) *rom_or_ins_ret_ = NULL; \
176 if (or_ins_entry_ptr_) \
177 { \
178 struct ccc_rtree_entry_ *rom_or_ins_ent_ \
179 = &or_ins_entry_ptr_->impl_; \
180 if (rom_or_ins_ent_->entry_.stats_ == CCC_ENTRY_OCCUPIED) \
181 { \
182 rom_or_ins_ret_ = rom_or_ins_ent_->entry_.e_; \
183 } \
184 else \
185 { \
186 rom_or_ins_ret_ = ccc_impl_rom_new(rom_or_ins_ent_); \
187 ccc_impl_rom_insert_key_val(rom_or_ins_ent_, rom_or_ins_ret_, \
188 lazy_key_value); \
189 } \
190 } \
191 rom_or_ins_ret_; \
192 }))
193
195#define ccc_impl_rom_insert_entry_w(realtime_ordered_map_entry_ptr, \
196 lazy_key_value...) \
197 (__extension__({ \
198 __auto_type ins_entry_ptr_ = (realtime_ordered_map_entry_ptr); \
199 typeof(lazy_key_value) *rom_ins_ent_ret_ = NULL; \
200 if (ins_entry_ptr_) \
201 { \
202 struct ccc_rtree_entry_ *rom_ins_ent_ = &ins_entry_ptr_->impl_; \
203 if (!(rom_ins_ent_->entry_.stats_ & CCC_ENTRY_OCCUPIED)) \
204 { \
205 rom_ins_ent_ret_ = ccc_impl_rom_new(rom_ins_ent_); \
206 ccc_impl_rom_insert_key_val(rom_ins_ent_, rom_ins_ent_ret_, \
207 lazy_key_value); \
208 } \
209 else if (rom_ins_ent_->entry_.stats_ == CCC_ENTRY_OCCUPIED) \
210 { \
211 struct ccc_romap_elem_ ins_ent_saved_ \
212 = *ccc_impl_romap_elem_in_slot(rom_ins_ent_->rom_, \
213 rom_ins_ent_->entry_.e_); \
214 *((typeof(rom_ins_ent_ret_))rom_ins_ent_->entry_.e_) \
215 = lazy_key_value; \
216 *ccc_impl_romap_elem_in_slot(rom_ins_ent_->rom_, \
217 rom_ins_ent_->entry_.e_) \
218 = ins_ent_saved_; \
219 rom_ins_ent_ret_ = rom_ins_ent_->entry_.e_; \
220 } \
221 } \
222 rom_ins_ent_ret_; \
223 }))
224
226#define ccc_impl_rom_try_insert_w(realtime_ordered_map_ptr, key, \
227 lazy_value...) \
228 (__extension__({ \
229 struct ccc_romap_ *const try_ins_map_ptr_ \
230 = (realtime_ordered_map_ptr); \
231 struct ccc_ent_ rom_try_ins_ent_ret_ \
232 = {.stats_ = CCC_ENTRY_ARG_ERROR}; \
233 if (try_ins_map_ptr_) \
234 { \
235 __auto_type rom_key_ = (key); \
236 struct ccc_rtree_entry_ rom_try_ins_ent_ \
237 = ccc_impl_rom_entry(try_ins_map_ptr_, (void *)&rom_key_); \
238 if (!(rom_try_ins_ent_.entry_.stats_ & CCC_ENTRY_OCCUPIED)) \
239 { \
240 ccc_impl_rom_insert_and_copy_key( \
241 rom_try_ins_ent_, rom_try_ins_ent_ret_, key, lazy_value); \
242 } \
243 else if (rom_try_ins_ent_.entry_.stats_ == CCC_ENTRY_OCCUPIED) \
244 { \
245 rom_try_ins_ent_ret_ = rom_try_ins_ent_.entry_; \
246 } \
247 } \
248 rom_try_ins_ent_ret_; \
249 }))
250
252#define ccc_impl_rom_insert_or_assign_w(realtime_ordered_map_ptr, key, \
253 lazy_value...) \
254 (__extension__({ \
255 struct ccc_romap_ *const ins_or_assign_map_ptr_ \
256 = (realtime_ordered_map_ptr); \
257 struct ccc_ent_ rom_ins_or_assign_ent_ret_ \
258 = {.stats_ = CCC_ENTRY_ARG_ERROR}; \
259 if (ins_or_assign_map_ptr_) \
260 { \
261 __auto_type rom_key_ = (key); \
262 struct ccc_rtree_entry_ rom_ins_or_assign_ent_ \
263 = ccc_impl_rom_entry(ins_or_assign_map_ptr_, \
264 (void *)&rom_key_); \
265 if (!(rom_ins_or_assign_ent_.entry_.stats_ & CCC_ENTRY_OCCUPIED)) \
266 { \
267 ccc_impl_rom_insert_and_copy_key(rom_ins_or_assign_ent_, \
268 rom_ins_or_assign_ent_ret_, \
269 key, lazy_value); \
270 } \
271 else if (rom_ins_or_assign_ent_.entry_.stats_ \
272 == CCC_ENTRY_OCCUPIED) \
273 { \
274 struct ccc_romap_elem_ ins_ent_saved_ \
275 = *ccc_impl_romap_elem_in_slot( \
276 rom_ins_or_assign_ent_.rom_, \
277 rom_ins_or_assign_ent_.entry_.e_); \
278 *((typeof(lazy_value) *)rom_ins_or_assign_ent_.entry_.e_) \
279 = lazy_value; \
280 *ccc_impl_romap_elem_in_slot(rom_ins_or_assign_ent_.rom_, \
281 rom_ins_or_assign_ent_.entry_.e_) \
282 = ins_ent_saved_; \
283 rom_ins_or_assign_ent_ret_ = rom_ins_or_assign_ent_.entry_; \
284 *((typeof(rom_key_) *)ccc_impl_rom_key_in_slot( \
285 rom_ins_or_assign_ent_.rom_, \
286 rom_ins_or_assign_ent_ret_.e_)) \
287 = rom_key_; \
288 } \
289 } \
290 rom_ins_or_assign_ent_ret_; \
291 }))
292
293/* NOLINTEND(readability-identifier-naming) */
294
295#endif /* CCC_IMPL_REALTIME__ORDERED_MAP_H */
ccc_key_cmp_fn
ccc_threeway_cmp ccc_key_cmp_fn(ccc_key_cmp)
A callback function for three-way comparing two stored keys.
Definition: types.h:333
ccc_alloc_fn
void * ccc_alloc_fn(void *ptr, size_t size, void *aux)
An allocation function at the core of all containers.
Definition: types.h:283
ccc_threeway_cmp
ccc_threeway_cmp
A three-way comparison for comparison functions.
Definition: types.h:138