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 "../types.h"
24#include "impl_types.h" /* NOLINT */
25
26/* NOLINTBEGIN(readability-identifier-naming) */
27
33struct ccc_homap_elem
34{
36 size_t branch[2];
37 union
38 {
40 size_t parent;
42 size_t next_free;
43 };
44};
45
69struct ccc_homap
70{
72 void *data;
74 struct ccc_homap_elem *nodes;
76 size_t capacity;
78 size_t count;
80 size_t root;
82 size_t free_list;
84 size_t sizeof_type;
86 size_t key_offset;
88 ccc_any_key_cmp_fn *cmp;
90 ccc_any_alloc_fn *alloc;
92 void *aux;
93};
94
97struct ccc_htree_handle
98{
100 struct ccc_homap *hom;
102 size_t i;
104 ccc_threeway_cmp last_cmp;
106 ccc_entry_status stats;
107};
108
112union ccc_homap_handle
113{
115 struct ccc_htree_handle impl;
116};
117
118/*=========================== Private Interface ===========================*/
119
121void ccc_impl_hom_insert(struct ccc_homap *hom, size_t elem_i);
123struct ccc_htree_handle ccc_impl_hom_handle(struct ccc_homap *hom,
124 void const *key);
126void *ccc_impl_hom_data_at(struct ccc_homap const *hom, size_t slot);
128void *ccc_impl_hom_key_at(struct ccc_homap const *hom, size_t slot);
130size_t ccc_impl_hom_alloc_slot(struct ccc_homap *hom);
131
132/*======================== Initialization =========================*/
133
136#define ccc_impl_hom_declare_fixed_map(impl_fixed_map_type_name, \
137 impl_key_val_type_name, impl_capacity) \
138 static_assert((impl_capacity) > 1, \
139 "fixed size map must have capacity greater than 1"); \
140 typedef struct \
141 { \
142 impl_key_val_type_name data[(impl_capacity)]; \
143 struct ccc_homap_elem nodes[(impl_capacity)]; \
144 }(impl_fixed_map_type_name)
145
148#define ccc_impl_hom_fixed_capacity(fixed_map_type_name) \
149 (sizeof((fixed_map_type_name){}.nodes) / sizeof(struct ccc_homap_elem))
150
152#define ccc_impl_hom_init(impl_memory_ptr, impl_type_name, \
153 impl_key_elem_field, impl_key_cmp_fn, impl_alloc_fn, \
154 impl_aux_data, impl_capacity) \
155 { \
156 .data = (impl_memory_ptr), \
157 .nodes = NULL, \
158 .capacity = (impl_capacity), \
159 .count = 0, \
160 .root = 0, \
161 .free_list = 0, \
162 .sizeof_type = sizeof(impl_type_name), \
163 .key_offset = offsetof(impl_type_name, impl_key_elem_field), \
164 .cmp = (impl_key_cmp_fn), \
165 .alloc = (impl_alloc_fn), \
166 .aux = (impl_aux_data), \
167 }
168
170#define ccc_impl_hom_as(handle_ordered_map_ptr, type_name, handle...) \
171 ((type_name *)ccc_impl_hom_data_at((handle_ordered_map_ptr), (handle)))
172
173/*================== Core Macro Implementations =====================*/
174
176#define ccc_impl_hom_and_modify_w(handle_ordered_map_handle_ptr, type_name, \
177 closure_over_T...) \
178 (__extension__({ \
179 __auto_type impl_hom_mod_hndl_ptr = (handle_ordered_map_handle_ptr); \
180 struct ccc_htree_handle impl_hom_mod_hndl \
181 = {.stats = CCC_ENTRY_ARG_ERROR}; \
182 if (impl_hom_mod_hndl_ptr) \
183 { \
184 impl_hom_mod_hndl = impl_hom_mod_hndl_ptr->impl; \
185 if (impl_hom_mod_hndl.stats & CCC_ENTRY_OCCUPIED) \
186 { \
187 type_name *const T = ccc_impl_hom_data_at( \
188 impl_hom_mod_hndl.hom, impl_hom_mod_hndl.i); \
189 if (T) \
190 { \
191 closure_over_T \
192 } \
193 } \
194 } \
195 impl_hom_mod_hndl; \
196 }))
197
199#define ccc_impl_hom_or_insert_w(handle_ordered_map_handle_ptr, \
200 lazy_key_value...) \
201 (__extension__({ \
202 __auto_type impl_hom_or_ins_hndl_ptr \
203 = (handle_ordered_map_handle_ptr); \
204 ccc_handle_i impl_hom_or_ins_ret = 0; \
205 if (impl_hom_or_ins_hndl_ptr) \
206 { \
207 if (impl_hom_or_ins_hndl_ptr->impl.stats == CCC_ENTRY_OCCUPIED) \
208 { \
209 impl_hom_or_ins_ret = impl_hom_or_ins_hndl_ptr->impl.i; \
210 } \
211 else \
212 { \
213 impl_hom_or_ins_ret = ccc_impl_hom_alloc_slot( \
214 impl_hom_or_ins_hndl_ptr->impl.hom); \
215 if (impl_hom_or_ins_ret) \
216 { \
217 *((typeof(lazy_key_value) *)ccc_impl_hom_data_at( \
218 impl_hom_or_ins_hndl_ptr->impl.hom, \
219 impl_hom_or_ins_ret)) \
220 = lazy_key_value; \
221 ccc_impl_hom_insert(impl_hom_or_ins_hndl_ptr->impl.hom, \
222 impl_hom_or_ins_ret); \
223 } \
224 } \
225 } \
226 impl_hom_or_ins_ret; \
227 }))
228
230#define ccc_impl_hom_insert_handle_w(handle_ordered_map_handle_ptr, \
231 lazy_key_value...) \
232 (__extension__({ \
233 __auto_type impl_hom_ins_hndl_ptr = (handle_ordered_map_handle_ptr); \
234 ccc_handle_i impl_hom_ins_hndl_ret = 0; \
235 if (impl_hom_ins_hndl_ptr) \
236 { \
237 if (!(impl_hom_ins_hndl_ptr->impl.stats & CCC_ENTRY_OCCUPIED)) \
238 { \
239 impl_hom_ins_hndl_ret = ccc_impl_hom_alloc_slot( \
240 impl_hom_ins_hndl_ptr->impl.hom); \
241 if (impl_hom_ins_hndl_ret) \
242 { \
243 *((typeof(lazy_key_value) *)ccc_impl_hom_data_at( \
244 impl_hom_ins_hndl_ptr->impl.hom, \
245 impl_hom_ins_hndl_ret)) \
246 = lazy_key_value; \
247 ccc_impl_hom_insert(impl_hom_ins_hndl_ptr->impl.hom, \
248 impl_hom_ins_hndl_ret); \
249 } \
250 } \
251 else if (impl_hom_ins_hndl_ptr->impl.stats == CCC_ENTRY_OCCUPIED) \
252 { \
253 *((typeof(lazy_key_value) *)ccc_impl_hom_data_at( \
254 impl_hom_ins_hndl_ptr->impl.hom, \
255 impl_hom_ins_hndl_ptr->impl.i)) \
256 = lazy_key_value; \
257 impl_hom_ins_hndl_ret = impl_hom_ins_hndl_ptr->impl.i; \
258 } \
259 } \
260 impl_hom_ins_hndl_ret; \
261 }))
262
264#define ccc_impl_hom_try_insert_w(handle_ordered_map_ptr, key, lazy_value...) \
265 (__extension__({ \
266 __auto_type impl_hom_try_ins_map_ptr = (handle_ordered_map_ptr); \
267 struct ccc_handl impl_hom_try_ins_hndl_ret \
268 = {.stats = CCC_ENTRY_ARG_ERROR}; \
269 if (impl_hom_try_ins_map_ptr) \
270 { \
271 __auto_type impl_hom_key = (key); \
272 struct ccc_htree_handle impl_hom_try_ins_hndl \
273 = ccc_impl_hom_handle(impl_hom_try_ins_map_ptr, \
274 (void *)&impl_hom_key); \
275 if (!(impl_hom_try_ins_hndl.stats & CCC_ENTRY_OCCUPIED)) \
276 { \
277 impl_hom_try_ins_hndl_ret = (struct ccc_handl){ \
278 .i = ccc_impl_hom_alloc_slot(impl_hom_try_ins_hndl.hom), \
279 .stats = CCC_ENTRY_INSERT_ERROR, \
280 }; \
281 if (impl_hom_try_ins_hndl_ret.i) \
282 { \
283 *((typeof(lazy_value) *)ccc_impl_hom_data_at( \
284 impl_hom_try_ins_map_ptr, \
285 impl_hom_try_ins_hndl_ret.i)) \
286 = lazy_value; \
287 *((typeof(impl_hom_key) *)ccc_impl_hom_key_at( \
288 impl_hom_try_ins_hndl.hom, \
289 impl_hom_try_ins_hndl_ret.i)) \
290 = impl_hom_key; \
291 ccc_impl_hom_insert(impl_hom_try_ins_hndl.hom, \
292 impl_hom_try_ins_hndl_ret.i); \
293 impl_hom_try_ins_hndl_ret.stats = CCC_ENTRY_VACANT; \
294 } \
295 } \
296 else if (impl_hom_try_ins_hndl.stats == CCC_ENTRY_OCCUPIED) \
297 { \
298 impl_hom_try_ins_hndl_ret = (struct ccc_handl){ \
299 .i = impl_hom_try_ins_hndl.i, \
300 .stats = impl_hom_try_ins_hndl.stats}; \
301 } \
302 } \
303 impl_hom_try_ins_hndl_ret; \
304 }))
305
307#define ccc_impl_hom_insert_or_assign_w(handle_ordered_map_ptr, key, \
308 lazy_value...) \
309 (__extension__({ \
310 __auto_type impl_hom_ins_or_assign_map_ptr = (handle_ordered_map_ptr); \
311 struct ccc_handl impl_hom_ins_or_assign_hndl_ret \
312 = {.stats = CCC_ENTRY_ARG_ERROR}; \
313 if (impl_hom_ins_or_assign_map_ptr) \
314 { \
315 __auto_type impl_hom_key = (key); \
316 struct ccc_htree_handle impl_hom_ins_or_assign_hndl \
317 = ccc_impl_hom_handle(impl_hom_ins_or_assign_map_ptr, \
318 (void *)&impl_hom_key); \
319 if (!(impl_hom_ins_or_assign_hndl.stats & CCC_ENTRY_OCCUPIED)) \
320 { \
321 impl_hom_ins_or_assign_hndl_ret = (struct ccc_handl){ \
322 .i = ccc_impl_hom_alloc_slot( \
323 impl_hom_ins_or_assign_hndl.hom), \
324 .stats = CCC_ENTRY_INSERT_ERROR, \
325 }; \
326 if (impl_hom_ins_or_assign_hndl_ret.i) \
327 { \
328 *((typeof(lazy_value) *)ccc_impl_hom_data_at( \
329 impl_hom_ins_or_assign_map_ptr, \
330 impl_hom_ins_or_assign_hndl_ret.i)) \
331 = lazy_value; \
332 *((typeof(impl_hom_key) *)ccc_impl_hom_key_at( \
333 impl_hom_ins_or_assign_hndl.hom, \
334 impl_hom_ins_or_assign_hndl_ret.i)) \
335 = impl_hom_key; \
336 ccc_impl_hom_insert(impl_hom_ins_or_assign_hndl.hom, \
337 impl_hom_ins_or_assign_hndl_ret.i); \
338 impl_hom_ins_or_assign_hndl_ret.stats = CCC_ENTRY_VACANT; \
339 } \
340 } \
341 else if (impl_hom_ins_or_assign_hndl.stats == CCC_ENTRY_OCCUPIED) \
342 { \
343 *((typeof(lazy_value) *)ccc_impl_hom_data_at( \
344 impl_hom_ins_or_assign_hndl.hom, \
345 impl_hom_ins_or_assign_hndl.i)) \
346 = lazy_value; \
347 impl_hom_ins_or_assign_hndl_ret = (struct ccc_handl){ \
348 .i = impl_hom_ins_or_assign_hndl.i, \
349 .stats = impl_hom_ins_or_assign_hndl.stats, \
350 }; \
351 *((typeof(impl_hom_key) *)ccc_impl_hom_key_at( \
352 impl_hom_ins_or_assign_hndl.hom, \
353 impl_hom_ins_or_assign_hndl.i)) \
354 = impl_hom_key; \
355 } \
356 } \
357 impl_hom_ins_or_assign_hndl_ret; \
358 }))
359
360/* NOLINTEND(readability-identifier-naming) */
361
362#endif /* CCC_IMPL_HANDLE_ORDERED_MAP_H */
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:73
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