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 <stdckdint.h>
17 : #include <stddef.h>
18 : #include <stdint.h>
19 :
20 : /** CCC provided headers. */
21 : #include "ccc/configuration.h" /* IWYU pragma: keep */
22 : #include "ccc/flat_buffer.h"
23 : #include "ccc/flat_double_ended_queue.h"
24 : #include "ccc/private/private_flat_double_ended_queue.h"
25 : #include "ccc/types.h"
26 : #include "source/compiler_utilities.h"
27 :
28 : enum : size_t {
29 : START_CAPACITY = 8,
30 : };
31 :
32 : /*========================== Prototypes ===============================*/
33 :
34 : static CCC_Result maybe_resize(
35 : struct CCC_Flat_double_ended_queue *, size_t, CCC_Allocator const *
36 : );
37 : static size_t
38 : index_of(struct CCC_Flat_double_ended_queue const *, void const *);
39 : static void *wrapping_at(struct CCC_Flat_double_ended_queue const *, size_t);
40 : static void *raw_at(CCC_Flat_buffer const *, size_t);
41 : static size_t increment(struct CCC_Flat_double_ended_queue const *, size_t);
42 : static size_t decrement(struct CCC_Flat_double_ended_queue const *, size_t);
43 : static size_t
44 : distance(struct CCC_Flat_double_ended_queue const *, size_t, size_t);
45 : static size_t
46 : reverse_distance(struct CCC_Flat_double_ended_queue const *, size_t, size_t);
47 : static void *push_front_range(
48 : struct CCC_Flat_double_ended_queue *,
49 : CCC_Flat_buffer const *,
50 : CCC_Allocator const *
51 : );
52 : static void *push_back_range(
53 : struct CCC_Flat_double_ended_queue *,
54 : CCC_Flat_buffer const *,
55 : CCC_Allocator const *
56 : );
57 : static size_t back_free_slot(struct CCC_Flat_double_ended_queue const *);
58 : static size_t front_free_slot(size_t, size_t);
59 : static size_t last_index(struct CCC_Flat_double_ended_queue const *);
60 : static void *push_range(
61 : struct CCC_Flat_double_ended_queue *,
62 : void const *,
63 : CCC_Flat_buffer const *,
64 : CCC_Allocator const *
65 : );
66 : static void *
67 : allocate_front(struct CCC_Flat_double_ended_queue *, CCC_Allocator const *);
68 : static void *
69 : allocate_back(struct CCC_Flat_double_ended_queue *, CCC_Allocator const *);
70 : static void
71 : destroy_all(struct CCC_Flat_double_ended_queue const *, CCC_Destructor const *);
72 :
73 : /*========================== Interface ===============================*/
74 :
75 : void *
76 104 : CCC_flat_double_ended_queue_push_back(
77 : CCC_Flat_double_ended_queue *const queue,
78 : void const *const type,
79 : CCC_Allocator const *const allocator
80 : ) {
81 104 : if (!queue || !type || !allocator) {
82 3 : return NULL;
83 : }
84 101 : void *const slot = allocate_back(queue, allocator);
85 101 : if (!slot || slot == type) {
86 2 : return NULL;
87 : }
88 99 : return memcpy(slot, type, queue->buffer.sizeof_type);
89 104 : }
90 :
91 : void *
92 99 : CCC_flat_double_ended_queue_push_front(
93 : CCC_Flat_double_ended_queue *const queue,
94 : void const *const type,
95 : CCC_Allocator const *const allocator
96 : ) {
97 99 : if (!queue || !type || !allocator) {
98 3 : return NULL;
99 : }
100 96 : void *const slot = allocate_front(queue, allocator);
101 96 : if (slot && slot != type) {
102 96 : (void)memcpy(slot, type, queue->buffer.sizeof_type);
103 96 : }
104 96 : return slot;
105 99 : }
106 :
107 : CCC_Result
108 14 : CCC_flat_double_ended_queue_push_front_range(
109 : CCC_Flat_double_ended_queue *const queue,
110 : CCC_Flat_buffer const *const range,
111 : CCC_Allocator const *const allocator
112 : ) {
113 14 : if (!queue || !range || range->sizeof_type != queue->buffer.sizeof_type
114 12 : || !allocator) {
115 3 : return CCC_RESULT_ARGUMENT_ERROR;
116 : }
117 11 : return push_front_range(queue, range, allocator)
118 : ? CCC_RESULT_OK
119 : : CCC_RESULT_ALLOCATOR_ERROR;
120 14 : }
121 :
122 : CCC_Result
123 32 : CCC_flat_double_ended_queue_push_back_range(
124 : CCC_Flat_double_ended_queue *const queue,
125 : CCC_Flat_buffer const *const range,
126 : CCC_Allocator const *const allocator
127 : ) {
128 32 : if (!queue || !range || range->sizeof_type != queue->buffer.sizeof_type
129 30 : || !allocator) {
130 3 : return CCC_RESULT_ARGUMENT_ERROR;
131 : }
132 29 : return push_back_range(queue, range, allocator)
133 : ? CCC_RESULT_OK
134 : : CCC_RESULT_ALLOCATOR_ERROR;
135 32 : }
136 :
137 : void *
138 31 : CCC_flat_double_ended_queue_insert_range(
139 : CCC_Flat_double_ended_queue *const queue,
140 : void *position,
141 : CCC_Flat_buffer const *const range,
142 : CCC_Allocator const *const allocator
143 : ) {
144 31 : if (!queue || !range || range->sizeof_type != queue->buffer.sizeof_type
145 29 : || !allocator) {
146 3 : return NULL;
147 : }
148 28 : if (!range->count) {
149 1 : return position;
150 : }
151 27 : if (position == CCC_flat_double_ended_queue_begin(queue)) {
152 6 : return push_front_range(queue, range, allocator);
153 : }
154 21 : if (position == CCC_flat_double_ended_queue_end(queue)) {
155 6 : return push_back_range(queue, range, allocator);
156 : }
157 15 : return push_range(queue, position, range, allocator);
158 31 : }
159 :
160 : CCC_Result
161 171 : CCC_flat_double_ended_queue_pop_front(
162 : CCC_Flat_double_ended_queue *const queue
163 : ) {
164 171 : if (!queue || !queue->buffer.count) {
165 1 : return CCC_RESULT_ARGUMENT_ERROR;
166 : }
167 170 : queue->front = increment(queue, queue->front);
168 170 : --queue->buffer.count;
169 170 : return CCC_RESULT_OK;
170 171 : }
171 :
172 : CCC_Result
173 110 : CCC_flat_double_ended_queue_pop_back(CCC_Flat_double_ended_queue *const queue) {
174 110 : if (!queue || !queue->buffer.count) {
175 1 : return CCC_RESULT_ARGUMENT_ERROR;
176 : }
177 109 : --queue->buffer.count;
178 109 : return CCC_RESULT_OK;
179 110 : }
180 :
181 : void *
182 171 : CCC_flat_double_ended_queue_front(
183 : CCC_Flat_double_ended_queue const *const queue
184 : ) {
185 171 : if (!queue || !queue->buffer.count) {
186 1 : return NULL;
187 : }
188 170 : return raw_at(&queue->buffer, queue->front);
189 171 : }
190 :
191 : void *
192 106 : CCC_flat_double_ended_queue_back(
193 : CCC_Flat_double_ended_queue const *const queue
194 : ) {
195 106 : if (!queue || !queue->buffer.count) {
196 1 : return NULL;
197 : }
198 105 : return raw_at(&queue->buffer, last_index(queue));
199 106 : }
200 :
201 : CCC_Tribool
202 343 : CCC_flat_double_ended_queue_is_empty(
203 : CCC_Flat_double_ended_queue const *const queue
204 : ) {
205 343 : if (!queue) {
206 1 : return CCC_TRIBOOL_ERROR;
207 : }
208 342 : return !queue->buffer.count;
209 343 : }
210 :
211 : CCC_Count
212 607 : CCC_flat_double_ended_queue_count(
213 : CCC_Flat_double_ended_queue const *const queue
214 : ) {
215 607 : if (!queue) {
216 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
217 : }
218 606 : return (CCC_Count){.count = queue->buffer.count};
219 607 : }
220 :
221 : CCC_Count
222 13 : CCC_flat_double_ended_queue_capacity(
223 : CCC_Flat_double_ended_queue const *const queue
224 : ) {
225 13 : if (!queue) {
226 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
227 : }
228 12 : return (CCC_Count){.count = queue->buffer.capacity};
229 13 : }
230 :
231 : void *
232 17 : CCC_flat_double_ended_queue_at(
233 : CCC_Flat_double_ended_queue const *const queue, size_t const i
234 : ) {
235 17 : if (!queue || i >= queue->buffer.capacity) {
236 2 : return NULL;
237 : }
238 15 : return wrapping_at(queue, i);
239 17 : }
240 :
241 : void *
242 128 : CCC_flat_double_ended_queue_begin(
243 : CCC_Flat_double_ended_queue const *const queue
244 : ) {
245 128 : if (!queue || !queue->buffer.count) {
246 2 : return NULL;
247 : }
248 126 : return raw_at(&queue->buffer, queue->front);
249 128 : }
250 :
251 : void *
252 98 : CCC_flat_double_ended_queue_reverse_begin(
253 : CCC_Flat_double_ended_queue const *const queue
254 : ) {
255 98 : if (!queue || !queue->buffer.count) {
256 1 : return NULL;
257 : }
258 97 : return raw_at(&queue->buffer, last_index(queue));
259 98 : }
260 :
261 : void *
262 515 : CCC_flat_double_ended_queue_next(
263 : CCC_Flat_double_ended_queue const *const queue,
264 : void const *const iterator_pointer
265 : ) {
266 515 : if (!queue || !iterator_pointer) {
267 2 : return NULL;
268 : }
269 513 : size_t const next_i = increment(queue, index_of(queue, iterator_pointer));
270 513 : if (next_i == queue->front
271 513 : || distance(queue, next_i, queue->front) >= queue->buffer.count) {
272 99 : return NULL;
273 : }
274 414 : return raw_at(&queue->buffer, next_i);
275 515 : }
276 :
277 : void *
278 501 : CCC_flat_double_ended_queue_reverse_next(
279 : CCC_Flat_double_ended_queue const *const queue,
280 : void const *const iterator_pointer
281 : ) {
282 501 : if (!queue || !iterator_pointer) {
283 2 : return NULL;
284 : }
285 499 : size_t const cur_i = index_of(queue, iterator_pointer);
286 499 : size_t const next_i = decrement(queue, cur_i);
287 499 : size_t const reverse_begin = last_index(queue);
288 499 : if (next_i == reverse_begin
289 499 : || reverse_distance(queue, next_i, reverse_begin)
290 449 : >= queue->buffer.count) {
291 97 : return NULL;
292 : }
293 402 : return raw_at(&queue->buffer, next_i);
294 501 : }
295 :
296 : void *
297 641 : CCC_flat_double_ended_queue_end(CCC_Flat_double_ended_queue const *const) {
298 641 : return NULL;
299 : }
300 :
301 : void *
302 597 : CCC_flat_double_ended_queue_reverse_end(
303 : CCC_Flat_double_ended_queue const *const
304 : ) {
305 597 : return NULL;
306 : }
307 :
308 : void *
309 1 : CCC_flat_double_ended_queue_data(
310 : CCC_Flat_double_ended_queue const *const queue
311 : ) {
312 1 : return queue ? CCC_flat_buffer_begin(&queue->buffer) : NULL;
313 : }
314 :
315 : CCC_Result
316 8 : CCC_flat_double_ended_queue_copy(
317 : CCC_Flat_double_ended_queue *const destination,
318 : CCC_Flat_double_ended_queue const *const source,
319 : CCC_Allocator const *const allocator
320 : ) {
321 8 : if (!destination || !source || !allocator || source == destination
322 7 : || (destination->buffer.capacity < source->buffer.capacity
323 7 : && !allocator->allocate)) {
324 2 : return CCC_RESULT_ARGUMENT_ERROR;
325 : }
326 : /* Copying from an empty source is odd but supported. */
327 6 : if (!source->buffer.capacity) {
328 1 : destination->front = destination->buffer.count = 0;
329 1 : return CCC_RESULT_OK;
330 : }
331 5 : if (destination->buffer.capacity < source->buffer.capacity) {
332 6 : CCC_Result resize_res = CCC_flat_buffer_allocate(
333 3 : &destination->buffer, source->buffer.capacity, allocator
334 : );
335 3 : if (resize_res != CCC_RESULT_OK) {
336 1 : return resize_res;
337 : }
338 2 : destination->buffer.capacity = source->buffer.capacity;
339 3 : }
340 4 : if (!destination->buffer.data || !source->buffer.data) {
341 1 : return CCC_RESULT_ARGUMENT_ERROR;
342 : }
343 3 : destination->buffer.count = source->buffer.count;
344 3 : if (destination->buffer.capacity > source->buffer.capacity) {
345 6 : size_t const first_chunk = CCC_min(
346 4 : source->buffer.count, source->buffer.capacity - source->front
347 : );
348 2 : (void)memcpy(
349 2 : destination->buffer.data,
350 2 : raw_at(&source->buffer, source->front),
351 2 : source->buffer.sizeof_type * first_chunk
352 : );
353 2 : if (first_chunk < source->buffer.count) {
354 2 : (void)memcpy(
355 1 : (char *)destination->buffer.data
356 1 : + (source->buffer.sizeof_type * first_chunk),
357 1 : source->buffer.data,
358 1 : source->buffer.sizeof_type
359 1 : * (source->buffer.count - first_chunk)
360 : );
361 1 : }
362 2 : destination->front = 0;
363 2 : return CCC_RESULT_OK;
364 2 : }
365 1 : destination->front = source->front;
366 1 : (void)memcpy(
367 1 : destination->buffer.data,
368 1 : source->buffer.data,
369 1 : source->buffer.capacity * source->buffer.sizeof_type
370 : );
371 1 : return CCC_RESULT_OK;
372 8 : }
373 :
374 : CCC_Result
375 3 : CCC_flat_double_ended_queue_reserve(
376 : CCC_Flat_double_ended_queue *const queue,
377 : size_t const to_add,
378 : CCC_Allocator const *const allocator
379 : ) {
380 3 : if (!queue || !allocator || !allocator->allocate || !to_add) {
381 2 : return CCC_RESULT_ARGUMENT_ERROR;
382 : }
383 1 : return maybe_resize(queue, to_add, allocator);
384 3 : }
385 :
386 : CCC_Result
387 4 : CCC_flat_double_ended_queue_clear(
388 : CCC_Flat_double_ended_queue *const queue,
389 : CCC_Destructor const *const destructor
390 : ) {
391 4 : if (!queue || !destructor) {
392 2 : return CCC_RESULT_ARGUMENT_ERROR;
393 : }
394 2 : if (!destructor->destroy || !queue->buffer.count) {
395 1 : queue->front = 0;
396 1 : queue->buffer.count = 0;
397 1 : return CCC_RESULT_OK;
398 : }
399 1 : destroy_all(queue, destructor);
400 1 : return CCC_RESULT_OK;
401 4 : }
402 :
403 : CCC_Result
404 15 : CCC_flat_double_ended_queue_clear_and_free(
405 : CCC_Flat_double_ended_queue *const queue,
406 : CCC_Destructor const *const destructor,
407 : CCC_Allocator const *const allocator
408 : ) {
409 15 : if (!queue || !destructor || !allocator || !allocator->allocate) {
410 5 : return CCC_RESULT_ARGUMENT_ERROR;
411 : }
412 10 : if (!destructor->destroy || !queue->buffer.count) {
413 9 : queue->buffer.count = queue->front = 0;
414 9 : return CCC_flat_buffer_allocate(&queue->buffer, 0, allocator);
415 : }
416 1 : destroy_all(queue, destructor);
417 1 : CCC_Result const r = CCC_flat_buffer_allocate(&queue->buffer, 0, allocator);
418 1 : if (r == CCC_RESULT_OK) {
419 1 : queue->buffer.count = queue->front = 0;
420 1 : }
421 1 : return r;
422 15 : }
423 :
424 : CCC_Tribool
425 43 : CCC_flat_double_ended_queue_validate(
426 : CCC_Flat_double_ended_queue const *const queue
427 : ) {
428 43 : if (!queue) {
429 0 : return CCC_TRIBOOL_ERROR;
430 : }
431 43 : if (CCC_flat_double_ended_queue_is_empty(queue)) {
432 3 : return CCC_TRUE;
433 : }
434 40 : void *iterator = CCC_flat_double_ended_queue_begin(queue);
435 40 : if (CCC_flat_buffer_index(&queue->buffer, iterator).count != queue->front) {
436 0 : return CCC_FALSE;
437 : }
438 40 : size_t size = 0;
439 194 : for (; iterator != CCC_flat_double_ended_queue_end(queue);
440 154 : iterator = CCC_flat_double_ended_queue_next(queue, iterator), ++size) {
441 154 : if (size >= CCC_flat_double_ended_queue_count(queue).count) {
442 0 : return CCC_FALSE;
443 : }
444 154 : }
445 40 : if (size != CCC_flat_double_ended_queue_count(queue).count) {
446 0 : return CCC_FALSE;
447 : }
448 40 : size = 0;
449 40 : iterator = CCC_flat_double_ended_queue_reverse_begin(queue);
450 80 : if (CCC_flat_buffer_index(&queue->buffer, iterator).count
451 40 : != last_index(queue)) {
452 0 : return CCC_FALSE;
453 : }
454 194 : for (; iterator != CCC_flat_double_ended_queue_reverse_end(queue);
455 154 : iterator = CCC_flat_double_ended_queue_reverse_next(queue, iterator),
456 154 : ++size) {
457 154 : if (size >= CCC_flat_double_ended_queue_count(queue).count) {
458 0 : return CCC_FALSE;
459 : }
460 154 : }
461 40 : return size == CCC_flat_double_ended_queue_count(queue).count;
462 43 : }
463 :
464 : /*====================== Private Interface ==============================*/
465 :
466 : void *
467 3 : CCC_private_flat_double_ended_queue_allocate_back(
468 : struct CCC_Flat_double_ended_queue *const queue,
469 : CCC_Allocator const *const allocator
470 : ) {
471 3 : return allocate_back(queue, allocator);
472 : }
473 :
474 : void *
475 1 : CCC_private_flat_double_ended_queue_allocate_front(
476 : struct CCC_Flat_double_ended_queue *const queue,
477 : CCC_Allocator const *const allocator
478 : ) {
479 1 : return allocate_front(queue, allocator);
480 : }
481 :
482 : /*====================== Static Helpers ==============================*/
483 :
484 : static void *
485 97 : allocate_front(
486 : struct CCC_Flat_double_ended_queue *const queue,
487 : CCC_Allocator const *const allocator
488 : ) {
489 97 : CCC_Tribool const full = maybe_resize(queue, 1, allocator) != CCC_RESULT_OK;
490 97 : if ((full && !queue->buffer.capacity) || (allocator->allocate && full)) {
491 128 : return NULL;
492 : }
493 97 : queue->front = front_free_slot(queue->front, queue->buffer.capacity);
494 97 : void *const new_slot = raw_at(&queue->buffer, queue->front);
495 97 : if (!full) {
496 97 : ++queue->buffer.count;
497 97 : }
498 97 : return new_slot;
499 97 : }
500 :
501 : static void *
502 110 : allocate_back(
503 : struct CCC_Flat_double_ended_queue *const queue,
504 : CCC_Allocator const *const allocator
505 : ) {
506 110 : CCC_Tribool const full = maybe_resize(queue, 1, allocator) != CCC_RESULT_OK;
507 110 : if ((full && !queue->buffer.capacity) || (allocator->allocate && full)) {
508 128 : return NULL;
509 : }
510 102 : void *const new_slot = raw_at(&queue->buffer, back_free_slot(queue));
511 : /* If no reallocation policy is given we are a ring buffer. */
512 102 : if (full) {
513 1 : queue->front = increment(queue, queue->front);
514 1 : } else {
515 101 : ++queue->buffer.count;
516 : }
517 102 : return new_slot;
518 104 : }
519 :
520 : static void *
521 43 : push_back_range(
522 : struct CCC_Flat_double_ended_queue *const queue,
523 : CCC_Flat_buffer const *const range,
524 : CCC_Allocator const *const allocator
525 : ) {
526 43 : size_t const sizeof_type = queue->buffer.sizeof_type;
527 86 : CCC_Tribool const full
528 43 : = maybe_resize(queue, range->count, allocator) != CCC_RESULT_OK;
529 43 : size_t const cap = queue->buffer.capacity;
530 43 : if ((full && !queue->buffer.capacity) || (allocator->allocate && full)) {
531 8 : return NULL;
532 : }
533 35 : if (range->count >= cap) {
534 11 : queue->front = 0;
535 22 : void *const return_this = memcpy(
536 11 : raw_at(&queue->buffer, 0),
537 11 : raw_at(range, range->count - cap),
538 11 : sizeof_type * cap
539 : );
540 11 : queue->buffer.count = cap;
541 11 : return return_this;
542 11 : }
543 24 : size_t const new_size = queue->buffer.count + range->count;
544 24 : size_t const back_slot = back_free_slot(queue);
545 24 : size_t const chunk = CCC_min(range->count, cap - back_slot);
546 24 : size_t const remainder_back_slot = (back_slot + chunk) % cap;
547 24 : size_t const remainder = (range->count - chunk);
548 48 : void *const return_this = memcpy(
549 24 : raw_at(&queue->buffer, back_slot), range->data, chunk * sizeof_type
550 : );
551 24 : if (remainder) {
552 2 : (void)memcpy(
553 2 : raw_at(&queue->buffer, remainder_back_slot),
554 2 : raw_at(range, chunk),
555 2 : remainder * sizeof_type
556 : );
557 2 : }
558 24 : if (new_size > cap) {
559 8 : queue->front = (queue->front + (new_size - cap)) % cap;
560 8 : }
561 24 : queue->buffer.count = CCC_min(cap, new_size);
562 24 : return return_this;
563 35 : }
564 :
565 : static void *
566 17 : push_front_range(
567 : struct CCC_Flat_double_ended_queue *const queue,
568 : CCC_Flat_buffer const *const range,
569 : CCC_Allocator const *const allocator
570 : ) {
571 17 : size_t const sizeof_type = queue->buffer.sizeof_type;
572 34 : CCC_Tribool const full
573 17 : = maybe_resize(queue, range->count, allocator) != CCC_RESULT_OK;
574 17 : size_t const cap = queue->buffer.capacity;
575 17 : if ((full && !queue->buffer.capacity) || (allocator->allocate && full)) {
576 0 : return NULL;
577 : }
578 17 : if (range->count >= cap) {
579 5 : queue->front = 0;
580 10 : void *const return_this = memcpy(
581 5 : raw_at(&queue->buffer, 0),
582 5 : raw_at(range, range->count - cap),
583 5 : sizeof_type * cap
584 : );
585 5 : queue->buffer.count = cap;
586 5 : return return_this;
587 5 : }
588 12 : size_t const space_ahead = front_free_slot(queue->front, cap) + 1;
589 24 : size_t const i
590 12 : = range->count > space_ahead ? 0 : space_ahead - range->count;
591 12 : size_t const chunk = CCC_min(range->count, space_ahead);
592 12 : size_t const remainder = (range->count - chunk);
593 24 : void *const return_this = memcpy(
594 12 : raw_at(&queue->buffer, i),
595 12 : raw_at(range, range->count - chunk),
596 12 : chunk * sizeof_type
597 : );
598 12 : if (remainder) {
599 4 : (void)memcpy(
600 4 : raw_at(&queue->buffer, cap - remainder),
601 4 : range->data,
602 4 : remainder * sizeof_type
603 : );
604 4 : }
605 12 : queue->buffer.count = CCC_min(cap, queue->buffer.count + range->count);
606 12 : queue->front = remainder ? cap - remainder : i;
607 12 : return return_this;
608 17 : }
609 :
610 : static void *
611 15 : push_range(
612 : struct CCC_Flat_double_ended_queue *const queue,
613 : void const *const position,
614 : CCC_Flat_buffer const *const range,
615 : CCC_Allocator const *const allocator
616 : ) {
617 15 : size_t const sizeof_type = queue->buffer.sizeof_type;
618 30 : CCC_Tribool const full
619 15 : = maybe_resize(queue, range->count, allocator) != CCC_RESULT_OK;
620 15 : if ((full && !queue->buffer.capacity) || (allocator->allocate && full)) {
621 0 : return NULL;
622 : }
623 15 : size_t const cap = queue->buffer.capacity;
624 15 : size_t const new_size = queue->buffer.count + range->count;
625 15 : if (range->count >= cap) {
626 2 : queue->front = 0;
627 4 : void *const return_this = memcpy(
628 2 : raw_at(&queue->buffer, 0),
629 2 : raw_at(range, range->count - cap),
630 2 : sizeof_type * cap
631 : );
632 2 : queue->buffer.count = cap;
633 2 : return return_this;
634 2 : }
635 13 : size_t const pos_i = index_of(queue, position);
636 13 : size_t const back = back_free_slot(queue);
637 13 : size_t const to_move = back > pos_i ? back - pos_i : cap - pos_i + back;
638 13 : size_t const move_i = (pos_i + range->count) % cap;
639 13 : size_t move_chunk = move_i + to_move > cap ? cap - move_i : to_move;
640 21 : move_chunk = back < pos_i ? CCC_min(cap - pos_i, move_chunk)
641 8 : : CCC_min(back - pos_i, move_chunk);
642 13 : size_t const move_remain = to_move - move_chunk;
643 13 : (void)memmove(
644 13 : raw_at(&queue->buffer, move_i),
645 13 : raw_at(&queue->buffer, pos_i),
646 13 : move_chunk * sizeof_type
647 : );
648 13 : if (move_remain) {
649 6 : size_t const move_remain_i = (move_i + move_chunk) % cap;
650 6 : size_t const remaining_start_i = (pos_i + move_chunk) % cap;
651 6 : (void)memmove(
652 6 : raw_at(&queue->buffer, move_remain_i),
653 6 : raw_at(&queue->buffer, remaining_start_i),
654 6 : move_remain * sizeof_type
655 : );
656 6 : }
657 13 : size_t const elements_chunk = CCC_min(range->count, cap - pos_i);
658 13 : size_t const elements_remain = range->count - elements_chunk;
659 26 : void *const return_this = memcpy(
660 13 : raw_at(&queue->buffer, pos_i), range->data, elements_chunk * sizeof_type
661 : );
662 13 : if (elements_remain) {
663 4 : size_t const second_chunk_i = (pos_i + elements_chunk) % cap;
664 4 : (void)memcpy(
665 4 : raw_at(&queue->buffer, second_chunk_i),
666 4 : raw_at(range, elements_chunk),
667 4 : elements_remain * sizeof_type
668 : );
669 4 : }
670 13 : if (new_size > cap) {
671 : /* Wrapping behavior stops if it would overwrite the start of the
672 : range being inserted. This is to preserve as much info about
673 : the range as possible. If wrapping occurs the range is the new
674 : front. */
675 8 : size_t const excess = (new_size - cap);
676 8 : size_t const front_to_pos_dist = (pos_i + cap - queue->front) % cap;
677 8 : queue->front
678 8 : = (queue->front + CCC_min(excess, front_to_pos_dist)) % cap;
679 8 : }
680 13 : queue->buffer.count = CCC_min(cap, new_size);
681 13 : return return_this;
682 15 : }
683 :
684 : static CCC_Result
685 269 : maybe_resize(
686 : struct CCC_Flat_double_ended_queue *const queue,
687 : size_t const to_add,
688 : CCC_Allocator const *const allocator
689 : ) {
690 269 : size_t required_capacity = 0;
691 269 : if (ckd_add(&required_capacity, queue->buffer.count, to_add)) {
692 0 : return CCC_RESULT_ALLOCATOR_ERROR;
693 : }
694 269 : if (required_capacity <= queue->buffer.capacity) {
695 225 : return CCC_RESULT_OK;
696 : }
697 44 : if (!allocator->allocate) {
698 39 : return CCC_RESULT_NO_ALLOCATION_FUNCTION;
699 : }
700 5 : size_t const sizeof_type = queue->buffer.sizeof_type;
701 5 : if (!queue->buffer.capacity && to_add == 1) {
702 0 : required_capacity = START_CAPACITY;
703 5 : } else if (to_add == 1
704 5 : && ckd_mul(&required_capacity, queue->buffer.capacity, 2)) {
705 0 : return CCC_RESULT_ALLOCATOR_ERROR;
706 : }
707 5 : size_t total_bytes = 0;
708 5 : if (ckd_mul(&total_bytes, required_capacity, sizeof_type)) {
709 0 : return CCC_RESULT_ALLOCATOR_ERROR;
710 : }
711 20 : void *const new_data = allocator->allocate((CCC_Allocator_arguments){
712 : .input = NULL,
713 5 : .bytes = total_bytes,
714 5 : .alignment = queue->buffer.alignof_type,
715 5 : .context = allocator->context,
716 : });
717 5 : if (!new_data) {
718 0 : return CCC_RESULT_ALLOCATOR_ERROR;
719 : }
720 5 : if (queue->buffer.count) {
721 9 : size_t const first_chunk = CCC_min(
722 6 : queue->buffer.count, queue->buffer.capacity - queue->front
723 : );
724 3 : (void)memcpy(
725 3 : new_data,
726 3 : raw_at(&queue->buffer, queue->front),
727 3 : sizeof_type * first_chunk
728 : );
729 3 : if (first_chunk < queue->buffer.count) {
730 6 : (void)memcpy(
731 3 : (char *)new_data + (sizeof_type * first_chunk),
732 3 : CCC_flat_buffer_begin(&queue->buffer),
733 3 : sizeof_type * (queue->buffer.count - first_chunk)
734 : );
735 3 : }
736 3 : }
737 5 : (void)CCC_flat_buffer_allocate(&queue->buffer, 0, allocator);
738 5 : queue->buffer.data = new_data;
739 5 : queue->front = 0;
740 5 : queue->buffer.capacity = required_capacity;
741 5 : return CCC_RESULT_OK;
742 269 : }
743 :
744 : static inline void
745 2 : destroy_all(
746 : struct CCC_Flat_double_ended_queue const *const queue,
747 : CCC_Destructor const *const destructor
748 : ) {
749 0 : assert(
750 2 : queue->buffer.count
751 2 : && "queue is not empty otherwise full cannot be distinguished from "
752 : "empty"
753 : );
754 2 : size_t const back = back_free_slot(queue);
755 2 : size_t i = queue->front;
756 2 : do {
757 24 : destructor->destroy((CCC_Arguments){
758 8 : .type = raw_at(&queue->buffer, i),
759 8 : .context = destructor->context,
760 : });
761 8 : i = increment(queue, i);
762 8 : } while (i != back);
763 2 : }
764 :
765 : /** Returns the distance between the current iterator position and the origin
766 : position. Distance is calculated in ascending indices, meaning the result is
767 : the number of forward steps in the Flat_buffer origin would need to take reach
768 : iterator, possibly accounting for wrapping around the end of the buffer. */
769 : static inline size_t
770 463 : distance(
771 : struct CCC_Flat_double_ended_queue const *const queue,
772 : size_t const iterator,
773 : size_t const origin
774 : ) {
775 463 : return iterator > origin ? iterator - origin
776 94 : : (queue->buffer.capacity - origin) + iterator;
777 : }
778 :
779 : /** Returns the rdistance between the current iterator position and the origin
780 : position. Rdistance is calculated in descending indices, meaning the result is
781 : the number of backward steps in the Flat_buffer origin would need to take to
782 : reach iterator, possibly accounting for wrapping around beginning of buffer. */
783 : static inline size_t
784 449 : reverse_distance(
785 : struct CCC_Flat_double_ended_queue const *const queue,
786 : size_t const iterator,
787 : size_t const origin
788 : ) {
789 449 : return iterator > origin ? (queue->buffer.capacity - iterator) + origin
790 323 : : origin - iterator;
791 : }
792 :
793 : static inline size_t
794 1025 : index_of(
795 : struct CCC_Flat_double_ended_queue const *const queue,
796 : void const *const position
797 : ) {
798 1025 : assert(position >= CCC_flat_buffer_begin(&queue->buffer));
799 0 : assert(
800 1025 : (char *)position
801 2050 : < (char *)queue->buffer.data
802 1025 : + (queue->buffer.capacity * queue->buffer.capacity)
803 : );
804 1025 : return (
805 1025 : (size_t)((char *)position
806 1025 : - (char *)CCC_flat_buffer_begin(&queue->buffer))
807 1025 : / queue->buffer.sizeof_type
808 : );
809 : }
810 :
811 : /** Delivers the element at the requested index relative to the front of the
812 : double ended queue. This accounts for the wrapping that can occur of elements
813 : if the front of the double ended queue is not 0. */
814 : static inline void *
815 15 : wrapping_at(
816 : CCC_Flat_double_ended_queue const *const queue, size_t const index
817 : ) {
818 0 : assert(
819 15 : index < queue->buffer.capacity && "wrap access to buffer is in bounds"
820 : );
821 30 : return (char *)queue->buffer.data
822 30 : + (((queue->front + index) % queue->buffer.capacity)
823 15 : * queue->buffer.sizeof_type);
824 : }
825 :
826 : /** Delivers the slot at the requested index zero based. Assumes the index is
827 : within capacity. */
828 : static inline void *
829 1677 : raw_at(CCC_Flat_buffer const *const buffer, size_t const index) {
830 1677 : assert(index < buffer->capacity && "raw access to buffer is in bounds");
831 1677 : return (char *)buffer->data + (buffer->sizeof_type * index);
832 : }
833 :
834 : static inline size_t
835 692 : increment(
836 : struct CCC_Flat_double_ended_queue const *const queue, size_t const index
837 : ) {
838 692 : return index == (queue->buffer.capacity - 1) ? 0 : index + 1;
839 : }
840 :
841 : static inline size_t
842 499 : decrement(
843 : struct CCC_Flat_double_ended_queue const *const queue, size_t const index
844 : ) {
845 499 : return index ? index - 1 : queue->buffer.capacity - 1;
846 : }
847 :
848 : static inline size_t
849 141 : back_free_slot(struct CCC_Flat_double_ended_queue const *const queue) {
850 141 : return (queue->front + queue->buffer.count) % queue->buffer.capacity;
851 : }
852 :
853 : static inline size_t
854 109 : front_free_slot(size_t const front, size_t const capacity) {
855 109 : return front ? front - 1 : capacity - 1;
856 : }
857 :
858 : /** Returns index of last element in the queue or front if empty. */
859 : static inline size_t
860 741 : last_index(struct CCC_Flat_double_ended_queue const *const queue) {
861 741 : return queue->buffer.count
862 741 : ? (queue->front + queue->buffer.count - 1) % queue->buffer.capacity
863 0 : : queue->front;
864 : }
|
