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 1221 : CCC_priority_queue_extract(
130 : CCC_Priority_queue *const priority_queue,
131 : CCC_Priority_queue_node *const type_intruder
132 : ) {
133 1221 : if (!priority_queue || !type_intruder || !priority_queue->root
134 1220 : || !type_intruder->next || !type_intruder->prev) {
135 1 : return NULL;
136 : }
137 1220 : priority_queue->root = delete_node(priority_queue, type_intruder);
138 1220 : priority_queue->count--;
139 1220 : clear_node(type_intruder);
140 1220 : return struct_base(priority_queue, type_intruder);
141 1221 : }
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 168 : 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 164 : if (node->child) {
184 11 : struct CCC_Priority_queue_node *const child = node->child;
185 11 : struct CCC_Priority_queue_node *const node_end = node->next;
186 : /* Final element of e child list pick up child as head */
187 11 : node_end->prev = child;
188 : /* Now e picks up the last (wrapping) element of child list. */
189 11 : node->next = child->next;
190 : /* Child has a list so don't just set child's prev to e. */
191 11 : child->next->prev = node;
192 : /* Child list wrapping element is now end of e list. */
193 11 : child->next = node_end;
194 : /* Our traversal now jumps to start of list we spliced in. */
195 11 : node->child = NULL;
196 11 : node = child;
197 : continue;
198 11 : }
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 83 : 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 83 : if (!priority_queue || !type_intruder || !modifier || !modifier->modify
255 80 : || !type_intruder->next || !type_intruder->prev) {
256 3 : return NULL;
257 : }
258 240 : modifier->modify((CCC_Arguments){
259 80 : .type = struct_base(priority_queue, type_intruder),
260 80 : .context = modifier->context,
261 : });
262 80 : update_fixup(priority_queue, type_intruder);
263 80 : return struct_base(priority_queue, type_intruder);
264 83 : }
265 :
266 : /* Preferable to use this function if it is known the value is increasing.
267 : Much more efficient. */
268 : void *
269 57 : 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 57 : if (!priority_queue || !type_intruder || !modifier || !modifier->modify
275 54 : || !type_intruder->next || !type_intruder->prev) {
276 3 : return NULL;
277 : }
278 162 : modifier->modify((CCC_Arguments){
279 54 : .type = struct_base(priority_queue, type_intruder),
280 54 : .context = modifier->context,
281 : });
282 54 : increase_fixup(priority_queue, type_intruder);
283 54 : return struct_base(priority_queue, type_intruder);
284 57 : }
285 :
286 : /* Preferable to use this function if it is known the value is decreasing.
287 : Much more efficient. */
288 : void *
289 154 : 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 154 : if (!priority_queue || !type_intruder || !modifier || !modifier->modify
295 151 : || !type_intruder->next || !type_intruder->prev) {
296 3 : return NULL;
297 : }
298 453 : modifier->modify((CCC_Arguments){
299 151 : .type = struct_base(priority_queue, type_intruder),
300 151 : .context = modifier->context,
301 : });
302 151 : decrease_fixup(priority_queue, type_intruder);
303 151 : return struct_base(priority_queue, type_intruder);
304 154 : }
305 :
306 : CCC_Tribool
307 5300 : CCC_priority_queue_validate(CCC_Priority_queue const *const priority_queue) {
308 5300 : if (!priority_queue
309 5300 : || (priority_queue->root && priority_queue->root->parent)) {
310 0 : return CCC_FALSE;
311 : }
312 5300 : if (!has_valid_links(priority_queue, NULL, priority_queue->root)) {
313 0 : return CCC_FALSE;
314 : }
315 5300 : if (traversal_count(priority_queue->root) != priority_queue->count) {
316 0 : return CCC_FALSE;
317 : }
318 5300 : return CCC_TRUE;
319 5300 : }
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 272 : CCC_private_priority_queue_node_in(
340 : struct CCC_Priority_queue const *const priority_queue,
341 : void const *const any_struct
342 : ) {
343 272 : return elem_in(priority_queue, any_struct);
344 : }
345 :
346 : void
347 70 : CCC_private_priority_queue_update_fixup(
348 : struct CCC_Priority_queue *const pq,
349 : struct CCC_Priority_queue_node *const node
350 : ) {
351 70 : return update_fixup(pq, node);
352 70 : }
353 :
354 : void
355 51 : CCC_private_priority_queue_increase_fixup(
356 : struct CCC_Priority_queue *const pq,
357 : struct CCC_Priority_queue_node *const node
358 : ) {
359 51 : return increase_fixup(pq, node);
360 51 : }
361 :
362 : void
363 148 : CCC_private_priority_queue_decrease_fixup(
364 : struct CCC_Priority_queue *const pq,
365 : struct CCC_Priority_queue_node *const node
366 : ) {
367 148 : return decrease_fixup(pq, node);
368 148 : }
369 :
370 : /*======================== Static Helpers ================================*/
371 :
372 : static void
373 150 : 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 150 : if (node->parent
380 150 : && order(priority_queue, node, node->parent) == priority_queue->order) {
381 2 : cut_child(node);
382 2 : } else {
383 148 : priority_queue->root = delete_node(priority_queue, node);
384 148 : init_node(node);
385 : }
386 150 : priority_queue->root = merge(priority_queue, priority_queue->root, node);
387 150 : }
388 :
389 : static void
390 105 : increase_fixup(
391 : struct CCC_Priority_queue *const priority_queue,
392 : struct CCC_Priority_queue_node *const node
393 : ) {
394 105 : if (priority_queue->order == CCC_ORDER_GREATER
395 105 : && node == priority_queue->root) {
396 1 : return;
397 : }
398 104 : if (priority_queue->order == CCC_ORDER_GREATER) {
399 1 : cut_child(node);
400 1 : } else {
401 103 : priority_queue->root = delete_node(priority_queue, node);
402 103 : init_node(node);
403 : }
404 104 : priority_queue->root = merge(priority_queue, priority_queue->root, node);
405 209 : }
406 :
407 : static void
408 299 : decrease_fixup(
409 : struct CCC_Priority_queue *const priority_queue,
410 : struct CCC_Priority_queue_node *const node
411 : ) {
412 299 : if (priority_queue->order == CCC_ORDER_LESSER
413 299 : && node == priority_queue->root) {
414 1 : return;
415 : }
416 298 : if (priority_queue->order == CCC_ORDER_LESSER) {
417 297 : cut_child(node);
418 297 : } else {
419 1 : priority_queue->root = delete_node(priority_queue, node);
420 1 : init_node(node);
421 : }
422 298 : priority_queue->root = merge(priority_queue, priority_queue->root, node);
423 597 : }
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 1738 : cut_child(struct CCC_Priority_queue_node *const child) {
431 1738 : child->next->prev = child->prev;
432 1738 : child->prev->next = child->next;
433 1738 : 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 1041 : child->parent->child = child->prev == child ? NULL : child->prev;
437 1041 : }
438 1738 : child->parent = NULL;
439 1738 : child->next = child->prev = child;
440 1738 : }
441 :
442 : static struct CCC_Priority_queue_node *
443 1572 : delete_node(
444 : struct CCC_Priority_queue *const priority_queue,
445 : struct CCC_Priority_queue_node *const root
446 : ) {
447 1572 : if (priority_queue->root == root) {
448 134 : return delete_root(priority_queue, root);
449 : }
450 1438 : cut_child(root);
451 1438 : return merge(
452 1438 : priority_queue, priority_queue->root, delete_root(priority_queue, root)
453 : );
454 1572 : }
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 2276 : delete_root(
501 : struct CCC_Priority_queue *const priority_queue,
502 : struct CCC_Priority_queue_node *root
503 : ) {
504 2276 : if (!root->child) {
505 960 : return NULL;
506 : }
507 1316 : struct CCC_Priority_queue_node *const eldest = root->child->next;
508 1316 : struct CCC_Priority_queue_node *accumulator = root->child->next;
509 1316 : struct CCC_Priority_queue_node *cur = root->child->next->next;
510 4172 : while (cur != eldest && cur->next != eldest) {
511 2856 : struct CCC_Priority_queue_node *const next = cur->next;
512 2856 : struct CCC_Priority_queue_node *const next_cur = cur->next->next;
513 2856 : next->next = next->prev = NULL;
514 2856 : cur->next = cur->prev = NULL;
515 : /* Double merge ensures `O(log(N))` steps rather than O(N). */
516 2856 : accumulator = merge(
517 2856 : priority_queue, accumulator, merge(priority_queue, cur, next)
518 : );
519 2856 : cur = next_cur;
520 2856 : }
521 : /* This covers the odd or even case for number of pairings. */
522 : root
523 1316 : = cur == eldest ? accumulator : merge(priority_queue, accumulator, cur);
524 : /* The root is always alone in its circular list at the end of merges. */
525 1316 : root->next = root->prev = root;
526 1316 : root->parent = NULL;
527 1316 : return root;
528 2276 : }
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 11047 : 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 11047 : if (!old || !new || old == new) {
542 979 : return old ? old : new;
543 : }
544 10068 : if (order(priority_queue, new, old) == priority_queue->order) {
545 1803 : link_child(new, old);
546 1803 : return new;
547 : }
548 8265 : link_child(old, new);
549 8265 : return old;
550 11047 : }
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 min 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 10068 : link_child(
571 : struct CCC_Priority_queue_node *const parent,
572 : struct CCC_Priority_queue_node *const child
573 : ) {
574 10068 : if (parent->child) {
575 8233 : child->next = parent->child->next;
576 8233 : child->prev = parent->child;
577 8233 : parent->child->next->prev = child;
578 8233 : parent->child->next = child;
579 8233 : } else {
580 1835 : child->next = child->prev = child;
581 : }
582 10068 : parent->child = child;
583 10068 : child->parent = parent;
584 10068 : }
585 :
586 : static inline CCC_Order
587 1160666 : 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 4642664 : return priority_queue->comparator.compare((CCC_Comparator_arguments){
593 1160666 : .type_left = struct_base(priority_queue, left),
594 1160666 : .type_right = struct_base(priority_queue, right),
595 1160666 : .context = priority_queue->comparator.context,
596 : });
597 : }
598 :
599 : static inline void *
600 2327573 : struct_base(
601 : struct CCC_Priority_queue const *const priority_queue,
602 : struct CCC_Priority_queue_node const *const node
603 : ) {
604 2327573 : return ((char *)&(node->child)) - priority_queue->type_intruder_offset;
605 : }
606 :
607 : static inline struct CCC_Priority_queue_node *
608 3140 : elem_in(
609 : struct CCC_Priority_queue const *const priority_queue,
610 : void const *const any_struct
611 : ) {
612 3140 : return (struct CCC_Priority_queue_node
613 3140 : *)((char *)any_struct + priority_queue->type_intruder_offset);
614 : }
615 :
616 : static inline void
617 3135 : init_node(struct CCC_Priority_queue_node *const node) {
618 3135 : node->child = node->parent = NULL;
619 3135 : node->next = node->prev = node;
620 3135 : }
621 :
622 : static inline void
623 1924 : clear_node(struct CCC_Priority_queue_node *const node) {
624 1924 : node->child = node->next = node->prev = node->parent = NULL;
625 1924 : }
626 :
627 : /*======================== Validation ================================*/
628 :
629 : /* NOLINTBEGIN(*misc-no-recursion) */
630 :
631 : static size_t
632 1161025 : traversal_count(struct CCC_Priority_queue_node const *const root) {
633 1161025 : if (!root) {
634 884803 : return 0;
635 : }
636 276222 : size_t count = 0;
637 276222 : struct CCC_Priority_queue_node const *cur = root;
638 276222 : do {
639 1155725 : count += 1 + traversal_count(cur->child);
640 1155725 : } while ((cur = cur->next) != root);
641 276222 : return count;
642 1161025 : }
643 :
644 : static CCC_Tribool
645 1161025 : 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 1161025 : if (!child) {
651 884803 : return CCC_TRUE;
652 : }
653 276222 : struct CCC_Priority_queue_node const *current = child;
654 276222 : CCC_Order const wrong_order = priority_queue->order == CCC_ORDER_LESSER
655 : ? CCC_ORDER_GREATER
656 : : CCC_ORDER_LESSER;
657 276222 : 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 1155725 : if (!current) {
661 0 : return CCC_FALSE;
662 : }
663 1155725 : if (parent && child->parent != parent) {
664 0 : return CCC_FALSE;
665 : }
666 1155725 : if (parent && parent->child != child->parent->child) {
667 0 : return CCC_FALSE;
668 : }
669 1155725 : if (child->next->prev != child || child->prev->next != child) {
670 0 : return CCC_FALSE;
671 : }
672 1155725 : if (parent && (order(priority_queue, parent, current) == wrong_order)) {
673 0 : return CCC_FALSE;
674 : }
675 : /* RECURSE! */
676 1155725 : if (!has_valid_links(priority_queue, current, current->child)) {
677 0 : return CCC_FALSE;
678 : }
679 1155725 : } while ((current = current->next) != child);
680 276222 : return CCC_TRUE;
681 1161025 : }
682 :
683 : /* NOLINTEND(*misc-no-recursion) */
|
