C Container Collection (CCC)
Loading...
Searching...
No Matches
impl_handle_realtime_ordered_map.h
1
16#ifndef IMPL_HANDLE_REALTIME_ORDERED_MAP_H
17#define IMPL_HANDLE_REALTIME_ORDERED_MAP_H
18
20#include <stddef.h>
21#include <stdint.h>
24#include "../buffer.h"
25#include "../types.h"
26#include "impl_types.h"
27
28/* NOLINTBEGIN(readability-identifier-naming) */
29
35struct ccc_hromap_elem
36{
38 size_t branch[2];
39 union
40 {
42 size_t parent;
44 size_t next_free;
45 };
47 uint8_t parity;
48};
49
55struct ccc_hromap
56{
58 ccc_buffer buf;
60 size_t root;
62 size_t free_list;
64 size_t key_offset;
66 size_t node_elem_offset;
68 ccc_any_key_cmp_fn *cmp;
69};
70
72struct ccc_hrtree_handle
73{
75 struct ccc_hromap *hrm;
77 ccc_threeway_cmp last_cmp;
79 struct ccc_handl handle;
80};
81
83union ccc_hromap_handle
84{
86 struct ccc_hrtree_handle impl;
87};
88
89/*======================== Private Interface ==============================*/
90
92void *ccc_impl_hrm_key_at(struct ccc_hromap const *hrm, size_t slot);
94struct ccc_hromap_elem *ccc_impl_hrm_elem_at(struct ccc_hromap const *hrm,
95 size_t i);
97struct ccc_hrtree_handle ccc_impl_hrm_handle(struct ccc_hromap const *hrm,
98 void const *key);
100void ccc_impl_hrm_insert(struct ccc_hromap *hrm, size_t parent_i,
101 ccc_threeway_cmp last_cmp, size_t elem_i);
103size_t ccc_impl_hrm_alloc_slot(struct ccc_hromap *hrm);
104
105/*========================= Initialization =========================*/
106
108#define ccc_impl_hrm_init(impl_memory_ptr, impl_node_elem_field, \
109 impl_key_elem_field, impl_key_cmp_fn, impl_alloc_fn, \
110 impl_aux_data, impl_capacity) \
111 { \
112 .buf = ccc_buf_init(impl_memory_ptr, impl_alloc_fn, impl_aux_data, \
113 impl_capacity), \
114 .root = 0, \
115 .free_list = 0, \
116 .key_offset \
117 = offsetof(typeof(*(impl_memory_ptr)), impl_key_elem_field), \
118 .node_elem_offset \
119 = offsetof(typeof(*(impl_memory_ptr)), impl_node_elem_field), \
120 .cmp = (impl_key_cmp_fn), \
121 }
122
124#define ccc_impl_hrm_as(handle_realtime_ordered_map_ptr, type_name, handle...) \
125 ((type_name *)ccc_buf_at(&(handle_realtime_ordered_map_ptr)->buf, (handle)))
126
127/*================== Core Macro Implementations =====================*/
128
130#define ccc_impl_hrm_and_modify_w(handle_realtime_ordered_map_handle_ptr, \
131 type_name, closure_over_T...) \
132 (__extension__({ \
133 __auto_type impl_hrm_hndl_ptr \
134 = (handle_realtime_ordered_map_handle_ptr); \
135 struct ccc_hrtree_handle impl_hrm_mod_hndl \
136 = {.handle = {.stats = CCC_ENTRY_ARG_ERROR}}; \
137 if (impl_hrm_hndl_ptr) \
138 { \
139 impl_hrm_mod_hndl = impl_hrm_hndl_ptr->impl; \
140 if (impl_hrm_mod_hndl.handle.stats & CCC_ENTRY_OCCUPIED) \
141 { \
142 type_name *const T = ccc_buf_at(&impl_hrm_mod_hndl.hrm->buf, \
143 impl_hrm_mod_hndl.handle.i); \
144 if (T) \
145 { \
146 closure_over_T \
147 } \
148 } \
149 } \
150 impl_hrm_mod_hndl; \
151 }))
152
154#define ccc_impl_hrm_or_insert_w(handle_realtime_ordered_map_handle_ptr, \
155 lazy_key_value...) \
156 (__extension__({ \
157 __auto_type impl_or_ins_handle_ptr \
158 = (handle_realtime_ordered_map_handle_ptr); \
159 ccc_handle_i impl_hrm_or_ins_ret = 0; \
160 if (impl_or_ins_handle_ptr) \
161 { \
162 struct ccc_hrtree_handle *impl_hrm_or_ins_hndl \
163 = &impl_or_ins_handle_ptr->impl; \
164 if (impl_hrm_or_ins_hndl->handle.stats == CCC_ENTRY_OCCUPIED) \
165 { \
166 impl_hrm_or_ins_ret = impl_hrm_or_ins_hndl->handle.i; \
167 } \
168 else \
169 { \
170 impl_hrm_or_ins_ret \
171 = ccc_impl_hrm_alloc_slot(impl_hrm_or_ins_hndl->hrm); \
172 if (impl_hrm_or_ins_ret) \
173 { \
174 *((typeof(lazy_key_value) *)ccc_buf_at( \
175 &impl_hrm_or_ins_hndl->hrm->buf, impl_hrm_or_ins_ret)) \
176 = lazy_key_value; \
177 ccc_impl_hrm_insert(impl_hrm_or_ins_hndl->hrm, \
178 impl_hrm_or_ins_hndl->handle.i, \
179 impl_hrm_or_ins_hndl->last_cmp, \
180 impl_hrm_or_ins_ret); \
181 } \
182 } \
183 } \
184 impl_hrm_or_ins_ret; \
185 }))
186
188#define ccc_impl_hrm_insert_handle_w(handle_realtime_ordered_map_handle_ptr, \
189 lazy_key_value...) \
190 (__extension__({ \
191 __auto_type impl_ins_handle_ptr \
192 = (handle_realtime_ordered_map_handle_ptr); \
193 ccc_handle_i impl_hrm_ins_hndl_ret = 0; \
194 if (impl_ins_handle_ptr) \
195 { \
196 struct ccc_hrtree_handle *impl_hrm_ins_hndl \
197 = &impl_ins_handle_ptr->impl; \
198 if (!(impl_hrm_ins_hndl->handle.stats & CCC_ENTRY_OCCUPIED)) \
199 { \
200 impl_hrm_ins_hndl_ret \
201 = ccc_impl_hrm_alloc_slot(impl_hrm_ins_hndl->hrm); \
202 if (impl_hrm_ins_hndl_ret) \
203 { \
204 *((typeof(lazy_key_value) *)ccc_buf_at( \
205 &impl_hrm_ins_hndl->hrm->buf, impl_hrm_ins_hndl_ret)) \
206 = lazy_key_value; \
207 ccc_impl_hrm_insert( \
208 impl_hrm_ins_hndl->hrm, impl_hrm_ins_hndl->handle.i, \
209 impl_hrm_ins_hndl->last_cmp, impl_hrm_ins_hndl_ret); \
210 } \
211 } \
212 else if (impl_hrm_ins_hndl->handle.stats == CCC_ENTRY_OCCUPIED) \
213 { \
214 impl_hrm_ins_hndl_ret = impl_hrm_ins_hndl->handle.i; \
215 struct ccc_hromap_elem impl_ins_hndl_saved \
216 = *ccc_impl_hrm_elem_at(impl_hrm_ins_hndl->hrm, \
217 impl_hrm_ins_hndl_ret); \
218 *((typeof(lazy_key_value) *)ccc_buf_at( \
219 &impl_hrm_ins_hndl->hrm->buf, impl_hrm_ins_hndl_ret)) \
220 = lazy_key_value; \
221 *ccc_impl_hrm_elem_at(impl_hrm_ins_hndl->hrm, \
222 impl_hrm_ins_hndl_ret) \
223 = impl_ins_hndl_saved; \
224 } \
225 } \
226 impl_hrm_ins_hndl_ret; \
227 }))
228
230#define ccc_impl_hrm_try_insert_w(handle_realtime_ordered_map_ptr, key, \
231 lazy_value...) \
232 (__extension__({ \
233 __auto_type impl_try_ins_map_ptr = (handle_realtime_ordered_map_ptr); \
234 struct ccc_handl impl_hrm_try_ins_hndl_ret \
235 = {.stats = CCC_ENTRY_ARG_ERROR}; \
236 if (impl_try_ins_map_ptr) \
237 { \
238 __auto_type impl_hrm_key = (key); \
239 struct ccc_hrtree_handle impl_hrm_try_ins_hndl \
240 = ccc_impl_hrm_handle(impl_try_ins_map_ptr, \
241 (void *)&impl_hrm_key); \
242 if (!(impl_hrm_try_ins_hndl.handle.stats & CCC_ENTRY_OCCUPIED)) \
243 { \
244 impl_hrm_try_ins_hndl_ret = (struct ccc_handl){ \
245 .i = ccc_impl_hrm_alloc_slot(impl_hrm_try_ins_hndl.hrm), \
246 .stats = CCC_ENTRY_INSERT_ERROR, \
247 }; \
248 if (impl_hrm_try_ins_hndl_ret.i) \
249 { \
250 *((typeof(lazy_value) *)ccc_buf_at( \
251 &impl_try_ins_map_ptr->buf, \
252 impl_hrm_try_ins_hndl_ret.i)) \
253 = lazy_value; \
254 *((typeof(impl_hrm_key) *)ccc_impl_hrm_key_at( \
255 impl_try_ins_map_ptr, impl_hrm_try_ins_hndl_ret.i)) \
256 = impl_hrm_key; \
257 ccc_impl_hrm_insert(impl_hrm_try_ins_hndl.hrm, \
258 impl_hrm_try_ins_hndl.handle.i, \
259 impl_hrm_try_ins_hndl.last_cmp, \
260 impl_hrm_try_ins_hndl_ret.i); \
261 impl_hrm_try_ins_hndl_ret.stats = CCC_ENTRY_VACANT; \
262 } \
263 } \
264 else if (impl_hrm_try_ins_hndl.handle.stats == CCC_ENTRY_OCCUPIED) \
265 { \
266 impl_hrm_try_ins_hndl_ret = (struct ccc_handl){ \
267 .i = impl_hrm_try_ins_hndl.handle.i, \
268 .stats = impl_hrm_try_ins_hndl.handle.stats, \
269 }; \
270 } \
271 } \
272 impl_hrm_try_ins_hndl_ret; \
273 }))
274
276#define ccc_impl_hrm_insert_or_assign_w(handle_realtime_ordered_map_ptr, key, \
277 lazy_value...) \
278 (__extension__({ \
279 __auto_type impl_ins_or_assign_map_ptr \
280 = (handle_realtime_ordered_map_ptr); \
281 struct ccc_handl impl_hrm_ins_or_assign_hndl_ret \
282 = {.stats = CCC_ENTRY_ARG_ERROR}; \
283 if (impl_ins_or_assign_map_ptr) \
284 { \
285 __auto_type impl_hrm_key = (key); \
286 struct ccc_hrtree_handle impl_hrm_ins_or_assign_hndl \
287 = ccc_impl_hrm_handle(impl_ins_or_assign_map_ptr, \
288 (void *)&impl_hrm_key); \
289 if (!(impl_hrm_ins_or_assign_hndl.handle.stats \
290 & CCC_ENTRY_OCCUPIED)) \
291 { \
292 impl_hrm_ins_or_assign_hndl_ret \
293 = (struct ccc_handl){.i = ccc_impl_hrm_alloc_slot( \
294 impl_hrm_ins_or_assign_hndl.hrm), \
295 .stats = CCC_ENTRY_INSERT_ERROR}; \
296 if (impl_hrm_ins_or_assign_hndl_ret.i) \
297 { \
298 *((typeof(lazy_value) *)ccc_buf_at( \
299 &impl_hrm_ins_or_assign_hndl.hrm->buf, \
300 impl_hrm_ins_or_assign_hndl_ret.i)) \
301 = lazy_value; \
302 *((typeof(impl_hrm_key) *)ccc_impl_hrm_key_at( \
303 impl_hrm_ins_or_assign_hndl.hrm, \
304 impl_hrm_ins_or_assign_hndl_ret.i)) \
305 = impl_hrm_key; \
306 ccc_impl_hrm_insert(impl_hrm_ins_or_assign_hndl.hrm, \
307 impl_hrm_ins_or_assign_hndl.handle.i, \
308 impl_hrm_ins_or_assign_hndl.last_cmp, \
309 impl_hrm_ins_or_assign_hndl_ret.i); \
310 impl_hrm_ins_or_assign_hndl_ret.stats = CCC_ENTRY_VACANT; \
311 } \
312 } \
313 else if (impl_hrm_ins_or_assign_hndl.handle.stats \
314 == CCC_ENTRY_OCCUPIED) \
315 { \
316 struct ccc_hromap_elem impl_ins_hndl_saved \
317 = *ccc_impl_hrm_elem_at( \
318 impl_hrm_ins_or_assign_hndl.hrm, \
319 impl_hrm_ins_or_assign_hndl.handle.i); \
320 *((typeof(lazy_value) *)ccc_buf_at( \
321 &impl_hrm_ins_or_assign_hndl.hrm->buf, \
322 impl_hrm_ins_or_assign_hndl.handle.i)) \
323 = lazy_value; \
324 *ccc_impl_hrm_elem_at(impl_hrm_ins_or_assign_hndl.hrm, \
325 impl_hrm_ins_or_assign_hndl.handle.i) \
326 = impl_ins_hndl_saved; \
327 impl_hrm_ins_or_assign_hndl_ret = (struct ccc_handl){ \
328 .i = impl_hrm_ins_or_assign_hndl.handle.i, \
329 .stats = impl_hrm_ins_or_assign_hndl.handle.stats}; \
330 *((typeof(impl_hrm_key) *)ccc_impl_hrm_key_at( \
331 impl_hrm_ins_or_assign_hndl.hrm, \
332 impl_hrm_ins_or_assign_hndl.handle.i)) \
333 = impl_hrm_key; \
334 } \
335 } \
336 impl_hrm_ins_or_assign_hndl_ret; \
337 }))
338
339/* NOLINTEND(readability-identifier-naming) */
340
341#endif /* IMPL_HANDLE_REALTIME_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_hromap_handle
union ccc_hromap_handle ccc_hromap_handle
A container specific handle used to implement the Handle Interface.
Definition: handle_realtime_ordered_map.h:82
ccc_hromap_elem
struct ccc_hromap_elem ccc_hromap_elem
The intrusive element for the user defined struct being stored in the map.
Definition: handle_realtime_ordered_map.h:72
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