Line data Source code
1 : /** Copyright 2025 Alexander G. Lopez
2 :
3 : Licensed under the Apache License, Version 2.0 (the "License");
4 : you may not use this file except in compliance with the License.
5 : You may obtain a copy of the License at
6 :
7 : http://www.apache.org/licenses/LICENSE-2.0
8 :
9 : Unless required by applicable law or agreed to in writing, software
10 : distributed under the License is distributed on an "AS IS" BASIS,
11 : WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : See the License for the specific language governing permissions and
13 : limitations under the License. */
14 : /** C23 provided headers. */
15 : #include <stddef.h>
16 :
17 : /** CCC provided headers. */
18 : #include "ccc/configuration.h" /* IWYU pragma: keep */
19 : #include "ccc/specialized/priority_queue.h"
20 : #include "ccc/specialized/private/private_priority_queue.h"
21 : #include "ccc/types.h"
22 :
23 : /*========================= Function Prototypes ==========================*/
24 :
25 : static struct CCC_Priority_queue_node *
26 : elem_in(struct CCC_Priority_queue const *, void const *);
27 : static struct CCC_Priority_queue_node *merge(
28 : struct CCC_Priority_queue *,
29 : struct CCC_Priority_queue_node *,
30 : struct CCC_Priority_queue_node *
31 : );
32 : static void
33 : link_child(struct CCC_Priority_queue_node *, struct CCC_Priority_queue_node *);
34 : static void init_node(struct CCC_Priority_queue_node *);
35 : static size_t traversal_count(struct CCC_Priority_queue_node const *);
36 : static CCC_Tribool has_valid_links(
37 : struct CCC_Priority_queue const *,
38 : struct CCC_Priority_queue_node const *,
39 : struct CCC_Priority_queue_node const *
40 : );
41 : static struct CCC_Priority_queue_node *
42 : delete_node(struct CCC_Priority_queue *, struct CCC_Priority_queue_node *);
43 : static struct CCC_Priority_queue_node *
44 : delete_root(struct CCC_Priority_queue *, struct CCC_Priority_queue_node *);
45 : static void clear_node(struct CCC_Priority_queue_node *);
46 : static void cut_child(struct CCC_Priority_queue_node *);
47 : static void *struct_base(
48 : struct CCC_Priority_queue const *, struct CCC_Priority_queue_node const *
49 : );
50 : static CCC_Order order(
51 : struct CCC_Priority_queue const *,
52 : struct CCC_Priority_queue_node const *,
53 : struct CCC_Priority_queue_node const *
54 : );
55 : static void
56 : update_fixup(struct CCC_Priority_queue *, struct CCC_Priority_queue_node *);
57 : static void
58 : increase_fixup(struct CCC_Priority_queue *, struct CCC_Priority_queue_node *);
59 : static void
60 : decrease_fixup(struct CCC_Priority_queue *, struct CCC_Priority_queue_node *);
61 :
62 : /*========================= Interface Functions ==========================*/
63 :
64 : void *
65 614 : CCC_priority_queue_front(CCC_Priority_queue const *const priority_queue) {
66 614 : if (!priority_queue) {
67 1 : return NULL;
68 : }
69 613 : return priority_queue->root
70 613 : ? struct_base(priority_queue, priority_queue->root)
71 : : NULL;
72 614 : }
73 :
74 : void *
75 2884 : CCC_priority_queue_push(
76 : CCC_Priority_queue *const priority_queue,
77 : CCC_Priority_queue_node *type_intruder,
78 : CCC_Allocator const *const allocator
79 : ) {
80 2884 : if (!type_intruder || !priority_queue || !allocator) {
81 3 : return NULL;
82 : }
83 2881 : void *ret = struct_base(priority_queue, type_intruder);
84 2881 : if (allocator->allocate) {
85 11476 : void *const node = allocator->allocate((CCC_Allocator_arguments){
86 : .input = NULL,
87 2869 : .bytes = priority_queue->sizeof_type,
88 2869 : .alignment = priority_queue->alignof_type,
89 2869 : .context = allocator->context,
90 : });
91 2869 : if (!node) {
92 1 : return NULL;
93 : }
94 2868 : (void)memcpy(node, ret, priority_queue->sizeof_type);
95 2868 : ret = node;
96 2868 : type_intruder = elem_in(priority_queue, ret);
97 2869 : }
98 2880 : init_node(type_intruder);
99 2880 : priority_queue->root
100 5760 : = merge(priority_queue, priority_queue->root, type_intruder);
101 2880 : ++priority_queue->count;
102 2880 : return ret;
103 2884 : }
104 :
105 : CCC_Result
106 706 : CCC_priority_queue_pop(
107 : CCC_Priority_queue *const priority_queue,
108 : CCC_Allocator const *const allocator
109 : ) {
110 706 : if (!priority_queue || !priority_queue->root || !allocator) {
111 2 : return CCC_RESULT_ARGUMENT_ERROR;
112 : }
113 704 : struct CCC_Priority_queue_node *const popped = priority_queue->root;
114 704 : priority_queue->root = delete_root(priority_queue, priority_queue->root);
115 704 : priority_queue->count--;
116 704 : clear_node(popped);
117 704 : if (allocator->allocate) {
118 2816 : (void)allocator->allocate((CCC_Allocator_arguments){
119 704 : .input = struct_base(priority_queue, popped),
120 : .bytes = 0,
121 704 : .alignment = priority_queue->alignof_type,
122 704 : .context = allocator->context,
123 : });
124 704 : }
125 704 : return CCC_RESULT_OK;
126 706 : }
127 :
128 : void *
129 1231 : CCC_priority_queue_extract(
130 : CCC_Priority_queue *const priority_queue,
131 : CCC_Priority_queue_node *const type_intruder
132 : ) {
133 1231 : if (!priority_queue || !type_intruder || !priority_queue->root
134 1230 : || !type_intruder->next || !type_intruder->prev) {
135 1 : return NULL;
136 : }
137 1230 : priority_queue->root = delete_node(priority_queue, type_intruder);
138 1230 : priority_queue->count--;
139 1230 : clear_node(type_intruder);
140 1230 : return struct_base(priority_queue, type_intruder);
141 1231 : }
142 :
143 : CCC_Result
144 102 : CCC_priority_queue_erase(
145 : CCC_Priority_queue *const priority_queue,
146 : CCC_Priority_queue_node *const type_intruder,
147 : CCC_Allocator const *const allocator
148 : ) {
149 102 : if (!priority_queue || !type_intruder || !priority_queue->root || !allocator
150 100 : || !type_intruder->next || !type_intruder->prev) {
151 2 : return CCC_RESULT_ARGUMENT_ERROR;
152 : }
153 100 : priority_queue->root = delete_node(priority_queue, type_intruder);
154 100 : priority_queue->count--;
155 100 : if (allocator->allocate) {
156 400 : (void)allocator->allocate((CCC_Allocator_arguments){
157 100 : .input = struct_base(priority_queue, type_intruder),
158 : .bytes = 0,
159 100 : .alignment = priority_queue->alignof_type,
160 100 : .context = allocator->context,
161 : });
162 100 : }
163 100 : return CCC_RESULT_OK;
164 102 : }
165 :
166 : /** Deletes all nodes in the heap in linear time and constant space. This is
167 : achieved by continually bringing up any child lists and splicing them into the
168 : current child list being considered. We are avoiding recursion or amortized
169 : O(log(N)) pops with this method. */
170 : CCC_Result
171 7 : CCC_priority_queue_clear(
172 : CCC_Priority_queue *const priority_queue,
173 : CCC_Destructor const *const destructor,
174 : CCC_Allocator const *const allocator
175 : ) {
176 7 : if (!priority_queue || !destructor || !allocator) {
177 3 : return CCC_RESULT_ARGUMENT_ERROR;
178 : }
179 4 : struct CCC_Priority_queue_node *node = priority_queue->root;
180 163 : while (node) {
181 : /* The child and its siblings cut to the front of the line and we
182 : start again as if the child is the first in this sibling list. */
183 159 : if (node->child) {
184 6 : struct CCC_Priority_queue_node *const child = node->child;
185 6 : struct CCC_Priority_queue_node *const node_end = node->next;
186 : /* Final element of e child list pick up child as head */
187 6 : node_end->prev = child;
188 : /* Now e picks up the last (wrapping) element of child list. */
189 6 : node->next = child->next;
190 : /* Child has a list so don't just set child's prev to e. */
191 6 : child->next->prev = node;
192 : /* Child list wrapping element is now end of e list. */
193 6 : child->next = node_end;
194 : /* Our traversal now jumps to start of list we spliced in. */
195 6 : node->child = NULL;
196 6 : node = child;
197 : continue;
198 6 : }
199 : /* No more child lists to splice in so this node is done. */
200 306 : struct CCC_Priority_queue_node *const prev_node
201 153 : = node->prev == node ? NULL : node->prev;
202 153 : node->next->prev = node->prev;
203 153 : node->prev->next = node->next;
204 153 : node->parent = node->next = node->prev = node->child = NULL;
205 153 : void *const destroy_this = struct_base(priority_queue, node);
206 153 : if (destructor->destroy) {
207 150 : destructor->destroy((CCC_Arguments){
208 50 : .type = destroy_this,
209 50 : .context = destructor->context,
210 : });
211 50 : }
212 153 : if (allocator->allocate) {
213 612 : (void)allocator->allocate((CCC_Allocator_arguments){
214 153 : .input = destroy_this,
215 : .bytes = 0,
216 153 : .alignment = priority_queue->alignof_type,
217 153 : .context = allocator->context,
218 : });
219 153 : }
220 153 : node = prev_node;
221 153 : }
222 4 : priority_queue->count = 0;
223 4 : priority_queue->root = NULL;
224 4 : return CCC_RESULT_OK;
225 7 : }
226 :
227 : CCC_Tribool
228 618 : CCC_priority_queue_is_empty(CCC_Priority_queue const *const priority_queue) {
229 618 : if (!priority_queue) {
230 1 : return CCC_TRIBOOL_ERROR;
231 : }
232 617 : return !priority_queue->count;
233 618 : }
234 :
235 : CCC_Count
236 548 : CCC_priority_queue_count(CCC_Priority_queue const *const priority_queue) {
237 548 : if (!priority_queue) {
238 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
239 : }
240 547 : return (CCC_Count){.count = priority_queue->count};
241 548 : }
242 :
243 : /** This is a difficult function. Without knowing if this new value is greater
244 : or less than the previous we must always perform a delete and reinsert if the
245 : value has not broken total order with the parent. It is not sufficient to check
246 : if the value has exceeded the value of the first left child as any sibling of
247 : that left child may be bigger than or smaller than that left child value. */
248 : void *
249 87 : CCC_priority_queue_update(
250 : CCC_Priority_queue *const priority_queue,
251 : CCC_Priority_queue_node *const type_intruder,
252 : CCC_Modifier const *const modifier
253 : ) {
254 87 : if (!priority_queue || !type_intruder || !modifier || !modifier->modify
255 84 : || !type_intruder->next || !type_intruder->prev) {
256 3 : return NULL;
257 : }
258 252 : modifier->modify((CCC_Arguments){
259 84 : .type = struct_base(priority_queue, type_intruder),
260 84 : .context = modifier->context,
261 : });
262 84 : update_fixup(priority_queue, type_intruder);
263 84 : return struct_base(priority_queue, type_intruder);
264 87 : }
265 :
266 : /* Preferable to use this function if it is known the value is increasing.
267 : Much more efficient. */
268 : void *
269 53 : CCC_priority_queue_increase(
270 : CCC_Priority_queue *const priority_queue,
271 : CCC_Priority_queue_node *const type_intruder,
272 : CCC_Modifier const *const modifier
273 : ) {
274 53 : if (!priority_queue || !type_intruder || !modifier || !modifier->modify
275 50 : || !type_intruder->next || !type_intruder->prev) {
276 3 : return NULL;
277 : }
278 150 : modifier->modify((CCC_Arguments){
279 50 : .type = struct_base(priority_queue, type_intruder),
280 50 : .context = modifier->context,
281 : });
282 50 : increase_fixup(priority_queue, type_intruder);
283 50 : return struct_base(priority_queue, type_intruder);
284 53 : }
285 :
286 : /* Preferable to use this function if it is known the value is decreasing.
287 : Much more efficient. */
288 : void *
289 156 : CCC_priority_queue_decrease(
290 : CCC_Priority_queue *const priority_queue,
291 : CCC_Priority_queue_node *const type_intruder,
292 : CCC_Modifier const *const modifier
293 : ) {
294 156 : if (!priority_queue || !type_intruder || !modifier || !modifier->modify
295 153 : || !type_intruder->next || !type_intruder->prev) {
296 3 : return NULL;
297 : }
298 459 : modifier->modify((CCC_Arguments){
299 153 : .type = struct_base(priority_queue, type_intruder),
300 153 : .context = modifier->context,
301 : });
302 153 : decrease_fixup(priority_queue, type_intruder);
303 153 : return struct_base(priority_queue, type_intruder);
304 156 : }
305 :
306 : CCC_Tribool
307 5322 : CCC_priority_queue_validate(CCC_Priority_queue const *const priority_queue) {
308 5322 : if (!priority_queue
309 5322 : || (priority_queue->root && priority_queue->root->parent)) {
310 0 : return CCC_FALSE;
311 : }
312 5322 : if (!has_valid_links(priority_queue, NULL, priority_queue->root)) {
313 0 : return CCC_FALSE;
314 : }
315 5322 : if (traversal_count(priority_queue->root) != priority_queue->count) {
316 0 : return CCC_FALSE;
317 : }
318 5322 : return CCC_TRUE;
319 5322 : }
320 :
321 : CCC_Order
322 5 : CCC_priority_queue_order(CCC_Priority_queue const *const priority_queue) {
323 5 : return priority_queue ? priority_queue->order : CCC_ORDER_ERROR;
324 : }
325 :
326 : /*========================= Private Interface ==========================*/
327 :
328 : void
329 3 : CCC_private_priority_queue_push(
330 : struct CCC_Priority_queue *const priority_queue,
331 : struct CCC_Priority_queue_node *const node
332 : ) {
333 3 : init_node(node);
334 3 : priority_queue->root = merge(priority_queue, priority_queue->root, node);
335 3 : ++priority_queue->count;
336 3 : }
337 :
338 : struct CCC_Priority_queue_node *
339 282 : CCC_private_priority_queue_node_in(
340 : struct CCC_Priority_queue const *const priority_queue,
341 : void const *const any_struct
342 : ) {
343 282 : return elem_in(priority_queue, any_struct);
344 : }
345 :
346 : void
347 79 : CCC_private_priority_queue_update_fixup(
348 : struct CCC_Priority_queue *const pq,
349 : struct CCC_Priority_queue_node *const node
350 : ) {
351 79 : return update_fixup(pq, node);
352 79 : }
353 :
354 : void
355 43 : CCC_private_priority_queue_increase_fixup(
356 : struct CCC_Priority_queue *const pq,
357 : struct CCC_Priority_queue_node *const node
358 : ) {
359 43 : return increase_fixup(pq, node);
360 43 : }
361 :
362 : void
363 157 : CCC_private_priority_queue_decrease_fixup(
364 : struct CCC_Priority_queue *const pq,
365 : struct CCC_Priority_queue_node *const node
366 : ) {
367 157 : return decrease_fixup(pq, node);
368 157 : }
369 :
370 : /*======================== Static Helpers ================================*/
371 :
372 : static void
373 163 : update_fixup(
374 : struct CCC_Priority_queue *const priority_queue,
375 : struct CCC_Priority_queue_node *const node
376 : ) {
377 : /* We could get lucky with a fast path but otherwise there is no way to
378 : know whether this is an increase or decrease and by how much. */
379 163 : if (node->parent
380 163 : && order(priority_queue, node, node->parent) == priority_queue->order) {
381 2 : cut_child(node);
382 2 : } else {
383 161 : priority_queue->root = delete_node(priority_queue, node);
384 161 : init_node(node);
385 : }
386 163 : priority_queue->root = merge(priority_queue, priority_queue->root, node);
387 163 : }
388 :
389 : static void
390 93 : increase_fixup(
391 : struct CCC_Priority_queue *const priority_queue,
392 : struct CCC_Priority_queue_node *const node
393 : ) {
394 93 : if (priority_queue->order == CCC_ORDER_GREATER
395 93 : && node == priority_queue->root) {
396 1 : return;
397 : }
398 92 : if (priority_queue->order == CCC_ORDER_GREATER) {
399 1 : cut_child(node);
400 1 : } else {
401 91 : priority_queue->root = delete_node(priority_queue, node);
402 91 : init_node(node);
403 : }
404 92 : priority_queue->root = merge(priority_queue, priority_queue->root, node);
405 185 : }
406 :
407 : static void
408 310 : decrease_fixup(
409 : struct CCC_Priority_queue *const priority_queue,
410 : struct CCC_Priority_queue_node *const node
411 : ) {
412 310 : if (priority_queue->order == CCC_ORDER_LESSER
413 310 : && node == priority_queue->root) {
414 1 : return;
415 : }
416 309 : if (priority_queue->order == CCC_ORDER_LESSER) {
417 308 : cut_child(node);
418 308 : } else {
419 1 : priority_queue->root = delete_node(priority_queue, node);
420 1 : init_node(node);
421 : }
422 309 : priority_queue->root = merge(priority_queue, priority_queue->root, node);
423 619 : }
424 :
425 : /** Cuts the child out of its current sibling list and redirects parent if
426 : this child is directly pointed to by parent. The child is then made into its
427 : own circular sibling list. The left child of this child, if one exists, is
428 : still pointed to and not modified by this function. */
429 : static void
430 1756 : cut_child(struct CCC_Priority_queue_node *const child) {
431 1756 : child->next->prev = child->prev;
432 1756 : child->prev->next = child->next;
433 1756 : if (child->parent && child == child->parent->child) {
434 : /* To preserve the shuffle down properties the prev child should
435 : become the new child as that is the next youngest node. */
436 1027 : child->parent->child = child->prev == child ? NULL : child->prev;
437 1027 : }
438 1756 : child->parent = NULL;
439 1756 : child->next = child->prev = child;
440 1756 : }
441 :
442 : static struct CCC_Priority_queue_node *
443 1583 : delete_node(
444 : struct CCC_Priority_queue *const priority_queue,
445 : struct CCC_Priority_queue_node *const root
446 : ) {
447 1583 : if (priority_queue->root == root) {
448 138 : return delete_root(priority_queue, root);
449 : }
450 1445 : cut_child(root);
451 1445 : return merge(
452 1445 : priority_queue, priority_queue->root, delete_root(priority_queue, root)
453 : );
454 1583 : }
455 :
456 : /* Uses Fredman et al. oldest to youngest pairing method mentioned on pg 124
457 : of the paper to pair nodes in one pass. Of all the variants for pairing given
458 : in the paper this one is the back-to-front variant and the only one for which
459 : the runtime analysis holds identically to the two-pass standard variant. A
460 : non-trivial example for a heap.
461 :
462 : < = next_sibling
463 : > = prev_sibling
464 :
465 : ┌<1>┐
466 : └/──┘
467 : ┌<9>─<1>─<9>─<7>─<8>┐
468 : └───────────────────┘
469 : |
470 : v
471 : ┌<9>─<1>─<7>─<8>┐
472 : └────────/──────┘
473 : ┌<9>┐
474 : └───┘
475 : |
476 : v
477 : ┌<9>─<1>─<7>┐
478 : └────────/──┘
479 : ┌<8>─<9>┐
480 : └───────┘
481 : |
482 : v
483 : ┌<1>─<7>┐
484 : └/────/─┘
485 : ┌<9>┐┌<8>─<9>┐
486 : └───┘└───────┘
487 : |
488 : v
489 : ┌<1>┐
490 : └/──┘
491 : ┌<7>─<9>┐
492 : └/──────┘
493 : ┌<8>─<9>┐
494 : └───────┘
495 :
496 : Delete root is the slowest operation offered by the priority queue and in
497 : part contributes to the amortized `o(log(N))` runtime of the decrease key
498 : operation. */
499 : static struct CCC_Priority_queue_node *
500 2287 : delete_root(
501 : struct CCC_Priority_queue *const priority_queue,
502 : struct CCC_Priority_queue_node *root
503 : ) {
504 2287 : if (!root->child) {
505 949 : return NULL;
506 : }
507 1338 : struct CCC_Priority_queue_node *const eldest = root->child->next;
508 1338 : struct CCC_Priority_queue_node *accumulator = root->child->next;
509 1338 : struct CCC_Priority_queue_node *cur = root->child->next->next;
510 4156 : while (cur != eldest && cur->next != eldest) {
511 2818 : struct CCC_Priority_queue_node *const next = cur->next;
512 2818 : struct CCC_Priority_queue_node *const next_cur = cur->next->next;
513 2818 : next->next = next->prev = NULL;
514 2818 : cur->next = cur->prev = NULL;
515 : /* Double merge ensures `O(log(N))` steps rather than O(N). */
516 2818 : accumulator = merge(
517 2818 : priority_queue, accumulator, merge(priority_queue, cur, next)
518 : );
519 2818 : cur = next_cur;
520 2818 : }
521 : /* This covers the odd or even case for number of pairings. */
522 : root
523 1338 : = cur == eldest ? accumulator : merge(priority_queue, accumulator, cur);
524 : /* The root is always alone in its circular list at the end of merges. */
525 1338 : root->next = root->prev = root;
526 1338 : root->parent = NULL;
527 1338 : return root;
528 2287 : }
529 :
530 : /** Merges two priority queues, making the winner by ordering the root and
531 : pushing the loser to the left child ring. Old should be the element that has
532 : been in the queue longer and new, newer. This algorithm will still work if this
533 : argument ordering is not respected and it does not change runtime, but it is how
534 : to comply with the strategy outlined in the Fredman et. al. paper. */
535 : static struct CCC_Priority_queue_node *
536 10993 : merge(
537 : struct CCC_Priority_queue *const priority_queue,
538 : struct CCC_Priority_queue_node *const old,
539 : struct CCC_Priority_queue_node *const new
540 : ) {
541 10993 : if (!old || !new || old == new) {
542 968 : return old ? old : new;
543 : }
544 10025 : if (order(priority_queue, new, old) == priority_queue->order) {
545 1768 : link_child(new, old);
546 1768 : return new;
547 : }
548 8257 : link_child(old, new);
549 8257 : return old;
550 10993 : }
551 :
552 : /* Oldest nodes shuffle down, new drops in to replace. This supports the
553 : ring representation from Fredman et al., pg 125, fig 14 where the left
554 : child's next pointer wraps to the last element in the list. The previous
555 : pointer is to support faster deletes and decrease key operations.
556 :
557 : < = next_sibling
558 : > = prev_sibling
559 :
560 : A A A
561 : ╱ ╱ ╱
562 : ┌─<B>─┐ ┌─<C>──<B>─┐ ┌─<D>──<C>──<B>─┐
563 : └─────┘ └──────────┘ └───────────────┘
564 :
565 : Pairing in the delete root phase would then start at B in this example and work
566 : towards D. That is the oldest to youngest order mentioned in the paper and
567 : helps set up the one-pass back-to-front variant mentioned in the paper allowing
568 : the same runtime guarantees as the two pass standard pairing heap. */
569 : static void
570 10025 : link_child(
571 : struct CCC_Priority_queue_node *const parent,
572 : struct CCC_Priority_queue_node *const child
573 : ) {
574 10025 : if (parent->child) {
575 8183 : child->next = parent->child->next;
576 8183 : child->prev = parent->child;
577 8183 : parent->child->next->prev = child;
578 8183 : parent->child->next = child;
579 8183 : } else {
580 1842 : child->next = child->prev = child;
581 : }
582 10025 : parent->child = child;
583 10025 : child->parent = parent;
584 10025 : }
585 :
586 : static inline CCC_Order
587 1162049 : order(
588 : struct CCC_Priority_queue const *const priority_queue,
589 : struct CCC_Priority_queue_node const *const left,
590 : struct CCC_Priority_queue_node const *const right
591 : ) {
592 4648196 : return priority_queue->comparator.compare((CCC_Comparator_arguments){
593 1162049 : .type_left = struct_base(priority_queue, left),
594 1162049 : .type_right = struct_base(priority_queue, right),
595 1162049 : .context = priority_queue->comparator.context,
596 : });
597 : }
598 :
599 : static inline void *
600 2330353 : struct_base(
601 : struct CCC_Priority_queue const *const priority_queue,
602 : struct CCC_Priority_queue_node const *const node
603 : ) {
604 2330353 : return ((char *)&(node->child)) - priority_queue->type_intruder_offset;
605 : }
606 :
607 : static inline struct CCC_Priority_queue_node *
608 3150 : elem_in(
609 : struct CCC_Priority_queue const *const priority_queue,
610 : void const *const any_struct
611 : ) {
612 3150 : return (struct CCC_Priority_queue_node
613 3150 : *)((char *)any_struct + priority_queue->type_intruder_offset);
614 : }
615 :
616 : static inline void
617 3136 : init_node(struct CCC_Priority_queue_node *const node) {
618 3136 : node->child = node->parent = NULL;
619 3136 : node->next = node->prev = node;
620 3136 : }
621 :
622 : static inline void
623 1934 : clear_node(struct CCC_Priority_queue_node *const node) {
624 1934 : node->child = node->next = node->prev = node->parent = NULL;
625 1934 : }
626 :
627 : /*======================== Validation ================================*/
628 :
629 : /* NOLINTBEGIN(*misc-no-recursion) */
630 :
631 : static size_t
632 1162482 : traversal_count(struct CCC_Priority_queue_node const *const root) {
633 1162482 : if (!root) {
634 997478 : return 0;
635 : }
636 165004 : size_t count = 0;
637 165004 : struct CCC_Priority_queue_node const *cur = root;
638 165004 : do {
639 1157160 : count += 1 + traversal_count(cur->child);
640 1157160 : } while ((cur = cur->next) != root);
641 165004 : return count;
642 1162482 : }
643 :
644 : static CCC_Tribool
645 1162482 : has_valid_links(
646 : struct CCC_Priority_queue const *const priority_queue,
647 : struct CCC_Priority_queue_node const *const parent,
648 : struct CCC_Priority_queue_node const *const child
649 : ) {
650 1162482 : if (!child) {
651 997478 : return CCC_TRUE;
652 : }
653 165004 : struct CCC_Priority_queue_node const *current = child;
654 165004 : CCC_Order const wrong_order = priority_queue->order == CCC_ORDER_LESSER
655 : ? CCC_ORDER_GREATER
656 : : CCC_ORDER_LESSER;
657 165004 : do {
658 : /* Reminder: Don't combine these if checks into one. Separating them
659 : makes it easier to find the problem when stepping through gdb. */
660 1157160 : if (!current) {
661 0 : return CCC_FALSE;
662 : }
663 1157160 : if (parent && child->parent != parent) {
664 0 : return CCC_FALSE;
665 : }
666 1157160 : if (parent && parent->child != child->parent->child) {
667 0 : return CCC_FALSE;
668 : }
669 1157160 : if (child->next->prev != child || child->prev->next != child) {
670 0 : return CCC_FALSE;
671 : }
672 1157160 : if (parent && (order(priority_queue, parent, current) == wrong_order)) {
673 0 : return CCC_FALSE;
674 : }
675 : /* RECURSE! */
676 1157160 : if (!has_valid_links(priority_queue, current, current->child)) {
677 0 : return CCC_FALSE;
678 : }
679 1157160 : } while ((current = current->next) != child);
680 165004 : return CCC_TRUE;
681 1162482 : }
682 :
683 : /* NOLINTEND(*misc-no-recursion) */
|
