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