C Container Collection (CCC)
Loading...
Searching...
No Matches
impl_handle_hash_map.h
1#ifndef CCC_IMPL_HANDLE_HASH_MAP_H
2#define CCC_IMPL_HANDLE_HASH_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
16enum : uint64_t
17{
18 CCC_HHM_EMPTY = 0,
19};
20
31struct ccc_hhmap_elem_
32{
34 uint64_t hash_;
36 size_t slot_i_;
37};
38
40struct ccc_hhmap_
41{
42 ccc_buffer buf_;
43 ccc_hash_fn *hash_fn_;
44 ccc_key_eq_fn *eq_fn_;
45 size_t key_offset_;
46 size_t hash_elem_offset_;
47};
48
50struct ccc_hhash_handle_
51{
52 struct ccc_hhmap_ *h_;
53 uint64_t hash_;
54 struct ccc_handl_ handle_;
55};
56
58union ccc_hhmap_handle_
59{
60 struct ccc_hhash_handle_ impl_;
61};
62
63/*====================== Private Interface =========================*/
64
66ccc_handle_i ccc_impl_hhm_insert_meta(struct ccc_hhmap_ *h, uint64_t hash,
67 size_t cur_i);
69struct ccc_hhash_handle_ ccc_impl_hhm_handle(struct ccc_hhmap_ *h,
70 void const *key);
72void *ccc_impl_hhm_key_at(struct ccc_hhmap_ const *h, size_t i);
74uint64_t *ccc_impl_hhm_hash_at(struct ccc_hhmap_ const *h, size_t i);
76struct ccc_hhmap_elem_ *ccc_impl_hhm_elem_at(struct ccc_hhmap_ const *h,
77 size_t i);
78
79/*====================== Macro Implementations =======================*/
80
82#define ccc_impl_hhm_init(memory_ptr, hhash_elem_field, key_field, hash_fn, \
83 key_eq_fn, alloc_fn, aux, capacity) \
84 { \
85 .buf_ \
86 = (ccc_buffer)ccc_buf_init((memory_ptr), (alloc_fn), (aux), capacity), \
87 .hash_fn_ = (hash_fn), \
88 .eq_fn_ = (key_eq_fn), \
89 .key_offset_ = offsetof(typeof(*(memory_ptr)), key_field), \
90 .hash_elem_offset_ \
91 = offsetof(typeof(*(memory_ptr)), hhash_elem_field), \
92 }
93
95#define ccc_impl_hhm_as(handle_hash_map_ptr, type_name, handle...) \
96 ((type_name *)ccc_buf_at(&(handle_hash_map_ptr)->buf_, (handle)))
97
100#define ccc_impl_hhm_swaps(swap_handle, lazy_key_value...) \
101 (__extension__({ \
102 size_t hhm_i_ = (swap_handle)->handle_.i_; \
103 struct ccc_hhmap_elem_ *hhm_elem_ \
104 = ccc_impl_hhm_elem_at((swap_handle)->h_, hhm_i_); \
105 if (hhm_elem_->hash_ == CCC_HHM_EMPTY) \
106 { \
107 struct ccc_hhmap_elem_ const save_slot_ = *ccc_impl_hhm_elem_at( \
108 (swap_handle)->h_, hhm_elem_->slot_i_); \
109 struct ccc_hhmap_elem_ const save_elem_ = *hhm_elem_; \
110 *((typeof(lazy_key_value) *)ccc_buf_at(&((swap_handle)->h_->buf_), \
111 save_elem_.slot_i_)) \
112 = lazy_key_value; \
113 *ccc_impl_hhm_elem_at((swap_handle)->h_, save_elem_.slot_i_) \
114 = save_slot_; \
115 *ccc_impl_hhm_hash_at((swap_handle)->h_, hhm_i_) \
116 = (swap_handle)->hash_; \
117 (void)ccc_buf_size_plus(&(swap_handle)->h_->buf_, 1); \
118 } \
119 else \
120 { \
121 hhm_i_ = ccc_impl_hhm_insert_meta((swap_handle)->h_, \
122 (swap_handle)->hash_, hhm_i_); \
123 struct ccc_hhmap_elem_ const save_slot_ = *ccc_impl_hhm_elem_at( \
124 (swap_handle)->h_, \
125 ccc_impl_hhm_elem_at((swap_handle)->h_, hhm_i_)->slot_i_); \
126 struct ccc_hhmap_elem_ const save_elem_ \
127 = *ccc_impl_hhm_elem_at((swap_handle)->h_, hhm_i_); \
128 *((typeof(lazy_key_value) *)ccc_buf_at(&((swap_handle)->h_->buf_), \
129 save_elem_.slot_i_)) \
130 = lazy_key_value; \
131 *ccc_impl_hhm_elem_at((swap_handle)->h_, save_elem_.slot_i_) \
132 = save_slot_; \
133 } \
134 hhm_i_; \
135 }))
136
137/*===================== Core Macro Implementations ==================*/
138
140#define ccc_impl_hhm_and_modify_w(handle_hash_map_handle_ptr, type_name, \
141 closure_over_T...) \
142 (__extension__({ \
143 __auto_type hhm_mod_handl_ptr_ = (handle_hash_map_handle_ptr); \
144 struct ccc_hhash_handle_ hhm_mod_with_handl_ \
145 = {.handle_ = {.stats_ = CCC_ENTRY_ARG_ERROR}}; \
146 if (hhm_mod_handl_ptr_) \
147 { \
148 hhm_mod_with_handl_ = hhm_mod_handl_ptr_->impl_; \
149 if (hhm_mod_with_handl_.handle_.stats_ == CCC_ENTRY_OCCUPIED) \
150 { \
151 type_name *const T = ccc_buf_at( \
152 &hhm_mod_with_handl_.h_->buf_, \
153 ccc_impl_hhm_elem_at(hhm_mod_with_handl_.h_, \
154 hhm_mod_with_handl_.handle_.i_) \
155 ->slot_i_); \
156 if (T) \
157 { \
158 closure_over_T \
159 } \
160 } \
161 } \
162 hhm_mod_with_handl_; \
163 }))
164
166#define ccc_impl_hhm_or_insert_w(handle_hash_map_handle_ptr, \
167 lazy_key_value...) \
168 (__extension__({ \
169 __auto_type hhm_or_ins_handl_ptr_ = (handle_hash_map_handle_ptr); \
170 ccc_handle_i hhm_or_ins_res_ = 0; \
171 if (hhm_or_ins_handl_ptr_) \
172 { \
173 struct ccc_hhash_handle_ *hhm_or_ins_handle_ \
174 = &hhm_or_ins_handl_ptr_->impl_; \
175 if (!(hhm_or_ins_handle_->handle_.stats_ \
176 & CCC_ENTRY_INSERT_ERROR)) \
177 { \
178 if (hhm_or_ins_handle_->handle_.stats_ & CCC_ENTRY_OCCUPIED) \
179 { \
180 hhm_or_ins_res_ = hhm_or_ins_handle_->handle_.i_; \
181 } \
182 else \
183 { \
184 hhm_or_ins_res_ = ccc_impl_hhm_swaps(hhm_or_ins_handle_, \
185 lazy_key_value); \
186 } \
187 hhm_or_ins_res_ \
188 = ccc_impl_hhm_elem_at(hhm_or_ins_handl_ptr_->impl_.h_, \
189 hhm_or_ins_res_) \
190 ->slot_i_; \
191 } \
192 } \
193 hhm_or_ins_res_; \
194 }))
195
197#define ccc_impl_hhm_insert_handle_w(handle_hash_map_handle_ptr, \
198 lazy_key_value...) \
199 (__extension__({ \
200 __auto_type hhm_ins_handl_ptr_ = (handle_hash_map_handle_ptr); \
201 ccc_handle_i hhm_res_ = 0; \
202 if (hhm_ins_handl_ptr_) \
203 { \
204 struct ccc_hhash_handle_ *hhm_ins_handl_ \
205 = &hhm_ins_handl_ptr_->impl_; \
206 if (!(hhm_ins_handl_->handle_.stats_ & CCC_ENTRY_INSERT_ERROR)) \
207 { \
208 if (hhm_ins_handl_->handle_.stats_ & CCC_ENTRY_OCCUPIED) \
209 { \
210 hhm_ins_handl_->handle_.stats_ = CCC_ENTRY_OCCUPIED; \
211 struct ccc_hhmap_elem_ save_slot_ = *ccc_impl_hhm_elem_at( \
212 hhm_ins_handl_->h_, \
213 ccc_impl_hhm_elem_at(hhm_ins_handl_->h_, \
214 hhm_ins_handl_->handle_.i_) \
215 ->slot_i_); \
216 struct ccc_hhmap_elem_ save_elem_ = *ccc_impl_hhm_elem_at( \
217 hhm_ins_handl_->h_, hhm_ins_handl_->handle_.i_); \
218 *((typeof(lazy_key_value) *)ccc_buf_at( \
219 &hhm_ins_handl_->h_->buf_, save_elem_.slot_i_)) \
220 = lazy_key_value; \
221 *ccc_impl_hhm_elem_at(hhm_ins_handl_->h_, \
222 save_elem_.slot_i_) \
223 = save_slot_; \
224 hhm_res_ = hhm_ins_handl_->handle_.i_; \
225 } \
226 else \
227 { \
228 hhm_res_ \
229 = ccc_impl_hhm_swaps(hhm_ins_handl_, lazy_key_value); \
230 } \
231 hhm_res_ = ccc_impl_hhm_elem_at(hhm_ins_handl_ptr_->impl_.h_, \
232 hhm_res_) \
233 ->slot_i_; \
234 } \
235 } \
236 hhm_res_; \
237 }))
238
240#define ccc_impl_hhm_try_insert_w(handle_hash_map_ptr, key, lazy_value...) \
241 (__extension__({ \
242 struct ccc_hhmap_ *handle_hash_map_ptr_ = (handle_hash_map_ptr); \
243 struct ccc_handl_ hhm_try_insert_res_ \
244 = {.stats_ = CCC_ENTRY_ARG_ERROR}; \
245 if (handle_hash_map_ptr_) \
246 { \
247 __auto_type hhm_key_ = key; \
248 struct ccc_hhash_handle_ hhm_try_ins_handl_ = ccc_impl_hhm_handle( \
249 handle_hash_map_ptr_, (void *)&hhm_key_); \
250 if ((hhm_try_ins_handl_.handle_.stats_ & CCC_ENTRY_OCCUPIED) \
251 || (hhm_try_ins_handl_.handle_.stats_ \
252 & CCC_ENTRY_INSERT_ERROR)) \
253 { \
254 hhm_try_insert_res_ = hhm_try_ins_handl_.handle_; \
255 } \
256 else \
257 { \
258 hhm_try_insert_res_ = (struct ccc_handl_){ \
259 .i_ \
260 = ccc_impl_hhm_swaps((&hhm_try_ins_handl_), lazy_value), \
261 .stats_ = CCC_ENTRY_VACANT, \
262 }; \
263 *((typeof(hhm_key_) *)ccc_impl_hhm_key_at( \
264 handle_hash_map_ptr_, \
265 ccc_impl_hhm_elem_at(handle_hash_map_ptr_, \
266 hhm_try_insert_res_.i_) \
267 ->slot_i_)) \
268 = hhm_key_; \
269 } \
270 hhm_try_insert_res_.i_ \
271 = ccc_impl_hhm_elem_at(handle_hash_map_ptr_, \
272 hhm_try_insert_res_.i_) \
273 ->slot_i_; \
274 } \
275 hhm_try_insert_res_; \
276 }))
277
279#define ccc_impl_hhm_insert_or_assign_w(handle_hash_map_ptr, key, \
280 lazy_value...) \
281 (__extension__({ \
282 struct ccc_hhmap_ *handle_hash_map_ptr_ = (handle_hash_map_ptr); \
283 struct ccc_handl_ hhm_ins_or_assign_res_ \
284 = {.stats_ = CCC_ENTRY_ARG_ERROR}; \
285 if (handle_hash_map_ptr_) \
286 { \
287 __auto_type hhm_key_ = key; \
288 struct ccc_hhash_handle_ hhm_ins_or_assign_handl_ \
289 = ccc_impl_hhm_handle(handle_hash_map_ptr_, \
290 (void *)&hhm_key_); \
291 if (hhm_ins_or_assign_handl_.handle_.stats_ & CCC_ENTRY_OCCUPIED) \
292 { \
293 hhm_ins_or_assign_res_ = hhm_ins_or_assign_handl_.handle_; \
294 struct ccc_hhmap_elem_ const save_elem_ \
295 = *ccc_impl_hhm_elem_at( \
296 handle_hash_map_ptr_, \
297 hhm_ins_or_assign_handl_.handle_.i_); \
298 struct ccc_hhmap_elem_ const save_slot_ \
299 = *ccc_impl_hhm_elem_at(handle_hash_map_ptr_, \
300 save_elem_.slot_i_); \
301 *((typeof(lazy_value) *)ccc_buf_at( \
302 &handle_hash_map_ptr_->buf_, save_elem_.slot_i_)) \
303 = lazy_value; \
304 *ccc_impl_hhm_elem_at(handle_hash_map_ptr_, \
305 save_elem_.slot_i_) \
306 = save_slot_; \
307 *((typeof(hhm_key_) *)ccc_impl_hhm_key_at( \
308 handle_hash_map_ptr_, save_elem_.slot_i_)) \
309 = hhm_key_; \
310 } \
311 else if (hhm_ins_or_assign_handl_.handle_.stats_ \
312 & CCC_ENTRY_INSERT_ERROR) \
313 { \
314 hhm_ins_or_assign_res_.i_ = 0; \
315 hhm_ins_or_assign_res_.stats_ = CCC_ENTRY_INSERT_ERROR; \
316 } \
317 else \
318 { \
319 hhm_ins_or_assign_res_ = (struct ccc_handl_){ \
320 .i_ = ccc_impl_hhm_swaps((&hhm_ins_or_assign_handl_), \
321 lazy_value), \
322 .stats_ = CCC_ENTRY_VACANT, \
323 }; \
324 *((typeof(hhm_key_) *)ccc_impl_hhm_key_at( \
325 handle_hash_map_ptr_, \
326 ccc_impl_hhm_elem_at(handle_hash_map_ptr_, \
327 hhm_ins_or_assign_handl_.handle_.i_) \
328 ->slot_i_)) \
329 = hhm_key_; \
330 } \
331 hhm_ins_or_assign_res_.i_ \
332 = ccc_impl_hhm_elem_at(handle_hash_map_ptr_, \
333 hhm_ins_or_assign_res_.i_) \
334 ->slot_i_; \
335 } \
336 hhm_ins_or_assign_res_; \
337 }))
338
339/* NOLINTEND(readability-identifier-naming) */
340
341#endif /* CCC_IMPL_HANDLE_HASH_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_hash_fn
uint64_t ccc_hash_fn(ccc_user_key to_hash)
A callback function to hash the key type used in a container.
Definition: types.h:339
ccc_handle_i
size_t ccc_handle_i
A stable index to user data in a container that uses a flat array as the underlying storage method.
Definition: types.h:78
ccc_key_eq_fn
ccc_tribool ccc_key_eq_fn(ccc_key_cmp)
A callback function to determining equality between two stored keys.
Definition: types.h:326