C Container Collection (CCC)
Loading...
Searching...
No Matches
impl_ordered_map.h
1
16#ifndef CCC_IMPL_ORDERED_MAP_H
17#define CCC_IMPL_ORDERED_MAP_H
18
20#include <stddef.h>
23#include "../types.h"
24#include "impl_types.h"
25
26/* NOLINTBEGIN(readability-identifier-naming) */
27
31struct ccc_omap_elem
32{
34 struct ccc_omap_elem *branch[2];
36 struct ccc_omap_elem *parent;
37};
38
46struct ccc_omap
47{
49 struct ccc_omap_elem *root;
51 struct ccc_omap_elem end;
53 size_t size;
55 size_t sizeof_type;
57 size_t node_elem_offset;
59 size_t key_offset;
61 ccc_any_key_cmp_fn *cmp;
63 ccc_any_alloc_fn *alloc;
65 void *aux;
66};
67
82struct ccc_otree_entry
83{
85 struct ccc_omap *t;
87 struct ccc_ent entry;
88};
89
93union ccc_omap_entry
94{
96 struct ccc_otree_entry impl;
97};
98
99/*========================== Private Interface ============================*/
100
102void *ccc_impl_om_key_in_slot(struct ccc_omap const *t, void const *slot);
104struct ccc_omap_elem *ccc_impl_omap_elem_in_slot(struct ccc_omap const *t,
105 void const *slot);
107struct ccc_otree_entry ccc_impl_om_entry(struct ccc_omap *t, void const *key);
109void *ccc_impl_om_insert(struct ccc_omap *t, struct ccc_omap_elem *n);
110
111/*====================== Macro Implementations ========================*/
112
114#define ccc_impl_om_init(impl_tree_name, impl_struct_name, \
115 impl_node_elem_field, impl_key_elem_field, \
116 impl_key_cmp_fn, impl_alloc_fn, impl_aux_data) \
117 { \
118 .root = &(impl_tree_name).end, \
119 .end = {.branch = {&(impl_tree_name).end, &(impl_tree_name).end}, \
120 .parent = &(impl_tree_name).end}, \
121 .alloc = (impl_alloc_fn), \
122 .cmp = (impl_key_cmp_fn), \
123 .aux = (impl_aux_data), \
124 .size = 0, \
125 .sizeof_type = sizeof(impl_struct_name), \
126 .node_elem_offset = offsetof(impl_struct_name, impl_node_elem_field), \
127 .key_offset = offsetof(impl_struct_name, impl_key_elem_field), \
128 }
129
131#define ccc_impl_om_new(ordered_map_entry) \
132 (__extension__({ \
133 void *impl_om_ins_alloc_ret = NULL; \
134 if ((ordered_map_entry)->t->alloc) \
135 { \
136 impl_om_ins_alloc_ret \
137 = (ordered_map_entry) \
138 ->t->alloc(NULL, (ordered_map_entry)->t->sizeof_type, \
139 (ordered_map_entry)->t->aux); \
140 } \
141 impl_om_ins_alloc_ret; \
142 }))
143
145#define ccc_impl_om_insert_key_val(ordered_map_entry, new_mem, \
146 lazy_key_value...) \
147 (__extension__({ \
148 if (new_mem) \
149 { \
150 *new_mem = lazy_key_value; \
151 new_mem = ccc_impl_om_insert( \
152 (ordered_map_entry)->t, \
153 ccc_impl_omap_elem_in_slot((ordered_map_entry)->t, new_mem)); \
154 } \
155 }))
156
158#define ccc_impl_om_insert_and_copy_key(om_insert_entry, om_insert_entry_ret, \
159 key, lazy_value...) \
160 (__extension__({ \
161 typeof(lazy_value) *impl_om_new_ins_base \
162 = ccc_impl_om_new((&om_insert_entry)); \
163 om_insert_entry_ret = (struct ccc_ent){ \
164 .e = impl_om_new_ins_base, \
165 .stats = CCC_ENTRY_INSERT_ERROR, \
166 }; \
167 if (impl_om_new_ins_base) \
168 { \
169 *((typeof(lazy_value) *)impl_om_new_ins_base) = lazy_value; \
170 *((typeof(key) *)ccc_impl_om_key_in_slot(om_insert_entry.t, \
171 impl_om_new_ins_base)) \
172 = key; \
173 (void)ccc_impl_om_insert( \
174 om_insert_entry.t, \
175 ccc_impl_omap_elem_in_slot(om_insert_entry.t, \
176 impl_om_new_ins_base)); \
177 } \
178 }))
179
180/*===================== Core Macro Implementations ==================*/
181
183#define ccc_impl_om_and_modify_w(ordered_map_entry_ptr, type_name, \
184 closure_over_T...) \
185 (__extension__({ \
186 __auto_type impl_om_ent_ptr = (ordered_map_entry_ptr); \
187 struct ccc_otree_entry impl_om_mod_ent \
188 = {.entry = {.stats = CCC_ENTRY_ARG_ERROR}}; \
189 if (impl_om_ent_ptr) \
190 { \
191 impl_om_mod_ent = impl_om_ent_ptr->impl; \
192 if (impl_om_mod_ent.entry.stats & CCC_ENTRY_OCCUPIED) \
193 { \
194 type_name *const T = impl_om_mod_ent.entry.e; \
195 if (T) \
196 { \
197 closure_over_T \
198 } \
199 } \
200 } \
201 impl_om_mod_ent; \
202 }))
203
205#define ccc_impl_om_or_insert_w(ordered_map_entry_ptr, lazy_key_value...) \
206 (__extension__({ \
207 __auto_type impl_or_ins_entry_ptr = (ordered_map_entry_ptr); \
208 typeof(lazy_key_value) *impl_or_ins_ret = NULL; \
209 if (impl_or_ins_entry_ptr) \
210 { \
211 if (impl_or_ins_entry_ptr->impl.entry.stats == CCC_ENTRY_OCCUPIED) \
212 { \
213 impl_or_ins_ret = impl_or_ins_entry_ptr->impl.entry.e; \
214 } \
215 else \
216 { \
217 impl_or_ins_ret \
218 = ccc_impl_om_new(&impl_or_ins_entry_ptr->impl); \
219 ccc_impl_om_insert_key_val(&impl_or_ins_entry_ptr->impl, \
220 impl_or_ins_ret, lazy_key_value); \
221 } \
222 } \
223 impl_or_ins_ret; \
224 }))
225
227#define ccc_impl_om_insert_entry_w(ordered_map_entry_ptr, lazy_key_value...) \
228 (__extension__({ \
229 __auto_type impl_ins_entry_ptr = (ordered_map_entry_ptr); \
230 typeof(lazy_key_value) *impl_om_ins_ent_ret = NULL; \
231 if (impl_ins_entry_ptr) \
232 { \
233 if (!(impl_ins_entry_ptr->impl.entry.stats & CCC_ENTRY_OCCUPIED)) \
234 { \
235 impl_om_ins_ent_ret \
236 = ccc_impl_om_new(&impl_ins_entry_ptr->impl); \
237 ccc_impl_om_insert_key_val(&impl_ins_entry_ptr->impl, \
238 impl_om_ins_ent_ret, \
239 lazy_key_value); \
240 } \
241 else if (impl_ins_entry_ptr->impl.entry.stats \
242 == CCC_ENTRY_OCCUPIED) \
243 { \
244 struct ccc_omap_elem impl_ins_ent_saved \
245 = *ccc_impl_omap_elem_in_slot( \
246 impl_ins_entry_ptr->impl.t, \
247 impl_ins_entry_ptr->impl.entry.e); \
248 *((typeof(lazy_key_value) *)impl_ins_entry_ptr->impl.entry.e) \
249 = lazy_key_value; \
250 *ccc_impl_omap_elem_in_slot(impl_ins_entry_ptr->impl.t, \
251 impl_ins_entry_ptr->impl.entry.e) \
252 = impl_ins_ent_saved; \
253 impl_om_ins_ent_ret = impl_ins_entry_ptr->impl.entry.e; \
254 } \
255 } \
256 impl_om_ins_ent_ret; \
257 }))
258
260#define ccc_impl_om_try_insert_w(ordered_map_ptr, key, lazy_value...) \
261 (__extension__({ \
262 __auto_type impl_try_ins_map_ptr = (ordered_map_ptr); \
263 struct ccc_ent impl_om_try_ins_ent_ret \
264 = {.stats = CCC_ENTRY_ARG_ERROR}; \
265 if (impl_try_ins_map_ptr) \
266 { \
267 __auto_type impl_om_key = (key); \
268 struct ccc_otree_entry impl_om_try_ins_ent = ccc_impl_om_entry( \
269 impl_try_ins_map_ptr, (void *)&impl_om_key); \
270 if (!(impl_om_try_ins_ent.entry.stats & CCC_ENTRY_OCCUPIED)) \
271 { \
272 ccc_impl_om_insert_and_copy_key(impl_om_try_ins_ent, \
273 impl_om_try_ins_ent_ret, \
274 impl_om_key, lazy_value); \
275 } \
276 else if (impl_om_try_ins_ent.entry.stats == CCC_ENTRY_OCCUPIED) \
277 { \
278 impl_om_try_ins_ent_ret = impl_om_try_ins_ent.entry; \
279 } \
280 } \
281 impl_om_try_ins_ent_ret; \
282 }))
283
285#define ccc_impl_om_insert_or_assign_w(ordered_map_ptr, key, lazy_value...) \
286 (__extension__({ \
287 __auto_type impl_ins_or_assign_map_ptr = (ordered_map_ptr); \
288 struct ccc_ent impl_om_ins_or_assign_ent_ret \
289 = {.stats = CCC_ENTRY_ARG_ERROR}; \
290 if (impl_ins_or_assign_map_ptr) \
291 { \
292 __auto_type impl_om_key = (key); \
293 struct ccc_otree_entry impl_om_ins_or_assign_ent \
294 = ccc_impl_om_entry(impl_ins_or_assign_map_ptr, \
295 (void *)&impl_om_key); \
296 if (!(impl_om_ins_or_assign_ent.entry.stats & CCC_ENTRY_OCCUPIED)) \
297 { \
298 ccc_impl_om_insert_and_copy_key(impl_om_ins_or_assign_ent, \
299 impl_om_ins_or_assign_ent_ret, \
300 impl_om_key, lazy_value); \
301 } \
302 else if (impl_om_ins_or_assign_ent.entry.stats \
303 == CCC_ENTRY_OCCUPIED) \
304 { \
305 struct ccc_omap_elem impl_ins_ent_saved \
306 = *ccc_impl_omap_elem_in_slot( \
307 impl_om_ins_or_assign_ent.t, \
308 impl_om_ins_or_assign_ent.entry.e); \
309 *((typeof(lazy_value) *)impl_om_ins_or_assign_ent.entry.e) \
310 = lazy_value; \
311 *ccc_impl_omap_elem_in_slot(impl_om_ins_or_assign_ent.t, \
312 impl_om_ins_or_assign_ent.entry.e) \
313 = impl_ins_ent_saved; \
314 impl_om_ins_or_assign_ent_ret \
315 = impl_om_ins_or_assign_ent.entry; \
316 *((typeof(impl_om_key) *)ccc_impl_om_key_in_slot( \
317 impl_ins_or_assign_map_ptr, \
318 impl_om_ins_or_assign_ent_ret.e)) \
319 = impl_om_key; \
320 } \
321 } \
322 impl_om_ins_or_assign_ent_ret; \
323 }))
324
325/* NOLINTEND(readability-identifier-naming) */
326
327#endif /* CCC_IMPL_ORDERED_MAP_H */
ccc_omap_elem
struct ccc_omap_elem ccc_omap_elem
The intrusive element for the user defined struct being stored in the map.
Definition: ordered_map.h:65
ccc_omap_entry
union ccc_omap_entry ccc_omap_entry
A container specific entry used to implement the Entry Interface.
Definition: ordered_map.h:71
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