C Container Collection (CCC)
Loading...
Searching...
No Matches
impl_ordered_multimap.h
1#ifndef CCC_IMPL_ORDERED_MULTIMAP_H
2#define CCC_IMPL_ORDERED_MULTIMAP_H
3
5#include <stddef.h>
8#include "../types.h"
9#include "impl_types.h"
10
11/* NOLINTBEGIN(readability-identifier-naming) */
12
28typedef struct ccc_ommap_elem_
29{
30 union
31 {
32 struct ccc_ommap_elem_ *branch_[2];
33 struct ccc_ommap_elem_ *link_[2];
34 };
35 union
36 {
37 struct ccc_ommap_elem_ *parent_;
38 struct ccc_ommap_elem_ *dup_head_;
39 };
40} ccc_ommap_elem_;
41
43struct ccc_ommap_
44{
45 struct ccc_ommap_elem_ *root_;
46 struct ccc_ommap_elem_ end_;
47 ccc_alloc_fn *alloc_;
48 ccc_key_cmp_fn *cmp_;
49 void *aux_;
50 size_t size_;
51 size_t elem_sz_;
52 size_t node_elem_offset_;
53 size_t key_offset_;
54};
55
57struct ccc_omultimap_entry_
58{
59 struct ccc_ommap_ *t_;
60 struct ccc_ent_ entry_;
61};
62
64union ccc_ommap_entry_
65{
66 struct ccc_omultimap_entry_ impl_;
67};
68
69/*========================== Private Interface ============================*/
70
72void *ccc_impl_omm_key_in_slot(struct ccc_ommap_ const *t, void const *slot);
74ccc_ommap_elem_ *ccc_impl_ommap_elem_in_slot(struct ccc_ommap_ const *t,
75 void const *slot);
77struct ccc_omultimap_entry_ ccc_impl_omm_entry(struct ccc_ommap_ *t,
78 void const *key);
80void *ccc_impl_omm_multimap_insert(struct ccc_ommap_ *t, ccc_ommap_elem_ *n);
81
82/*========================== Initialization ==============================*/
83
85#define ccc_impl_omm_init(tree_name, struct_name, node_elem_field, \
86 key_elem_field, key_cmp_fn, alloc_fn, aux_data) \
87 { \
88 .root_ = &(tree_name).end_, \
89 .end_ = {{.branch_ = {&(tree_name).end_, &(tree_name).end_}}, \
90 {.parent_ = &(tree_name).end_}}, \
91 .alloc_ = (alloc_fn), \
92 .cmp_ = (key_cmp_fn), \
93 .aux_ = (aux_data), \
94 .size_ = 0, \
95 .elem_sz_ = sizeof(struct_name), \
96 .node_elem_offset_ = offsetof(struct_name, node_elem_field), \
97 .key_offset_ = offsetof(struct_name, key_elem_field), \
98 }
99
100/*================== Helper Macros for Repeated Logic =================*/
101
103#define ccc_impl_omm_new(ordered_map_entry) \
104 (__extension__({ \
105 void *omm_ins_alloc_ret_ = NULL; \
106 if ((ordered_map_entry)->t_->alloc_) \
107 { \
108 omm_ins_alloc_ret_ \
109 = (ordered_map_entry) \
110 ->t_->alloc_(NULL, (ordered_map_entry)->t_->elem_sz_, \
111 (ordered_map_entry)->t_->aux_); \
112 } \
113 omm_ins_alloc_ret_; \
114 }))
115
117#define ccc_impl_omm_insert_key_val(ordered_map_entry, new_mem, \
118 lazy_key_value...) \
119 (__extension__({ \
120 if (new_mem) \
121 { \
122 *new_mem = lazy_key_value; \
123 new_mem = ccc_impl_omm_multimap_insert( \
124 (ordered_map_entry)->t_, \
125 ccc_impl_ommap_elem_in_slot((ordered_map_entry)->t_, \
126 new_mem)); \
127 } \
128 }))
129
131#define ccc_impl_omm_insert_and_copy_key( \
132 omm_insert_entry, omm_insert_entry_ret, key, lazy_value...) \
133 (__extension__({ \
134 typeof(lazy_value) *omm_new_ins_base_ \
135 = ccc_impl_omm_new((&omm_insert_entry)); \
136 omm_insert_entry_ret = (struct ccc_ent_){ \
137 .e_ = omm_new_ins_base_, \
138 .stats_ = CCC_ENTRY_INSERT_ERROR, \
139 }; \
140 if (omm_new_ins_base_) \
141 { \
142 *((typeof(lazy_value) *)omm_new_ins_base_) = lazy_value; \
143 *((typeof(key) *)ccc_impl_omm_key_in_slot(omm_insert_entry.t_, \
144 omm_new_ins_base_)) \
145 = key; \
146 (void)ccc_impl_omm_multimap_insert( \
147 omm_insert_entry.t_, \
148 ccc_impl_ommap_elem_in_slot(omm_insert_entry.t_, \
149 omm_new_ins_base_)); \
150 } \
151 }))
152
153/*===================== Core Macro Implementations ==================*/
154
156#define ccc_impl_omm_and_modify_w(ordered_map_entry_ptr, type_name, \
157 closure_over_T...) \
158 (__extension__({ \
159 __auto_type omm_ent_ptr_ = (ordered_map_entry_ptr); \
160 struct ccc_omultimap_entry_ omm_mod_ent_ \
161 = {.entry_ = {.stats_ = CCC_ENTRY_ARG_ERROR}}; \
162 if (omm_ent_ptr_) \
163 { \
164 omm_mod_ent_ = omm_ent_ptr_->impl_; \
165 if (omm_mod_ent_.entry_.stats_ & CCC_ENTRY_OCCUPIED) \
166 { \
167 type_name *const T = omm_mod_ent_.entry_.e_; \
168 if (T) \
169 { \
170 closure_over_T \
171 } \
172 } \
173 } \
174 omm_mod_ent_; \
175 }))
176
178#define ccc_impl_omm_or_insert_w(ordered_map_entry_ptr, lazy_key_value...) \
179 (__extension__({ \
180 __auto_type omm_or_ins_ent_ptr_ = (ordered_map_entry_ptr); \
181 typeof(lazy_key_value) *or_ins_ret_ = NULL; \
182 if (omm_or_ins_ent_ptr_) \
183 { \
184 struct ccc_omultimap_entry_ *omm_or_ins_ent_ \
185 = &omm_or_ins_ent_ptr_->impl_; \
186 if (omm_or_ins_ent_->entry_.stats_ == CCC_ENTRY_OCCUPIED) \
187 { \
188 or_ins_ret_ = omm_or_ins_ent_->entry_.e_; \
189 } \
190 else \
191 { \
192 or_ins_ret_ = ccc_impl_omm_new(omm_or_ins_ent_); \
193 ccc_impl_omm_insert_key_val(omm_or_ins_ent_, or_ins_ret_, \
194 lazy_key_value); \
195 } \
196 } \
197 or_ins_ret_; \
198 }))
199
201#define ccc_impl_omm_insert_entry_w(ordered_map_entry_ptr, lazy_key_value...) \
202 (__extension__({ \
203 __auto_type omm_ins_ent_ptr_ = (ordered_map_entry_ptr); \
204 typeof(lazy_key_value) *omm_ins_ent_ret_ = NULL; \
205 if (omm_ins_ent_ptr_) \
206 { \
207 struct ccc_omultimap_entry_ *omm_ins_ent_ \
208 = &omm_ins_ent_ptr_->impl_; \
209 omm_ins_ent_ret_ = ccc_impl_omm_new(omm_ins_ent_); \
210 ccc_impl_omm_insert_key_val(omm_ins_ent_, omm_ins_ent_ret_, \
211 lazy_key_value); \
212 } \
213 omm_ins_ent_ret_; \
214 }))
215
217#define ccc_impl_omm_try_insert_w(ordered_map_ptr, key, lazy_value...) \
218 (__extension__({ \
219 __auto_type omm_try_ins_ptr_ = (ordered_map_ptr); \
220 struct ccc_ent_ omm_try_ins_ent_ret_ \
221 = {.stats_ = CCC_ENTRY_ARG_ERROR}; \
222 if (omm_try_ins_ptr_) \
223 { \
224 __auto_type omm_key_ = (key); \
225 struct ccc_omultimap_entry_ omm_try_ins_ent_ \
226 = ccc_impl_omm_entry(omm_try_ins_ptr_, (void *)&omm_key_); \
227 if (!(omm_try_ins_ent_.entry_.stats_ & CCC_ENTRY_OCCUPIED)) \
228 { \
229 ccc_impl_omm_insert_and_copy_key(omm_try_ins_ent_, \
230 omm_try_ins_ent_ret_, \
231 omm_key_, lazy_value); \
232 } \
233 else if (omm_try_ins_ent_.entry_.stats_ == CCC_ENTRY_OCCUPIED) \
234 { \
235 omm_try_ins_ent_ret_ = omm_try_ins_ent_.entry_; \
236 } \
237 } \
238 omm_try_ins_ent_ret_; \
239 }))
240
242#define ccc_impl_omm_insert_or_assign_w(ordered_map_ptr, key, lazy_value...) \
243 (__extension__({ \
244 __auto_type omm_ins_or_assign_ptr_ = (ordered_map_ptr); \
245 struct ccc_ent_ omm_ins_or_assign_ent_ret_ \
246 = {.stats_ = CCC_ENTRY_ARG_ERROR}; \
247 if (omm_ins_or_assign_ptr_) \
248 { \
249 __auto_type omm_key_ = (key); \
250 struct ccc_omultimap_entry_ omm_ins_or_assign_ent_ \
251 = ccc_impl_omm_entry(omm_ins_or_assign_ptr_, \
252 (void *)&omm_key_); \
253 if (!(omm_ins_or_assign_ent_.entry_.stats_ & CCC_ENTRY_OCCUPIED)) \
254 { \
255 ccc_impl_omm_insert_and_copy_key(omm_ins_or_assign_ent_, \
256 omm_ins_or_assign_ent_ret_, \
257 omm_key_, lazy_value); \
258 } \
259 else if (omm_ins_or_assign_ent_.entry_.stats_ \
260 == CCC_ENTRY_OCCUPIED) \
261 { \
262 struct ccc_ommap_elem_ ins_ent_saved_ \
263 = *ccc_impl_ommap_elem_in_slot( \
264 omm_ins_or_assign_ent_.t_, \
265 omm_ins_or_assign_ent_.entry_.e_); \
266 *((typeof(lazy_value) *)omm_ins_or_assign_ent_.entry_.e_) \
267 = lazy_value; \
268 *ccc_impl_ommap_elem_in_slot(omm_ins_or_assign_ent_.t_, \
269 omm_ins_or_assign_ent_.entry_.e_) \
270 = ins_ent_saved_; \
271 omm_ins_or_assign_ent_ret_ = omm_ins_or_assign_ent_.entry_; \
272 *((typeof(omm_key_) *)ccc_impl_omm_key_in_slot( \
273 omm_ins_or_assign_ptr_, omm_ins_or_assign_ent_ret_.e_)) \
274 = omm_key_; \
275 } \
276 } \
277 omm_ins_or_assign_ent_ret_; \
278 }))
279
280/* NOLINTEND(readability-identifier-naming) */
281
282#endif /* CCC_IMPL_ORDERED_MULTIMAP_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