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 : /** A standard flat priority queue binary heap implementation. This is
15 : 0-indexed so that there is no wasted space. The heap is fairly standard.
16 : However, due to CCC's use of callbacks for comparison it is valuable to limit
17 : the number of calls to this comparison callback with Bottom up heapify and
18 : heapsort implementations when possible.
19 :
20 : [1] The following paper was used to implement bottom-up heapsort.
21 : "BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on an average, QUICKSORT
22 : (if n is not very small)" by Ingo Wegener, Theoretical Computer Science 118
23 : (1993) 81-98. */
24 : /** C23 provided headers. */
25 : #include <limits.h>
26 : #include <stddef.h>
27 : #include <stdint.h>
28 :
29 : /** CCC provided headers. */
30 : #include "ccc/configuration.h" /* IWYU pragma: keep */
31 : #include "ccc/flat_buffer.h"
32 : #include "ccc/flat_priority_queue.h"
33 : #include "ccc/private/private_flat_priority_queue.h"
34 : #include "ccc/sort.h"
35 : #include "ccc/types.h"
36 :
37 : enum : size_t {
38 : START_CAP = 8,
39 : };
40 :
41 : /*===================== Prototypes ================================*/
42 :
43 : static size_t index_of(struct CCC_Flat_priority_queue const *, void const *);
44 : static CCC_Tribool
45 : wins(void const *, void const *, CCC_Order, CCC_Comparator const *);
46 : static size_t bubble_up(
47 : CCC_Flat_buffer const *, size_t, void *, CCC_Order, CCC_Comparator const *
48 : );
49 : static size_t
50 : update_fixup(struct CCC_Flat_priority_queue const *, void *, void *);
51 : static void
52 : heapify(CCC_Flat_buffer const *, void *, CCC_Order, CCC_Comparator const *);
53 : static size_t bottom_up_reheap(
54 : CCC_Flat_buffer const *,
55 : size_t,
56 : size_t,
57 : void *,
58 : CCC_Order,
59 : CCC_Comparator const *
60 : );
61 : static void
62 : destroy_each(struct CCC_Flat_priority_queue *, CCC_Destructor const *);
63 : static void swap(void *, size_t, void *, void *);
64 : static void *at(CCC_Flat_buffer const *buffer, size_t i);
65 : static unsigned count_leading_zeros_size_t(size_t n);
66 :
67 : /*===================== Interface ================================*/
68 :
69 : CCC_Result
70 3 : CCC_flat_priority_queue_copy_heapify(
71 : CCC_Flat_priority_queue *const priority_queue,
72 : CCC_Flat_buffer const *const buffer,
73 : void *const temp,
74 : CCC_Allocator const *const allocator
75 : ) {
76 3 : if (!priority_queue || !temp || !allocator) {
77 1 : return CCC_RESULT_ARGUMENT_ERROR;
78 : }
79 4 : CCC_Result const copy_result
80 2 : = CCC_flat_buffer_copy(&priority_queue->buffer, buffer, allocator);
81 2 : if (copy_result != CCC_RESULT_OK) {
82 1 : return copy_result;
83 : }
84 1 : heapify(
85 1 : &priority_queue->buffer,
86 1 : temp,
87 1 : priority_queue->order,
88 1 : &priority_queue->comparator
89 : );
90 1 : return CCC_RESULT_OK;
91 3 : }
92 :
93 : CCC_Flat_priority_queue
94 2 : CCC_flat_priority_queue_in_place_heapify(
95 : CCC_Flat_buffer *const buffer,
96 : void *const temp,
97 : CCC_Order const order,
98 : CCC_Comparator const *const comparator
99 : ) {
100 2 : if (!buffer || !temp || !comparator || !comparator->compare
101 2 : || (order != CCC_ORDER_GREATER && order != CCC_ORDER_LESSER)) {
102 1 : return (CCC_Flat_priority_queue){
103 : .order = CCC_ORDER_ERROR,
104 : };
105 : }
106 3 : CCC_Flat_priority_queue priority_queue = {
107 1 : .buffer = *buffer,
108 1 : .order = order,
109 1 : .comparator = *comparator,
110 : };
111 1 : heapify(
112 1 : &priority_queue.buffer,
113 1 : temp,
114 1 : priority_queue.order,
115 1 : &priority_queue.comparator
116 : );
117 1 : *buffer = (CCC_Flat_buffer){};
118 1 : return priority_queue;
119 2 : }
120 :
121 : void *
122 1223 : CCC_flat_priority_queue_push(
123 : CCC_Flat_priority_queue *const priority_queue,
124 : void const *const type,
125 : void *const temp,
126 : CCC_Allocator const *const allocator
127 : ) {
128 1223 : if (!priority_queue || !type || !temp || !allocator) {
129 1 : return NULL;
130 : }
131 2444 : void *const new
132 1222 : = CCC_flat_buffer_allocate_back(&priority_queue->buffer, allocator);
133 1222 : if (!new) {
134 2 : return NULL;
135 : }
136 1220 : if (new != type) {
137 1219 : (void)memcpy(new, type, priority_queue->buffer.sizeof_type);
138 1219 : }
139 1220 : assert(temp);
140 2440 : size_t const i = bubble_up(
141 1220 : &priority_queue->buffer,
142 1220 : priority_queue->buffer.count - 1,
143 1220 : temp,
144 1220 : priority_queue->order,
145 1220 : &priority_queue->comparator
146 : );
147 1220 : assert(i < priority_queue->buffer.count);
148 1220 : return at(&priority_queue->buffer, i);
149 1223 : }
150 :
151 : CCC_Result
152 925 : CCC_flat_priority_queue_pop(
153 : CCC_Flat_priority_queue *const priority_queue, void *const temp
154 : ) {
155 925 : if (!priority_queue || !temp || !priority_queue->buffer.count) {
156 1 : return CCC_RESULT_ARGUMENT_ERROR;
157 : }
158 924 : --priority_queue->buffer.count;
159 924 : if (!priority_queue->buffer.count) {
160 13 : return CCC_RESULT_OK;
161 : }
162 911 : swap(
163 911 : temp,
164 911 : priority_queue->buffer.sizeof_type,
165 911 : at(&priority_queue->buffer, 0),
166 911 : at(&priority_queue->buffer, priority_queue->buffer.count)
167 : );
168 911 : bottom_up_reheap(
169 911 : &priority_queue->buffer,
170 911 : priority_queue->buffer.count,
171 : 0,
172 911 : temp,
173 911 : priority_queue->order,
174 911 : &priority_queue->comparator
175 : );
176 911 : return CCC_RESULT_OK;
177 925 : }
178 :
179 : CCC_Result
180 530 : CCC_flat_priority_queue_erase(
181 : CCC_Flat_priority_queue *const priority_queue,
182 : void *const type,
183 : void *const temp
184 : ) {
185 530 : if (!priority_queue || !type || !temp || !priority_queue->buffer.count) {
186 1 : return CCC_RESULT_ARGUMENT_ERROR;
187 : }
188 529 : size_t const i = index_of(priority_queue, type);
189 529 : --priority_queue->buffer.count;
190 529 : if (i == priority_queue->buffer.count) {
191 13 : return CCC_RESULT_OK;
192 : }
193 516 : swap(
194 516 : temp,
195 516 : priority_queue->buffer.sizeof_type,
196 516 : at(&priority_queue->buffer, i),
197 516 : at(&priority_queue->buffer, priority_queue->buffer.count)
198 : );
199 1032 : CCC_Order const order_res
200 2064 : = priority_queue->comparator.compare((CCC_Comparator_arguments){
201 516 : .type_left = at(&priority_queue->buffer, i),
202 : .type_right
203 516 : = at(&priority_queue->buffer, priority_queue->buffer.count),
204 516 : .context = priority_queue->comparator.context,
205 : });
206 516 : if (order_res == priority_queue->order) {
207 147 : (void)bubble_up(
208 147 : &priority_queue->buffer,
209 147 : i,
210 147 : temp,
211 147 : priority_queue->order,
212 147 : &priority_queue->comparator
213 : );
214 516 : } else if (order_res != CCC_ORDER_EQUAL) {
215 367 : bottom_up_reheap(
216 367 : &priority_queue->buffer,
217 367 : priority_queue->buffer.count,
218 367 : i,
219 367 : temp,
220 367 : priority_queue->order,
221 367 : &priority_queue->comparator
222 : );
223 367 : }
224 516 : return CCC_RESULT_OK;
225 530 : }
226 :
227 : void *
228 701 : CCC_flat_priority_queue_update(
229 : CCC_Flat_priority_queue const *const priority_queue,
230 : void *const type,
231 : void *const temp,
232 : CCC_Modifier const *const modifier
233 : ) {
234 701 : if (!priority_queue || !type || !temp || !modifier || !modifier->modify
235 699 : || !priority_queue->buffer.count) {
236 3 : return NULL;
237 : }
238 2094 : modifier->modify((CCC_Arguments){
239 698 : .type = type,
240 698 : .context = modifier->context,
241 : });
242 698 : return at(
243 698 : &priority_queue->buffer, update_fixup(priority_queue, type, temp)
244 : );
245 701 : }
246 :
247 : /* There are no efficiency benefits in knowing an increase will occur. */
248 : void *
249 203 : CCC_flat_priority_queue_increase(
250 : CCC_Flat_priority_queue const *const priority_queue,
251 : void *const type,
252 : void *const temp,
253 : CCC_Modifier const *const modifier
254 : ) {
255 203 : return CCC_flat_priority_queue_update(priority_queue, type, temp, modifier);
256 : }
257 :
258 : /* There are no efficiency benefits in knowing an decrease will occur. */
259 : void *
260 252 : CCC_flat_priority_queue_decrease(
261 : CCC_Flat_priority_queue const *const priority_queue,
262 : void *const type,
263 : void *const temp,
264 : CCC_Modifier const *const modifier
265 : ) {
266 252 : return CCC_flat_priority_queue_update(priority_queue, type, temp, modifier);
267 : }
268 :
269 : void *
270 432 : CCC_flat_priority_queue_front(
271 : CCC_Flat_priority_queue const *const priority_queue
272 : ) {
273 432 : if (!priority_queue || !priority_queue->buffer.count) {
274 1 : return NULL;
275 : }
276 431 : return at(&priority_queue->buffer, 0);
277 432 : }
278 :
279 : CCC_Tribool
280 1250 : CCC_flat_priority_queue_is_empty(
281 : CCC_Flat_priority_queue const *const priority_queue
282 : ) {
283 1250 : if (!priority_queue) {
284 1 : return CCC_TRIBOOL_ERROR;
285 : }
286 1249 : return CCC_flat_buffer_is_empty(&priority_queue->buffer);
287 1250 : }
288 :
289 : CCC_Count
290 1008 : CCC_flat_priority_queue_count(
291 : CCC_Flat_priority_queue const *const priority_queue
292 : ) {
293 1008 : if (!priority_queue) {
294 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
295 : }
296 1007 : return CCC_flat_buffer_count(&priority_queue->buffer);
297 1008 : }
298 :
299 : CCC_Count
300 9 : CCC_flat_priority_queue_capacity(
301 : CCC_Flat_priority_queue const *const priority_queue
302 : ) {
303 9 : if (!priority_queue) {
304 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
305 : }
306 8 : return CCC_flat_buffer_capacity(&priority_queue->buffer);
307 9 : }
308 :
309 : void *
310 1 : CCC_flat_priority_queue_data(
311 : CCC_Flat_priority_queue const *const priority_queue
312 : ) {
313 1 : return priority_queue ? CCC_flat_buffer_begin(&priority_queue->buffer)
314 : : NULL;
315 : }
316 :
317 : CCC_Order
318 1 : CCC_flat_priority_queue_order(
319 : CCC_Flat_priority_queue const *const priority_queue
320 : ) {
321 1 : return priority_queue ? priority_queue->order : CCC_ORDER_ERROR;
322 : }
323 :
324 : CCC_Result
325 3 : CCC_flat_priority_queue_reserve(
326 : CCC_Flat_priority_queue *const priority_queue,
327 : size_t const to_add,
328 : CCC_Allocator const *const allocator
329 : ) {
330 3 : if (!priority_queue || !allocator) {
331 1 : return CCC_RESULT_ARGUMENT_ERROR;
332 : }
333 2 : return CCC_flat_buffer_reserve(&priority_queue->buffer, to_add, allocator);
334 3 : }
335 :
336 : CCC_Result
337 7 : CCC_flat_priority_queue_copy(
338 : CCC_Flat_priority_queue *const destination,
339 : CCC_Flat_priority_queue const *const source,
340 : CCC_Allocator const *const allocator
341 : ) {
342 7 : if (!destination || !source || source == destination || !allocator
343 7 : || (destination->buffer.capacity < source->buffer.capacity
344 7 : && !allocator->allocate)) {
345 2 : return CCC_RESULT_ARGUMENT_ERROR;
346 : }
347 5 : destination->order = source->order;
348 5 : destination->comparator = source->comparator;
349 5 : if (destination->buffer.capacity < source->buffer.capacity) {
350 4 : CCC_Result const r = CCC_flat_buffer_allocate(
351 2 : &destination->buffer, source->buffer.capacity, allocator
352 : );
353 2 : if (r != CCC_RESULT_OK) {
354 1 : return r;
355 : }
356 1 : destination->buffer.capacity = source->buffer.capacity;
357 2 : }
358 4 : destination->buffer.count = source->buffer.count;
359 : /* It is ok to only copy count elements because we know that all elements
360 : in a binary heap are contiguous from [0, C), where C is count. */
361 4 : if (source->buffer.count) {
362 3 : if (!source->buffer.data || !destination->buffer.data) {
363 1 : return CCC_RESULT_ARGUMENT_ERROR;
364 : }
365 2 : (void)memcpy(
366 2 : destination->buffer.data,
367 2 : source->buffer.data,
368 2 : source->buffer.count * source->buffer.sizeof_type
369 : );
370 2 : }
371 3 : return CCC_RESULT_OK;
372 7 : }
373 :
374 : CCC_Result
375 4 : CCC_flat_priority_queue_clear(
376 : CCC_Flat_priority_queue *const priority_queue,
377 : CCC_Destructor const *const destructor
378 : ) {
379 4 : if (!priority_queue || !destructor) {
380 3 : return CCC_RESULT_ARGUMENT_ERROR;
381 : }
382 1 : if (destructor->destroy) {
383 1 : destroy_each(priority_queue, destructor);
384 1 : }
385 1 : priority_queue->buffer.count = 0;
386 1 : return CCC_RESULT_OK;
387 4 : }
388 :
389 : CCC_Result
390 13 : CCC_flat_priority_queue_clear_and_free(
391 : CCC_Flat_priority_queue *const priority_queue,
392 : CCC_Destructor const *const destructor,
393 : CCC_Allocator const *const allocator
394 : ) {
395 13 : if (!priority_queue || !destructor || !allocator) {
396 2 : return CCC_RESULT_ARGUMENT_ERROR;
397 : }
398 11 : if (destructor->destroy) {
399 1 : destroy_each(priority_queue, destructor);
400 1 : }
401 11 : return CCC_flat_buffer_allocate(&priority_queue->buffer, 0, allocator);
402 13 : }
403 :
404 : CCC_Tribool
405 7076 : CCC_flat_priority_queue_validate(
406 : CCC_Flat_priority_queue const *const priority_queue
407 : ) {
408 7076 : if (!priority_queue) {
409 0 : return CCC_TRIBOOL_ERROR;
410 : }
411 7076 : size_t const count = priority_queue->buffer.count;
412 7076 : if (count <= 1) {
413 33 : return CCC_TRUE;
414 : }
415 992558 : for (size_t i = 0,
416 7043 : left = (i * 2) + 1,
417 7043 : right = (i * 2) + 2,
418 7043 : end = (count - 2) / 2;
419 971429 : i <= end;
420 964386 : ++i, left = (i * 2) + 1, right = (i * 2) + 2) {
421 964386 : void const *const this_pointer = at(&priority_queue->buffer, i);
422 : /* Putting the child in the comparison function first evaluates
423 : the child's three way comparison in relation to the parent. If
424 : the child beats the parent in total ordering (min/max) something
425 : has gone wrong. */
426 964386 : if (left < count
427 964386 : && wins(
428 964386 : at(&priority_queue->buffer, left),
429 964386 : this_pointer,
430 964386 : priority_queue->order,
431 964386 : &priority_queue->comparator
432 : )) {
433 0 : return CCC_FALSE;
434 : }
435 964386 : if (right < count
436 964386 : && wins(
437 960168 : at(&priority_queue->buffer, right),
438 960168 : this_pointer,
439 960168 : priority_queue->order,
440 960168 : &priority_queue->comparator
441 : )) {
442 0 : return CCC_FALSE;
443 : }
444 964386 : }
445 7043 : return CCC_TRUE;
446 7076 : }
447 :
448 : /*=================== Interface in sort.h =============================*/
449 :
450 : /** Bottom-Up-Heapsort adapted from "BOTTOM-UP-HEAPSORT, a new variant of
451 : HEAPSORT beating, on an average, QUICKSORT (if n is not very small)" by Ingo
452 : Wegener, Theoretical Computer Science 118 (1993) 81-98.
453 :
454 : This implementation is valuable to the C Container Collection because we rely
455 : on comparison callback functions over generic data. Therefore, we want to limit
456 : the number of calls to this callback function. A bottom up heapify
457 : significantly cuts down on comparisons by only comparing our element of interest
458 : to other elements starting at the leaves of the tree. Because most elements in
459 : a heap are leaves, or near leaves, the likelihood of finding a heap ordered
460 : position near the bottom is extremely likely. This means we only require a few
461 : comparisons on average. */
462 : CCC_Result
463 16 : CCC_sort_heapsort(
464 : CCC_Flat_buffer const *const buffer,
465 : void *const temp,
466 : CCC_Order order,
467 : CCC_Comparator const *const comparator
468 : ) {
469 16 : if (!buffer || !temp || !comparator || !comparator->compare
470 14 : || (order != CCC_ORDER_GREATER && order != CCC_ORDER_LESSER)) {
471 3 : return CCC_RESULT_ARGUMENT_ERROR;
472 : }
473 : /* For sorting the user expects the buffer to be in the order they specify.
474 : Just like they would expect their input order to the priority queue to
475 : place the least or greatest element closest to the root. However,
476 : heap sort fills a buffer from back to front, so flip it. */
477 13 : order == CCC_ORDER_GREATER ? (order = CCC_ORDER_LESSER)
478 8 : : (order = CCC_ORDER_GREATER);
479 13 : if (buffer->count > 1) {
480 11 : heapify(buffer, temp, order, comparator);
481 11 : size_t count = buffer->count;
482 11 : void *const root = at(buffer, 0);
483 432 : while (--count) {
484 421 : swap(temp, buffer->sizeof_type, root, at(buffer, count));
485 421 : bottom_up_reheap(buffer, count, 0, temp, order, comparator);
486 : }
487 11 : }
488 13 : return CCC_RESULT_OK;
489 16 : }
490 :
491 : /*=================== Private Interface =============================*/
492 :
493 : size_t
494 3496 : CCC_private_flat_priority_queue_bubble_up(
495 : struct CCC_Flat_priority_queue const *const priority_queue,
496 : void *const temp,
497 : size_t index
498 : ) {
499 3496 : return bubble_up(
500 3496 : &priority_queue->buffer,
501 3496 : index,
502 3496 : temp,
503 3496 : priority_queue->order,
504 3496 : &priority_queue->comparator
505 : );
506 : }
507 :
508 : void *
509 677 : CCC_private_flat_priority_queue_update_fixup(
510 : struct CCC_Flat_priority_queue const *const priority_queue,
511 : void *const type,
512 : void *const temp
513 : ) {
514 677 : return at(
515 677 : &priority_queue->buffer, update_fixup(priority_queue, type, temp)
516 : );
517 : }
518 :
519 : void
520 2 : CCC_private_flat_priority_queue_heap_order(
521 : struct CCC_Flat_priority_queue const *const priority_queue, void *const temp
522 : ) {
523 2 : heapify(
524 2 : &priority_queue->buffer,
525 2 : temp,
526 2 : priority_queue->order,
527 2 : &priority_queue->comparator
528 : );
529 2 : }
530 :
531 : /*==================== Static Helpers ===============================*/
532 :
533 : /* Orders the heap in O(N) time. Assumes n > 0 and n <= capacity. */
534 : static inline void
535 15 : heapify(
536 : CCC_Flat_buffer const *const buffer,
537 : void *temp,
538 : CCC_Order const order,
539 : CCC_Comparator const *const comparator
540 : ) {
541 15 : size_t i = buffer->count / 2;
542 384 : while (i--) {
543 369 : bottom_up_reheap(buffer, buffer->count, i, temp, order, comparator);
544 : }
545 15 : }
546 :
547 : /** The Bottom-Up-Reheap procedures from the research paper but all in one
548 : function. No need to break out into tiny functions because they are only used
549 : here and this makes the logic easy to track in one short function. Such an
550 : operation also replaces the traditional bubble-down of a standard heap. The
551 : bubble-up operation can still be helpful in certain cases and is therefore kept
552 : as a separate function.
553 :
554 : This function also returns the final resting position of the root element for
555 : this reheap operation. This is the location that the data previously at the root
556 : index has been swapped to such that heap order is maintained. This is helpful if
557 : the root element has been swapped to its special position on the special path
558 : and we want to report that back for operations such as update, increase, and
559 : decrease. */
560 : static size_t
561 3130 : bottom_up_reheap(
562 : CCC_Flat_buffer const *const buffer,
563 : size_t const count,
564 : size_t const root,
565 : void *const temp,
566 : CCC_Order const order,
567 : CCC_Comparator const *const comparator
568 : ) {
569 3130 : size_t leaf = root;
570 : {
571 : /* Procedure leaf-search(count, root) */
572 3130 : size_t left = (2 * leaf) + 1;
573 11341 : while (left + 1 < count) {
574 8211 : size_t const right = left + 1;
575 8211 : if (wins(at(buffer, left), at(buffer, right), order, comparator)) {
576 4009 : leaf = left;
577 4009 : } else {
578 4202 : leaf = right;
579 : }
580 8211 : left = (2 * leaf) + 1;
581 8211 : }
582 3130 : if (left < count) {
583 117 : leaf = left;
584 117 : }
585 3130 : }
586 : {
587 : /* Procedure bottom-up-search(root, leaf). This is where we hope to
588 : save on comparison callbacks in the best case. In the heapsort case,
589 : we are constantly swapping the last element to the root and then
590 : performing this operation so it is extremely likely that the root
591 : element will find another home close to the leaf layer. In an
592 : arbitrary bottom up reheap operation the likelihood is still good due
593 : to 1/2 of all nodes being leaves. */
594 3130 : void const *const node = at(buffer, root);
595 4036 : while (leaf > root && wins(node, at(buffer, leaf), order, comparator)) {
596 906 : leaf = (leaf - 1) / 2;
597 : }
598 3130 : }
599 : {
600 : /* Procedure interchange-1(root, leaf). We can reduce the calls to
601 : memcpy by avoiding the traditional swap with our temp position. We
602 : can figure out the ancestry of the special path leaf position we have
603 : found using bitwise checks. This cuts the calls to memcpy from `3 *
604 : height` to `height + 2` which is significant for data sizes that can
605 : vary significantly in this type of generic container. */
606 3130 : (void)memcpy(temp, at(buffer, root), buffer->sizeof_type);
607 6260 : size_t tree_levels = count_leading_zeros_size_t(root + 1)
608 3130 : - count_leading_zeros_size_t(leaf + 1);
609 10552 : while (tree_levels--) {
610 14844 : size_t const vacant_ancestor_index
611 7422 : = ((leaf + 1) >> (tree_levels + 1)) - 1;
612 14844 : size_t const occupied_ancestor_child_index
613 7422 : = ((leaf + 1) >> tree_levels) - 1;
614 7422 : memcpy(
615 7422 : at(buffer, vacant_ancestor_index),
616 7422 : at(buffer, occupied_ancestor_child_index),
617 7422 : buffer->sizeof_type
618 : );
619 7422 : }
620 3130 : (void)memcpy(at(buffer, leaf), temp, buffer->sizeof_type);
621 3130 : }
622 6260 : return leaf;
623 3130 : }
624 :
625 : /** Returns the sorted position of the index element that may be out of heap
626 : order. This element may move closer to the root index of 0. */
627 : static inline size_t
628 5170 : bubble_up(
629 : CCC_Flat_buffer const *const buffer,
630 : size_t index,
631 : void *const temp,
632 : CCC_Order const order,
633 : CCC_Comparator const *const comparator
634 : ) {
635 5170 : if (!index) {
636 27 : return 0;
637 : }
638 5143 : size_t node = index;
639 : /* We can make the same optimization in terms of comparisons and calls
640 : to memcpy that we make in the bottom-up reheap function. This is better
641 : than calling swap making the calls to memcpy equivalent to the height of
642 : the path plus the two additional calls to save the element and write it
643 : to its new home in the tree. */
644 10286 : void const *const bubble
645 5143 : = memcpy(temp, at(buffer, index), buffer->sizeof_type);
646 11041 : while (node) {
647 10957 : size_t const parent_index = (node - 1) / 2;
648 10957 : void const *const parent_node = at(buffer, parent_index);
649 10957 : if (!wins(bubble, parent_node, order, comparator)) {
650 5059 : break;
651 : }
652 5898 : (void)memcpy(at(buffer, node), parent_node, buffer->sizeof_type);
653 5898 : node = parent_index;
654 10957 : }
655 5143 : if (node != index) {
656 3112 : (void)memcpy(at(buffer, node), bubble, buffer->sizeof_type);
657 3112 : }
658 5143 : return node;
659 5170 : }
660 :
661 : /* Fixes the position of element e after its key value has been changed. */
662 : static size_t
663 1375 : update_fixup(
664 : struct CCC_Flat_priority_queue const *const priority_queue,
665 : void *const type,
666 : void *const temp
667 : ) {
668 1375 : size_t const index = index_of(priority_queue, type);
669 1375 : if (!index) {
670 2 : return bottom_up_reheap(
671 2 : &priority_queue->buffer,
672 2 : priority_queue->buffer.count,
673 : 0,
674 2 : temp,
675 2 : priority_queue->order,
676 2 : &priority_queue->comparator
677 : );
678 : }
679 2746 : CCC_Order const parent_order
680 5492 : = priority_queue->comparator.compare((CCC_Comparator_arguments){
681 1373 : .type_left = at(&priority_queue->buffer, index),
682 1373 : .type_right = at(&priority_queue->buffer, (index - 1) / 2),
683 1373 : .context = priority_queue->comparator.context,
684 : });
685 1373 : if (parent_order == priority_queue->order) {
686 307 : return bubble_up(
687 307 : &priority_queue->buffer,
688 307 : index,
689 307 : temp,
690 307 : priority_queue->order,
691 307 : &priority_queue->comparator
692 : );
693 : }
694 1066 : if (parent_order != CCC_ORDER_EQUAL) {
695 1060 : return bottom_up_reheap(
696 1060 : &priority_queue->buffer,
697 1060 : priority_queue->buffer.count,
698 1060 : index,
699 1060 : temp,
700 1060 : priority_queue->order,
701 1060 : &priority_queue->comparator
702 : );
703 : }
704 6 : return index;
705 1375 : }
706 :
707 : /** Returns true if the winner, the first argument, wins the comparison.
708 : Winning in a three-way comparison means satisfying the total order of the
709 : priority queue. So, the comparison resulting in elements being equal means this
710 : function returns false. If the winner is in the wrong order, thus losing the
711 : total order comparison, the function also returns false. The function only
712 : returns true when the three-way comparison of the winner to the loser results in
713 : the winner matching the heap order specified upon container initialization. In
714 : terms of the heap tree structure this means the winner should be closer to the
715 : root. */
716 : static inline CCC_Tribool
717 1946744 : wins(
718 : void const *const winner,
719 : void const *const loser,
720 : CCC_Order const order,
721 : CCC_Comparator const *const comparator
722 : ) {
723 9733720 : return comparator->compare((CCC_Comparator_arguments){
724 1946744 : .type_left = winner,
725 1946744 : .type_right = loser,
726 1946744 : .context = comparator->context,
727 : })
728 1946744 : == order;
729 : }
730 :
731 : /* Flat priority queue code that uses indices of the underlying Flat_buffer
732 : should always be within the Flat_buffer range. It should never exceed the
733 : current size and start at or after the Flat_buffer base. Only checked in
734 : debug. */
735 : static inline size_t
736 1904 : index_of(
737 : struct CCC_Flat_priority_queue const *const priority_queue,
738 : void const *const slot
739 : ) {
740 1904 : assert(slot >= priority_queue->buffer.data);
741 3808 : size_t const i
742 1904 : = (size_t)((char *)slot - (char *)priority_queue->buffer.data)
743 1904 : / priority_queue->buffer.sizeof_type;
744 1904 : assert(i < priority_queue->buffer.count);
745 3808 : return i;
746 1904 : }
747 :
748 : /** Swaps data in a and b according to buffer element size. Assumes a, b, and
749 : temp are non-null. */
750 : static inline void
751 1848 : swap(void *const temp, size_t const sizeof_type, void *const a, void *const b) {
752 1848 : assert(temp);
753 1848 : assert(a);
754 1848 : assert(b);
755 1848 : (void)memcpy(temp, a, sizeof_type);
756 1848 : (void)memcpy(a, b, sizeof_type);
757 1848 : (void)memcpy(b, temp, sizeof_type);
758 1848 : }
759 :
760 : /** Provides data at index. Assumes buffer is non-null and i is within
761 : capacity. */
762 : static inline void *
763 2967850 : at(CCC_Flat_buffer const *const buffer, size_t const i) {
764 2967850 : assert(buffer);
765 2967850 : assert(i < buffer->capacity);
766 2967850 : return (char *)buffer->data + (i * buffer->sizeof_type);
767 : }
768 :
769 : static inline void
770 2 : destroy_each(
771 : struct CCC_Flat_priority_queue *const priority_queue,
772 : CCC_Destructor const *const destructor
773 : ) {
774 2 : size_t const count = priority_queue->buffer.count;
775 34 : for (size_t i = 0; i < count; ++i) {
776 96 : destructor->destroy((CCC_Arguments){
777 32 : .type = at(&priority_queue->buffer, i),
778 32 : .context = destructor->context,
779 : });
780 32 : }
781 2 : }
782 :
783 : #if defined(__has_builtin) && __has_builtin(__builtin_clzl)
784 :
785 : static inline unsigned
786 6260 : count_leading_zeros_size_t(size_t const n) {
787 : static_assert(
788 : sizeof(size_t) == sizeof(unsigned long),
789 : "Ensure the available builtin works for the platform defined "
790 : "size of a size_t."
791 : );
792 6260 : return n ? (unsigned)__builtin_clzl(n) : sizeof(size_t) * CHAR_BIT;
793 : }
794 :
795 : #else /* !defined(__has_builtin) || !__has_builtin(__builtin_clzl) */
796 :
797 : static inline unsigned
798 : count_leading_zeros_size_t(size_t n) {
799 : enum : size_t {
800 : /** @internal Most significant bit of size_t for bit counting. */
801 : SIZE_T_MSB = (size_t)1 << ((sizeof(size_t) * CHAR_BIT) - 1),
802 : };
803 : if (!n) {
804 : return sizeof(size_t) * CHAR_BIT;
805 : }
806 : unsigned cnt = 0;
807 : for (; !(n & SIZE_T_MSB); ++cnt, n <<= 1U) {}
808 : return cnt;
809 : }
810 :
811 : #endif /* defined(__has_builtin) && __has_builtin(__builtin_clzl) */
|
