C Container Collection (CCC)
Loading...
Searching...
No Matches
impl_handle_ordered_map.h
1
16#ifndef CCC_IMPL_HANDLE_ORDERED_MAP_H
17#define CCC_IMPL_HANDLE_ORDERED_MAP_H
18
20#include <stddef.h>
23#include "../buffer.h"
24#include "../types.h"
25#include "impl_types.h"
26
27/* NOLINTBEGIN(readability-identifier-naming) */
28
34struct ccc_homap_elem
35{
37 size_t branch[2];
38 union
39 {
41 size_t parent;
43 size_t next_free;
44 };
45};
46
52struct ccc_homap
53{
55 ccc_buffer buf;
57 size_t root;
59 size_t free_list;
61 size_t key_offset;
63 size_t node_elem_offset;
65 ccc_any_key_cmp_fn *cmp;
66};
67
70struct ccc_htree_handle
71{
73 struct ccc_homap *hom;
75 ccc_threeway_cmp last_cmp;
77 struct ccc_handl handle;
78};
79
83union ccc_homap_handle
84{
86 struct ccc_htree_handle impl;
87};
88
89/*=========================== Private Interface ===========================*/
90
92void ccc_impl_hom_insert(struct ccc_homap *hom, size_t elem_i);
94struct ccc_htree_handle ccc_impl_hom_handle(struct ccc_homap *hom,
95 void const *key);
97void *ccc_impl_hom_key_at(struct ccc_homap const *hom, size_t slot);
99struct ccc_homap_elem *ccc_impl_homap_elem_at(struct ccc_homap const *hom,
100 size_t slot);
102size_t ccc_impl_hom_alloc_slot(struct ccc_homap *hom);
103
104/*======================== Initialization =========================*/
105
107#define ccc_impl_hom_init(impl_mem_ptr, impl_node_elem_field, \
108 impl_key_elem_field, impl_key_cmp_fn, impl_alloc_fn, \
109 impl_aux_data, impl_capacity) \
110 { \
111 .buf = ccc_buf_init(impl_mem_ptr, impl_alloc_fn, impl_aux_data, \
112 impl_capacity), \
113 .root = 0, \
114 .free_list = 0, \
115 .key_offset = offsetof(typeof(*(impl_mem_ptr)), impl_key_elem_field), \
116 .node_elem_offset \
117 = offsetof(typeof(*(impl_mem_ptr)), impl_node_elem_field), \
118 .cmp = (impl_key_cmp_fn), \
119 }
120
122#define ccc_impl_hom_as(handle_ordered_map_ptr, type_name, handle...) \
123 ((type_name *)ccc_buf_at(&(handle_ordered_map_ptr)->buf, (handle)))
124
125/*================== Core Macro Implementations =====================*/
126
128#define ccc_impl_hom_and_modify_w(handle_ordered_map_handle_ptr, type_name, \
129 closure_over_T...) \
130 (__extension__({ \
131 __auto_type impl_hom_mod_hndl_ptr = (handle_ordered_map_handle_ptr); \
132 struct ccc_htree_handle impl_hom_mod_hndl \
133 = {.handle = {.stats = CCC_ENTRY_ARG_ERROR}}; \
134 if (impl_hom_mod_hndl_ptr) \
135 { \
136 impl_hom_mod_hndl = impl_hom_mod_hndl_ptr->impl; \
137 if (impl_hom_mod_hndl.handle.stats & CCC_ENTRY_OCCUPIED) \
138 { \
139 type_name *const T = ccc_buf_at(&impl_hom_mod_hndl.hom->buf, \
140 impl_hom_mod_hndl.handle.i); \
141 if (T) \
142 { \
143 closure_over_T \
144 } \
145 } \
146 } \
147 impl_hom_mod_hndl; \
148 }))
149
151#define ccc_impl_hom_or_insert_w(handle_ordered_map_handle_ptr, \
152 lazy_key_value...) \
153 (__extension__({ \
154 __auto_type impl_hom_or_ins_hndl_ptr \
155 = (handle_ordered_map_handle_ptr); \
156 ccc_handle_i impl_hom_or_ins_ret = 0; \
157 if (impl_hom_or_ins_hndl_ptr) \
158 { \
159 struct ccc_htree_handle *impl_hom_or_ins_hndl \
160 = &impl_hom_or_ins_hndl_ptr->impl; \
161 if (impl_hom_or_ins_hndl->handle.stats == CCC_ENTRY_OCCUPIED) \
162 { \
163 impl_hom_or_ins_ret = impl_hom_or_ins_hndl->handle.i; \
164 } \
165 else \
166 { \
167 impl_hom_or_ins_ret \
168 = ccc_impl_hom_alloc_slot(impl_hom_or_ins_hndl->hom); \
169 if (impl_hom_or_ins_ret) \
170 { \
171 *((typeof(lazy_key_value) *)ccc_buf_at( \
172 &impl_hom_or_ins_hndl->hom->buf, impl_hom_or_ins_ret)) \
173 = lazy_key_value; \
174 ccc_impl_hom_insert(impl_hom_or_ins_hndl->hom, \
175 impl_hom_or_ins_ret); \
176 } \
177 } \
178 } \
179 impl_hom_or_ins_ret; \
180 }))
181
183#define ccc_impl_hom_insert_handle_w(handle_ordered_map_handle_ptr, \
184 lazy_key_value...) \
185 (__extension__({ \
186 __auto_type impl_hom_ins_hndl_ptr = (handle_ordered_map_handle_ptr); \
187 ccc_handle_i impl_hom_ins_hndl_ret = 0; \
188 if (impl_hom_ins_hndl_ptr) \
189 { \
190 struct ccc_htree_handle *impl_hom_ins_hndl \
191 = &impl_hom_ins_hndl_ptr->impl; \
192 if (!(impl_hom_ins_hndl->handle.stats & CCC_ENTRY_OCCUPIED)) \
193 { \
194 impl_hom_ins_hndl_ret \
195 = ccc_impl_hom_alloc_slot(impl_hom_ins_hndl->hom); \
196 if (impl_hom_ins_hndl_ret) \
197 { \
198 *((typeof(lazy_key_value) *)ccc_buf_at( \
199 &impl_hom_ins_hndl->hom->buf, impl_hom_ins_hndl_ret)) \
200 = lazy_key_value; \
201 ccc_impl_hom_insert(impl_hom_ins_hndl->hom, \
202 impl_hom_ins_hndl_ret); \
203 } \
204 } \
205 else if (impl_hom_ins_hndl->handle.stats == CCC_ENTRY_OCCUPIED) \
206 { \
207 impl_hom_ins_hndl_ret = impl_hom_ins_hndl->handle.i; \
208 struct ccc_homap_elem impl_ins_hndl_saved \
209 = *ccc_impl_homap_elem_at(impl_hom_ins_hndl->hom, \
210 impl_hom_ins_hndl_ret); \
211 *((typeof(lazy_key_value) *)ccc_buf_at( \
212 &impl_hom_ins_hndl->hom->buf, impl_hom_ins_hndl_ret)) \
213 = lazy_key_value; \
214 *ccc_impl_homap_elem_at(impl_hom_ins_hndl->hom, \
215 impl_hom_ins_hndl_ret) \
216 = impl_ins_hndl_saved; \
217 } \
218 } \
219 impl_hom_ins_hndl_ret; \
220 }))
221
223#define ccc_impl_hom_try_insert_w(handle_ordered_map_ptr, key, lazy_value...) \
224 (__extension__({ \
225 __auto_type impl_hom_try_ins_map_ptr = (handle_ordered_map_ptr); \
226 struct ccc_handl impl_hom_try_ins_hndl_ret \
227 = {.stats = CCC_ENTRY_ARG_ERROR}; \
228 if (impl_hom_try_ins_map_ptr) \
229 { \
230 __auto_type impl_hom_key = (key); \
231 struct ccc_htree_handle impl_hom_try_ins_hndl \
232 = ccc_impl_hom_handle(impl_hom_try_ins_map_ptr, \
233 (void *)&impl_hom_key); \
234 if (!(impl_hom_try_ins_hndl.handle.stats & CCC_ENTRY_OCCUPIED)) \
235 { \
236 impl_hom_try_ins_hndl_ret = (struct ccc_handl){ \
237 .i = ccc_impl_hom_alloc_slot(impl_hom_try_ins_hndl.hom), \
238 .stats = CCC_ENTRY_INSERT_ERROR}; \
239 if (impl_hom_try_ins_hndl_ret.i) \
240 { \
241 *((typeof(lazy_value) *)ccc_buf_at( \
242 &impl_hom_try_ins_map_ptr->buf, \
243 impl_hom_try_ins_hndl_ret.i)) \
244 = lazy_value; \
245 *((typeof(impl_hom_key) *)ccc_impl_hom_key_at( \
246 impl_hom_try_ins_hndl.hom, \
247 impl_hom_try_ins_hndl_ret.i)) \
248 = impl_hom_key; \
249 ccc_impl_hom_insert(impl_hom_try_ins_hndl.hom, \
250 impl_hom_try_ins_hndl_ret.i); \
251 impl_hom_try_ins_hndl_ret.stats = CCC_ENTRY_VACANT; \
252 } \
253 } \
254 else if (impl_hom_try_ins_hndl.handle.stats == CCC_ENTRY_OCCUPIED) \
255 { \
256 impl_hom_try_ins_hndl_ret = (struct ccc_handl){ \
257 .i = impl_hom_try_ins_hndl.handle.i, \
258 .stats = impl_hom_try_ins_hndl.handle.stats}; \
259 } \
260 } \
261 impl_hom_try_ins_hndl_ret; \
262 }))
263
265#define ccc_impl_hom_insert_or_assign_w(handle_ordered_map_ptr, key, \
266 lazy_value...) \
267 (__extension__({ \
268 __auto_type impl_hom_ins_or_assign_map_ptr = (handle_ordered_map_ptr); \
269 struct ccc_handl impl_hom_ins_or_assign_hndl_ret \
270 = {.stats = CCC_ENTRY_ARG_ERROR}; \
271 if (impl_hom_ins_or_assign_map_ptr) \
272 { \
273 __auto_type impl_hom_key = (key); \
274 struct ccc_htree_handle impl_hom_ins_or_assign_hndl \
275 = ccc_impl_hom_handle(impl_hom_ins_or_assign_map_ptr, \
276 (void *)&impl_hom_key); \
277 if (!(impl_hom_ins_or_assign_hndl.handle.stats \
278 & CCC_ENTRY_OCCUPIED)) \
279 { \
280 impl_hom_ins_or_assign_hndl_ret \
281 = (struct ccc_handl){.i = ccc_impl_hom_alloc_slot( \
282 impl_hom_ins_or_assign_hndl.hom), \
283 .stats = CCC_ENTRY_INSERT_ERROR}; \
284 if (impl_hom_ins_or_assign_hndl_ret.i) \
285 { \
286 *((typeof(lazy_value) *)ccc_buf_at( \
287 &impl_hom_ins_or_assign_map_ptr->buf, \
288 impl_hom_ins_or_assign_hndl_ret.i)) \
289 = lazy_value; \
290 *((typeof(impl_hom_key) *)ccc_impl_hom_key_at( \
291 impl_hom_ins_or_assign_hndl.hom, \
292 impl_hom_ins_or_assign_hndl_ret.i)) \
293 = impl_hom_key; \
294 ccc_impl_hom_insert(impl_hom_ins_or_assign_hndl.hom, \
295 impl_hom_ins_or_assign_hndl_ret.i); \
296 impl_hom_ins_or_assign_hndl_ret.stats = CCC_ENTRY_VACANT; \
297 } \
298 } \
299 else if (impl_hom_ins_or_assign_hndl.handle.stats \
300 == CCC_ENTRY_OCCUPIED) \
301 { \
302 struct ccc_homap_elem impl_ins_hndl_saved \
303 = *ccc_impl_homap_elem_at( \
304 impl_hom_ins_or_assign_hndl.hom, \
305 impl_hom_ins_or_assign_hndl.handle.i); \
306 *((typeof(lazy_value) *)ccc_buf_at( \
307 &impl_hom_ins_or_assign_hndl.hom->buf, \
308 impl_hom_ins_or_assign_hndl.handle.i)) \
309 = lazy_value; \
310 *ccc_impl_homap_elem_at(impl_hom_ins_or_assign_hndl.hom, \
311 impl_hom_ins_or_assign_hndl.handle.i) \
312 = impl_ins_hndl_saved; \
313 impl_hom_ins_or_assign_hndl_ret = (struct ccc_handl){ \
314 .i = impl_hom_ins_or_assign_hndl.handle.i, \
315 .stats = impl_hom_ins_or_assign_hndl.handle.stats}; \
316 *((typeof(impl_hom_key) *)ccc_impl_hom_key_at( \
317 impl_hom_ins_or_assign_hndl.hom, \
318 impl_hom_ins_or_assign_hndl.handle.i)) \
319 = impl_hom_key; \
320 } \
321 } \
322 impl_hom_ins_or_assign_hndl_ret; \
323 }))
324
325/* NOLINTEND(readability-identifier-naming) */
326
327#endif /* CCC_IMPL_HANDLE_ORDERED_MAP_H */
ccc_buffer
struct ccc_buffer ccc_buffer
A contiguous block of storage for elements of the same type.
Definition: buffer.h:65
ccc_homap_handle
union ccc_homap_handle ccc_homap_handle
A container specific handle used to implement the Handle Interface.
Definition: handle_ordered_map.h:82
ccc_homap_elem
struct ccc_homap_elem ccc_homap_elem
The intrusive element for the user defined type being stored in the map.
Definition: handle_ordered_map.h:76
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
ccc_threeway_cmp
ccc_threeway_cmp
A three-way comparison for comparison functions.
Definition: types.h:153