C Container Collection (CCC)
Loading...
Searching...
No Matches
impl_handle_realtime_ordered_map.h
1#ifndef IMPL_HANDLE_REALTIME_ORDERED_MAP_H
2#define IMPL_HANDLE_REALTIME_ORDERED_MAP_H
3
5#include <stddef.h>
6#include <stdint.h>
9#include "../buffer.h"
10#include "../types.h"
11#include "impl_types.h"
12
13/* NOLINTBEGIN(readability-identifier-naming) */
14
20struct ccc_hromap_elem_
21{
22 size_t branch_[2];
23 union
24 {
25 size_t parent_;
26 size_t next_free_;
27 };
28 uint8_t parity_;
29};
30
36struct ccc_hromap_
37{
38 ccc_buffer buf_;
39 size_t root_;
40 size_t free_list_;
41 size_t key_offset_;
42 size_t node_elem_offset_;
43 ccc_key_cmp_fn *cmp_;
44};
45
47struct ccc_hrtree_handle_
48{
49 struct ccc_hromap_ *hrm_;
50 ccc_threeway_cmp last_cmp_;
51 struct ccc_handl_ handle_;
52};
53
55union ccc_hromap_handle_
56{
57 struct ccc_hrtree_handle_ impl_;
58};
59
60/*======================== Private Interface ==============================*/
61
63void *ccc_impl_hrm_key_at(struct ccc_hromap_ const *hrm, size_t slot);
65struct ccc_hromap_elem_ *ccc_impl_hrm_elem_at(struct ccc_hromap_ const *hrm,
66 size_t i);
68struct ccc_hrtree_handle_ ccc_impl_hrm_handle(struct ccc_hromap_ const *hrm,
69 void const *key);
71void ccc_impl_hrm_insert(struct ccc_hromap_ *hrm, size_t parent_i,
72 ccc_threeway_cmp last_cmp, size_t elem_i);
74size_t ccc_impl_hrm_alloc_slot(struct ccc_hromap_ *hrm);
75
76/*========================= Initialization =========================*/
77
79#define ccc_impl_hrm_init(memory_ptr, node_elem_field, key_elem_field, \
80 key_cmp_fn, alloc_fn, aux_data, capacity) \
81 { \
82 .buf_ = ccc_buf_init(memory_ptr, alloc_fn, aux_data, capacity), \
83 .root_ = 0, \
84 .free_list_ = 0, \
85 .key_offset_ = offsetof(typeof(*(memory_ptr)), key_elem_field), \
86 .node_elem_offset_ = offsetof(typeof(*(memory_ptr)), node_elem_field), \
87 .cmp_ = (key_cmp_fn), \
88 }
89
91#define ccc_impl_hrm_as(handle_realtime_ordered_map_ptr, type_name, handle...) \
92 ((type_name *)ccc_buf_at(&(handle_realtime_ordered_map_ptr)->buf_, \
93 (handle)))
94
95/*================== Core Macro Implementations =====================*/
96
98#define ccc_impl_hrm_and_modify_w(handle_realtime_ordered_map_handle_ptr, \
99 type_name, closure_over_T...) \
100 (__extension__({ \
101 __auto_type hrm_hndl_ptr_ = (handle_realtime_ordered_map_handle_ptr); \
102 struct ccc_hrtree_handle_ hrm_mod_hndl_ \
103 = {.handle_ = {.stats_ = CCC_ENTRY_ARG_ERROR}}; \
104 if (hrm_hndl_ptr_) \
105 { \
106 hrm_mod_hndl_ = hrm_hndl_ptr_->impl_; \
107 if (hrm_mod_hndl_.handle_.stats_ & CCC_ENTRY_OCCUPIED) \
108 { \
109 type_name *const T = ccc_buf_at(&hrm_mod_hndl_.hrm_->buf_, \
110 hrm_mod_hndl_.handle_.i_); \
111 if (T) \
112 { \
113 closure_over_T \
114 } \
115 } \
116 } \
117 hrm_mod_hndl_; \
118 }))
119
121#define ccc_impl_hrm_or_insert_w(handle_realtime_ordered_map_handle_ptr, \
122 lazy_key_value...) \
123 (__extension__({ \
124 __auto_type or_ins_handle_ptr_ \
125 = (handle_realtime_ordered_map_handle_ptr); \
126 ccc_handle_i hrm_or_ins_ret_ = 0; \
127 if (or_ins_handle_ptr_) \
128 { \
129 struct ccc_hrtree_handle_ *hrm_or_ins_hndl_ \
130 = &or_ins_handle_ptr_->impl_; \
131 if (hrm_or_ins_hndl_->handle_.stats_ == CCC_ENTRY_OCCUPIED) \
132 { \
133 hrm_or_ins_ret_ = hrm_or_ins_hndl_->handle_.i_; \
134 } \
135 else \
136 { \
137 hrm_or_ins_ret_ \
138 = ccc_impl_hrm_alloc_slot(hrm_or_ins_hndl_->hrm_); \
139 if (hrm_or_ins_ret_) \
140 { \
141 *((typeof(lazy_key_value) *)ccc_buf_at( \
142 &hrm_or_ins_hndl_->hrm_->buf_, hrm_or_ins_ret_)) \
143 = lazy_key_value; \
144 ccc_impl_hrm_insert( \
145 hrm_or_ins_hndl_->hrm_, hrm_or_ins_hndl_->handle_.i_, \
146 hrm_or_ins_hndl_->last_cmp_, hrm_or_ins_ret_); \
147 } \
148 } \
149 } \
150 hrm_or_ins_ret_; \
151 }))
152
154#define ccc_impl_hrm_insert_handle_w(handle_realtime_ordered_map_handle_ptr, \
155 lazy_key_value...) \
156 (__extension__({ \
157 __auto_type ins_handle_ptr_ \
158 = (handle_realtime_ordered_map_handle_ptr); \
159 ccc_handle_i hrm_ins_hndl_ret_ = 0; \
160 if (ins_handle_ptr_) \
161 { \
162 struct ccc_hrtree_handle_ *hrm_ins_hndl_ \
163 = &ins_handle_ptr_->impl_; \
164 if (!(hrm_ins_hndl_->handle_.stats_ & CCC_ENTRY_OCCUPIED)) \
165 { \
166 hrm_ins_hndl_ret_ \
167 = ccc_impl_hrm_alloc_slot(hrm_ins_hndl_->hrm_); \
168 if (hrm_ins_hndl_ret_) \
169 { \
170 *((typeof(lazy_key_value) *)ccc_buf_at( \
171 &hrm_ins_hndl_->hrm_->buf_, hrm_ins_hndl_ret_)) \
172 = lazy_key_value; \
173 ccc_impl_hrm_insert( \
174 hrm_ins_hndl_->hrm_, hrm_ins_hndl_->handle_.i_, \
175 hrm_ins_hndl_->last_cmp_, hrm_ins_hndl_ret_); \
176 } \
177 } \
178 else if (hrm_ins_hndl_->handle_.stats_ == CCC_ENTRY_OCCUPIED) \
179 { \
180 hrm_ins_hndl_ret_ = hrm_ins_hndl_->handle_.i_; \
181 struct ccc_hromap_elem_ ins_hndl_saved_ \
182 = *ccc_impl_hrm_elem_at(hrm_ins_hndl_->hrm_, \
183 hrm_ins_hndl_ret_); \
184 *((typeof(lazy_key_value) *)ccc_buf_at( \
185 &hrm_ins_hndl_->hrm_->buf_, hrm_ins_hndl_ret_)) \
186 = lazy_key_value; \
187 *ccc_impl_hrm_elem_at(hrm_ins_hndl_->hrm_, hrm_ins_hndl_ret_) \
188 = ins_hndl_saved_; \
189 } \
190 } \
191 hrm_ins_hndl_ret_; \
192 }))
193
195#define ccc_impl_hrm_try_insert_w(handle_realtime_ordered_map_ptr, key, \
196 lazy_value...) \
197 (__extension__({ \
198 __auto_type try_ins_map_ptr_ = (handle_realtime_ordered_map_ptr); \
199 struct ccc_handl_ hrm_try_ins_hndl_ret_ \
200 = {.stats_ = CCC_ENTRY_ARG_ERROR}; \
201 if (try_ins_map_ptr_) \
202 { \
203 __auto_type hrm_key_ = (key); \
204 struct ccc_hrtree_handle_ hrm_try_ins_hndl_ \
205 = ccc_impl_hrm_handle(try_ins_map_ptr_, (void *)&hrm_key_); \
206 if (!(hrm_try_ins_hndl_.handle_.stats_ & CCC_ENTRY_OCCUPIED)) \
207 { \
208 hrm_try_ins_hndl_ret_ = (struct ccc_handl_){ \
209 .i_ = ccc_impl_hrm_alloc_slot(hrm_try_ins_hndl_.hrm_), \
210 .stats_ = CCC_ENTRY_INSERT_ERROR}; \
211 if (hrm_try_ins_hndl_ret_.i_) \
212 { \
213 *((typeof(lazy_value) *)ccc_buf_at( \
214 &try_ins_map_ptr_->buf_, hrm_try_ins_hndl_ret_.i_)) \
215 = lazy_value; \
216 *((typeof(hrm_key_) *)ccc_impl_hrm_key_at( \
217 try_ins_map_ptr_, hrm_try_ins_hndl_ret_.i_)) \
218 = hrm_key_; \
219 ccc_impl_hrm_insert(hrm_try_ins_hndl_.hrm_, \
220 hrm_try_ins_hndl_.handle_.i_, \
221 hrm_try_ins_hndl_.last_cmp_, \
222 hrm_try_ins_hndl_ret_.i_); \
223 hrm_try_ins_hndl_ret_.stats_ = CCC_ENTRY_VACANT; \
224 } \
225 } \
226 else if (hrm_try_ins_hndl_.handle_.stats_ == CCC_ENTRY_OCCUPIED) \
227 { \
228 hrm_try_ins_hndl_ret_ = (struct ccc_handl_){ \
229 .i_ = hrm_try_ins_hndl_.handle_.i_, \
230 .stats_ = hrm_try_ins_hndl_.handle_.stats_}; \
231 } \
232 } \
233 hrm_try_ins_hndl_ret_; \
234 }))
235
237#define ccc_impl_hrm_insert_or_assign_w(handle_realtime_ordered_map_ptr, key, \
238 lazy_value...) \
239 (__extension__({ \
240 __auto_type ins_or_assign_map_ptr_ \
241 = (handle_realtime_ordered_map_ptr); \
242 struct ccc_handl_ hrm_ins_or_assign_hndl_ret_ \
243 = {.stats_ = CCC_ENTRY_ARG_ERROR}; \
244 if (ins_or_assign_map_ptr_) \
245 { \
246 __auto_type hrm_key_ = (key); \
247 struct ccc_hrtree_handle_ hrm_ins_or_assign_hndl_ \
248 = ccc_impl_hrm_handle(ins_or_assign_map_ptr_, \
249 (void *)&hrm_key_); \
250 if (!(hrm_ins_or_assign_hndl_.handle_.stats_ \
251 & CCC_ENTRY_OCCUPIED)) \
252 { \
253 hrm_ins_or_assign_hndl_ret_ \
254 = (struct ccc_handl_){.i_ = ccc_impl_hrm_alloc_slot( \
255 hrm_ins_or_assign_hndl_.hrm_), \
256 .stats_ = CCC_ENTRY_INSERT_ERROR}; \
257 if (hrm_ins_or_assign_hndl_ret_.i_) \
258 { \
259 *((typeof(lazy_value) *)ccc_buf_at( \
260 &hrm_ins_or_assign_hndl_.hrm_->buf_, \
261 hrm_ins_or_assign_hndl_ret_.i_)) \
262 = lazy_value; \
263 *((typeof(hrm_key_) *)ccc_impl_hrm_key_at( \
264 hrm_ins_or_assign_hndl_.hrm_, \
265 hrm_ins_or_assign_hndl_ret_.i_)) \
266 = hrm_key_; \
267 ccc_impl_hrm_insert(hrm_ins_or_assign_hndl_.hrm_, \
268 hrm_ins_or_assign_hndl_.handle_.i_, \
269 hrm_ins_or_assign_hndl_.last_cmp_, \
270 hrm_ins_or_assign_hndl_ret_.i_); \
271 hrm_ins_or_assign_hndl_ret_.stats_ = CCC_ENTRY_VACANT; \
272 } \
273 } \
274 else if (hrm_ins_or_assign_hndl_.handle_.stats_ \
275 == CCC_ENTRY_OCCUPIED) \
276 { \
277 struct ccc_hromap_elem_ ins_hndl_saved_ \
278 = *ccc_impl_hrm_elem_at( \
279 hrm_ins_or_assign_hndl_.hrm_, \
280 hrm_ins_or_assign_hndl_.handle_.i_); \
281 *((typeof(lazy_value) *)ccc_buf_at( \
282 &hrm_ins_or_assign_hndl_.hrm_->buf_, \
283 hrm_ins_or_assign_hndl_.handle_.i_)) \
284 = lazy_value; \
285 *ccc_impl_hrm_elem_at(hrm_ins_or_assign_hndl_.hrm_, \
286 hrm_ins_or_assign_hndl_.handle_.i_) \
287 = ins_hndl_saved_; \
288 hrm_ins_or_assign_hndl_ret_ = (struct ccc_handl_){ \
289 .i_ = hrm_ins_or_assign_hndl_.handle_.i_, \
290 .stats_ = hrm_ins_or_assign_hndl_.handle_.stats_}; \
291 *((typeof(hrm_key_) *)ccc_impl_hrm_key_at( \
292 hrm_ins_or_assign_hndl_.hrm_, \
293 hrm_ins_or_assign_hndl_.handle_.i_)) \
294 = hrm_key_; \
295 } \
296 } \
297 hrm_ins_or_assign_hndl_ret_; \
298 }))
299
300/* NOLINTEND(readability-identifier-naming) */
301
302#endif /* IMPL_HANDLE_REALTIME_ORDERED_MAP_H */
ccc_buffer
struct ccc_buf_ ccc_buffer
A contiguous block of storage for elements of the same type.
Definition: buffer.h:50
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_threeway_cmp
ccc_threeway_cmp
A three-way comparison for comparison functions.
Definition: types.h:138