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