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 1224 : CCC_priority_queue_extract(
128 : CCC_Priority_queue *const priority_queue,
129 : CCC_Priority_queue_node *const type_intruder
130 : ) {
131 1224 : if (!priority_queue || !type_intruder || !priority_queue->root
132 1223 : || !type_intruder->next || !type_intruder->prev) {
133 1 : return NULL;
134 : }
135 1223 : priority_queue->root = delete_node(priority_queue, type_intruder);
136 1223 : priority_queue->count--;
137 1223 : clear_node(type_intruder);
138 1223 : return struct_base(priority_queue, type_intruder);
139 1224 : }
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 160 : 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 156 : if (node->child) {
181 3 : struct CCC_Priority_queue_node *const child = node->child;
182 3 : struct CCC_Priority_queue_node *const node_end = node->next;
183 : /* Final element of e child list pick up child as head */
184 3 : node_end->prev = child;
185 : /* Now e picks up the last (wrapping) element of child list. */
186 3 : node->next = child->next;
187 : /* Child has a list so don't just set child's prev to e. */
188 3 : child->next->prev = node;
189 : /* Child list wrapping element is now end of e list. */
190 3 : child->next = node_end;
191 : /* Our traversal now jumps to start of list we spliced in. */
192 3 : node->child = NULL;
193 3 : node = child;
194 : continue;
195 3 : }
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
241 : the value has not broken total order with the parent. It is not sufficient
242 : to check if the value has exceeded the value of the first left child as
243 : any sibling of that left child may be bigger than or smaller than that
244 : left child value. */
245 : void *
246 78 : CCC_priority_queue_update(
247 : CCC_Priority_queue *const priority_queue,
248 : CCC_Priority_queue_node *const type_intruder,
249 : CCC_Modifier const *const modifier
250 : ) {
251 78 : if (!priority_queue || !type_intruder || !modifier || !modifier->modify
252 75 : || !type_intruder->next || !type_intruder->prev) {
253 3 : return NULL;
254 : }
255 225 : modifier->modify((CCC_Arguments){
256 75 : .type = struct_base(priority_queue, type_intruder),
257 75 : .context = modifier->context,
258 : });
259 75 : update_fixup(priority_queue, type_intruder);
260 75 : return struct_base(priority_queue, type_intruder);
261 78 : }
262 :
263 : /* Preferable to use this function if it is known the value is increasing.
264 : Much more efficient. */
265 : void *
266 57 : CCC_priority_queue_increase(
267 : CCC_Priority_queue *const priority_queue,
268 : CCC_Priority_queue_node *const type_intruder,
269 : CCC_Modifier const *const modifier
270 : ) {
271 57 : if (!priority_queue || !type_intruder || !modifier || !modifier->modify
272 54 : || !type_intruder->next || !type_intruder->prev) {
273 3 : return NULL;
274 : }
275 162 : modifier->modify((CCC_Arguments){
276 54 : .type = struct_base(priority_queue, type_intruder),
277 54 : .context = modifier->context,
278 : });
279 54 : increase_fixup(priority_queue, type_intruder);
280 54 : return struct_base(priority_queue, type_intruder);
281 57 : }
282 :
283 : /* Preferable to use this function if it is known the value is decreasing.
284 : Much more efficient. */
285 : void *
286 154 : CCC_priority_queue_decrease(
287 : CCC_Priority_queue *const priority_queue,
288 : CCC_Priority_queue_node *const type_intruder,
289 : CCC_Modifier const *const modifier
290 : ) {
291 154 : if (!priority_queue || !type_intruder || !modifier || !modifier->modify
292 151 : || !type_intruder->next || !type_intruder->prev) {
293 3 : return NULL;
294 : }
295 453 : modifier->modify((CCC_Arguments){
296 151 : .type = struct_base(priority_queue, type_intruder),
297 151 : .context = modifier->context,
298 : });
299 151 : decrease_fixup(priority_queue, type_intruder);
300 151 : return struct_base(priority_queue, type_intruder);
301 154 : }
302 :
303 : CCC_Tribool
304 5303 : CCC_priority_queue_validate(CCC_Priority_queue const *const priority_queue) {
305 5303 : if (!priority_queue
306 5303 : || (priority_queue->root && priority_queue->root->parent)) {
307 0 : return CCC_FALSE;
308 : }
309 5303 : if (!has_valid_links(priority_queue, NULL, priority_queue->root)) {
310 0 : return CCC_FALSE;
311 : }
312 5303 : if (traversal_count(priority_queue->root) != priority_queue->count) {
313 0 : return CCC_FALSE;
314 : }
315 5303 : return CCC_TRUE;
316 5303 : }
317 :
318 : CCC_Order
319 5 : CCC_priority_queue_order(CCC_Priority_queue const *const priority_queue) {
320 5 : return priority_queue ? priority_queue->order : CCC_ORDER_ERROR;
321 : }
322 :
323 : /*========================= Private Interface ==========================*/
324 :
325 : void
326 3 : CCC_private_priority_queue_push(
327 : struct CCC_Priority_queue *const priority_queue,
328 : struct CCC_Priority_queue_node *const node
329 : ) {
330 3 : init_node(node);
331 3 : priority_queue->root = merge(priority_queue, priority_queue->root, node);
332 3 : ++priority_queue->count;
333 3 : }
334 :
335 : struct CCC_Priority_queue_node *
336 277 : CCC_private_priority_queue_node_in(
337 : struct CCC_Priority_queue const *const priority_queue,
338 : void const *const any_struct
339 : ) {
340 277 : return elem_in(priority_queue, any_struct);
341 : }
342 :
343 : void
344 74 : CCC_private_priority_queue_update_fixup(
345 : struct CCC_Priority_queue *const pq,
346 : struct CCC_Priority_queue_node *const node
347 : ) {
348 74 : return update_fixup(pq, node);
349 74 : }
350 :
351 : void
352 52 : CCC_private_priority_queue_increase_fixup(
353 : struct CCC_Priority_queue *const pq,
354 : struct CCC_Priority_queue_node *const node
355 : ) {
356 52 : return increase_fixup(pq, node);
357 52 : }
358 :
359 : void
360 148 : CCC_private_priority_queue_decrease_fixup(
361 : struct CCC_Priority_queue *const pq,
362 : struct CCC_Priority_queue_node *const node
363 : ) {
364 148 : return decrease_fixup(pq, node);
365 148 : }
366 :
367 : /*======================== Static Helpers ================================*/
368 :
369 : static void
370 149 : update_fixup(
371 : struct CCC_Priority_queue *const priority_queue,
372 : struct CCC_Priority_queue_node *const node
373 : ) {
374 : /* We could get lucky with a fast path but otherwise there is no way to
375 : know whether this is an increase or decrease and by how much. */
376 149 : if (node->parent
377 149 : && order(priority_queue, node, node->parent) == priority_queue->order) {
378 5 : cut_child(node);
379 5 : } else {
380 144 : priority_queue->root = delete_node(priority_queue, node);
381 144 : init_node(node);
382 : }
383 149 : priority_queue->root = merge(priority_queue, priority_queue->root, node);
384 149 : }
385 :
386 : static void
387 106 : increase_fixup(
388 : struct CCC_Priority_queue *const priority_queue,
389 : struct CCC_Priority_queue_node *const node
390 : ) {
391 106 : if (priority_queue->order == CCC_ORDER_GREATER
392 106 : && node == priority_queue->root) {
393 1 : return;
394 : }
395 105 : if (priority_queue->order == CCC_ORDER_GREATER) {
396 1 : cut_child(node);
397 1 : } else {
398 104 : priority_queue->root = delete_node(priority_queue, node);
399 104 : init_node(node);
400 : }
401 105 : priority_queue->root = merge(priority_queue, priority_queue->root, node);
402 211 : }
403 :
404 : static void
405 299 : decrease_fixup(
406 : struct CCC_Priority_queue *const priority_queue,
407 : struct CCC_Priority_queue_node *const node
408 : ) {
409 299 : if (priority_queue->order == CCC_ORDER_LESSER
410 299 : && node == priority_queue->root) {
411 1 : return;
412 : }
413 298 : if (priority_queue->order == CCC_ORDER_LESSER) {
414 297 : cut_child(node);
415 297 : } else {
416 1 : priority_queue->root = delete_node(priority_queue, node);
417 1 : init_node(node);
418 : }
419 298 : priority_queue->root = merge(priority_queue, priority_queue->root, node);
420 597 : }
421 :
422 : /** Cuts the child out of its current sibling list and redirects parent if
423 : this child is directly pointed to by parent. The child is then made into its
424 : own circular sibling list. The left child of this child, if one exists, is
425 : still pointed to and not modified by this function. */
426 : static void
427 1747 : cut_child(struct CCC_Priority_queue_node *const child) {
428 1747 : child->next->prev = child->prev;
429 1747 : child->prev->next = child->next;
430 1747 : if (child->parent && child == child->parent->child) {
431 : /* To preserve the shuffle down properties the prev child should
432 : become the new child as that is the next youngest node. */
433 1007 : child->parent->child = child->prev == child ? NULL : child->prev;
434 1007 : }
435 1747 : child->parent = NULL;
436 1747 : child->next = child->prev = child;
437 1747 : }
438 :
439 : static struct CCC_Priority_queue_node *
440 1572 : delete_node(
441 : struct CCC_Priority_queue *const priority_queue,
442 : struct CCC_Priority_queue_node *const root
443 : ) {
444 1572 : if (priority_queue->root == root) {
445 128 : return delete_min(priority_queue, root);
446 : }
447 1444 : cut_child(root);
448 1444 : return merge(
449 1444 : priority_queue, priority_queue->root, delete_min(priority_queue, root)
450 : );
451 1572 : }
452 :
453 : /* Uses Fredman et al. oldest to youngest pairing method mentioned on pg 124
454 : of the paper to pair nodes in one pass. Of all the variants for pairing given
455 : in the paper this one is the back-to-front variant and the only one for which
456 : the runtime analysis holds identically to the two-pass standard variant. A
457 : non-trivial example for min heap.
458 :
459 : ```
460 : < = next_sibling
461 : > = prev_sibling
462 :
463 : ┌<1>┐
464 : └/──┘
465 : ┌<9>─<1>─<9>─<7>─<8>┐
466 : └───────────────────┘
467 : |
468 : v
469 : ┌<9>─<1>─<7>─<8>┐
470 : └────────/──────┘
471 : ┌<9>┐
472 : └───┘
473 : |
474 : v
475 : ┌<9>─<1>─<7>┐
476 : └────────/──┘
477 : ┌<8>─<9>┐
478 : └───────┘
479 : |
480 : v
481 : ┌<1>─<7>┐
482 : └/────/─┘
483 : ┌<9>┐┌<8>─<9>┐
484 : └───┘└───────┘
485 : |
486 : v
487 : ┌<1>┐
488 : └/──┘
489 : ┌<7>─<9>┐
490 : └/──────┘
491 : ┌<8>─<9>┐
492 : └───────┘
493 : ```
494 :
495 : Delete min is the slowest operation offered by the priority queue and in
496 : part contributes to the amortized `o(log(N))` runtime of the decrease key
497 : operation. */
498 : static struct CCC_Priority_queue_node *
499 2276 : delete_min(
500 : struct CCC_Priority_queue *const priority_queue,
501 : struct CCC_Priority_queue_node *root
502 : ) {
503 2276 : if (!root->child) {
504 908 : return NULL;
505 : }
506 1368 : struct CCC_Priority_queue_node *const eldest = root->child->next;
507 1368 : struct CCC_Priority_queue_node *accumulator = root->child->next;
508 1368 : struct CCC_Priority_queue_node *cur = root->child->next->next;
509 4151 : while (cur != eldest && cur->next != eldest) {
510 2783 : struct CCC_Priority_queue_node *const next = cur->next;
511 2783 : struct CCC_Priority_queue_node *const next_cur = cur->next->next;
512 2783 : next->next = next->prev = NULL;
513 2783 : cur->next = cur->prev = NULL;
514 : /* Double merge ensures `O(log(N))` steps rather than O(N). */
515 2783 : accumulator = merge(
516 2783 : priority_queue, accumulator, merge(priority_queue, cur, next)
517 : );
518 2783 : cur = next_cur;
519 2783 : }
520 : /* This covers the odd or even case for number of pairings. */
521 : root
522 1368 : = cur == eldest ? accumulator : merge(priority_queue, accumulator, cur);
523 : /* The root is always alone in its circular list at the end of merges. */
524 1368 : root->next = root->prev = root;
525 1368 : root->parent = NULL;
526 1368 : return root;
527 2276 : }
528 :
529 : /** Merges two priority queues, making the winner by ordering the root and
530 : pushing the loser to the left child ring. Old should be the element that has
531 : been in the queue longer and new, newer. This algorithm will still work if this
532 : argument ordering is not respected and it does not change runtime, but it is how
533 : to comply with the strategy outlined in the Fredman et. al. paper. */
534 : static struct CCC_Priority_queue_node *
535 10918 : merge(
536 : struct CCC_Priority_queue *const priority_queue,
537 : struct CCC_Priority_queue_node *const old,
538 : struct CCC_Priority_queue_node *const new
539 : ) {
540 10918 : if (!old || !new || old == new) {
541 927 : return old ? old : new;
542 : }
543 9991 : if (order(priority_queue, new, old) == priority_queue->order) {
544 1680 : link_child(new, old);
545 1680 : return new;
546 : }
547 8311 : link_child(old, new);
548 8311 : return old;
549 10918 : }
550 :
551 : /* Oldest nodes shuffle down, new drops in to replace. This supports the
552 : ring representation from Fredman et al., pg 125, fig 14 where the left
553 : child's next pointer wraps to the last element in the list. The previous
554 : pointer is to support faster deletes and decrease key operations.
555 :
556 : < = next_sibling
557 : > = prev_sibling
558 :
559 : A A A
560 : ╱ ╱ ╱
561 : ┌─<B>─┐ ┌─<C>──<B>─┐ ┌─<D>──<C>──<B>─┐
562 : └─────┘ └──────────┘ └───────────────┘
563 :
564 : Pairing in the delete min phase would then start at B in this example and work
565 : towards D. That is the oldest to youngest order mentioned in the paper and
566 : helps set up the one-pass back-to-front variant mentioned in the paper allowing
567 : the same runtime guarantees as the two pass standard pairing heap. */
568 : static void
569 9991 : link_child(
570 : struct CCC_Priority_queue_node *const parent,
571 : struct CCC_Priority_queue_node *const child
572 : ) {
573 9991 : if (parent->child) {
574 8188 : child->next = parent->child->next;
575 8188 : child->prev = parent->child;
576 8188 : parent->child->next->prev = child;
577 8188 : parent->child->next = child;
578 8188 : } else {
579 1803 : child->next = child->prev = child;
580 : }
581 9991 : parent->child = child;
582 9991 : child->parent = parent;
583 9991 : }
584 :
585 : static inline CCC_Order
586 1160666 : order(
587 : struct CCC_Priority_queue const *const priority_queue,
588 : struct CCC_Priority_queue_node const *const left,
589 : struct CCC_Priority_queue_node const *const right
590 : ) {
591 4642664 : return priority_queue->comparator.compare((CCC_Comparator_arguments){
592 1160666 : .type_left = struct_base(priority_queue, left),
593 1160666 : .type_right = struct_base(priority_queue, right),
594 1160666 : .context = priority_queue->comparator.context,
595 : });
596 : }
597 :
598 : static inline void *
599 2327566 : struct_base(
600 : struct CCC_Priority_queue const *const priority_queue,
601 : struct CCC_Priority_queue_node const *const node
602 : ) {
603 2327566 : return ((char *)&(node->child)) - priority_queue->type_intruder_offset;
604 : }
605 :
606 : static inline struct CCC_Priority_queue_node *
607 3145 : elem_in(
608 : struct CCC_Priority_queue const *const priority_queue,
609 : void const *const any_struct
610 : ) {
611 3145 : return (struct CCC_Priority_queue_node
612 3145 : *)((char *)any_struct + priority_queue->type_intruder_offset);
613 : }
614 :
615 : static inline void
616 3132 : init_node(struct CCC_Priority_queue_node *const node) {
617 3132 : node->child = node->parent = NULL;
618 3132 : node->next = node->prev = node;
619 3132 : }
620 :
621 : static inline void
622 1927 : clear_node(struct CCC_Priority_queue_node *const node) {
623 1927 : node->child = node->next = node->prev = node->parent = NULL;
624 1927 : }
625 :
626 : /*======================== Validation ================================*/
627 :
628 : /* NOLINTBEGIN(*misc-no-recursion) */
629 :
630 : static size_t
631 1161109 : traversal_count(struct CCC_Priority_queue_node const *const root) {
632 1161109 : if (!root) {
633 1058379 : return 0;
634 : }
635 102730 : size_t count = 0;
636 102730 : struct CCC_Priority_queue_node const *cur = root;
637 102730 : do {
638 1155806 : count += 1 + traversal_count(cur->child);
639 1155806 : } while ((cur = cur->next) != root);
640 102730 : return count;
641 1161109 : }
642 :
643 : static CCC_Tribool
644 1161109 : has_valid_links(
645 : struct CCC_Priority_queue const *const priority_queue,
646 : struct CCC_Priority_queue_node const *const parent,
647 : struct CCC_Priority_queue_node const *const child
648 : ) {
649 1161109 : if (!child) {
650 1058379 : return CCC_TRUE;
651 : }
652 102730 : struct CCC_Priority_queue_node const *current = child;
653 102730 : CCC_Order const wrong_order = priority_queue->order == CCC_ORDER_LESSER
654 : ? CCC_ORDER_GREATER
655 : : CCC_ORDER_LESSER;
656 102730 : do {
657 : /* Reminder: Don't combine these if checks into one. Separating them
658 : makes it easier to find the problem when stepping through gdb. */
659 1155806 : if (!current) {
660 0 : return CCC_FALSE;
661 : }
662 1155806 : if (parent && child->parent != parent) {
663 0 : return CCC_FALSE;
664 : }
665 1155806 : if (parent && parent->child != child->parent->child) {
666 0 : return CCC_FALSE;
667 : }
668 1155806 : if (child->next->prev != child || child->prev->next != child) {
669 0 : return CCC_FALSE;
670 : }
671 1155806 : if (parent && (order(priority_queue, parent, current) == wrong_order)) {
672 0 : return CCC_FALSE;
673 : }
674 : /* RECURSE! */
675 1155806 : if (!has_valid_links(priority_queue, current, current->child)) {
676 0 : return CCC_FALSE;
677 : }
678 1155806 : } while ((current = current->next) != child);
679 102730 : return CCC_TRUE;
680 1161109 : }
681 :
682 : /* NOLINTEND(*misc-no-recursion) */
|
