C Container Collection (CCC)
Loading...
Searching...
No Matches
impl_handle_ordered_map.h
1#ifndef CCC_IMPL_HANDLE_ORDERED_MAP_H
2#define CCC_IMPL_HANDLE_ORDERED_MAP_H
3
5#include <stddef.h>
8#include "../buffer.h"
9#include "../types.h"
10#include "impl_types.h"
11
12/* NOLINTBEGIN(readability-identifier-naming) */
13
19struct ccc_homap_elem_
20{
21 size_t branch_[2];
22 union
23 {
24 size_t parent_;
25 size_t next_free_;
26 };
27};
28
34struct ccc_homap_
35{
36 ccc_buffer buf_;
37 size_t root_;
38 size_t free_list_;
39 size_t key_offset_;
40 size_t node_elem_offset_;
41 ccc_key_cmp_fn *cmp_;
42};
43
45struct ccc_htree_handle_
46{
47 struct ccc_homap_ *hom_;
48 ccc_threeway_cmp last_cmp_;
49 struct ccc_handl_ handle_;
50};
51
53union ccc_homap_handle_
54{
55 struct ccc_htree_handle_ impl_;
56};
57
58/*=========================== Private Interface ===========================*/
59
61void ccc_impl_hom_insert(struct ccc_homap_ *hom, size_t elem_i);
63struct ccc_htree_handle_ ccc_impl_hom_handle(struct ccc_homap_ *hom,
64 void const *key);
66void *ccc_impl_hom_key_at(struct ccc_homap_ const *hom, size_t slot);
68struct ccc_homap_elem_ *ccc_impl_homap_elem_at(struct ccc_homap_ const *hom,
69 size_t slot);
71size_t ccc_impl_hom_alloc_slot(struct ccc_homap_ *hom);
72
73/*======================== Initialization =========================*/
74
76#define ccc_impl_hom_init(mem_ptr, node_elem_field, key_elem_field, \
77 key_cmp_fn, alloc_fn, aux_data, capacity) \
78 { \
79 .buf_ = ccc_buf_init(mem_ptr, alloc_fn, aux_data, capacity), \
80 .root_ = 0, \
81 .free_list_ = 0, \
82 .key_offset_ = offsetof(typeof(*(mem_ptr)), key_elem_field), \
83 .node_elem_offset_ = offsetof(typeof(*(mem_ptr)), node_elem_field), \
84 .cmp_ = (key_cmp_fn), \
85 }
86
88#define ccc_impl_hom_as(handle_ordered_map_ptr, type_name, handle...) \
89 ((type_name *)ccc_buf_at(&(handle_ordered_map_ptr)->buf_, (handle)))
90
91/*================== Core Macro Implementations =====================*/
92
94#define ccc_impl_hom_and_modify_w(handle_ordered_map_handle_ptr, type_name, \
95 closure_over_T...) \
96 (__extension__({ \
97 __auto_type hom_mod_hndl_ptr_ = (handle_ordered_map_handle_ptr); \
98 struct ccc_htree_handle_ hom_mod_hndl_ \
99 = {.handle_ = {.stats_ = CCC_ENTRY_ARG_ERROR}}; \
100 if (hom_mod_hndl_ptr_) \
101 { \
102 hom_mod_hndl_ = hom_mod_hndl_ptr_->impl_; \
103 if (hom_mod_hndl_.handle_.stats_ & CCC_ENTRY_OCCUPIED) \
104 { \
105 type_name *const T = ccc_buf_at(&hom_mod_hndl_.hom_->buf_, \
106 hom_mod_hndl_.handle_.i_); \
107 if (T) \
108 { \
109 closure_over_T \
110 } \
111 } \
112 } \
113 hom_mod_hndl_; \
114 }))
115
117#define ccc_impl_hom_or_insert_w(handle_ordered_map_handle_ptr, \
118 lazy_key_value...) \
119 (__extension__({ \
120 __auto_type hom_or_ins_hndl_ptr_ = (handle_ordered_map_handle_ptr); \
121 ccc_handle_i hom_or_ins_ret_ = 0; \
122 if (hom_or_ins_hndl_ptr_) \
123 { \
124 struct ccc_htree_handle_ *hom_or_ins_hndl_ \
125 = &hom_or_ins_hndl_ptr_->impl_; \
126 if (hom_or_ins_hndl_->handle_.stats_ == CCC_ENTRY_OCCUPIED) \
127 { \
128 hom_or_ins_ret_ = hom_or_ins_hndl_->handle_.i_; \
129 } \
130 else \
131 { \
132 hom_or_ins_ret_ \
133 = ccc_impl_hom_alloc_slot(hom_or_ins_hndl_->hom_); \
134 if (hom_or_ins_ret_) \
135 { \
136 *((typeof(lazy_key_value) *)ccc_buf_at( \
137 &hom_or_ins_hndl_->hom_->buf_, hom_or_ins_ret_)) \
138 = lazy_key_value; \
139 ccc_impl_hom_insert(hom_or_ins_hndl_->hom_, \
140 hom_or_ins_ret_); \
141 } \
142 } \
143 } \
144 hom_or_ins_ret_; \
145 }))
146
148#define ccc_impl_hom_insert_handle_w(handle_ordered_map_handle_ptr, \
149 lazy_key_value...) \
150 (__extension__({ \
151 __auto_type hom_ins_hndl_ptr_ = (handle_ordered_map_handle_ptr); \
152 ccc_handle_i hom_ins_hndl_ret_ = 0; \
153 if (hom_ins_hndl_ptr_) \
154 { \
155 struct ccc_htree_handle_ *hom_ins_hndl_ \
156 = &hom_ins_hndl_ptr_->impl_; \
157 if (!(hom_ins_hndl_->handle_.stats_ & CCC_ENTRY_OCCUPIED)) \
158 { \
159 hom_ins_hndl_ret_ \
160 = ccc_impl_hom_alloc_slot(hom_ins_hndl_->hom_); \
161 if (hom_ins_hndl_ret_) \
162 { \
163 *((typeof(lazy_key_value) *)ccc_buf_at( \
164 &hom_ins_hndl_->hom_->buf_, hom_ins_hndl_ret_)) \
165 = lazy_key_value; \
166 ccc_impl_hom_insert(hom_ins_hndl_->hom_, \
167 hom_ins_hndl_ret_); \
168 } \
169 } \
170 else if (hom_ins_hndl_->handle_.stats_ == CCC_ENTRY_OCCUPIED) \
171 { \
172 hom_ins_hndl_ret_ = hom_ins_hndl_->handle_.i_; \
173 struct ccc_homap_elem_ ins_hndl_saved_ \
174 = *ccc_impl_homap_elem_at(hom_ins_hndl_->hom_, \
175 hom_ins_hndl_ret_); \
176 *((typeof(lazy_key_value) *)ccc_buf_at( \
177 &hom_ins_hndl_->hom_->buf_, hom_ins_hndl_ret_)) \
178 = lazy_key_value; \
179 *ccc_impl_homap_elem_at(hom_ins_hndl_->hom_, \
180 hom_ins_hndl_ret_) \
181 = ins_hndl_saved_; \
182 } \
183 } \
184 hom_ins_hndl_ret_; \
185 }))
186
188#define ccc_impl_hom_try_insert_w(handle_ordered_map_ptr, key, lazy_value...) \
189 (__extension__({ \
190 __auto_type hom_try_ins_map_ptr_ = (handle_ordered_map_ptr); \
191 struct ccc_handl_ hom_try_ins_hndl_ret_ \
192 = {.stats_ = CCC_ENTRY_ARG_ERROR}; \
193 if (hom_try_ins_map_ptr_) \
194 { \
195 __auto_type hom_key_ = (key); \
196 struct ccc_htree_handle_ hom_try_ins_hndl_ = ccc_impl_hom_handle( \
197 hom_try_ins_map_ptr_, (void *)&hom_key_); \
198 if (!(hom_try_ins_hndl_.handle_.stats_ & CCC_ENTRY_OCCUPIED)) \
199 { \
200 hom_try_ins_hndl_ret_ = (struct ccc_handl_){ \
201 .i_ = ccc_impl_hom_alloc_slot(hom_try_ins_hndl_.hom_), \
202 .stats_ = CCC_ENTRY_INSERT_ERROR}; \
203 if (hom_try_ins_hndl_ret_.i_) \
204 { \
205 *((typeof(lazy_value) *)ccc_buf_at( \
206 &hom_try_ins_map_ptr_->buf_, \
207 hom_try_ins_hndl_ret_.i_)) \
208 = lazy_value; \
209 *((typeof(hom_key_) *)ccc_impl_hom_key_at( \
210 hom_try_ins_hndl_.hom_, hom_try_ins_hndl_ret_.i_)) \
211 = hom_key_; \
212 ccc_impl_hom_insert(hom_try_ins_hndl_.hom_, \
213 hom_try_ins_hndl_ret_.i_); \
214 hom_try_ins_hndl_ret_.stats_ = CCC_ENTRY_VACANT; \
215 } \
216 } \
217 else if (hom_try_ins_hndl_.handle_.stats_ == CCC_ENTRY_OCCUPIED) \
218 { \
219 hom_try_ins_hndl_ret_ = (struct ccc_handl_){ \
220 .i_ = hom_try_ins_hndl_.handle_.i_, \
221 .stats_ = hom_try_ins_hndl_.handle_.stats_}; \
222 } \
223 } \
224 hom_try_ins_hndl_ret_; \
225 }))
226
228#define ccc_impl_hom_insert_or_assign_w(handle_ordered_map_ptr, key, \
229 lazy_value...) \
230 (__extension__({ \
231 __auto_type hom_ins_or_assign_map_ptr_ = (handle_ordered_map_ptr); \
232 struct ccc_handl_ hom_ins_or_assign_hndl_ret_ \
233 = {.stats_ = CCC_ENTRY_ARG_ERROR}; \
234 if (hom_ins_or_assign_map_ptr_) \
235 { \
236 __auto_type hom_key_ = (key); \
237 struct ccc_htree_handle_ hom_ins_or_assign_hndl_ \
238 = ccc_impl_hom_handle((handle_ordered_map_ptr), \
239 (void *)&hom_key_); \
240 if (!(hom_ins_or_assign_hndl_.handle_.stats_ \
241 & CCC_ENTRY_OCCUPIED)) \
242 { \
243 hom_ins_or_assign_hndl_ret_ \
244 = (struct ccc_handl_){.i_ = ccc_impl_hom_alloc_slot( \
245 hom_ins_or_assign_hndl_.hom_), \
246 .stats_ = CCC_ENTRY_INSERT_ERROR}; \
247 if (hom_ins_or_assign_hndl_ret_.i_) \
248 { \
249 *((typeof(lazy_value) *)ccc_buf_at( \
250 &hom_ins_or_assign_map_ptr_->buf_, \
251 hom_ins_or_assign_hndl_ret_.i_)) \
252 = lazy_value; \
253 *((typeof(hom_key_) *)ccc_impl_hom_key_at( \
254 hom_ins_or_assign_hndl_.hom_, \
255 hom_ins_or_assign_hndl_ret_.i_)) \
256 = hom_key_; \
257 ccc_impl_hom_insert(hom_ins_or_assign_hndl_.hom_, \
258 hom_ins_or_assign_hndl_ret_.i_); \
259 hom_ins_or_assign_hndl_ret_.stats_ = CCC_ENTRY_VACANT; \
260 } \
261 } \
262 else if (hom_ins_or_assign_hndl_.handle_.stats_ \
263 == CCC_ENTRY_OCCUPIED) \
264 { \
265 struct ccc_homap_elem_ ins_hndl_saved_ \
266 = *ccc_impl_homap_elem_at( \
267 hom_ins_or_assign_hndl_.hom_, \
268 hom_ins_or_assign_hndl_.handle_.i_); \
269 *((typeof(lazy_value) *)ccc_buf_at( \
270 &hom_ins_or_assign_hndl_.hom_->buf_, \
271 hom_ins_or_assign_hndl_.handle_.i_)) \
272 = lazy_value; \
273 *ccc_impl_homap_elem_at(hom_ins_or_assign_hndl_.hom_, \
274 hom_ins_or_assign_hndl_.handle_.i_) \
275 = ins_hndl_saved_; \
276 hom_ins_or_assign_hndl_ret_ = (struct ccc_handl_){ \
277 .i_ = hom_ins_or_assign_hndl_.handle_.i_, \
278 .stats_ = hom_ins_or_assign_hndl_.handle_.stats_}; \
279 *((typeof(hom_key_) *)ccc_impl_hom_key_at( \
280 hom_ins_or_assign_hndl_.hom_, \
281 hom_ins_or_assign_hndl_.handle_.i_)) \
282 = hom_key_; \
283 } \
284 } \
285 hom_ins_or_assign_hndl_ret_; \
286 }))
287
288/* NOLINTEND(readability-identifier-naming) */
289
290#endif /* CCC_IMPL_HANDLE_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