C Container Collection (CCC)
Loading...
Searching...
No Matches
impl_ordered_multimap.h
1
16#ifndef CCC_IMPL_ORDERED_MULTIMAP_H
17#define CCC_IMPL_ORDERED_MULTIMAP_H
18
20#include <stddef.h>
23#include "../types.h"
24#include "impl_types.h"
25
26/* NOLINTBEGIN(readability-identifier-naming) */
27
44struct ccc_ommap_elem
45{
47 union
48 {
50 struct ccc_ommap_elem *branch[2];
52 struct ccc_ommap_elem *link[2];
53 };
55 union
56 {
58 struct ccc_ommap_elem *parent;
60 struct ccc_ommap_elem *dup_head;
61 };
62};
63
71struct ccc_ommap
72{
74 struct ccc_ommap_elem *root;
76 struct ccc_ommap_elem end;
78 size_t size;
80 size_t sizeof_type;
82 size_t node_elem_offset;
84 size_t key_offset;
86 ccc_any_key_cmp_fn *cmp;
88 ccc_any_alloc_fn *alloc;
90 void *aux;
91};
92
107struct ccc_omultimap_entry
108{
110 struct ccc_ommap *t;
112 struct ccc_ent entry;
113};
114
118union ccc_ommap_entry
119{
121 struct ccc_omultimap_entry impl;
122};
123
124/*========================== Private Interface ============================*/
125
127void *ccc_impl_omm_key_in_slot(struct ccc_ommap const *t, void const *slot);
129struct ccc_ommap_elem *ccc_impl_ommap_elem_in_slot(struct ccc_ommap const *t,
130 void const *slot);
132struct ccc_omultimap_entry ccc_impl_omm_entry(struct ccc_ommap *t,
133 void const *key);
135void *ccc_impl_omm_multimap_insert(struct ccc_ommap *t,
136 struct ccc_ommap_elem *n);
137
138/*========================== Initialization ==============================*/
139
141#define ccc_impl_omm_init(impl_tree_name, impl_struct_name, \
142 impl_node_elem_field, impl_key_elem_field, \
143 impl_key_cmp_fn, impl_alloc_fn, impl_aux_data) \
144 { \
145 .root = &(impl_tree_name).end, \
146 .end = {{.branch = {&(impl_tree_name).end, &(impl_tree_name).end}}, \
147 {.parent = &(impl_tree_name).end}}, \
148 .alloc = (impl_alloc_fn), \
149 .cmp = (impl_key_cmp_fn), \
150 .aux = (impl_aux_data), \
151 .size = 0, \
152 .sizeof_type = sizeof(impl_struct_name), \
153 .node_elem_offset = offsetof(impl_struct_name, impl_node_elem_field), \
154 .key_offset = offsetof(impl_struct_name, impl_key_elem_field), \
155 }
156
157/*================== Helper Macros for Repeated Logic =================*/
158
160#define ccc_impl_omm_new(ordered_map_entry) \
161 (__extension__({ \
162 void *impl_omm_ins_alloc_ret = NULL; \
163 if ((ordered_map_entry)->t->alloc) \
164 { \
165 impl_omm_ins_alloc_ret \
166 = (ordered_map_entry) \
167 ->t->alloc(NULL, (ordered_map_entry)->t->sizeof_type, \
168 (ordered_map_entry)->t->aux); \
169 } \
170 impl_omm_ins_alloc_ret; \
171 }))
172
174#define ccc_impl_omm_insert_key_val(ordered_map_entry, new_mem, \
175 lazy_key_value...) \
176 (__extension__({ \
177 if (new_mem) \
178 { \
179 *new_mem = lazy_key_value; \
180 new_mem = ccc_impl_omm_multimap_insert( \
181 (ordered_map_entry)->t, \
182 ccc_impl_ommap_elem_in_slot((ordered_map_entry)->t, new_mem)); \
183 } \
184 }))
185
187#define ccc_impl_omm_insert_and_copy_key( \
188 omm_insert_entry, omm_insert_entry_ret, key, lazy_value...) \
189 (__extension__({ \
190 typeof(lazy_value) *impl_omm_new_ins_base \
191 = ccc_impl_omm_new((&omm_insert_entry)); \
192 omm_insert_entry_ret = (struct ccc_ent){ \
193 .e = impl_omm_new_ins_base, \
194 .stats = CCC_ENTRY_INSERT_ERROR, \
195 }; \
196 if (impl_omm_new_ins_base) \
197 { \
198 *((typeof(lazy_value) *)impl_omm_new_ins_base) = lazy_value; \
199 *((typeof(key) *)ccc_impl_omm_key_in_slot(omm_insert_entry.t, \
200 impl_omm_new_ins_base)) \
201 = key; \
202 (void)ccc_impl_omm_multimap_insert( \
203 omm_insert_entry.t, \
204 ccc_impl_ommap_elem_in_slot(omm_insert_entry.t, \
205 impl_omm_new_ins_base)); \
206 } \
207 }))
208
209/*===================== Core Macro Implementations ==================*/
210
212#define ccc_impl_omm_and_modify_w(ordered_map_entry_ptr, type_name, \
213 closure_over_T...) \
214 (__extension__({ \
215 __auto_type impl_omm_ent_ptr = (ordered_map_entry_ptr); \
216 struct ccc_omultimap_entry impl_omm_mod_ent \
217 = {.entry = {.stats = CCC_ENTRY_ARG_ERROR}}; \
218 if (impl_omm_ent_ptr) \
219 { \
220 impl_omm_mod_ent = impl_omm_ent_ptr->impl; \
221 if (impl_omm_mod_ent.entry.stats & CCC_ENTRY_OCCUPIED) \
222 { \
223 type_name *const T = impl_omm_mod_ent.entry.e; \
224 if (T) \
225 { \
226 closure_over_T \
227 } \
228 } \
229 } \
230 impl_omm_mod_ent; \
231 }))
232
234#define ccc_impl_omm_or_insert_w(ordered_map_entry_ptr, lazy_key_value...) \
235 (__extension__({ \
236 __auto_type impl_omm_or_ins_ent_ptr = (ordered_map_entry_ptr); \
237 typeof(lazy_key_value) *impl_or_ins_ret = NULL; \
238 if (impl_omm_or_ins_ent_ptr) \
239 { \
240 struct ccc_omultimap_entry *impl_omm_or_ins_ent \
241 = &impl_omm_or_ins_ent_ptr->impl; \
242 if (impl_omm_or_ins_ent->entry.stats == CCC_ENTRY_OCCUPIED) \
243 { \
244 impl_or_ins_ret = impl_omm_or_ins_ent->entry.e; \
245 } \
246 else \
247 { \
248 impl_or_ins_ret = ccc_impl_omm_new(impl_omm_or_ins_ent); \
249 ccc_impl_omm_insert_key_val(impl_omm_or_ins_ent, \
250 impl_or_ins_ret, lazy_key_value); \
251 } \
252 } \
253 impl_or_ins_ret; \
254 }))
255
257#define ccc_impl_omm_insert_entry_w(ordered_map_entry_ptr, lazy_key_value...) \
258 (__extension__({ \
259 __auto_type impl_omm_ins_ent_ptr = (ordered_map_entry_ptr); \
260 typeof(lazy_key_value) *impl_omm_ins_ent_ret = NULL; \
261 if (impl_omm_ins_ent_ptr) \
262 { \
263 struct ccc_omultimap_entry *impl_omm_ins_ent \
264 = &impl_omm_ins_ent_ptr->impl; \
265 impl_omm_ins_ent_ret = ccc_impl_omm_new(impl_omm_ins_ent); \
266 ccc_impl_omm_insert_key_val(impl_omm_ins_ent, \
267 impl_omm_ins_ent_ret, lazy_key_value); \
268 } \
269 impl_omm_ins_ent_ret; \
270 }))
271
273#define ccc_impl_omm_try_insert_w(ordered_map_ptr, key, lazy_value...) \
274 (__extension__({ \
275 __auto_type impl_omm_try_ins_ptr = (ordered_map_ptr); \
276 struct ccc_ent impl_omm_try_ins_ent_ret \
277 = {.stats = CCC_ENTRY_ARG_ERROR}; \
278 if (impl_omm_try_ins_ptr) \
279 { \
280 __auto_type impl_omm_key = (key); \
281 struct ccc_omultimap_entry impl_omm_try_ins_ent \
282 = ccc_impl_omm_entry(impl_omm_try_ins_ptr, \
283 (void *)&impl_omm_key); \
284 if (!(impl_omm_try_ins_ent.entry.stats & CCC_ENTRY_OCCUPIED)) \
285 { \
286 ccc_impl_omm_insert_and_copy_key(impl_omm_try_ins_ent, \
287 impl_omm_try_ins_ent_ret, \
288 impl_omm_key, lazy_value); \
289 } \
290 else if (impl_omm_try_ins_ent.entry.stats == CCC_ENTRY_OCCUPIED) \
291 { \
292 impl_omm_try_ins_ent_ret = impl_omm_try_ins_ent.entry; \
293 } \
294 } \
295 impl_omm_try_ins_ent_ret; \
296 }))
297
299#define ccc_impl_omm_insert_or_assign_w(ordered_map_ptr, key, lazy_value...) \
300 (__extension__({ \
301 __auto_type impl_omm_ins_or_assign_ptr = (ordered_map_ptr); \
302 struct ccc_ent impl_omm_ins_or_assign_ent_ret \
303 = {.stats = CCC_ENTRY_ARG_ERROR}; \
304 if (impl_omm_ins_or_assign_ptr) \
305 { \
306 __auto_type impl_omm_key = (key); \
307 struct ccc_omultimap_entry impl_omm_ins_or_assign_ent \
308 = ccc_impl_omm_entry(impl_omm_ins_or_assign_ptr, \
309 (void *)&impl_omm_key); \
310 if (!(impl_omm_ins_or_assign_ent.entry.stats \
311 & CCC_ENTRY_OCCUPIED)) \
312 { \
313 ccc_impl_omm_insert_and_copy_key( \
314 impl_omm_ins_or_assign_ent, \
315 impl_omm_ins_or_assign_ent_ret, impl_omm_key, lazy_value); \
316 } \
317 else if (impl_omm_ins_or_assign_ent.entry.stats \
318 == CCC_ENTRY_OCCUPIED) \
319 { \
320 struct ccc_ommap_elem impl_ins_ent_saved \
321 = *ccc_impl_ommap_elem_in_slot( \
322 impl_omm_ins_or_assign_ent.t, \
323 impl_omm_ins_or_assign_ent.entry.e); \
324 *((typeof(lazy_value) *)impl_omm_ins_or_assign_ent.entry.e) \
325 = lazy_value; \
326 *ccc_impl_ommap_elem_in_slot( \
327 impl_omm_ins_or_assign_ent.t, \
328 impl_omm_ins_or_assign_ent.entry.e) \
329 = impl_ins_ent_saved; \
330 impl_omm_ins_or_assign_ent_ret \
331 = impl_omm_ins_or_assign_ent.entry; \
332 *((typeof(impl_omm_key) *)ccc_impl_omm_key_in_slot( \
333 impl_omm_ins_or_assign_ptr, \
334 impl_omm_ins_or_assign_ent_ret.e)) \
335 = impl_omm_key; \
336 } \
337 } \
338 impl_omm_ins_or_assign_ent_ret; \
339 }))
340
341/* NOLINTEND(readability-identifier-naming) */
342
343#endif /* CCC_IMPL_ORDERED_MULTIMAP_H */
ccc_ommap_elem
struct ccc_ommap_elem ccc_ommap_elem
The intrusive element for the user defined type stored in the multimap.
Definition: ordered_multimap.h:77
ccc_ommap_entry
union ccc_ommap_entry ccc_ommap_entry
The container specific type to support the Entry Interface.
Definition: ordered_multimap.h:85
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