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 <stdckdint.h>
16 : #include <stddef.h>
17 :
18 : /** CCC provided headers. */
19 : #include "ccc/configuration.h" /* IWYU pragma: keep */
20 : #include "ccc/flat_buffer.h"
21 : #include "ccc/private/private_flat_buffer.h"
22 : #include "ccc/types.h"
23 : #include "source/compiler_utilities.h"
24 :
25 : enum : size_t {
26 : START_CAPACITY = 8,
27 : };
28 :
29 : /*========================== Prototypes ================================*/
30 :
31 : static void *at(CCC_Flat_buffer const *, size_t);
32 :
33 : /*========================== Interface ================================*/
34 :
35 : CCC_Result
36 63 : CCC_flat_buffer_allocate(
37 : CCC_Flat_buffer *const buffer,
38 : size_t const capacity,
39 : CCC_Allocator const *const allocator
40 : ) {
41 63 : if (!buffer || !allocator) {
42 2 : return CCC_RESULT_ARGUMENT_ERROR;
43 : }
44 61 : if (!allocator->allocate) {
45 9 : return CCC_RESULT_NO_ALLOCATION_FUNCTION;
46 : }
47 52 : size_t total_bytes = 0;
48 52 : if (ckd_mul(&total_bytes, capacity, buffer->sizeof_type)) {
49 0 : return CCC_RESULT_ALLOCATOR_ERROR;
50 : }
51 260 : void *const new_data = allocator->allocate((CCC_Allocator_arguments){
52 52 : .input = buffer->data,
53 52 : .bytes = total_bytes,
54 52 : .alignment = buffer->alignof_type,
55 52 : .context = allocator->context,
56 : });
57 52 : if (capacity && !new_data) {
58 4 : return CCC_RESULT_ALLOCATOR_ERROR;
59 : }
60 48 : buffer->data = new_data;
61 48 : buffer->capacity = capacity;
62 48 : return CCC_RESULT_OK;
63 63 : }
64 :
65 : CCC_Result
66 51 : CCC_flat_buffer_reserve(
67 : CCC_Flat_buffer *const buffer,
68 : size_t const to_add,
69 : CCC_Allocator const *const allocator
70 : ) {
71 51 : if (!buffer || !allocator || !allocator->allocate || !to_add) {
72 9 : return CCC_RESULT_ARGUMENT_ERROR;
73 : }
74 42 : size_t new_capacity = 0;
75 42 : if (ckd_add(&new_capacity, buffer->count, to_add)) {
76 0 : return CCC_RESULT_ALLOCATOR_ERROR;
77 : }
78 42 : if (new_capacity <= buffer->capacity) {
79 1 : return CCC_RESULT_OK;
80 : }
81 41 : if (new_capacity < START_CAPACITY) {
82 3 : new_capacity = START_CAPACITY;
83 3 : }
84 41 : size_t total_bytes = 0;
85 41 : if (ckd_mul(&total_bytes, new_capacity, buffer->sizeof_type)) {
86 0 : return CCC_RESULT_ALLOCATOR_ERROR;
87 : }
88 205 : void *const new_data = allocator->allocate((CCC_Allocator_arguments){
89 41 : .input = buffer->data,
90 41 : .bytes = total_bytes,
91 41 : .alignment = buffer->alignof_type,
92 41 : .context = allocator->context,
93 : });
94 41 : if (!new_data) {
95 1 : return CCC_RESULT_ALLOCATOR_ERROR;
96 : }
97 40 : buffer->data = new_data;
98 40 : buffer->capacity = new_capacity;
99 40 : return CCC_RESULT_OK;
100 51 : }
101 :
102 : CCC_Result
103 4 : CCC_flat_buffer_clear(
104 : CCC_Flat_buffer *const buffer, CCC_Destructor const *const destructor
105 : ) {
106 4 : if (!buffer || !destructor) {
107 2 : return CCC_RESULT_ARGUMENT_ERROR;
108 : }
109 2 : if (!destructor->destroy) {
110 1 : buffer->count = 0;
111 1 : return CCC_RESULT_OK;
112 : }
113 9 : for (void *i = CCC_flat_buffer_begin(buffer);
114 9 : i != CCC_flat_buffer_end(buffer);
115 8 : i = CCC_flat_buffer_next(buffer, i)) {
116 24 : destructor->destroy((CCC_Arguments){
117 8 : .type = i,
118 8 : .context = destructor->context,
119 : });
120 8 : }
121 1 : buffer->count = 0;
122 1 : return CCC_RESULT_OK;
123 4 : }
124 :
125 : CCC_Result
126 20 : CCC_flat_buffer_clear_and_free(
127 : CCC_Flat_buffer *const buffer,
128 : CCC_Destructor const *const destructor,
129 : CCC_Allocator const *const allocator
130 : ) {
131 20 : if (!buffer || !allocator || !destructor || !allocator->allocate) {
132 1 : return CCC_RESULT_ARGUMENT_ERROR;
133 : }
134 19 : if (destructor->destroy) {
135 9 : for (void *i = CCC_flat_buffer_begin(buffer);
136 9 : i != CCC_flat_buffer_end(buffer);
137 8 : i = CCC_flat_buffer_next(buffer, i)) {
138 24 : destructor->destroy((CCC_Arguments){
139 8 : .type = i,
140 8 : .context = destructor->context,
141 : });
142 8 : }
143 1 : }
144 76 : (void)allocator->allocate((CCC_Allocator_arguments){
145 19 : .input = buffer->data,
146 : .bytes = 0,
147 19 : .alignment = buffer->alignof_type,
148 19 : .context = allocator->context,
149 : });
150 19 : buffer->data = NULL;
151 19 : buffer->count = 0;
152 19 : buffer->capacity = 0;
153 19 : return CCC_RESULT_OK;
154 20 : }
155 :
156 : void *
157 3696 : CCC_flat_buffer_at(CCC_Flat_buffer const *const buffer, size_t const i) {
158 3696 : if (!buffer || i >= buffer->capacity) {
159 3 : return NULL;
160 : }
161 3693 : return ((char *)buffer->data + (i * buffer->sizeof_type));
162 3696 : }
163 :
164 : void *
165 90 : CCC_flat_buffer_back(CCC_Flat_buffer const *const buffer) {
166 90 : return CCC_flat_buffer_at(buffer, buffer->count - 1);
167 : }
168 :
169 : void *
170 7 : CCC_flat_buffer_front(CCC_Flat_buffer const *const buffer) {
171 7 : return CCC_flat_buffer_at(buffer, 0);
172 : }
173 :
174 : void *
175 4877 : CCC_flat_buffer_allocate_back(
176 : CCC_Flat_buffer *const buffer, CCC_Allocator const *const allocator
177 : ) {
178 4877 : if (!buffer || !allocator) {
179 4 : return NULL;
180 : }
181 4873 : if (buffer->count == buffer->capacity) {
182 20 : size_t new_capacity = 0;
183 20 : if (ckd_mul(&new_capacity, buffer->capacity, 2)) {
184 0 : return NULL;
185 : }
186 40 : CCC_Result const resize_res = CCC_flat_buffer_allocate(
187 20 : buffer, CCC_max(new_capacity, START_CAPACITY), allocator
188 : );
189 20 : if (resize_res != CCC_RESULT_OK) {
190 6 : return NULL;
191 : }
192 20 : }
193 9734 : void *const ret
194 4867 : = ((char *)buffer->data + (buffer->sizeof_type * buffer->count));
195 4867 : ++buffer->count;
196 4867 : return ret;
197 4877 : }
198 :
199 : void *
200 149 : CCC_flat_buffer_push_back(
201 : CCC_Flat_buffer *const buffer,
202 : void const *const data,
203 : CCC_Allocator const *const allocator
204 : ) {
205 149 : if (!data) {
206 1 : return NULL;
207 : }
208 148 : void *const slot = CCC_flat_buffer_allocate_back(buffer, allocator);
209 148 : if (slot) {
210 142 : (void)memcpy(slot, data, buffer->sizeof_type);
211 142 : }
212 148 : return slot;
213 149 : }
214 :
215 : CCC_Result
216 5 : CCC_flat_buffer_swap(
217 : CCC_Flat_buffer const *const buffer,
218 : void *const temp,
219 : size_t const index,
220 : size_t const swap_index
221 : ) {
222 5 : if (!buffer || !temp || index >= buffer->capacity
223 5 : || swap_index >= buffer->capacity || swap_index == index) {
224 1 : return CCC_RESULT_ARGUMENT_ERROR;
225 : }
226 4 : (void)memcpy(temp, at(buffer, index), buffer->sizeof_type);
227 4 : (void)memcpy(
228 4 : at(buffer, index), at(buffer, swap_index), buffer->sizeof_type
229 : );
230 4 : (void)memcpy(at(buffer, swap_index), temp, buffer->sizeof_type);
231 4 : return CCC_RESULT_OK;
232 5 : }
233 :
234 : void *
235 3 : CCC_flat_buffer_move(
236 : CCC_Flat_buffer const *const buffer,
237 : size_t const destination,
238 : size_t const source
239 : ) {
240 3 : if (!buffer || destination >= buffer->capacity
241 3 : || source >= buffer->capacity) {
242 1 : return NULL;
243 : }
244 2 : if (destination == source) {
245 1 : return at(buffer, destination);
246 : }
247 1 : return memcpy(
248 1 : at(buffer, destination), at(buffer, source), buffer->sizeof_type
249 : );
250 3 : }
251 :
252 : CCC_Result
253 10 : CCC_flat_buffer_write(
254 : CCC_Flat_buffer const *const buffer, size_t const i, void const *const data
255 : ) {
256 10 : if (!buffer || !buffer->data || !data) {
257 1 : return CCC_RESULT_ARGUMENT_ERROR;
258 : }
259 9 : void *const pos = CCC_flat_buffer_at(buffer, i);
260 9 : if (!pos || data == pos) {
261 2 : return CCC_RESULT_ARGUMENT_ERROR;
262 : }
263 7 : (void)memcpy(pos, data, buffer->sizeof_type);
264 7 : return CCC_RESULT_OK;
265 10 : }
266 :
267 : CCC_Result
268 6 : CCC_flat_buffer_erase(CCC_Flat_buffer *const buffer, size_t const i) {
269 6 : if (!buffer || !buffer->count || i >= buffer->count) {
270 2 : return CCC_RESULT_ARGUMENT_ERROR;
271 : }
272 4 : if (1 == buffer->count) {
273 1 : buffer->count = 0;
274 1 : return CCC_RESULT_OK;
275 : }
276 3 : if (i == buffer->count - 1) {
277 1 : --buffer->count;
278 1 : return CCC_RESULT_OK;
279 : }
280 2 : (void)memmove(
281 2 : at(buffer, i),
282 2 : at(buffer, i + 1),
283 2 : buffer->sizeof_type * (buffer->count - (i + 1))
284 : );
285 2 : --buffer->count;
286 2 : return CCC_RESULT_OK;
287 6 : }
288 :
289 : void *
290 11 : CCC_flat_buffer_insert(
291 : CCC_Flat_buffer *const buffer,
292 : size_t const i,
293 : void const *const data,
294 : CCC_Allocator const *const allocator
295 : ) {
296 11 : if (!buffer || !buffer->data || i > buffer->count || !allocator) {
297 4 : return NULL;
298 : }
299 7 : if (i == buffer->count) {
300 1 : return CCC_flat_buffer_push_back(buffer, data, allocator);
301 : }
302 6 : if (buffer->count == buffer->capacity) {
303 1 : size_t new_capacity = 0;
304 1 : if (ckd_mul(&new_capacity, buffer->count, 2)) {
305 0 : return NULL;
306 : }
307 2 : CCC_Result const r = CCC_flat_buffer_allocate(
308 1 : buffer, CCC_max(new_capacity, START_CAPACITY), allocator
309 : );
310 1 : if (r != CCC_RESULT_OK) {
311 1 : return NULL;
312 : }
313 1 : }
314 5 : (void)memmove(
315 5 : at(buffer, i + 1),
316 5 : at(buffer, i),
317 5 : buffer->sizeof_type * (buffer->count - i)
318 : );
319 5 : ++buffer->count;
320 5 : return memcpy(at(buffer, i), data, buffer->sizeof_type);
321 11 : }
322 :
323 : CCC_Result
324 66 : CCC_flat_buffer_pop_back_n(CCC_Flat_buffer *const buffer, size_t count) {
325 66 : if (!buffer || count > buffer->count) {
326 4 : return CCC_RESULT_ARGUMENT_ERROR;
327 : }
328 62 : buffer->count -= count;
329 62 : return CCC_RESULT_OK;
330 66 : }
331 :
332 : CCC_Result
333 64 : CCC_flat_buffer_pop_back(CCC_Flat_buffer *const buffer) {
334 64 : return CCC_flat_buffer_pop_back_n(buffer, 1);
335 : }
336 :
337 : CCC_Count
338 1089 : CCC_flat_buffer_count(CCC_Flat_buffer const *const buffer) {
339 1089 : if (!buffer) {
340 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
341 : }
342 1088 : return (CCC_Count){.count = buffer->count};
343 1089 : }
344 :
345 : CCC_Count
346 29 : CCC_flat_buffer_capacity(CCC_Flat_buffer const *const buffer) {
347 29 : if (!buffer) {
348 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
349 : }
350 28 : return (CCC_Count){.count = buffer->capacity};
351 29 : }
352 :
353 : CCC_Count
354 140 : CCC_flat_buffer_sizeof_type(CCC_Flat_buffer const *const buffer) {
355 140 : if (!buffer) {
356 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
357 : }
358 139 : return (CCC_Count){.count = buffer->sizeof_type};
359 140 : }
360 :
361 : CCC_Tribool
362 2043 : CCC_flat_buffer_is_empty(CCC_Flat_buffer const *const buffer) {
363 2043 : if (!buffer) {
364 1 : return CCC_TRIBOOL_ERROR;
365 : }
366 2042 : return !buffer->count;
367 2043 : }
368 :
369 : CCC_Tribool
370 29 : CCC_flat_buffer_is_full(CCC_Flat_buffer const *const buffer) {
371 29 : if (!buffer) {
372 1 : return CCC_TRIBOOL_ERROR;
373 : }
374 28 : if (!buffer->capacity) {
375 1 : return CCC_FALSE;
376 : }
377 27 : return buffer->count == buffer->capacity ? CCC_TRUE : CCC_FALSE;
378 29 : }
379 :
380 : void *
381 2164 : CCC_flat_buffer_begin(CCC_Flat_buffer const *const buffer) {
382 2164 : return buffer ? buffer->data : NULL;
383 : }
384 :
385 : void *
386 64 : CCC_flat_buffer_reverse_begin(CCC_Flat_buffer const *const buffer) {
387 64 : if (!buffer || !buffer->data) {
388 2 : return NULL;
389 : }
390 : /* OK if count is 0. Negative offset puts at reverse_end anyway. */
391 124 : return (unsigned char *)buffer->data
392 62 : + ((buffer->count - 1) * buffer->sizeof_type);
393 64 : }
394 :
395 : void *
396 1474 : CCC_flat_buffer_next(
397 : CCC_Flat_buffer const *const buffer, void const *const iterator
398 : ) {
399 1474 : if (!buffer || !buffer->capacity || !iterator) {
400 1 : return NULL;
401 : }
402 1473 : if ((char *)iterator
403 1473 : >= (char *)buffer->data + ((buffer->count - 1) * buffer->sizeof_type)) {
404 86 : return CCC_flat_buffer_end(buffer);
405 : }
406 1387 : return (unsigned char *)iterator + buffer->sizeof_type;
407 1474 : }
408 :
409 : void *
410 386 : CCC_flat_buffer_reverse_next(
411 : CCC_Flat_buffer const *const buffer, void const *const iterator
412 : ) {
413 386 : if (!buffer || !buffer->data || !iterator) {
414 1 : return NULL;
415 : }
416 385 : if (iterator <= CCC_flat_buffer_reverse_end(buffer)) {
417 1 : return CCC_flat_buffer_reverse_end(buffer);
418 : }
419 384 : return (char *)iterator - buffer->sizeof_type;
420 386 : }
421 :
422 : void *
423 1328 : CCC_flat_buffer_end(CCC_Flat_buffer const *const buffer) {
424 1328 : if (!buffer || !buffer->data) {
425 2 : return NULL;
426 : }
427 2652 : return (unsigned char *)buffer->data
428 1326 : + (buffer->count * buffer->sizeof_type);
429 1328 : }
430 :
431 : /** We accept that reverse_end is out of bounds and the address before start.
432 : Even if the array base was somehow 0 and wrapping occurred upon subtraction the
433 : iterator would eventually reach this same address through reverse_next and be
434 : compared to it in the main user loop. */
435 : void *
436 740 : CCC_flat_buffer_reverse_end(CCC_Flat_buffer const *const buffer) {
437 740 : if (!buffer || !buffer->data) {
438 1 : return NULL;
439 : }
440 739 : return (unsigned char *)buffer->data - buffer->sizeof_type;
441 740 : }
442 :
443 : CCC_Count
444 91 : CCC_flat_buffer_index(
445 : CCC_Flat_buffer const *const buffer, void const *const slot
446 : ) {
447 91 : if (!buffer || !buffer->data || !slot || slot < buffer->data
448 89 : || (char *)slot
449 176 : >= ((char *)buffer->data
450 88 : + (buffer->capacity * buffer->sizeof_type))) {
451 3 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
452 : }
453 0 : assert(
454 88 : slot >= buffer->data && "positive pointer difference is caught at entry"
455 : );
456 176 : return (CCC_Count){
457 : .count
458 88 : = ((size_t)((char *)slot - ((char *)buffer->data))
459 88 : / buffer->sizeof_type),
460 : };
461 91 : }
462 :
463 : CCC_Result
464 3 : CCC_flat_buffer_count_plus(CCC_Flat_buffer *const buffer, size_t const count) {
465 3 : if (!buffer) {
466 1 : return CCC_RESULT_ARGUMENT_ERROR;
467 : }
468 2 : size_t new_count = 0;
469 2 : if (ckd_add(&new_count, buffer->count, count)) {
470 0 : return CCC_RESULT_ALLOCATOR_ERROR;
471 : }
472 2 : if (new_count > buffer->capacity) {
473 1 : buffer->count = buffer->capacity;
474 1 : return CCC_RESULT_ARGUMENT_ERROR;
475 : }
476 1 : buffer->count = new_count;
477 1 : return CCC_RESULT_OK;
478 3 : }
479 :
480 : CCC_Result
481 3 : CCC_flat_buffer_count_minus(CCC_Flat_buffer *const buffer, size_t const count) {
482 3 : if (!buffer) {
483 1 : return CCC_RESULT_ARGUMENT_ERROR;
484 : }
485 2 : if (count > buffer->count) {
486 1 : buffer->count = 0;
487 1 : return CCC_RESULT_ARGUMENT_ERROR;
488 : }
489 1 : buffer->count -= count;
490 1 : return CCC_RESULT_OK;
491 3 : }
492 :
493 : CCC_Result
494 3 : CCC_flat_buffer_count_set(CCC_Flat_buffer *const buffer, size_t const count) {
495 3 : if (!buffer) {
496 1 : return CCC_RESULT_ARGUMENT_ERROR;
497 : }
498 2 : if (count > buffer->capacity) {
499 1 : buffer->count = buffer->capacity;
500 1 : return CCC_RESULT_ARGUMENT_ERROR;
501 : }
502 1 : buffer->count = count;
503 1 : return CCC_RESULT_OK;
504 3 : }
505 :
506 : CCC_Count
507 3 : CCC_flat_buffer_count_bytes(CCC_Flat_buffer const *buffer) {
508 3 : if (!buffer) {
509 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
510 : }
511 : /* No overflow check needed if buffer already exists. */
512 2 : return (CCC_Count){.count = buffer->count * buffer->sizeof_type};
513 3 : }
514 :
515 : CCC_Count
516 2 : CCC_flat_buffer_capacity_bytes(CCC_Flat_buffer const *buffer) {
517 2 : if (!buffer) {
518 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
519 : }
520 : /* No overflow check needed if buffer already exists. */
521 2 : return (CCC_Count){
522 1 : .count = buffer->capacity * buffer->sizeof_type,
523 : };
524 2 : }
525 :
526 : CCC_Result
527 18 : CCC_flat_buffer_copy(
528 : CCC_Flat_buffer *const destination,
529 : CCC_Flat_buffer const *const source,
530 : CCC_Allocator const *const allocator
531 : ) {
532 18 : if (!destination || !source || source == destination || !allocator
533 16 : || (destination->capacity < source->capacity && !allocator->allocate)) {
534 6 : return CCC_RESULT_ARGUMENT_ERROR;
535 : }
536 12 : if (!source->capacity) {
537 1 : return CCC_RESULT_OK;
538 : }
539 11 : if (destination->capacity < source->capacity) {
540 16 : CCC_Result const r = CCC_flat_buffer_allocate(
541 8 : destination, source->capacity, allocator
542 : );
543 8 : if (r != CCC_RESULT_OK) {
544 1 : return r;
545 : }
546 7 : destination->capacity = source->capacity;
547 8 : }
548 10 : if (!source->data || !destination->data) {
549 1 : return CCC_RESULT_ARGUMENT_ERROR;
550 : }
551 9 : destination->count = source->count;
552 9 : (void)memcpy(
553 9 : destination->data, source->data, source->capacity * source->sizeof_type
554 : );
555 9 : return CCC_RESULT_OK;
556 18 : }
557 :
558 : void *
559 11 : CCC_flat_buffer_data(CCC_Flat_buffer const *const buffer) {
560 11 : return buffer ? buffer->data : NULL;
561 : }
562 :
563 : /*====================== Static Helpers ==================================*/
564 :
565 : static inline void *
566 38 : at(struct CCC_Flat_buffer const *const buffer, size_t const i) {
567 38 : return ((char *)buffer->data + (i * buffer->sizeof_type));
568 : }
|
