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_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 *at(struct CCC_Flat_double_ended_queue const *, size_t);
38 : static size_t increment(struct CCC_Flat_double_ended_queue const *, size_t);
39 : static size_t decrement(struct CCC_Flat_double_ended_queue const *, size_t);
40 : static size_t
41 : distance(struct CCC_Flat_double_ended_queue const *, size_t, size_t);
42 : static size_t
43 : rdistance(struct CCC_Flat_double_ended_queue const *, size_t, size_t);
44 : static CCC_Result push_front_range(
45 : struct CCC_Flat_double_ended_queue *,
46 : CCC_Buffer const *,
47 : CCC_Allocator const *
48 : );
49 : static CCC_Result push_back_range(
50 : struct CCC_Flat_double_ended_queue *,
51 : CCC_Buffer const *,
52 : CCC_Allocator const *
53 : );
54 : static size_t back_free_slot(struct CCC_Flat_double_ended_queue const *);
55 : static size_t front_free_slot(size_t, size_t);
56 : static size_t last_index(struct CCC_Flat_double_ended_queue const *);
57 : static void *push_range(
58 : struct CCC_Flat_double_ended_queue *,
59 : void const *,
60 : CCC_Buffer const *,
61 : CCC_Allocator const *
62 : );
63 : static void *
64 : allocate_front(struct CCC_Flat_double_ended_queue *, CCC_Allocator const *);
65 : static void *
66 : allocate_back(struct CCC_Flat_double_ended_queue *, CCC_Allocator const *);
67 : static size_t min(size_t, size_t);
68 : static void
69 : destroy_all(struct CCC_Flat_double_ended_queue const *, CCC_Destructor const *);
70 :
71 : /*========================== Interface ===============================*/
72 :
73 : void *
74 104 : CCC_flat_double_ended_queue_push_back(
75 : CCC_Flat_double_ended_queue *const queue,
76 : void const *const type,
77 : CCC_Allocator const *const allocator
78 : ) {
79 104 : if (!queue || !type || !allocator) {
80 3 : return NULL;
81 : }
82 101 : void *const slot = allocate_back(queue, allocator);
83 101 : if (slot && slot != type) {
84 99 : (void)memcpy(slot, type, queue->buffer.sizeof_type);
85 99 : }
86 101 : return slot;
87 104 : }
88 :
89 : void *
90 99 : CCC_flat_double_ended_queue_push_front(
91 : CCC_Flat_double_ended_queue *const queue,
92 : void const *const type,
93 : CCC_Allocator const *const allocator
94 : ) {
95 99 : if (!queue || !type || !allocator) {
96 3 : return NULL;
97 : }
98 96 : void *const slot = allocate_front(queue, allocator);
99 96 : if (slot && slot != type) {
100 96 : (void)memcpy(slot, type, queue->buffer.sizeof_type);
101 96 : }
102 96 : return slot;
103 99 : }
104 :
105 : CCC_Result
106 14 : CCC_flat_double_ended_queue_push_front_range(
107 : CCC_Flat_double_ended_queue *const queue,
108 : CCC_Buffer const *const range,
109 : CCC_Allocator const *const allocator
110 : ) {
111 14 : if (!queue || !range || range->sizeof_type != queue->buffer.sizeof_type
112 12 : || !allocator) {
113 3 : return CCC_RESULT_ARGUMENT_ERROR;
114 : }
115 11 : return push_front_range(queue, range, allocator);
116 14 : }
117 :
118 : CCC_Result
119 32 : CCC_flat_double_ended_queue_push_back_range(
120 : CCC_Flat_double_ended_queue *const queue,
121 : CCC_Buffer const *const range,
122 : CCC_Allocator const *const allocator
123 : ) {
124 32 : if (!queue || !range || range->sizeof_type != queue->buffer.sizeof_type
125 30 : || !allocator) {
126 3 : return CCC_RESULT_ARGUMENT_ERROR;
127 : }
128 29 : return push_back_range(queue, range, allocator);
129 32 : }
130 :
131 : void *
132 31 : CCC_flat_double_ended_queue_insert_range(
133 : CCC_Flat_double_ended_queue *const queue,
134 : void *position,
135 : CCC_Buffer const *const range,
136 : CCC_Allocator const *const allocator
137 : ) {
138 31 : if (!queue || !range || range->sizeof_type != queue->buffer.sizeof_type
139 29 : || !allocator) {
140 3 : return NULL;
141 : }
142 28 : if (!range->count) {
143 1 : return position;
144 : }
145 27 : if (position == CCC_flat_double_ended_queue_begin(queue)) {
146 6 : return push_front_range(queue, range, allocator) != CCC_RESULT_OK
147 : ? NULL
148 6 : : at(queue, range->count - 1);
149 : }
150 21 : if (position == CCC_flat_double_ended_queue_end(queue)) {
151 6 : return push_back_range(queue, range, allocator) != CCC_RESULT_OK
152 : ? NULL
153 6 : : at(queue, queue->buffer.count - range->count);
154 : }
155 15 : return push_range(queue, position, range, allocator);
156 31 : }
157 :
158 : CCC_Result
159 171 : CCC_flat_double_ended_queue_pop_front(
160 : CCC_Flat_double_ended_queue *const queue
161 : ) {
162 171 : if (!queue || !queue->buffer.count) {
163 1 : return CCC_RESULT_ARGUMENT_ERROR;
164 : }
165 170 : queue->front = increment(queue, queue->front);
166 170 : --queue->buffer.count;
167 170 : return CCC_RESULT_OK;
168 171 : }
169 :
170 : CCC_Result
171 110 : CCC_flat_double_ended_queue_pop_back(CCC_Flat_double_ended_queue *const queue) {
172 110 : if (!queue || !queue->buffer.count) {
173 1 : return CCC_RESULT_ARGUMENT_ERROR;
174 : }
175 109 : --queue->buffer.count;
176 109 : return CCC_RESULT_OK;
177 110 : }
178 :
179 : void *
180 171 : CCC_flat_double_ended_queue_front(
181 : CCC_Flat_double_ended_queue const *const queue
182 : ) {
183 171 : if (!queue || !queue->buffer.count) {
184 1 : return NULL;
185 : }
186 170 : return CCC_buffer_at(&queue->buffer, queue->front);
187 171 : }
188 :
189 : void *
190 106 : CCC_flat_double_ended_queue_back(
191 : CCC_Flat_double_ended_queue const *const queue
192 : ) {
193 106 : if (!queue || !queue->buffer.count) {
194 1 : return NULL;
195 : }
196 105 : return CCC_buffer_at(&queue->buffer, last_index(queue));
197 106 : }
198 :
199 : CCC_Tribool
200 343 : CCC_flat_double_ended_queue_is_empty(
201 : CCC_Flat_double_ended_queue const *const queue
202 : ) {
203 343 : if (!queue) {
204 1 : return CCC_TRIBOOL_ERROR;
205 : }
206 342 : return !queue->buffer.count;
207 343 : }
208 :
209 : CCC_Count
210 607 : CCC_flat_double_ended_queue_count(
211 : CCC_Flat_double_ended_queue const *const queue
212 : ) {
213 607 : if (!queue) {
214 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
215 : }
216 606 : return (CCC_Count){.count = queue->buffer.count};
217 607 : }
218 :
219 : CCC_Count
220 13 : CCC_flat_double_ended_queue_capacity(
221 : CCC_Flat_double_ended_queue const *const queue
222 : ) {
223 13 : if (!queue) {
224 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
225 : }
226 12 : return (CCC_Count){.count = queue->buffer.capacity};
227 13 : }
228 :
229 : void *
230 17 : CCC_flat_double_ended_queue_at(
231 : CCC_Flat_double_ended_queue const *const queue, size_t const i
232 : ) {
233 17 : if (!queue || i >= queue->buffer.capacity) {
234 2 : return NULL;
235 : }
236 15 : return CCC_buffer_at(
237 15 : &queue->buffer, (queue->front + i) % queue->buffer.capacity
238 : );
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 CCC_buffer_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 CCC_buffer_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 CCC_buffer_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 : || rdistance(queue, next_i, reverse_begin) >= queue->buffer.count) {
290 97 : return NULL;
291 : }
292 402 : return CCC_buffer_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_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_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 : CCC_buffer_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_buffer_allocate(&queue->buffer, 0, allocator);
414 : }
415 1 : destroy_all(queue, destructor);
416 1 : CCC_Result const r = CCC_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_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 40 : if (CCC_buffer_index(&queue->buffer, iterator).count != last_index(queue)) {
450 0 : return CCC_FALSE;
451 : }
452 194 : for (; iterator != CCC_flat_double_ended_queue_reverse_end(queue);
453 154 : iterator = CCC_flat_double_ended_queue_reverse_next(queue, iterator),
454 154 : ++size) {
455 154 : if (size >= CCC_flat_double_ended_queue_count(queue).count) {
456 0 : return CCC_FALSE;
457 : }
458 154 : }
459 40 : return size == CCC_flat_double_ended_queue_count(queue).count;
460 43 : }
461 :
462 : /*====================== Private Interface ==============================*/
463 :
464 : void *
465 3 : CCC_private_flat_double_ended_queue_allocate_back(
466 : struct CCC_Flat_double_ended_queue *const queue,
467 : CCC_Allocator const *const allocator
468 : ) {
469 3 : return allocate_back(queue, allocator);
470 : }
471 :
472 : void *
473 1 : CCC_private_flat_double_ended_queue_allocate_front(
474 : struct CCC_Flat_double_ended_queue *const queue,
475 : CCC_Allocator const *const allocator
476 : ) {
477 1 : return allocate_front(queue, allocator);
478 : }
479 :
480 : /*====================== Static Helpers ==============================*/
481 :
482 : static void *
483 97 : allocate_front(
484 : struct CCC_Flat_double_ended_queue *const queue,
485 : CCC_Allocator const *const allocator
486 : ) {
487 97 : CCC_Tribool const full = maybe_resize(queue, 1, allocator) != CCC_RESULT_OK;
488 : /* Should have been able to resize. Bad error. */
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 = CCC_buffer_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 : /* Should have been able to resize. Bad error. */
507 110 : if ((full && !queue->buffer.capacity) || (allocator->allocate && full)) {
508 128 : return NULL;
509 : }
510 102 : void *const new_slot = CCC_buffer_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 CCC_Result
521 43 : push_back_range(
522 : struct CCC_Flat_double_ended_queue *const queue,
523 : CCC_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 CCC_RESULT_ALLOCATOR_ERROR;
532 : }
533 : /* If a range is too large we can make various simplifications to preserve
534 : the final capacity elements. */
535 35 : if (range->count >= cap) {
536 11 : queue->front = 0;
537 11 : (void)memcpy(
538 11 : CCC_buffer_at(&queue->buffer, 0),
539 11 : CCC_buffer_at(range, range->count - cap),
540 11 : sizeof_type * cap
541 : );
542 11 : queue->buffer.count = cap;
543 11 : return CCC_RESULT_OK;
544 : }
545 24 : size_t const new_size = queue->buffer.count + range->count;
546 24 : size_t const back_slot = back_free_slot(queue);
547 24 : size_t const chunk = min(range->count, cap - back_slot);
548 24 : size_t const remainder_back_slot = (back_slot + chunk) % cap;
549 24 : size_t const remainder = (range->count - chunk);
550 24 : (void)memcpy(
551 24 : CCC_buffer_at(&queue->buffer, back_slot),
552 24 : range->data,
553 24 : chunk * sizeof_type
554 : );
555 24 : if (remainder) {
556 2 : (void)memcpy(
557 2 : CCC_buffer_at(&queue->buffer, remainder_back_slot),
558 2 : CCC_buffer_at(range, chunk),
559 2 : remainder * sizeof_type
560 : );
561 2 : }
562 24 : if (new_size > cap) {
563 8 : queue->front = (queue->front + (new_size - cap)) % cap;
564 8 : }
565 24 : queue->buffer.count = min(cap, new_size);
566 24 : return CCC_RESULT_OK;
567 35 : }
568 :
569 : static CCC_Result
570 17 : push_front_range(
571 : struct CCC_Flat_double_ended_queue *const queue,
572 : CCC_Buffer const *const range,
573 : CCC_Allocator const *const allocator
574 : ) {
575 17 : size_t const sizeof_type = queue->buffer.sizeof_type;
576 34 : CCC_Tribool const full
577 17 : = maybe_resize(queue, range->count, allocator) != CCC_RESULT_OK;
578 17 : size_t const cap = queue->buffer.capacity;
579 17 : if ((full && !queue->buffer.capacity) || (allocator->allocate && full)) {
580 0 : return CCC_RESULT_ALLOCATOR_ERROR;
581 : }
582 : /* If a range is too large we can make various simplifications to preserve
583 : the final capacity elements. */
584 17 : if (range->count >= cap) {
585 5 : queue->front = 0;
586 5 : (void)memcpy(
587 5 : CCC_buffer_at(&queue->buffer, 0),
588 5 : CCC_buffer_at(range, range->count - cap),
589 5 : sizeof_type * cap
590 : );
591 5 : queue->buffer.count = cap;
592 5 : return CCC_RESULT_OK;
593 : }
594 12 : size_t const space_ahead = front_free_slot(queue->front, cap) + 1;
595 24 : size_t const i
596 12 : = range->count > space_ahead ? 0 : space_ahead - range->count;
597 12 : size_t const chunk = min(range->count, space_ahead);
598 12 : size_t const remainder = (range->count - chunk);
599 12 : (void)memcpy(
600 12 : CCC_buffer_at(&queue->buffer, i),
601 12 : CCC_buffer_at(range, range->count - chunk),
602 12 : chunk * sizeof_type
603 : );
604 12 : if (remainder) {
605 4 : (void)memcpy(
606 4 : CCC_buffer_at(&queue->buffer, cap - remainder),
607 4 : range->data,
608 4 : remainder * sizeof_type
609 : );
610 4 : }
611 12 : queue->buffer.count = min(cap, queue->buffer.count + range->count);
612 12 : queue->front = remainder ? cap - remainder : i;
613 12 : return CCC_RESULT_OK;
614 17 : }
615 :
616 : static void *
617 15 : push_range(
618 : struct CCC_Flat_double_ended_queue *const queue,
619 : void const *const position,
620 : CCC_Buffer const *const range,
621 : CCC_Allocator const *const allocator
622 : ) {
623 15 : size_t const sizeof_type = queue->buffer.sizeof_type;
624 30 : CCC_Tribool const full
625 15 : = maybe_resize(queue, range->count, allocator) != CCC_RESULT_OK;
626 15 : if ((full && !queue->buffer.capacity) || (allocator->allocate && full)) {
627 0 : return NULL;
628 : }
629 15 : size_t const cap = queue->buffer.capacity;
630 15 : size_t const new_size = queue->buffer.count + range->count;
631 15 : if (range->count >= cap) {
632 2 : queue->front = 0;
633 2 : void *const ret = CCC_buffer_at(&queue->buffer, 0);
634 2 : (void)memcpy(
635 2 : ret, CCC_buffer_at(range, range->count - cap), sizeof_type * cap
636 : );
637 2 : queue->buffer.count = cap;
638 2 : return ret;
639 2 : }
640 13 : size_t const pos_i = index_of(queue, position);
641 13 : size_t const back = back_free_slot(queue);
642 13 : size_t const to_move = back > pos_i ? back - pos_i : cap - pos_i + back;
643 13 : size_t const move_i = (pos_i + range->count) % cap;
644 13 : size_t move_chunk = move_i + to_move > cap ? cap - move_i : to_move;
645 13 : move_chunk = back < pos_i ? min(cap - pos_i, move_chunk)
646 8 : : min(back - pos_i, move_chunk);
647 13 : size_t const move_remain = to_move - move_chunk;
648 13 : (void)memmove(
649 13 : CCC_buffer_at(&queue->buffer, move_i),
650 13 : CCC_buffer_at(&queue->buffer, pos_i),
651 13 : move_chunk * sizeof_type
652 : );
653 13 : if (move_remain) {
654 6 : size_t const move_remain_i = (move_i + move_chunk) % cap;
655 6 : size_t const remaining_start_i = (pos_i + move_chunk) % cap;
656 6 : (void)memmove(
657 6 : CCC_buffer_at(&queue->buffer, move_remain_i),
658 6 : CCC_buffer_at(&queue->buffer, remaining_start_i),
659 6 : move_remain * sizeof_type
660 : );
661 6 : }
662 13 : size_t const elements_chunk = min(range->count, cap - pos_i);
663 13 : size_t const elements_remain = range->count - elements_chunk;
664 13 : (void)memcpy(
665 13 : CCC_buffer_at(&queue->buffer, pos_i),
666 13 : range->data,
667 13 : elements_chunk * sizeof_type
668 : );
669 13 : if (elements_remain) {
670 4 : size_t const second_chunk_i = (pos_i + elements_chunk) % cap;
671 4 : (void)memcpy(
672 4 : CCC_buffer_at(&queue->buffer, second_chunk_i),
673 4 : CCC_buffer_at(range, elements_chunk),
674 4 : elements_remain * sizeof_type
675 : );
676 4 : }
677 13 : if (new_size > cap) {
678 : /* Wrapping behavior stops if it would overwrite the start of the
679 : range being inserted. This is to preserve as much info about
680 : the range as possible. If wrapping occurs the range is the new
681 : front. */
682 8 : size_t const excess = (new_size - cap);
683 8 : size_t const front_to_pos_dist = (pos_i + cap - queue->front) % cap;
684 8 : queue->front = (queue->front + min(excess, front_to_pos_dist)) % cap;
685 8 : }
686 13 : queue->buffer.count = min(cap, new_size);
687 13 : return CCC_buffer_at(&queue->buffer, pos_i);
688 15 : }
689 :
690 : static CCC_Result
691 269 : maybe_resize(
692 : struct CCC_Flat_double_ended_queue *const queue,
693 : size_t const to_add,
694 : CCC_Allocator const *const allocator
695 : ) {
696 269 : size_t required = queue->buffer.count + to_add;
697 269 : if (required < queue->buffer.count) {
698 0 : return CCC_RESULT_ARGUMENT_ERROR;
699 : }
700 269 : if (required <= queue->buffer.capacity) {
701 225 : return CCC_RESULT_OK;
702 : }
703 44 : if (!allocator->allocate) {
704 39 : return CCC_RESULT_NO_ALLOCATION_FUNCTION;
705 : }
706 5 : size_t const sizeof_type = queue->buffer.sizeof_type;
707 5 : if (!queue->buffer.capacity && to_add == 1) {
708 0 : required = START_CAPACITY;
709 5 : } else if (to_add == 1) {
710 3 : required = queue->buffer.capacity * 2;
711 3 : }
712 15 : void *const new_data = allocator->allocate((CCC_Allocator_arguments){
713 : .input = NULL,
714 5 : .bytes = sizeof_type * required,
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 6 : size_t const first_chunk
722 3 : = min(queue->buffer.count, queue->buffer.capacity - queue->front);
723 3 : (void)memcpy(
724 3 : new_data,
725 3 : CCC_buffer_at(&queue->buffer, queue->front),
726 3 : sizeof_type * first_chunk
727 : );
728 3 : if (first_chunk < queue->buffer.count) {
729 6 : (void)memcpy(
730 3 : (char *)new_data + (sizeof_type * first_chunk),
731 3 : CCC_buffer_begin(&queue->buffer),
732 3 : sizeof_type * (queue->buffer.count - first_chunk)
733 : );
734 3 : }
735 3 : }
736 5 : (void)CCC_buffer_allocate(&queue->buffer, 0, allocator);
737 5 : queue->buffer.data = new_data;
738 5 : queue->front = 0;
739 5 : queue->buffer.capacity = required;
740 5 : return CCC_RESULT_OK;
741 269 : }
742 :
743 : static inline void
744 2 : destroy_all(
745 : struct CCC_Flat_double_ended_queue const *const queue,
746 : CCC_Destructor const *const destructor
747 : ) {
748 0 : assert(
749 2 : queue->buffer.count
750 2 : && "queue is not empty otherwise full cannot be distinguished from "
751 : "empty"
752 : );
753 2 : size_t const back = back_free_slot(queue);
754 2 : size_t i = queue->front;
755 2 : do {
756 24 : destructor->destroy((CCC_Arguments){
757 8 : .type = CCC_buffer_at(&queue->buffer, i),
758 8 : .context = destructor->context,
759 : });
760 8 : i = increment(queue, i);
761 8 : } while (i != back);
762 2 : }
763 :
764 : /** Returns the distance between the current iterator position and the origin
765 : position. Distance is calculated in ascending indices, meaning the result is
766 : the number of forward steps in the Buffer origin would need to take reach
767 : iterator, possibly accounting for wrapping around the end of the buffer. */
768 : static inline size_t
769 463 : distance(
770 : struct CCC_Flat_double_ended_queue const *const queue,
771 : size_t const iterator,
772 : size_t const origin
773 : ) {
774 463 : return iterator > origin ? iterator - origin
775 94 : : (queue->buffer.capacity - origin) + iterator;
776 : }
777 :
778 : /** Returns the rdistance between the current iterator position and the origin
779 : position. Rdistance is calculated in descending indices, meaning the result is
780 : the number of backward steps in the Buffer origin would need to take to reach
781 : iterator, possibly accounting for wrapping around the beginning of buffer. */
782 : static inline size_t
783 449 : rdistance(
784 : struct CCC_Flat_double_ended_queue const *const queue,
785 : size_t const iterator,
786 : size_t const origin
787 : ) {
788 449 : return iterator > origin ? (queue->buffer.capacity - iterator) + origin
789 323 : : origin - iterator;
790 : }
791 :
792 : static inline size_t
793 1025 : index_of(
794 : struct CCC_Flat_double_ended_queue const *const queue,
795 : void const *const position
796 : ) {
797 1025 : assert(position >= CCC_buffer_begin(&queue->buffer));
798 0 : assert(
799 1025 : (char *)position
800 2050 : < (char *)queue->buffer.data
801 1025 : + (queue->buffer.capacity * queue->buffer.capacity)
802 : );
803 1025 : return (
804 1025 : (size_t)((char *)position - (char *)CCC_buffer_begin(&queue->buffer))
805 1025 : / queue->buffer.sizeof_type
806 : );
807 : }
808 :
809 : static inline void *
810 12 : at(struct CCC_Flat_double_ended_queue const *const queue, size_t const index) {
811 12 : return CCC_buffer_at(
812 12 : &queue->buffer, (queue->front + index) % queue->buffer.capacity
813 : );
814 : }
815 :
816 : static inline size_t
817 692 : increment(
818 : struct CCC_Flat_double_ended_queue const *const queue, size_t const index
819 : ) {
820 692 : return index == (queue->buffer.capacity - 1) ? 0 : index + 1;
821 : }
822 :
823 : static inline size_t
824 499 : decrement(
825 : struct CCC_Flat_double_ended_queue const *const queue, size_t const index
826 : ) {
827 499 : return index ? index - 1 : queue->buffer.capacity - 1;
828 : }
829 :
830 : static inline size_t
831 141 : back_free_slot(struct CCC_Flat_double_ended_queue const *const queue) {
832 141 : return (queue->front + queue->buffer.count) % queue->buffer.capacity;
833 : }
834 :
835 : static inline size_t
836 109 : front_free_slot(size_t const front, size_t const capacity) {
837 109 : return front ? front - 1 : capacity - 1;
838 : }
839 :
840 : /** Returns index of last element in the queue or front if empty. */
841 : static inline size_t
842 741 : last_index(struct CCC_Flat_double_ended_queue const *const queue) {
843 741 : return queue->buffer.count
844 741 : ? (queue->front + queue->buffer.count - 1) % queue->buffer.capacity
845 0 : : queue->front;
846 : }
847 :
848 : static inline size_t
849 124 : min(size_t const left, size_t const right) {
850 124 : return left < right ? left : right;
851 : }
|
