C Container Collection (CCC)
Loading...
Searching...
No Matches
impl_ordered_map.h
1#ifndef CCC_IMPL_ORDERED_MAP_H
2#define CCC_IMPL_ORDERED_MAP_H
3
5#include <stddef.h>
8#include "../types.h"
9#include "impl_types.h"
10
11/* NOLINTBEGIN(readability-identifier-naming) */
12
14typedef struct ccc_omap_elem_
15{
16 struct ccc_omap_elem_ *branch_[2];
17 struct ccc_omap_elem_ *parent_;
18} ccc_omap_elem_;
19
21struct ccc_omap_
22{
23 struct ccc_omap_elem_ *root_;
24 struct ccc_omap_elem_ end_;
25 ccc_alloc_fn *alloc_;
26 ccc_key_cmp_fn *cmp_;
27 void *aux_;
28 size_t size_;
29 size_t elem_sz_;
30 size_t node_elem_offset_;
31 size_t key_offset_;
32};
33
35struct ccc_otree_entry_
36{
37 struct ccc_omap_ *t_;
38 struct ccc_ent_ entry_;
39};
40
41union ccc_omap_entry_
42{
43 struct ccc_otree_entry_ impl_;
44};
45
46/*========================== Private Interface ============================*/
47
49void *ccc_impl_om_key_in_slot(struct ccc_omap_ const *t, void const *slot);
51ccc_omap_elem_ *ccc_impl_omap_elem_in_slot(struct ccc_omap_ const *t,
52 void const *slot);
54struct ccc_otree_entry_ ccc_impl_om_entry(struct ccc_omap_ *t, void const *key);
56void *ccc_impl_om_insert(struct ccc_omap_ *t, ccc_omap_elem_ *n);
57
58/*====================== Macro Implementations ========================*/
59
61#define ccc_impl_om_init(tree_name, struct_name, node_elem_field, \
62 key_elem_field, key_cmp_fn, alloc_fn, aux_data) \
63 { \
64 .root_ = &(tree_name).end_, \
65 .end_ = {.branch_ = {&(tree_name).end_, &(tree_name).end_}, \
66 .parent_ = &(tree_name).end_}, \
67 .alloc_ = (alloc_fn), \
68 .cmp_ = (key_cmp_fn), \
69 .aux_ = (aux_data), \
70 .size_ = 0, \
71 .elem_sz_ = sizeof(struct_name), \
72 .node_elem_offset_ = offsetof(struct_name, node_elem_field), \
73 .key_offset_ = offsetof(struct_name, key_elem_field), \
74 }
75
77#define ccc_impl_om_new(ordered_map_entry) \
78 (__extension__({ \
79 void *om_ins_alloc_ret_ = NULL; \
80 if ((ordered_map_entry)->t_->alloc_) \
81 { \
82 om_ins_alloc_ret_ \
83 = (ordered_map_entry) \
84 ->t_->alloc_(NULL, (ordered_map_entry)->t_->elem_sz_, \
85 (ordered_map_entry)->t_->aux_); \
86 } \
87 om_ins_alloc_ret_; \
88 }))
89
91#define ccc_impl_om_insert_key_val(ordered_map_entry, new_mem, \
92 lazy_key_value...) \
93 (__extension__({ \
94 if (new_mem) \
95 { \
96 *new_mem = lazy_key_value; \
97 new_mem = ccc_impl_om_insert( \
98 (ordered_map_entry)->t_, \
99 ccc_impl_omap_elem_in_slot((ordered_map_entry)->t_, new_mem)); \
100 } \
101 }))
102
104#define ccc_impl_om_insert_and_copy_key(om_insert_entry, om_insert_entry_ret, \
105 key, lazy_value...) \
106 (__extension__({ \
107 typeof(lazy_value) *om_new_ins_base_ \
108 = ccc_impl_om_new((&om_insert_entry)); \
109 om_insert_entry_ret = (struct ccc_ent_){ \
110 .e_ = om_new_ins_base_, \
111 .stats_ = CCC_ENTRY_INSERT_ERROR, \
112 }; \
113 if (om_new_ins_base_) \
114 { \
115 *((typeof(lazy_value) *)om_new_ins_base_) = lazy_value; \
116 *((typeof(key) *)ccc_impl_om_key_in_slot(om_insert_entry.t_, \
117 om_new_ins_base_)) \
118 = key; \
119 (void)ccc_impl_om_insert( \
120 om_insert_entry.t_, \
121 ccc_impl_omap_elem_in_slot(om_insert_entry.t_, \
122 om_new_ins_base_)); \
123 } \
124 }))
125
126/*===================== Core Macro Implementations ==================*/
127
129#define ccc_impl_om_and_modify_w(ordered_map_entry_ptr, type_name, \
130 closure_over_T...) \
131 (__extension__({ \
132 __auto_type om_ent_ptr_ = (ordered_map_entry_ptr); \
133 struct ccc_otree_entry_ om_mod_ent_ \
134 = {.entry_ = {.stats_ = CCC_ENTRY_ARG_ERROR}}; \
135 if (om_ent_ptr_) \
136 { \
137 om_mod_ent_ = om_ent_ptr_->impl_; \
138 if (om_mod_ent_.entry_.stats_ & CCC_ENTRY_OCCUPIED) \
139 { \
140 type_name *const T = om_mod_ent_.entry_.e_; \
141 if (T) \
142 { \
143 closure_over_T \
144 } \
145 } \
146 } \
147 om_mod_ent_; \
148 }))
149
151#define ccc_impl_om_or_insert_w(ordered_map_entry_ptr, lazy_key_value...) \
152 (__extension__({ \
153 __auto_type or_ins_entry_ptr_ = (ordered_map_entry_ptr); \
154 typeof(lazy_key_value) *or_ins_ret_ = NULL; \
155 if (or_ins_entry_ptr_) \
156 { \
157 struct ccc_otree_entry_ *om_or_ins_ent_ \
158 = &or_ins_entry_ptr_->impl_; \
159 if (om_or_ins_ent_->entry_.stats_ == CCC_ENTRY_OCCUPIED) \
160 { \
161 or_ins_ret_ = om_or_ins_ent_->entry_.e_; \
162 } \
163 else \
164 { \
165 or_ins_ret_ = ccc_impl_om_new(om_or_ins_ent_); \
166 ccc_impl_om_insert_key_val(om_or_ins_ent_, or_ins_ret_, \
167 lazy_key_value); \
168 } \
169 } \
170 or_ins_ret_; \
171 }))
172
174#define ccc_impl_om_insert_entry_w(ordered_map_entry_ptr, lazy_key_value...) \
175 (__extension__({ \
176 __auto_type ins_entry_ptr_ = (ordered_map_entry_ptr); \
177 typeof(lazy_key_value) *om_ins_ent_ret_ = NULL; \
178 if (ins_entry_ptr_) \
179 { \
180 struct ccc_otree_entry_ *om_ins_ent_ = &ins_entry_ptr_->impl_; \
181 if (!(om_ins_ent_->entry_.stats_ & CCC_ENTRY_OCCUPIED)) \
182 { \
183 om_ins_ent_ret_ = ccc_impl_om_new(om_ins_ent_); \
184 ccc_impl_om_insert_key_val(om_ins_ent_, om_ins_ent_ret_, \
185 lazy_key_value); \
186 } \
187 else if (om_ins_ent_->entry_.stats_ == CCC_ENTRY_OCCUPIED) \
188 { \
189 struct ccc_omap_elem_ ins_ent_saved_ \
190 = *ccc_impl_omap_elem_in_slot(om_ins_ent_->t_, \
191 om_ins_ent_->entry_.e_); \
192 *((typeof(lazy_key_value) *)om_ins_ent_->entry_.e_) \
193 = lazy_key_value; \
194 *ccc_impl_omap_elem_in_slot(om_ins_ent_->t_, \
195 om_ins_ent_->entry_.e_) \
196 = ins_ent_saved_; \
197 om_ins_ent_ret_ = om_ins_ent_->entry_.e_; \
198 } \
199 } \
200 om_ins_ent_ret_; \
201 }))
202
204#define ccc_impl_om_try_insert_w(ordered_map_ptr, key, lazy_value...) \
205 (__extension__({ \
206 __auto_type try_ins_map_ptr_ = (ordered_map_ptr); \
207 struct ccc_ent_ om_try_ins_ent_ret_ = {.stats_ = CCC_ENTRY_ARG_ERROR}; \
208 if (try_ins_map_ptr_) \
209 { \
210 __auto_type om_key_ = (key); \
211 struct ccc_otree_entry_ om_try_ins_ent_ \
212 = ccc_impl_om_entry(try_ins_map_ptr_, (void *)&om_key_); \
213 if (!(om_try_ins_ent_.entry_.stats_ & CCC_ENTRY_OCCUPIED)) \
214 { \
215 ccc_impl_om_insert_and_copy_key(om_try_ins_ent_, \
216 om_try_ins_ent_ret_, om_key_, \
217 lazy_value); \
218 } \
219 else if (om_try_ins_ent_.entry_.stats_ == CCC_ENTRY_OCCUPIED) \
220 { \
221 om_try_ins_ent_ret_ = om_try_ins_ent_.entry_; \
222 } \
223 } \
224 om_try_ins_ent_ret_; \
225 }))
226
228#define ccc_impl_om_insert_or_assign_w(ordered_map_ptr, key, lazy_value...) \
229 (__extension__({ \
230 __auto_type ins_or_assign_map_ptr_ = (ordered_map_ptr); \
231 struct ccc_ent_ om_ins_or_assign_ent_ret_ \
232 = {.stats_ = CCC_ENTRY_ARG_ERROR}; \
233 if (ins_or_assign_map_ptr_) \
234 { \
235 __auto_type om_key_ = (key); \
236 struct ccc_otree_entry_ om_ins_or_assign_ent_ \
237 = ccc_impl_om_entry(ins_or_assign_map_ptr_, (void *)&om_key_); \
238 if (!(om_ins_or_assign_ent_.entry_.stats_ & CCC_ENTRY_OCCUPIED)) \
239 { \
240 ccc_impl_om_insert_and_copy_key(om_ins_or_assign_ent_, \
241 om_ins_or_assign_ent_ret_, \
242 om_key_, lazy_value); \
243 } \
244 else if (om_ins_or_assign_ent_.entry_.stats_ \
245 == CCC_ENTRY_OCCUPIED) \
246 { \
247 struct ccc_omap_elem_ ins_ent_saved_ \
248 = *ccc_impl_omap_elem_in_slot( \
249 om_ins_or_assign_ent_.t_, \
250 om_ins_or_assign_ent_.entry_.e_); \
251 *((typeof(lazy_value) *)om_ins_or_assign_ent_.entry_.e_) \
252 = lazy_value; \
253 *ccc_impl_omap_elem_in_slot(om_ins_or_assign_ent_.t_, \
254 om_ins_or_assign_ent_.entry_.e_) \
255 = ins_ent_saved_; \
256 om_ins_or_assign_ent_ret_ = om_ins_or_assign_ent_.entry_; \
257 *((typeof(om_key_) *)ccc_impl_om_key_in_slot( \
258 ins_or_assign_map_ptr_, om_ins_or_assign_ent_ret_.e_)) \
259 = om_key_; \
260 } \
261 } \
262 om_ins_or_assign_ent_ret_; \
263 }))
264
265/* NOLINTEND(readability-identifier-naming) */
266
267#endif /* CCC_IMPL_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_omap_entry_
Definition: impl_ordered_map.h:42