C Container Collection (CCC)
Loading...
Searching...
No Matches
private_priority_queue.h
1
16#ifndef CCC_PRIVATE_PRIORITY_QUEUE_H
17#define CCC_PRIVATE_PRIORITY_QUEUE_H
18
20#include <stddef.h>
23#include "../types.h"
24
25/* NOLINTBEGIN(readability-identifier-naming) */
26
33struct CCC_Priority_queue_node
34{
36 struct CCC_Priority_queue_node *child;
38 struct CCC_Priority_queue_node *next;
40 struct CCC_Priority_queue_node *prev;
42 struct CCC_Priority_queue_node *parent;
43};
44
86struct CCC_Priority_queue
87{
89 struct CCC_Priority_queue_node *root;
91 size_t count;
93 size_t type_intruder_offset;
95 size_t sizeof_type;
98 CCC_Order order;
100 CCC_Type_comparator *compare;
102 CCC_Allocator *allocate;
104 void *context;
105};
106
107/*========================= Private Interface ==========================*/
108
110void CCC_private_priority_queue_push(struct CCC_Priority_queue *,
111 struct CCC_Priority_queue_node *);
113struct CCC_Priority_queue_node *
114CCC_private_priority_queue_node_in(struct CCC_Priority_queue const *,
115 void const *);
117CCC_Order
118CCC_private_priority_queue_order(struct CCC_Priority_queue const *,
119 struct CCC_Priority_queue_node const *,
120 struct CCC_Priority_queue_node const *);
122struct CCC_Priority_queue_node *
123CCC_private_priority_queue_merge(struct CCC_Priority_queue *,
124 struct CCC_Priority_queue_node *,
125 struct CCC_Priority_queue_node *);
127void CCC_private_priority_queue_cut_child(struct CCC_Priority_queue_node *);
129void CCC_private_priority_queue_init_node(struct CCC_Priority_queue_node *);
131struct CCC_Priority_queue_node *
132CCC_private_priority_queue_delete_node(struct CCC_Priority_queue *,
133 struct CCC_Priority_queue_node *);
135void *
136CCC_private_priority_queue_struct_base(struct CCC_Priority_queue const *,
137 struct CCC_Priority_queue_node const *);
138
139/*========================= Macro Implementations ======================*/
140
142#define CCC_private_priority_queue_initialize( \
143 private_struct_name, private_type_intruder_field, \
144 private_priority_queue_order, private_compare, private_allocate, \
145 private_context_data) \
146 { \
147 .root = NULL, \
148 .count = 0, \
149 .type_intruder_offset \
150 = offsetof(private_struct_name, private_type_intruder_field), \
151 .sizeof_type = sizeof(private_struct_name), \
152 .order = (private_priority_queue_order), \
153 .compare = (private_compare), \
154 .allocate = (private_allocate), \
155 .context = (private_context_data), \
156 }
157
159#define CCC_private_priority_queue_from( \
160 private_type_intruder_field, private_priority_queue_order, \
161 private_compare, private_allocate, private_destroy, private_context_data, \
162 private_compound_literal_array...) \
163 (__extension__({ \
164 typeof(*private_compound_literal_array) \
165 *private_priority_queue_type_array \
166 = private_compound_literal_array; \
167 struct CCC_Priority_queue private_priority_queue \
168 = CCC_private_priority_queue_initialize( \
169 typeof(*private_priority_queue_type_array), \
170 private_type_intruder_field, private_priority_queue_order, \
171 private_compare, private_allocate, private_context_data); \
172 if (private_priority_queue.allocate) \
173 { \
174 size_t const private_count \
175 = sizeof(private_compound_literal_array) \
176 / sizeof(*private_priority_queue_type_array); \
177 for (size_t private_i = 0; private_i < private_count; ++private_i) \
178 { \
179 typeof(*private_priority_queue_type_array) *const \
180 private_new_node \
181 = private_priority_queue.allocate((CCC_Allocator_context){ \
182 .input = NULL, \
183 .bytes = private_priority_queue.sizeof_type, \
184 .context = private_priority_queue.context, \
185 }); \
186 if (!private_new_node) \
187 { \
188 CCC_priority_queue_clear(&private_priority_queue, \
189 private_destroy); \
190 break; \
191 } \
192 *private_new_node \
193 = private_priority_queue_type_array[private_i]; \
194 CCC_private_priority_queue_push( \
195 &private_priority_queue, \
196 CCC_private_priority_queue_node_in( \
197 &private_priority_queue, private_new_node)); \
198 } \
199 } \
200 private_priority_queue; \
201 }))
202
204#define CCC_private_priority_queue_emplace(priority_queue_pointer, \
205 type_compound_literal...) \
206 (__extension__({ \
207 typeof(type_compound_literal) *private_priority_queue_res = NULL; \
208 struct CCC_Priority_queue *private_priority_queue \
209 = (priority_queue_pointer); \
210 if (private_priority_queue) \
211 { \
212 if (!private_priority_queue->allocate) \
213 { \
214 private_priority_queue_res = NULL; \
215 } \
216 else \
217 { \
218 private_priority_queue_res = private_priority_queue->allocate( \
219 (CCC_Allocator_context){ \
220 .input = NULL, \
221 .bytes = private_priority_queue->sizeof_type, \
222 .context = private_priority_queue->context, \
223 }); \
224 if (private_priority_queue_res) \
225 { \
226 *private_priority_queue_res = type_compound_literal; \
227 CCC_private_priority_queue_push( \
228 private_priority_queue, \
229 CCC_private_priority_queue_node_in( \
230 private_priority_queue, \
231 private_priority_queue_res)); \
232 } \
233 } \
234 } \
235 private_priority_queue_res; \
236 }))
237
239#define CCC_private_priority_queue_update_with( \
240 priority_queue_pointer, type_pointer, update_closure_over_T...) \
241 (__extension__({ \
242 struct CCC_Priority_queue *const private_priority_queue \
243 = (priority_queue_pointer); \
244 typeof(*type_pointer) *T = (type_pointer); \
245 if (private_priority_queue && T) \
246 { \
247 struct CCC_Priority_queue_node *const \
248 private_priority_queue_node_pointer \
249 = CCC_private_priority_queue_node_in(private_priority_queue, \
250 T); \
251 if (private_priority_queue_node_pointer->parent \
252 && CCC_private_priority_queue_order( \
253 private_priority_queue, \
254 private_priority_queue_node_pointer, \
255 private_priority_queue_node_pointer->parent) \
256 == private_priority_queue->order) \
257 { \
258 CCC_private_priority_queue_cut_child( \
259 private_priority_queue_node_pointer); \
260 {update_closure_over_T} private_priority_queue->root \
261 = CCC_private_priority_queue_merge( \
262 private_priority_queue, private_priority_queue->root, \
263 private_priority_queue_node_pointer); \
264 } \
265 else \
266 { \
267 private_priority_queue->root \
268 = CCC_private_priority_queue_delete_node( \
269 private_priority_queue, \
270 private_priority_queue_node_pointer); \
271 CCC_private_priority_queue_init_node( \
272 private_priority_queue_node_pointer); \
273 {update_closure_over_T} private_priority_queue->root \
274 = CCC_private_priority_queue_merge( \
275 private_priority_queue, private_priority_queue->root, \
276 private_priority_queue_node_pointer); \
277 } \
278 } \
279 T; \
280 }))
281
283#define CCC_private_priority_queue_increase_with( \
284 priority_queue_pointer, type_pointer, increase_closure_over_T...) \
285 (__extension__({ \
286 struct CCC_Priority_queue *const private_priority_queue \
287 = (priority_queue_pointer); \
288 typeof(*type_pointer) *T = (type_pointer); \
289 if (private_priority_queue && T) \
290 { \
291 struct CCC_Priority_queue_node *const \
292 private_priority_queue_node_pointer \
293 = CCC_private_priority_queue_node_in(private_priority_queue, \
294 T); \
295 if (private_priority_queue->order == CCC_ORDER_GREATER) \
296 { \
297 CCC_private_priority_queue_cut_child( \
298 private_priority_queue_node_pointer); \
299 } \
300 else \
301 { \
302 private_priority_queue->root \
303 = CCC_private_priority_queue_delete_node( \
304 private_priority_queue, \
305 private_priority_queue_node_pointer); \
306 CCC_private_priority_queue_init_node( \
307 private_priority_queue_node_pointer); \
308 } \
309 {increase_closure_over_T} private_priority_queue->root \
310 = CCC_private_priority_queue_merge( \
311 private_priority_queue, private_priority_queue->root, \
312 private_priority_queue_node_pointer); \
313 } \
314 T; \
315 }))
316
318#define CCC_private_priority_queue_decrease_with( \
319 priority_queue_pointer, type_pointer, decrease_closure_over_T...) \
320 (__extension__({ \
321 struct CCC_Priority_queue *const private_priority_queue \
322 = (priority_queue_pointer); \
323 typeof(*type_pointer) *T = (type_pointer); \
324 if (private_priority_queue && T) \
325 { \
326 struct CCC_Priority_queue_node *const \
327 private_priority_queue_node_pointer \
328 = CCC_private_priority_queue_node_in(private_priority_queue, \
329 T); \
330 if (private_priority_queue->order == CCC_ORDER_LESSER) \
331 { \
332 CCC_private_priority_queue_cut_child( \
333 private_priority_queue_node_pointer); \
334 } \
335 else \
336 { \
337 private_priority_queue->root \
338 = CCC_private_priority_queue_delete_node( \
339 private_priority_queue, \
340 private_priority_queue_node_pointer); \
341 CCC_private_priority_queue_init_node( \
342 private_priority_queue_node_pointer); \
343 } \
344 {decrease_closure_over_T} private_priority_queue->root \
345 = CCC_private_priority_queue_merge( \
346 private_priority_queue, private_priority_queue->root, \
347 private_priority_queue_node_pointer); \
348 } \
349 T; \
350 }))
351
352/* NOLINTEND(readability-identifier-naming) */
353
354#endif /* CCC_PRIVATE_PRIORITY_QUEUE_H */
CCC_Priority_queue_node
Definition: private_priority_queue.h:34
CCC_Priority_queue_node::child
struct CCC_Priority_queue_node * child
Definition: private_priority_queue.h:36
CCC_Priority_queue_node::parent
struct CCC_Priority_queue_node * parent
Definition: private_priority_queue.h:42
CCC_Priority_queue_node::prev
struct CCC_Priority_queue_node * prev
Definition: private_priority_queue.h:40
CCC_Priority_queue_node::next
struct CCC_Priority_queue_node * next
Definition: private_priority_queue.h:38
CCC_Priority_queue
Definition: private_priority_queue.h:87
CCC_Priority_queue::order
CCC_Order order
Definition: private_priority_queue.h:98
CCC_Priority_queue::root
struct CCC_Priority_queue_node * root
Definition: private_priority_queue.h:89
CCC_Priority_queue::count
size_t count
Definition: private_priority_queue.h:91
CCC_Priority_queue::context
void * context
Definition: private_priority_queue.h:104
CCC_Priority_queue::allocate
CCC_Allocator * allocate
Definition: private_priority_queue.h:102
CCC_Priority_queue::sizeof_type
size_t sizeof_type
Definition: private_priority_queue.h:95
CCC_Priority_queue::compare
CCC_Type_comparator * compare
Definition: private_priority_queue.h:100
CCC_Priority_queue::type_intruder_offset
size_t type_intruder_offset
Definition: private_priority_queue.h:93
CCC_Order
CCC_Order
A three-way comparison for comparison functions.
Definition: types.h:171
CCC_Type_comparator
CCC_Order CCC_Type_comparator(CCC_Type_comparator_context)
A callback function for comparing two elements in a container.
Definition: types.h:348
CCC_Allocator
void * CCC_Allocator(CCC_Allocator_context)
An allocation function at the core of all containers.
Definition: types.h:340