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 <limits.h>
16 : #include <stddef.h>
17 : #include <stdint.h>
18 :
19 : /** CCC provided headers. */
20 : #include "ccc/configuration.h"
21 : #include "ccc/flat_buffer.h"
22 : #include "ccc/flat_priority_queue.h"
23 : #include "ccc/private/private_flat_priority_queue.h"
24 : #include "ccc/sort.h"
25 : #include "ccc/types.h"
26 :
27 : enum : size_t {
28 : START_CAP = 8,
29 : };
30 :
31 : /*===================== Prototypes ================================*/
32 :
33 : static size_t index_of(struct CCC_Flat_priority_queue const *, void const *);
34 : static CCC_Tribool
35 : wins(void const *, void const *, CCC_Order, CCC_Comparator const *);
36 : static size_t bubble_up(
37 : CCC_Flat_buffer const *, size_t, void *, CCC_Order, CCC_Comparator const *
38 : );
39 : static size_t bubble_down(
40 : CCC_Flat_buffer const *,
41 : size_t,
42 : size_t,
43 : void *,
44 : CCC_Order,
45 : CCC_Comparator const *
46 : );
47 : static size_t
48 : update_fixup(struct CCC_Flat_priority_queue const *, void *, void *);
49 : static void
50 : heapify(CCC_Flat_buffer const *, void *, CCC_Order, CCC_Comparator const *);
51 : static void
52 : destroy_each(struct CCC_Flat_priority_queue *, CCC_Destructor const *);
53 : static void swap(CCC_Flat_buffer const *, void *, void *, void *);
54 : static void *at(CCC_Flat_buffer const *buffer, size_t i);
55 :
56 : /*===================== Interface ================================*/
57 :
58 : CCC_Result
59 3 : CCC_flat_priority_queue_copy_heapify(
60 : CCC_Flat_priority_queue *const priority_queue,
61 : CCC_Flat_buffer const *const buffer,
62 : void *const temp,
63 : CCC_Allocator const *const allocator
64 : ) {
65 3 : if (!priority_queue || !temp || !allocator) {
66 1 : return CCC_RESULT_ARGUMENT_ERROR;
67 : }
68 4 : CCC_Result const copy_result
69 2 : = CCC_flat_buffer_copy(&priority_queue->buffer, buffer, allocator);
70 2 : if (copy_result != CCC_RESULT_OK) {
71 1 : return copy_result;
72 : }
73 1 : heapify(
74 1 : &priority_queue->buffer,
75 1 : temp,
76 1 : priority_queue->order,
77 1 : &priority_queue->comparator
78 : );
79 1 : return CCC_RESULT_OK;
80 3 : }
81 :
82 : CCC_Flat_priority_queue
83 2 : CCC_flat_priority_queue_in_place_heapify(
84 : CCC_Flat_buffer *const buffer,
85 : void *const temp,
86 : CCC_Order const order,
87 : CCC_Comparator const *const comparator
88 : ) {
89 2 : if (!buffer || !temp || !comparator || !comparator->compare
90 2 : || (order != CCC_ORDER_GREATER && order != CCC_ORDER_LESSER)) {
91 1 : return (CCC_Flat_priority_queue){
92 : .order = CCC_ORDER_ERROR,
93 : };
94 : }
95 3 : CCC_Flat_priority_queue priority_queue = {
96 1 : .buffer = *buffer,
97 1 : .order = order,
98 1 : .comparator = *comparator,
99 : };
100 1 : heapify(
101 1 : &priority_queue.buffer,
102 1 : temp,
103 1 : priority_queue.order,
104 1 : &priority_queue.comparator
105 : );
106 1 : *buffer = (CCC_Flat_buffer){};
107 1 : return priority_queue;
108 2 : }
109 :
110 : void *
111 1223 : CCC_flat_priority_queue_push(
112 : CCC_Flat_priority_queue *const priority_queue,
113 : void const *const type,
114 : void *const temp,
115 : CCC_Allocator const *const allocator
116 : ) {
117 1223 : if (!priority_queue || !type || !temp || !allocator) {
118 1 : return NULL;
119 : }
120 2444 : void *const new
121 1222 : = CCC_flat_buffer_allocate_back(&priority_queue->buffer, allocator);
122 1222 : if (!new) {
123 2 : return NULL;
124 : }
125 1220 : if (new != type) {
126 1219 : (void)memcpy(new, type, priority_queue->buffer.sizeof_type);
127 1219 : }
128 1220 : assert(temp);
129 2440 : size_t const i = bubble_up(
130 1220 : &priority_queue->buffer,
131 1220 : priority_queue->buffer.count - 1,
132 1220 : temp,
133 1220 : priority_queue->order,
134 1220 : &priority_queue->comparator
135 : );
136 1220 : assert(i < priority_queue->buffer.count);
137 1220 : return at(&priority_queue->buffer, i);
138 1223 : }
139 :
140 : CCC_Result
141 925 : CCC_flat_priority_queue_pop(
142 : CCC_Flat_priority_queue *const priority_queue, void *const temp
143 : ) {
144 925 : if (!priority_queue || !temp || !priority_queue->buffer.count) {
145 1 : return CCC_RESULT_ARGUMENT_ERROR;
146 : }
147 924 : --priority_queue->buffer.count;
148 924 : if (!priority_queue->buffer.count) {
149 13 : return CCC_RESULT_OK;
150 : }
151 911 : swap(
152 911 : &priority_queue->buffer,
153 911 : temp,
154 911 : at(&priority_queue->buffer, 0),
155 911 : at(&priority_queue->buffer, priority_queue->buffer.count)
156 : );
157 911 : (void)bubble_down(
158 911 : &priority_queue->buffer,
159 : 0,
160 911 : priority_queue->buffer.count,
161 911 : temp,
162 911 : priority_queue->order,
163 911 : &priority_queue->comparator
164 : );
165 911 : return CCC_RESULT_OK;
166 925 : }
167 :
168 : CCC_Result
169 547 : CCC_flat_priority_queue_erase(
170 : CCC_Flat_priority_queue *const priority_queue,
171 : void *const type,
172 : void *const temp
173 : ) {
174 547 : if (!priority_queue || !type || !temp || !priority_queue->buffer.count) {
175 1 : return CCC_RESULT_ARGUMENT_ERROR;
176 : }
177 546 : size_t const i = index_of(priority_queue, type);
178 546 : --priority_queue->buffer.count;
179 546 : if (i == priority_queue->buffer.count) {
180 29 : return CCC_RESULT_OK;
181 : }
182 517 : swap(
183 517 : &priority_queue->buffer,
184 517 : temp,
185 517 : at(&priority_queue->buffer, i),
186 517 : at(&priority_queue->buffer, priority_queue->buffer.count)
187 : );
188 1034 : CCC_Order const order_res
189 2068 : = priority_queue->comparator.compare((CCC_Comparator_arguments){
190 517 : .type_left = at(&priority_queue->buffer, i),
191 : .type_right
192 517 : = at(&priority_queue->buffer, priority_queue->buffer.count),
193 517 : .context = priority_queue->comparator.context,
194 : });
195 517 : if (order_res == priority_queue->order) {
196 153 : (void)bubble_up(
197 153 : &priority_queue->buffer,
198 153 : i,
199 153 : temp,
200 153 : priority_queue->order,
201 153 : &priority_queue->comparator
202 : );
203 517 : } else if (order_res != CCC_ORDER_EQUAL) {
204 362 : (void)bubble_down(
205 362 : &priority_queue->buffer,
206 362 : i,
207 362 : priority_queue->buffer.count,
208 362 : temp,
209 362 : priority_queue->order,
210 362 : &priority_queue->comparator
211 : );
212 362 : }
213 517 : return CCC_RESULT_OK;
214 547 : }
215 :
216 : void *
217 718 : CCC_flat_priority_queue_update(
218 : CCC_Flat_priority_queue const *const priority_queue,
219 : void *const type,
220 : void *const temp,
221 : CCC_Modifier const *const modifier
222 : ) {
223 718 : if (!priority_queue || !type || !temp || !modifier || !modifier->modify
224 716 : || !priority_queue->buffer.count) {
225 3 : return NULL;
226 : }
227 2145 : modifier->modify((CCC_Arguments){
228 715 : .type = type,
229 715 : .context = modifier->context,
230 : });
231 715 : return at(
232 715 : &priority_queue->buffer, update_fixup(priority_queue, type, temp)
233 : );
234 718 : }
235 :
236 : /* There are no efficiency benefits in knowing an increase will occur. */
237 : void *
238 189 : CCC_flat_priority_queue_increase(
239 : CCC_Flat_priority_queue const *const priority_queue,
240 : void *const type,
241 : void *const temp,
242 : CCC_Modifier const *const modifier
243 : ) {
244 189 : return CCC_flat_priority_queue_update(priority_queue, type, temp, modifier);
245 : }
246 :
247 : /* There are no efficiency benefits in knowing an decrease will occur. */
248 : void *
249 263 : CCC_flat_priority_queue_decrease(
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 263 : return CCC_flat_priority_queue_update(priority_queue, type, temp, modifier);
256 : }
257 :
258 : void *
259 432 : CCC_flat_priority_queue_front(
260 : CCC_Flat_priority_queue const *const priority_queue
261 : ) {
262 432 : if (!priority_queue || !priority_queue->buffer.count) {
263 1 : return NULL;
264 : }
265 431 : return at(&priority_queue->buffer, 0);
266 432 : }
267 :
268 : CCC_Tribool
269 1250 : CCC_flat_priority_queue_is_empty(
270 : CCC_Flat_priority_queue const *const priority_queue
271 : ) {
272 1250 : if (!priority_queue) {
273 1 : return CCC_TRIBOOL_ERROR;
274 : }
275 1249 : return CCC_flat_buffer_is_empty(&priority_queue->buffer);
276 1250 : }
277 :
278 : CCC_Count
279 1008 : CCC_flat_priority_queue_count(
280 : CCC_Flat_priority_queue const *const priority_queue
281 : ) {
282 1008 : if (!priority_queue) {
283 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
284 : }
285 1007 : return CCC_flat_buffer_count(&priority_queue->buffer);
286 1008 : }
287 :
288 : CCC_Count
289 9 : CCC_flat_priority_queue_capacity(
290 : CCC_Flat_priority_queue const *const priority_queue
291 : ) {
292 9 : if (!priority_queue) {
293 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
294 : }
295 8 : return CCC_flat_buffer_capacity(&priority_queue->buffer);
296 9 : }
297 :
298 : void *
299 1 : CCC_flat_priority_queue_data(
300 : CCC_Flat_priority_queue const *const priority_queue
301 : ) {
302 1 : return priority_queue ? CCC_flat_buffer_begin(&priority_queue->buffer)
303 : : NULL;
304 : }
305 :
306 : CCC_Order
307 1 : CCC_flat_priority_queue_order(
308 : CCC_Flat_priority_queue const *const priority_queue
309 : ) {
310 1 : return priority_queue ? priority_queue->order : CCC_ORDER_ERROR;
311 : }
312 :
313 : CCC_Result
314 3 : CCC_flat_priority_queue_reserve(
315 : CCC_Flat_priority_queue *const priority_queue,
316 : size_t const to_add,
317 : CCC_Allocator const *const allocator
318 : ) {
319 3 : if (!priority_queue || !allocator) {
320 1 : return CCC_RESULT_ARGUMENT_ERROR;
321 : }
322 2 : return CCC_flat_buffer_reserve(&priority_queue->buffer, to_add, allocator);
323 3 : }
324 :
325 : CCC_Result
326 7 : CCC_flat_priority_queue_copy(
327 : CCC_Flat_priority_queue *const destination,
328 : CCC_Flat_priority_queue const *const source,
329 : CCC_Allocator const *const allocator
330 : ) {
331 7 : if (!destination || !source || source == destination || !allocator
332 7 : || (destination->buffer.capacity < source->buffer.capacity
333 7 : && !allocator->allocate)) {
334 2 : return CCC_RESULT_ARGUMENT_ERROR;
335 : }
336 5 : destination->order = source->order;
337 5 : destination->comparator = source->comparator;
338 5 : if (destination->buffer.capacity < source->buffer.capacity) {
339 4 : CCC_Result const r = CCC_flat_buffer_allocate(
340 2 : &destination->buffer, source->buffer.capacity, allocator
341 : );
342 2 : if (r != CCC_RESULT_OK) {
343 1 : return r;
344 : }
345 1 : destination->buffer.capacity = source->buffer.capacity;
346 2 : }
347 4 : destination->buffer.count = source->buffer.count;
348 : /* It is ok to only copy count elements because we know that all elements
349 : in a binary heap are contiguous from [0, C), where C is count. */
350 4 : if (source->buffer.count) {
351 3 : if (!source->buffer.data || !destination->buffer.data) {
352 1 : return CCC_RESULT_ARGUMENT_ERROR;
353 : }
354 2 : (void)memcpy(
355 2 : destination->buffer.data,
356 2 : source->buffer.data,
357 2 : source->buffer.count * source->buffer.sizeof_type
358 : );
359 2 : }
360 3 : return CCC_RESULT_OK;
361 7 : }
362 :
363 : CCC_Result
364 4 : CCC_flat_priority_queue_clear(
365 : CCC_Flat_priority_queue *const priority_queue,
366 : CCC_Destructor const *const destructor
367 : ) {
368 4 : if (!priority_queue || !destructor) {
369 3 : return CCC_RESULT_ARGUMENT_ERROR;
370 : }
371 1 : if (destructor->destroy) {
372 1 : destroy_each(priority_queue, destructor);
373 1 : }
374 1 : priority_queue->buffer.count = 0;
375 1 : return CCC_RESULT_OK;
376 4 : }
377 :
378 : CCC_Result
379 13 : CCC_flat_priority_queue_clear_and_free(
380 : CCC_Flat_priority_queue *const priority_queue,
381 : CCC_Destructor const *const destructor,
382 : CCC_Allocator const *const allocator
383 : ) {
384 13 : if (!priority_queue || !destructor || !allocator) {
385 2 : return CCC_RESULT_ARGUMENT_ERROR;
386 : }
387 11 : if (destructor->destroy) {
388 1 : destroy_each(priority_queue, destructor);
389 1 : }
390 11 : return CCC_flat_buffer_allocate(&priority_queue->buffer, 0, allocator);
391 13 : }
392 :
393 : CCC_Tribool
394 7148 : CCC_flat_priority_queue_validate(
395 : CCC_Flat_priority_queue const *const priority_queue
396 : ) {
397 7148 : if (!priority_queue) {
398 0 : return CCC_TRIBOOL_ERROR;
399 : }
400 7148 : size_t const count = priority_queue->buffer.count;
401 7148 : if (count <= 1) {
402 33 : return CCC_TRUE;
403 : }
404 1009669 : for (size_t i = 0,
405 7115 : left = (i * 2) + 1,
406 7115 : right = (i * 2) + 2,
407 7115 : end = (count - 2) / 2;
408 988324 : i <= end;
409 981209 : ++i, left = (i * 2) + 1, right = (i * 2) + 2) {
410 981209 : void const *const this_pointer = at(&priority_queue->buffer, i);
411 : /* Putting the child in the comparison function first evaluates
412 : the child's three way comparison in relation to the parent. If
413 : the child beats the parent in total ordering (min/max) something
414 : has gone wrong. */
415 981209 : if (left < count
416 981209 : && wins(
417 981209 : at(&priority_queue->buffer, left),
418 981209 : this_pointer,
419 981209 : priority_queue->order,
420 981209 : &priority_queue->comparator
421 : )) {
422 0 : return CCC_FALSE;
423 : }
424 981209 : if (right < count
425 981209 : && wins(
426 976927 : at(&priority_queue->buffer, right),
427 976927 : this_pointer,
428 976927 : priority_queue->order,
429 976927 : &priority_queue->comparator
430 : )) {
431 0 : return CCC_FALSE;
432 : }
433 981209 : }
434 7115 : return CCC_TRUE;
435 7148 : }
436 :
437 : /*=================== Interface in sort.h =============================*/
438 :
439 : CCC_Result
440 10 : CCC_sort_heapsort(
441 : CCC_Flat_buffer const *const buffer,
442 : void *const temp,
443 : CCC_Order order,
444 : CCC_Comparator const *const comparator
445 : ) {
446 10 : if (!buffer || !temp || !comparator || !comparator->compare
447 8 : || (order != CCC_ORDER_GREATER && order != CCC_ORDER_LESSER)) {
448 3 : return CCC_RESULT_ARGUMENT_ERROR;
449 : }
450 : /* For sorting the user expects the buffer to be in the order they specify.
451 : Just like they would expect their input order to the priority queue to
452 : place the least or greatest element closest to the root. However,
453 : heap sort fills a buffer from back to front, so flip it. */
454 7 : order == CCC_ORDER_GREATER ? (order = CCC_ORDER_LESSER)
455 6 : : (order = CCC_ORDER_GREATER);
456 7 : if (buffer->count > 1) {
457 7 : heapify(buffer, temp, order, comparator);
458 7 : size_t count = buffer->count;
459 7 : void *const root = at(buffer, 0);
460 400 : while (--count) {
461 393 : swap(buffer, temp, root, at(buffer, count));
462 393 : (void)bubble_down(buffer, 0, count, temp, order, comparator);
463 : }
464 7 : }
465 7 : return CCC_RESULT_OK;
466 10 : }
467 :
468 : /*=================== Private Interface =============================*/
469 :
470 : size_t
471 3496 : CCC_private_flat_priority_queue_bubble_up(
472 : struct CCC_Flat_priority_queue const *const priority_queue,
473 : void *const temp,
474 : size_t index
475 : ) {
476 3496 : return bubble_up(
477 3496 : &priority_queue->buffer,
478 3496 : index,
479 3496 : temp,
480 3496 : priority_queue->order,
481 3496 : &priority_queue->comparator
482 : );
483 : }
484 :
485 : void *
486 715 : CCC_private_flat_priority_queue_update_fixup(
487 : struct CCC_Flat_priority_queue const *const priority_queue,
488 : void *const type,
489 : void *const temp
490 : ) {
491 715 : return at(
492 715 : &priority_queue->buffer, update_fixup(priority_queue, type, temp)
493 : );
494 : }
495 :
496 : void
497 2 : CCC_private_flat_priority_queue_heap_order(
498 : struct CCC_Flat_priority_queue const *const priority_queue, void *const temp
499 : ) {
500 2 : heapify(
501 2 : &priority_queue->buffer,
502 2 : temp,
503 2 : priority_queue->order,
504 2 : &priority_queue->comparator
505 : );
506 2 : }
507 :
508 : /*==================== Static Helpers ===============================*/
509 :
510 : /* Orders the heap in O(N) time. Assumes n > 0 and n <= capacity. */
511 : static inline void
512 11 : heapify(
513 : CCC_Flat_buffer const *const buffer,
514 : void *temp,
515 : CCC_Order const order,
516 : CCC_Comparator const *const comparator
517 : ) {
518 11 : size_t i = ((buffer->count - 1) / 2) + 1;
519 365 : while (i--) {
520 354 : (void)bubble_down(buffer, i, buffer->count, temp, order, comparator);
521 : }
522 11 : }
523 :
524 : /* Fixes the position of element e after its key value has been changed. */
525 : static size_t
526 1430 : update_fixup(
527 : struct CCC_Flat_priority_queue const *const priority_queue,
528 : void *const type,
529 : void *const temp
530 : ) {
531 1430 : size_t const index = index_of(priority_queue, type);
532 1430 : if (!index) {
533 2 : return bubble_down(
534 2 : &priority_queue->buffer,
535 : 0,
536 2 : priority_queue->buffer.count,
537 2 : temp,
538 2 : priority_queue->order,
539 2 : &priority_queue->comparator
540 : );
541 : }
542 2856 : CCC_Order const parent_order
543 5712 : = priority_queue->comparator.compare((CCC_Comparator_arguments){
544 1428 : .type_left = at(&priority_queue->buffer, index),
545 1428 : .type_right = at(&priority_queue->buffer, (index - 1) / 2),
546 1428 : .context = priority_queue->comparator.context,
547 : });
548 1428 : if (parent_order == priority_queue->order) {
549 368 : return bubble_up(
550 368 : &priority_queue->buffer,
551 368 : index,
552 368 : temp,
553 368 : priority_queue->order,
554 368 : &priority_queue->comparator
555 : );
556 : }
557 1060 : if (parent_order != CCC_ORDER_EQUAL) {
558 1056 : return bubble_down(
559 1056 : &priority_queue->buffer,
560 1056 : index,
561 1056 : priority_queue->buffer.count,
562 1056 : temp,
563 1056 : priority_queue->order,
564 1056 : &priority_queue->comparator
565 : );
566 : }
567 4 : return index;
568 1430 : }
569 :
570 : /* Returns the sorted position of the element starting at position i. */
571 : static inline size_t
572 5237 : bubble_up(
573 : CCC_Flat_buffer const *const buffer,
574 : size_t index,
575 : void *const temp,
576 : CCC_Order const order,
577 : CCC_Comparator const *const comparator
578 : ) {
579 16479 : for (size_t parent = (index - 1) / 2; index;
580 6120 : index = parent, parent = (parent - 1) / 2) {
581 11242 : void *const parent_pointer = at(buffer, parent);
582 11242 : void *const this_pointer = at(buffer, index);
583 : /* Not winning here means we are in correct order or equal. */
584 11242 : if (!wins(this_pointer, parent_pointer, order, comparator)) {
585 5122 : return index;
586 : }
587 6120 : swap(buffer, temp, this_pointer, parent_pointer);
588 11242 : }
589 115 : return 0;
590 5237 : }
591 :
592 : /* Returns the sorted position of the element starting at position i. */
593 : static inline size_t
594 3078 : bubble_down(
595 : CCC_Flat_buffer const *const buffer,
596 : size_t index,
597 : size_t const count,
598 : void *const temp,
599 : CCC_Order const order,
600 : CCC_Comparator const *const comparator
601 : ) {
602 11080 : for (size_t next = 0, left = (index * 2) + 1, right = left + 1;
603 10485 : left < count;
604 7407 : index = next, left = (index * 2) + 1, right = left + 1) {
605 8002 : void const *const left_pointer = at(buffer, left);
606 8002 : next = left;
607 8002 : if (right < count) {
608 7910 : void const *const right_pointer = at(buffer, right);
609 7910 : if (wins(right_pointer, left_pointer, order, comparator)) {
610 4038 : next = right;
611 4038 : }
612 7910 : }
613 8002 : void *const next_pointer = at(buffer, next);
614 8002 : void *const this_pointer = at(buffer, index);
615 : /* If the child beats the parent we must swap. Equal is OK to break. */
616 8002 : if (!wins(next_pointer, this_pointer, order, comparator)) {
617 595 : return index;
618 : }
619 7407 : swap(buffer, temp, this_pointer, next_pointer);
620 8002 : }
621 2483 : return index;
622 3078 : }
623 :
624 : /* Returns true if the winner (the "left hand side") wins the comparison.
625 : Winning in a three-way comparison means satisfying the total order of the
626 : priority queue. So, there is no winner if the elements are equal and this
627 : function would return false. If the winner is in the wrong order, thus
628 : losing the total order comparison, the function also returns false. */
629 : static inline CCC_Tribool
630 1985290 : wins(
631 : void const *const winner,
632 : void const *const loser,
633 : CCC_Order const order,
634 : CCC_Comparator const *const comparator
635 : ) {
636 9926450 : return comparator->compare((CCC_Comparator_arguments){
637 1985290 : .type_left = winner,
638 1985290 : .type_right = loser,
639 1985290 : .context = comparator->context,
640 : })
641 1985290 : == order;
642 : }
643 :
644 : /* Flat priority queue code that uses indices of the underlying Flat_buffer
645 : should always be within the Flat_buffer range. It should never exceed the
646 : current size and start at or after the Flat_buffer base. Only checked in
647 : debug. */
648 : static inline size_t
649 1976 : index_of(
650 : struct CCC_Flat_priority_queue const *const priority_queue,
651 : void const *const slot
652 : ) {
653 1976 : assert(slot >= priority_queue->buffer.data);
654 3952 : size_t const i
655 1976 : = (size_t)((char *)slot - (char *)priority_queue->buffer.data)
656 1976 : / priority_queue->buffer.sizeof_type;
657 1976 : assert(i < priority_queue->buffer.count);
658 3952 : return i;
659 1976 : }
660 :
661 : /** Swaps data in a and b according to buffer element size. Assumes a, b, and
662 : temp are non-null. */
663 : static inline void
664 15348 : swap(
665 : CCC_Flat_buffer const *const buffer,
666 : void *const temp,
667 : void *const a,
668 : void *const b
669 : ) {
670 15348 : assert(temp);
671 15348 : assert(a);
672 15348 : assert(b);
673 15348 : (void)memcpy(temp, a, buffer->sizeof_type);
674 15348 : (void)memcpy(a, b, buffer->sizeof_type);
675 15348 : (void)memcpy(b, temp, buffer->sizeof_type);
676 15348 : }
677 :
678 : /** Provides data at index. Assumes buffer is non-null and i is within
679 : capacity. */
680 : static inline void *
681 3004004 : at(CCC_Flat_buffer const *const buffer, size_t const i) {
682 3004004 : assert(buffer);
683 3004004 : assert(i < buffer->capacity);
684 3004004 : return (char *)buffer->data + (i * buffer->sizeof_type);
685 : }
686 :
687 : static inline void
688 2 : destroy_each(
689 : struct CCC_Flat_priority_queue *const priority_queue,
690 : CCC_Destructor const *const destructor
691 : ) {
692 2 : size_t const count = priority_queue->buffer.count;
693 34 : for (size_t i = 0; i < count; ++i) {
694 96 : destructor->destroy((CCC_Arguments){
695 32 : .type = at(&priority_queue->buffer, i),
696 32 : .context = destructor->context,
697 : });
698 32 : }
699 2 : }
|
