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_with_allocator( \
160 private_struct_name, private_type_intruder_field, \
161 private_priority_queue_order, private_compare, private_allocate) \
162 { \
163 .root = NULL, \
164 .count = 0, \
165 .type_intruder_offset \
166 = offsetof(private_struct_name, private_type_intruder_field), \
167 .sizeof_type = sizeof(private_struct_name), \
168 .order = (private_priority_queue_order), \
169 .compare = (private_compare), \
170 .allocate = (private_allocate), \
171 .context = NULL, \
172 }
173
175#define CCC_private_priority_queue_with_context_allocator( \
176 private_struct_name, private_type_intruder_field, \
177 private_priority_queue_order, private_compare, private_allocate, \
178 private_context) \
179 { \
180 .root = NULL, \
181 .count = 0, \
182 .type_intruder_offset \
183 = offsetof(private_struct_name, private_type_intruder_field), \
184 .sizeof_type = sizeof(private_struct_name), \
185 .order = (private_priority_queue_order), \
186 .compare = (private_compare), \
187 .allocate = (private_allocate), \
188 .context = (private_context), \
189 }
190
192#define CCC_private_priority_queue_from( \
193 private_type_intruder_field, private_priority_queue_order, \
194 private_compare, private_allocate, private_destroy, private_context_data, \
195 private_compound_literal_array...) \
196 (__extension__({ \
197 typeof(*private_compound_literal_array) \
198 *private_priority_queue_type_array \
199 = private_compound_literal_array; \
200 struct CCC_Priority_queue private_priority_queue \
201 = CCC_private_priority_queue_initialize( \
202 typeof(*private_priority_queue_type_array), \
203 private_type_intruder_field, private_priority_queue_order, \
204 private_compare, private_allocate, private_context_data); \
205 if (private_priority_queue.allocate) \
206 { \
207 size_t const private_count \
208 = sizeof(private_compound_literal_array) \
209 / sizeof(*private_priority_queue_type_array); \
210 for (size_t private_i = 0; private_i < private_count; ++private_i) \
211 { \
212 typeof(*private_priority_queue_type_array) *const \
213 private_new_node \
214 = private_priority_queue.allocate((CCC_Allocator_context){ \
215 .input = NULL, \
216 .bytes = private_priority_queue.sizeof_type, \
217 .context = private_priority_queue.context, \
218 }); \
219 if (!private_new_node) \
220 { \
221 CCC_priority_queue_clear(&private_priority_queue, \
222 private_destroy); \
223 break; \
224 } \
225 *private_new_node \
226 = private_priority_queue_type_array[private_i]; \
227 CCC_private_priority_queue_push( \
228 &private_priority_queue, \
229 CCC_private_priority_queue_node_in( \
230 &private_priority_queue, private_new_node)); \
231 } \
232 } \
233 private_priority_queue; \
234 }))
235
237#define CCC_private_priority_queue_emplace(priority_queue_pointer, \
238 type_compound_literal...) \
239 (__extension__({ \
240 typeof(type_compound_literal) *private_priority_queue_res = NULL; \
241 struct CCC_Priority_queue *private_priority_queue \
242 = (priority_queue_pointer); \
243 if (private_priority_queue) \
244 { \
245 if (!private_priority_queue->allocate) \
246 { \
247 private_priority_queue_res = NULL; \
248 } \
249 else \
250 { \
251 private_priority_queue_res = private_priority_queue->allocate( \
252 (CCC_Allocator_context){ \
253 .input = NULL, \
254 .bytes = private_priority_queue->sizeof_type, \
255 .context = private_priority_queue->context, \
256 }); \
257 if (private_priority_queue_res) \
258 { \
259 *private_priority_queue_res = type_compound_literal; \
260 CCC_private_priority_queue_push( \
261 private_priority_queue, \
262 CCC_private_priority_queue_node_in( \
263 private_priority_queue, \
264 private_priority_queue_res)); \
265 } \
266 } \
267 } \
268 private_priority_queue_res; \
269 }))
270
272#define CCC_private_priority_queue_update_with( \
273 priority_queue_pointer, type_pointer, update_closure_over_T...) \
274 (__extension__({ \
275 struct CCC_Priority_queue *const private_priority_queue \
276 = (priority_queue_pointer); \
277 typeof(*type_pointer) *T = (type_pointer); \
278 if (private_priority_queue && T) \
279 { \
280 struct CCC_Priority_queue_node *const \
281 private_priority_queue_node_pointer \
282 = CCC_private_priority_queue_node_in(private_priority_queue, \
283 T); \
284 if (private_priority_queue_node_pointer->parent \
285 && CCC_private_priority_queue_order( \
286 private_priority_queue, \
287 private_priority_queue_node_pointer, \
288 private_priority_queue_node_pointer->parent) \
289 == private_priority_queue->order) \
290 { \
291 CCC_private_priority_queue_cut_child( \
292 private_priority_queue_node_pointer); \
293 {update_closure_over_T} private_priority_queue->root \
294 = CCC_private_priority_queue_merge( \
295 private_priority_queue, private_priority_queue->root, \
296 private_priority_queue_node_pointer); \
297 } \
298 else \
299 { \
300 private_priority_queue->root \
301 = CCC_private_priority_queue_delete_node( \
302 private_priority_queue, \
303 private_priority_queue_node_pointer); \
304 CCC_private_priority_queue_init_node( \
305 private_priority_queue_node_pointer); \
306 {update_closure_over_T} private_priority_queue->root \
307 = CCC_private_priority_queue_merge( \
308 private_priority_queue, private_priority_queue->root, \
309 private_priority_queue_node_pointer); \
310 } \
311 } \
312 T; \
313 }))
314
316#define CCC_private_priority_queue_increase_with( \
317 priority_queue_pointer, type_pointer, increase_closure_over_T...) \
318 (__extension__({ \
319 struct CCC_Priority_queue *const private_priority_queue \
320 = (priority_queue_pointer); \
321 typeof(*type_pointer) *T = (type_pointer); \
322 if (private_priority_queue && T) \
323 { \
324 struct CCC_Priority_queue_node *const \
325 private_priority_queue_node_pointer \
326 = CCC_private_priority_queue_node_in(private_priority_queue, \
327 T); \
328 if (private_priority_queue->order == CCC_ORDER_GREATER) \
329 { \
330 CCC_private_priority_queue_cut_child( \
331 private_priority_queue_node_pointer); \
332 } \
333 else \
334 { \
335 private_priority_queue->root \
336 = CCC_private_priority_queue_delete_node( \
337 private_priority_queue, \
338 private_priority_queue_node_pointer); \
339 CCC_private_priority_queue_init_node( \
340 private_priority_queue_node_pointer); \
341 } \
342 {increase_closure_over_T} private_priority_queue->root \
343 = CCC_private_priority_queue_merge( \
344 private_priority_queue, private_priority_queue->root, \
345 private_priority_queue_node_pointer); \
346 } \
347 T; \
348 }))
349
351#define CCC_private_priority_queue_decrease_with( \
352 priority_queue_pointer, type_pointer, decrease_closure_over_T...) \
353 (__extension__({ \
354 struct CCC_Priority_queue *const private_priority_queue \
355 = (priority_queue_pointer); \
356 typeof(*type_pointer) *T = (type_pointer); \
357 if (private_priority_queue && T) \
358 { \
359 struct CCC_Priority_queue_node *const \
360 private_priority_queue_node_pointer \
361 = CCC_private_priority_queue_node_in(private_priority_queue, \
362 T); \
363 if (private_priority_queue->order == CCC_ORDER_LESSER) \
364 { \
365 CCC_private_priority_queue_cut_child( \
366 private_priority_queue_node_pointer); \
367 } \
368 else \
369 { \
370 private_priority_queue->root \
371 = CCC_private_priority_queue_delete_node( \
372 private_priority_queue, \
373 private_priority_queue_node_pointer); \
374 CCC_private_priority_queue_init_node( \
375 private_priority_queue_node_pointer); \
376 } \
377 {decrease_closure_over_T} private_priority_queue->root \
378 = CCC_private_priority_queue_merge( \
379 private_priority_queue, private_priority_queue->root, \
380 private_priority_queue_node_pointer); \
381 } \
382 T; \
383 }))
384
385/* NOLINTEND(readability-identifier-naming) */
386
387#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