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 <limits.h>
21#include <stddef.h>
22#include <stdint.h>
25#include "../types.h"
26#include "impl_types.h" /* NOLINT */
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 };
46};
47
117struct ccc_hromap
118{
120 void *data;
122 struct ccc_hromap_elem *nodes;
124 unsigned *parity;
126 size_t capacity;
128 size_t count;
130 size_t root;
132 size_t free_list;
134 size_t sizeof_type;
136 size_t key_offset;
138 ccc_any_key_cmp_fn *cmp;
140 ccc_any_alloc_fn *alloc;
142 void *aux;
143};
144
146struct ccc_hrtree_handle
147{
149 struct ccc_hromap *hrm;
151 size_t i;
153 ccc_threeway_cmp last_cmp;
155 ccc_entry_status stats;
156};
157
159union ccc_hromap_handle
160{
162 struct ccc_hrtree_handle impl;
163};
164
165/*======================== Private Interface ==============================*/
166
168void *ccc_impl_hrm_data_at(struct ccc_hromap const *hrm, size_t slot);
170void *ccc_impl_hrm_key_at(struct ccc_hromap const *hrm, size_t slot);
172struct ccc_hromap_elem *ccc_impl_hrm_elem_at(struct ccc_hromap const *hrm,
173 size_t i);
175struct ccc_hrtree_handle ccc_impl_hrm_handle(struct ccc_hromap const *hrm,
176 void const *key);
178void ccc_impl_hrm_insert(struct ccc_hromap *hrm, size_t parent_i,
179 ccc_threeway_cmp last_cmp, size_t elem_i);
181size_t ccc_impl_hrm_alloc_slot(struct ccc_hromap *hrm);
182
183/*========================= Initialization =========================*/
184
188#define ccc_impl_hrm_blocks(impl_cap) \
189 (((impl_cap) + ((sizeof(*(struct ccc_hromap){}.parity) * CHAR_BIT) - 1)) \
190 / (sizeof(*(struct ccc_hromap){}.parity) * CHAR_BIT))
191
195#define ccc_impl_hrm_declare_fixed_map(impl_fixed_map_type_name, \
196 impl_key_val_type_name, impl_capacity) \
197 static_assert((impl_capacity) > 1, \
198 "fixed size map must have capacity greater than 1"); \
199 typedef struct \
200 { \
201 impl_key_val_type_name data[(impl_capacity)]; \
202 struct ccc_hromap_elem nodes[(impl_capacity)]; \
203 typeof(*(struct ccc_hromap){} \
204 .parity) parity[ccc_impl_hrm_blocks((impl_capacity))]; \
205 }(impl_fixed_map_type_name)
206
209#define ccc_impl_hrm_fixed_capacity(fixed_map_type_name) \
210 (sizeof((fixed_map_type_name){}.nodes) / sizeof(struct ccc_hromap_elem))
211
217#define ccc_impl_hrm_init(impl_memory_ptr, impl_type_name, \
218 impl_key_elem_field, impl_key_cmp_fn, impl_alloc_fn, \
219 impl_aux_data, impl_capacity) \
220 { \
221 .data = (impl_memory_ptr), \
222 .nodes = NULL, \
223 .parity = NULL, \
224 .capacity = (impl_capacity), \
225 .count = 0, \
226 .root = 0, \
227 .free_list = 0, \
228 .sizeof_type = sizeof(impl_type_name), \
229 .key_offset = offsetof(impl_type_name, impl_key_elem_field), \
230 .cmp = (impl_key_cmp_fn), \
231 .alloc = (impl_alloc_fn), \
232 .aux = (impl_aux_data), \
233 }
234
236#define ccc_impl_hrm_as(handle_realtime_ordered_map_ptr, type_name, handle...) \
237 ((type_name *)ccc_impl_hrm_data_at((handle_realtime_ordered_map_ptr), \
238 (handle)))
239
240/*================== Core Macro Implementations =====================*/
241
243#define ccc_impl_hrm_and_modify_w(handle_realtime_ordered_map_handle_ptr, \
244 type_name, closure_over_T...) \
245 (__extension__({ \
246 __auto_type impl_hrm_hndl_ptr \
247 = (handle_realtime_ordered_map_handle_ptr); \
248 struct ccc_hrtree_handle impl_hrm_mod_hndl \
249 = {.stats = CCC_ENTRY_ARG_ERROR}; \
250 if (impl_hrm_hndl_ptr) \
251 { \
252 impl_hrm_mod_hndl = impl_hrm_hndl_ptr->impl; \
253 if (impl_hrm_mod_hndl.stats & CCC_ENTRY_OCCUPIED) \
254 { \
255 type_name *const T = ccc_impl_hrm_data_at( \
256 impl_hrm_mod_hndl.hrm, impl_hrm_mod_hndl.i); \
257 if (T) \
258 { \
259 closure_over_T \
260 } \
261 } \
262 } \
263 impl_hrm_mod_hndl; \
264 }))
265
267#define ccc_impl_hrm_or_insert_w(handle_realtime_ordered_map_handle_ptr, \
268 lazy_key_value...) \
269 (__extension__({ \
270 __auto_type impl_or_ins_handle_ptr \
271 = (handle_realtime_ordered_map_handle_ptr); \
272 ccc_handle_i impl_hrm_or_ins_ret = 0; \
273 if (impl_or_ins_handle_ptr) \
274 { \
275 if (impl_or_ins_handle_ptr->impl.stats == CCC_ENTRY_OCCUPIED) \
276 { \
277 impl_hrm_or_ins_ret = impl_or_ins_handle_ptr->impl.i; \
278 } \
279 else \
280 { \
281 impl_hrm_or_ins_ret = ccc_impl_hrm_alloc_slot( \
282 impl_or_ins_handle_ptr->impl.hrm); \
283 if (impl_hrm_or_ins_ret) \
284 { \
285 *((typeof(lazy_key_value) *)ccc_impl_hrm_data_at( \
286 impl_or_ins_handle_ptr->impl.hrm, \
287 impl_hrm_or_ins_ret)) \
288 = lazy_key_value; \
289 ccc_impl_hrm_insert(impl_or_ins_handle_ptr->impl.hrm, \
290 impl_or_ins_handle_ptr->impl.i, \
291 impl_or_ins_handle_ptr->impl.last_cmp, \
292 impl_hrm_or_ins_ret); \
293 } \
294 } \
295 } \
296 impl_hrm_or_ins_ret; \
297 }))
298
300#define ccc_impl_hrm_insert_handle_w(handle_realtime_ordered_map_handle_ptr, \
301 lazy_key_value...) \
302 (__extension__({ \
303 __auto_type impl_ins_handle_ptr \
304 = (handle_realtime_ordered_map_handle_ptr); \
305 ccc_handle_i impl_hrm_ins_hndl_ret = 0; \
306 if (impl_ins_handle_ptr) \
307 { \
308 if (!(impl_ins_handle_ptr->impl.stats & CCC_ENTRY_OCCUPIED)) \
309 { \
310 impl_hrm_ins_hndl_ret \
311 = ccc_impl_hrm_alloc_slot(impl_ins_handle_ptr->impl.hrm); \
312 if (impl_hrm_ins_hndl_ret) \
313 { \
314 *((typeof(lazy_key_value) *)ccc_impl_hrm_data_at( \
315 impl_ins_handle_ptr->impl.hrm, impl_hrm_ins_hndl_ret)) \
316 = lazy_key_value; \
317 ccc_impl_hrm_insert(impl_ins_handle_ptr->impl.hrm, \
318 impl_ins_handle_ptr->impl.i, \
319 impl_ins_handle_ptr->impl.last_cmp, \
320 impl_hrm_ins_hndl_ret); \
321 } \
322 } \
323 else if (impl_ins_handle_ptr->impl.stats == CCC_ENTRY_OCCUPIED) \
324 { \
325 impl_hrm_ins_hndl_ret = impl_ins_handle_ptr->impl.i; \
326 *((typeof(lazy_key_value) *)ccc_impl_hrm_data_at( \
327 impl_ins_handle_ptr->impl.hrm, impl_hrm_ins_hndl_ret)) \
328 = lazy_key_value; \
329 } \
330 } \
331 impl_hrm_ins_hndl_ret; \
332 }))
333
335#define ccc_impl_hrm_try_insert_w(handle_realtime_ordered_map_ptr, key, \
336 lazy_value...) \
337 (__extension__({ \
338 __auto_type impl_try_ins_map_ptr = (handle_realtime_ordered_map_ptr); \
339 struct ccc_handl impl_hrm_try_ins_hndl_ret \
340 = {.stats = CCC_ENTRY_ARG_ERROR}; \
341 if (impl_try_ins_map_ptr) \
342 { \
343 __auto_type impl_hrm_key = (key); \
344 struct ccc_hrtree_handle impl_hrm_try_ins_hndl \
345 = ccc_impl_hrm_handle(impl_try_ins_map_ptr, \
346 (void *)&impl_hrm_key); \
347 if (!(impl_hrm_try_ins_hndl.stats & CCC_ENTRY_OCCUPIED)) \
348 { \
349 impl_hrm_try_ins_hndl_ret = (struct ccc_handl){ \
350 .i = ccc_impl_hrm_alloc_slot(impl_hrm_try_ins_hndl.hrm), \
351 .stats = CCC_ENTRY_INSERT_ERROR, \
352 }; \
353 if (impl_hrm_try_ins_hndl_ret.i) \
354 { \
355 *((typeof(lazy_value) *)ccc_impl_hrm_data_at( \
356 impl_try_ins_map_ptr, impl_hrm_try_ins_hndl_ret.i)) \
357 = lazy_value; \
358 *((typeof(impl_hrm_key) *)ccc_impl_hrm_key_at( \
359 impl_try_ins_map_ptr, impl_hrm_try_ins_hndl_ret.i)) \
360 = impl_hrm_key; \
361 ccc_impl_hrm_insert(impl_hrm_try_ins_hndl.hrm, \
362 impl_hrm_try_ins_hndl.i, \
363 impl_hrm_try_ins_hndl.last_cmp, \
364 impl_hrm_try_ins_hndl_ret.i); \
365 impl_hrm_try_ins_hndl_ret.stats = CCC_ENTRY_VACANT; \
366 } \
367 } \
368 else if (impl_hrm_try_ins_hndl.stats == CCC_ENTRY_OCCUPIED) \
369 { \
370 impl_hrm_try_ins_hndl_ret = (struct ccc_handl){ \
371 .i = impl_hrm_try_ins_hndl.i, \
372 .stats = impl_hrm_try_ins_hndl.stats, \
373 }; \
374 } \
375 } \
376 impl_hrm_try_ins_hndl_ret; \
377 }))
378
380#define ccc_impl_hrm_insert_or_assign_w(handle_realtime_ordered_map_ptr, key, \
381 lazy_value...) \
382 (__extension__({ \
383 __auto_type impl_ins_or_assign_map_ptr \
384 = (handle_realtime_ordered_map_ptr); \
385 struct ccc_handl impl_hrm_ins_or_assign_hndl_ret \
386 = {.stats = CCC_ENTRY_ARG_ERROR}; \
387 if (impl_ins_or_assign_map_ptr) \
388 { \
389 __auto_type impl_hrm_key = (key); \
390 struct ccc_hrtree_handle impl_hrm_ins_or_assign_hndl \
391 = ccc_impl_hrm_handle(impl_ins_or_assign_map_ptr, \
392 (void *)&impl_hrm_key); \
393 if (!(impl_hrm_ins_or_assign_hndl.stats & CCC_ENTRY_OCCUPIED)) \
394 { \
395 impl_hrm_ins_or_assign_hndl_ret = (struct ccc_handl){ \
396 .i = ccc_impl_hrm_alloc_slot( \
397 impl_hrm_ins_or_assign_hndl.hrm), \
398 .stats = CCC_ENTRY_INSERT_ERROR, \
399 }; \
400 if (impl_hrm_ins_or_assign_hndl_ret.i) \
401 { \
402 *((typeof(lazy_value) *)ccc_impl_hrm_data_at( \
403 impl_hrm_ins_or_assign_hndl.hrm, \
404 impl_hrm_ins_or_assign_hndl_ret.i)) \
405 = lazy_value; \
406 *((typeof(impl_hrm_key) *)ccc_impl_hrm_key_at( \
407 impl_hrm_ins_or_assign_hndl.hrm, \
408 impl_hrm_ins_or_assign_hndl_ret.i)) \
409 = impl_hrm_key; \
410 ccc_impl_hrm_insert(impl_hrm_ins_or_assign_hndl.hrm, \
411 impl_hrm_ins_or_assign_hndl.i, \
412 impl_hrm_ins_or_assign_hndl.last_cmp, \
413 impl_hrm_ins_or_assign_hndl_ret.i); \
414 impl_hrm_ins_or_assign_hndl_ret.stats = CCC_ENTRY_VACANT; \
415 } \
416 } \
417 else if (impl_hrm_ins_or_assign_hndl.stats == CCC_ENTRY_OCCUPIED) \
418 { \
419 *((typeof(lazy_value) *)ccc_impl_hrm_data_at( \
420 impl_hrm_ins_or_assign_hndl.hrm, \
421 impl_hrm_ins_or_assign_hndl.i)) \
422 = lazy_value; \
423 impl_hrm_ins_or_assign_hndl_ret = (struct ccc_handl){ \
424 .i = impl_hrm_ins_or_assign_hndl.i, \
425 .stats = impl_hrm_ins_or_assign_hndl.stats, \
426 }; \
427 *((typeof(impl_hrm_key) *)ccc_impl_hrm_key_at( \
428 impl_hrm_ins_or_assign_hndl.hrm, \
429 impl_hrm_ins_or_assign_hndl.i)) \
430 = impl_hrm_key; \
431 } \
432 } \
433 impl_hrm_ins_or_assign_hndl_ret; \
434 }))
435
436/* NOLINTEND(readability-identifier-naming) */
437
438#endif /* IMPL_HANDLE_REALTIME_ORDERED_MAP_H */
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_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
ccc_threeway_cmp
ccc_threeway_cmp
A three-way comparison for comparison functions.
Definition: types.h:153