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