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 struct ccc_otree_entry *impl_om_or_ins_ent \
212 = &impl_or_ins_entry_ptr->impl; \
213 if (impl_om_or_ins_ent->entry.stats == CCC_ENTRY_OCCUPIED) \
214 { \
215 impl_or_ins_ret = impl_om_or_ins_ent->entry.e; \
216 } \
217 else \
218 { \
219 impl_or_ins_ret = ccc_impl_om_new(impl_om_or_ins_ent); \
220 ccc_impl_om_insert_key_val(impl_om_or_ins_ent, \
221 impl_or_ins_ret, lazy_key_value); \
222 } \
223 } \
224 impl_or_ins_ret; \
225 }))
226
228#define ccc_impl_om_insert_entry_w(ordered_map_entry_ptr, lazy_key_value...) \
229 (__extension__({ \
230 __auto_type impl_ins_entry_ptr = (ordered_map_entry_ptr); \
231 typeof(lazy_key_value) *impl_om_ins_ent_ret = NULL; \
232 if (impl_ins_entry_ptr) \
233 { \
234 struct ccc_otree_entry *impl_om_ins_ent \
235 = &impl_ins_entry_ptr->impl; \
236 if (!(impl_om_ins_ent->entry.stats & CCC_ENTRY_OCCUPIED)) \
237 { \
238 impl_om_ins_ent_ret = ccc_impl_om_new(impl_om_ins_ent); \
239 ccc_impl_om_insert_key_val( \
240 impl_om_ins_ent, impl_om_ins_ent_ret, lazy_key_value); \
241 } \
242 else if (impl_om_ins_ent->entry.stats == CCC_ENTRY_OCCUPIED) \
243 { \
244 struct ccc_omap_elem impl_ins_ent_saved \
245 = *ccc_impl_omap_elem_in_slot(impl_om_ins_ent->t, \
246 impl_om_ins_ent->entry.e); \
247 *((typeof(lazy_key_value) *)impl_om_ins_ent->entry.e) \
248 = lazy_key_value; \
249 *ccc_impl_omap_elem_in_slot(impl_om_ins_ent->t, \
250 impl_om_ins_ent->entry.e) \
251 = impl_ins_ent_saved; \
252 impl_om_ins_ent_ret = impl_om_ins_ent->entry.e; \
253 } \
254 } \
255 impl_om_ins_ent_ret; \
256 }))
257
259#define ccc_impl_om_try_insert_w(ordered_map_ptr, key, lazy_value...) \
260 (__extension__({ \
261 __auto_type impl_try_ins_map_ptr = (ordered_map_ptr); \
262 struct ccc_ent impl_om_try_ins_ent_ret \
263 = {.stats = CCC_ENTRY_ARG_ERROR}; \
264 if (impl_try_ins_map_ptr) \
265 { \
266 __auto_type impl_om_key = (key); \
267 struct ccc_otree_entry impl_om_try_ins_ent = ccc_impl_om_entry( \
268 impl_try_ins_map_ptr, (void *)&impl_om_key); \
269 if (!(impl_om_try_ins_ent.entry.stats & CCC_ENTRY_OCCUPIED)) \
270 { \
271 ccc_impl_om_insert_and_copy_key(impl_om_try_ins_ent, \
272 impl_om_try_ins_ent_ret, \
273 impl_om_key, lazy_value); \
274 } \
275 else if (impl_om_try_ins_ent.entry.stats == CCC_ENTRY_OCCUPIED) \
276 { \
277 impl_om_try_ins_ent_ret = impl_om_try_ins_ent.entry; \
278 } \
279 } \
280 impl_om_try_ins_ent_ret; \
281 }))
282
284#define ccc_impl_om_insert_or_assign_w(ordered_map_ptr, key, lazy_value...) \
285 (__extension__({ \
286 __auto_type impl_ins_or_assign_map_ptr = (ordered_map_ptr); \
287 struct ccc_ent impl_om_ins_or_assign_ent_ret \
288 = {.stats = CCC_ENTRY_ARG_ERROR}; \
289 if (impl_ins_or_assign_map_ptr) \
290 { \
291 __auto_type impl_om_key = (key); \
292 struct ccc_otree_entry impl_om_ins_or_assign_ent \
293 = ccc_impl_om_entry(impl_ins_or_assign_map_ptr, \
294 (void *)&impl_om_key); \
295 if (!(impl_om_ins_or_assign_ent.entry.stats & CCC_ENTRY_OCCUPIED)) \
296 { \
297 ccc_impl_om_insert_and_copy_key(impl_om_ins_or_assign_ent, \
298 impl_om_ins_or_assign_ent_ret, \
299 impl_om_key, lazy_value); \
300 } \
301 else if (impl_om_ins_or_assign_ent.entry.stats \
302 == CCC_ENTRY_OCCUPIED) \
303 { \
304 struct ccc_omap_elem impl_ins_ent_saved \
305 = *ccc_impl_omap_elem_in_slot( \
306 impl_om_ins_or_assign_ent.t, \
307 impl_om_ins_or_assign_ent.entry.e); \
308 *((typeof(lazy_value) *)impl_om_ins_or_assign_ent.entry.e) \
309 = lazy_value; \
310 *ccc_impl_omap_elem_in_slot(impl_om_ins_or_assign_ent.t, \
311 impl_om_ins_or_assign_ent.entry.e) \
312 = impl_ins_ent_saved; \
313 impl_om_ins_or_assign_ent_ret \
314 = impl_om_ins_or_assign_ent.entry; \
315 *((typeof(impl_om_key) *)ccc_impl_om_key_in_slot( \
316 impl_ins_or_assign_map_ptr, \
317 impl_om_ins_or_assign_ent_ret.e)) \
318 = impl_om_key; \
319 } \
320 } \
321 impl_om_ins_or_assign_ent_ret; \
322 }))
323
324/* NOLINTEND(readability-identifier-naming) */
325
326#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