1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 #include "cx/array_list.h"
30 #include "cx/compare.h"
31 #include <assert.h>
32 #include <string.h>
33
34 // Default array reallocator
35
36 static void *cx_array_default_realloc(
37 void *array,
38 size_t capacity,
39 size_t elem_size,
40 __attribute__((__unused__)) struct cx_array_reallocator_s *alloc
41 ) {
42 return realloc(array, capacity * elem_size);
43 }
44
45 struct cx_array_reallocator_s cx_array_default_reallocator_impl = {
46 cx_array_default_realloc, NULL, NULL, 0, 0
47 };
48
49 struct cx_array_reallocator_s *cx_array_default_reallocator = &cx_array_default_reallocator_impl;
50
51 // LOW LEVEL ARRAY LIST FUNCTIONS
52
53 enum cx_array_result cx_array_copy(
54 void **target,
55 size_t *size,
56 size_t *capacity,
57 size_t index,
58 void const *src,
59 size_t elem_size,
60 size_t elem_count,
61 struct cx_array_reallocator_s *reallocator
62 ) {
63 // assert pointers
64 assert(target != NULL);
65 assert(size != NULL);
66 assert(src != NULL);
67
68 // determine capacity
69 size_t cap = capacity == NULL ? *size : *capacity;
70
71 // check if resize is required
72 size_t minsize = index + elem_count;
73 size_t newsize = *size < minsize ? minsize : *size;
74 bool needrealloc = newsize > cap;
75
76 // reallocate if possible
77 if (needrealloc) {
78 // a reallocator and a capacity variable must be available
79 if (reallocator == NULL || capacity == NULL) {
80 return CX_ARRAY_REALLOC_NOT_SUPPORTED;
81 }
82
83 // check, if we need to repair the src pointer
84 uintptr_t targetaddr = (uintptr_t) *target;
85 uintptr_t srcaddr = (uintptr_t) src;
86 bool repairsrc = targetaddr <= srcaddr
87 && srcaddr < targetaddr + cap * elem_size;
88
89 // calculate new capacity (next number divisible by 16)
90 cap = newsize - (newsize % 16) + 16;
91 assert(cap > newsize);
92
93 // perform reallocation
94 void *newmem = reallocator->realloc(
95 *target, cap, elem_size, reallocator
96 );
97 if (newmem == NULL) {
98 return CX_ARRAY_REALLOC_FAILED;
99 }
100
101 // repair src pointer, if necessary
102 if (repairsrc) {
103 src = ((char *) newmem) + (srcaddr - targetaddr);
104 }
105
106 // store new pointer and capacity
107 *target = newmem;
108 *capacity = cap;
109 }
110
111 // determine target pointer
112 char *start = *target;
113 start += index * elem_size;
114
115 // copy elements and set new size
116 memmove(start, src, elem_count * elem_size);
117 *size = newsize;
118
119 // return successfully
120 return CX_ARRAY_SUCCESS;
121 }
122
123 #ifndef CX_ARRAY_SWAP_SBO_SIZE
124 #define CX_ARRAY_SWAP_SBO_SIZE 128
125 #endif
126 unsigned cx_array_swap_sbo_size = CX_ARRAY_SWAP_SBO_SIZE;
127
128 void cx_array_swap(
129 void *arr,
130 size_t elem_size,
131 size_t idx1,
132 size_t idx2
133 ) {
134 assert(arr != NULL);
135
136 // short circuit
137 if (idx1 == idx2) return;
138
139 char sbo_mem[CX_ARRAY_SWAP_SBO_SIZE];
140 void *tmp;
141
142 // decide if we can use the local buffer
143 if (elem_size > CX_ARRAY_SWAP_SBO_SIZE) {
144 tmp = malloc(elem_size);
145 // we don't want to enforce error handling
146 if (tmp == NULL) abort();
147 } else {
148 tmp = sbo_mem;
149 }
150
151 // calculate memory locations
152 char *left = arr, *right = arr;
153 left += idx1 * elem_size;
154 right += idx2 * elem_size;
155
156 // three-way swap
157 memcpy(tmp, left, elem_size);
158 memcpy(left, right, elem_size);
159 memcpy(right, tmp, elem_size);
160
161 // free dynamic memory, if it was needed
162 if (tmp != sbo_mem) {
163 free(tmp);
164 }
165 }
166
167 // HIGH LEVEL ARRAY LIST FUNCTIONS
168
169 typedef struct {
170 struct cx_list_s base;
171 void *data;
172 size_t capacity;
173 struct cx_array_reallocator_s reallocator;
174 } cx_array_list;
175
176 static void *cx_arl_realloc(
177 void *array,
178 size_t capacity,
179 size_t elem_size,
180 struct cx_array_reallocator_s *alloc
181 ) {
182 // retrieve the pointer to the list allocator
183 CxAllocator const *al = alloc->ptr1;
184
185 // use the list allocator to reallocate the memory
186 return cxRealloc(al, array, capacity * elem_size);
187 }
188
189 static void cx_arl_destructor(struct cx_list_s *list) {
190 cx_array_list *arl = (cx_array_list *) list;
191
192 char *ptr = arl->data;
193
194 if (list->collection.simple_destructor) {
195 for (size_t i = 0; i < list->collection.size; i++) {
196 cx_invoke_simple_destructor(list, ptr);
197 ptr += list->collection.elem_size;
198 }
199 }
200 if (list->collection.advanced_destructor) {
201 for (size_t i = 0; i < list->collection.size; i++) {
202 cx_invoke_advanced_destructor(list, ptr);
203 ptr += list->collection.elem_size;
204 }
205 }
206
207 cxFree(list->collection.allocator, arl->data);
208 cxFree(list->collection.allocator, list);
209 }
210
211 static size_t cx_arl_insert_array(
212 struct cx_list_s *list,
213 size_t index,
214 void const *array,
215 size_t n
216 ) {
217 // out of bounds and special case check
218 if (index > list->collection.size || n == 0) return 0;
219
220 // get a correctly typed pointer to the list
221 cx_array_list *arl = (cx_array_list *) list;
222
223 // do we need to move some elements?
224 if (index < list->collection.size) {
225 char const *first_to_move = (char const *) arl->data;
226 first_to_move += index * list->collection.elem_size;
227 size_t elems_to_move = list->collection.size - index;
228 size_t start_of_moved = index + n;
229
230 if (CX_ARRAY_SUCCESS != cx_array_copy(
231 &arl->data,
232 &list->collection.size,
233 &arl->capacity,
234 start_of_moved,
235 first_to_move,
236 list->collection.elem_size,
237 elems_to_move,
238 &arl->reallocator
239 )) {
240 // if moving existing elems is unsuccessful, abort
241 return 0;
242 }
243 }
244
245 // note that if we had to move the elements, the following operation
246 // is guaranteed to succeed, because we have the memory already allocated
247 // therefore, it is impossible to leave this function with an invalid array
248
249 // place the new elements
250 if (CX_ARRAY_SUCCESS == cx_array_copy(
251 &arl->data,
252 &list->collection.size,
253 &arl->capacity,
254 index,
255 array,
256 list->collection.elem_size,
257 n,
258 &arl->reallocator
259 )) {
260 return n;
261 } else {
262 // array list implementation is "all or nothing"
263 return 0;
264 }
265 }
266
267 static int cx_arl_insert_element(
268 struct cx_list_s *list,
269 size_t index,
270 void const *element
271 ) {
272 return 1 != cx_arl_insert_array(list, index, element, 1);
273 }
274
275 static int cx_arl_insert_iter(
276 struct cx_iterator_s *iter,
277 void const *elem,
278 int prepend
279 ) {
280 struct cx_list_s *list = iter->src_handle.m;
281 if (iter->index < list->collection.size) {
282 int result = cx_arl_insert_element(
283 list,
284 iter->index + 1 - prepend,
285 elem
286 );
287 if (result == 0 && prepend != 0) {
288 iter->index++;
289 iter->elem_handle = ((char *) iter->elem_handle) + list->collection.elem_size;
290 }
291 return result;
292 } else {
293 int result = cx_arl_insert_element(list, list->collection.size, elem);
294 iter->index = list->collection.size;
295 return result;
296 }
297 }
298
299 static int cx_arl_remove(
300 struct cx_list_s *list,
301 size_t index
302 ) {
303 cx_array_list *arl = (cx_array_list *) list;
304
305 // out-of-bounds check
306 if (index >= list->collection.size) {
307 return 1;
308 }
309
310 // content destruction
311 cx_invoke_destructor(list, ((char *) arl->data) + index * list->collection.elem_size);
312
313 // short-circuit removal of last element
314 if (index == list->collection.size - 1) {
315 list->collection.size--;
316 return 0;
317 }
318
319 // just move the elements starting at index to the left
320 int result = cx_array_copy(
321 &arl->data,
322 &list->collection.size,
323 &arl->capacity,
324 index,
325 ((char *) arl->data) + (index + 1) * list->collection.elem_size,
326 list->collection.elem_size,
327 list->collection.size - index - 1,
328 &arl->reallocator
329 );
330
331 // cx_array_copy cannot fail, array cannot grow
332 assert(result == 0);
333
334 // decrease the size
335 list->collection.size--;
336
337 return 0;
338 }
339
340 static void cx_arl_clear(struct cx_list_s *list) {
341 if (list->collection.size == 0) return;
342
343 cx_array_list *arl = (cx_array_list *) list;
344 char *ptr = arl->data;
345
346 if (list->collection.simple_destructor) {
347 for (size_t i = 0; i < list->collection.size; i++) {
348 cx_invoke_simple_destructor(list, ptr);
349 ptr += list->collection.elem_size;
350 }
351 }
352 if (list->collection.advanced_destructor) {
353 for (size_t i = 0; i < list->collection.size; i++) {
354 cx_invoke_advanced_destructor(list, ptr);
355 ptr += list->collection.elem_size;
356 }
357 }
358
359 memset(arl->data, 0, list->collection.size * list->collection.elem_size);
360 list->collection.size = 0;
361 }
362
363 static int cx_arl_swap(
364 struct cx_list_s *list,
365 size_t i,
366 size_t j
367 ) {
368 if (i >= list->collection.size || j >= list->collection.size) return 1;
369 cx_array_list *arl = (cx_array_list *) list;
370 cx_array_swap(arl->data, list->collection.elem_size, i, j);
371 return 0;
372 }
373
374 static void *cx_arl_at(
375 struct cx_list_s const *list,
376 size_t index
377 ) {
378 if (index < list->collection.size) {
379 cx_array_list const *arl = (cx_array_list const *) list;
380 char *space = arl->data;
381 return space + index * list->collection.elem_size;
382 } else {
383 return NULL;
384 }
385 }
386
387 static ssize_t cx_arl_find_remove(
388 struct cx_list_s *list,
389 void const *elem,
390 bool remove
391 ) {
392 assert(list->collection.cmpfunc != NULL);
393 assert(list->collection.size < SIZE_MAX / 2);
394 char *cur = ((cx_array_list const *) list)->data;
395
396 for (ssize_t i = 0; i < (ssize_t) list->collection.size; i++) {
397 if (0 == list->collection.cmpfunc(elem, cur)) {
398 if (remove) {
399 if (0 == cx_arl_remove(list, i)) {
400 return i;
401 } else {
402 return -1;
403 }
404 } else {
405 return i;
406 }
407 }
408 cur += list->collection.elem_size;
409 }
410
411 return -1;
412 }
413
414 static void cx_arl_sort(struct cx_list_s *list) {
415 assert(list->collection.cmpfunc != NULL);
416 qsort(((cx_array_list *) list)->data,
417 list->collection.size,
418 list->collection.elem_size,
419 list->collection.cmpfunc
420 );
421 }
422
423 static int cx_arl_compare(
424 struct cx_list_s const *list,
425 struct cx_list_s const *other
426 ) {
427 assert(list->collection.cmpfunc != NULL);
428 if (list->collection.size == other->collection.size) {
429 char const *left = ((cx_array_list const *) list)->data;
430 char const *right = ((cx_array_list const *) other)->data;
431 for (size_t i = 0; i < list->collection.size; i++) {
432 int d = list->collection.cmpfunc(left, right);
433 if (d != 0) {
434 return d;
435 }
436 left += list->collection.elem_size;
437 right += other->collection.elem_size;
438 }
439 return 0;
440 } else {
441 return list->collection.size < other->collection.size ? -1 : 1;
442 }
443 }
444
445 static void cx_arl_reverse(struct cx_list_s *list) {
446 if (list->collection.size < 2) return;
447 void *data = ((cx_array_list const *) list)->data;
448 size_t half = list->collection.size / 2;
449 for (size_t i = 0; i < half; i++) {
450 cx_array_swap(data, list->collection.elem_size, i, list->collection.size - 1 - i);
451 }
452 }
453
454 static bool cx_arl_iter_valid(void const *it) {
455 struct cx_iterator_s const *iter = it;
456 struct cx_list_s const *list = iter->src_handle.c;
457 return iter->index < list->collection.size;
458 }
459
460 static void *cx_arl_iter_current(void const *it) {
461 struct cx_iterator_s const *iter = it;
462 return iter->elem_handle;
463 }
464
465 static void cx_arl_iter_next(void *it) {
466 struct cx_iterator_s *iter = it;
467 if (iter->base.remove) {
468 iter->base.remove = false;
469 cx_arl_remove(iter->src_handle.m, iter->index);
470 } else {
471 iter->index++;
472 iter->elem_handle =
473 ((char *) iter->elem_handle)
474 + ((struct cx_list_s const *) iter->src_handle.c)->collection.elem_size;
475 }
476 }
477
478 static void cx_arl_iter_prev(void *it) {
479 struct cx_iterator_s *iter = it;
480 cx_array_list const* list = iter->src_handle.c;
481 if (iter->base.remove) {
482 iter->base.remove = false;
483 cx_arl_remove(iter->src_handle.m, iter->index);
484 }
485 iter->index--;
486 if (iter->index < list->base.collection.size) {
487 iter->elem_handle = ((char *) list->data)
488 + iter->index * list->base.collection.elem_size;
489 }
490 }
491
492
493 static struct cx_iterator_s cx_arl_iterator(
494 struct cx_list_s const *list,
495 size_t index,
496 bool backwards
497 ) {
498 struct cx_iterator_s iter;
499
500 iter.index = index;
501 iter.src_handle.c = list;
502 iter.elem_handle = cx_arl_at(list, index);
503 iter.elem_size = list->collection.elem_size;
504 iter.elem_count = list->collection.size;
505 iter.base.valid = cx_arl_iter_valid;
506 iter.base.current = cx_arl_iter_current;
507 iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next;
508 iter.base.remove = false;
509 iter.base.mutating = false;
510
511 return iter;
512 }
513
514 static cx_list_class cx_array_list_class = {
515 cx_arl_destructor,
516 cx_arl_insert_element,
517 cx_arl_insert_array,
518 cx_arl_insert_iter,
519 cx_arl_remove,
520 cx_arl_clear,
521 cx_arl_swap,
522 cx_arl_at,
523 cx_arl_find_remove,
524 cx_arl_sort,
525 cx_arl_compare,
526 cx_arl_reverse,
527 cx_arl_iterator,
528 };
529
530 CxList *cxArrayListCreate(
531 CxAllocator const *allocator,
532 cx_compare_func comparator,
533 size_t elem_size,
534 size_t initial_capacity
535 ) {
536 if (allocator == NULL) {
537 allocator = cxDefaultAllocator;
538 }
539
540 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list));
541 if (list == NULL) return NULL;
542
543 list->base.cl = &cx_array_list_class;
544 list->base.collection.allocator = allocator;
545 list->capacity = initial_capacity;
546
547 if (elem_size > 0) {
548 list->base.collection.elem_size = elem_size;
549 list->base.collection.cmpfunc = comparator;
550 } else {
551 elem_size = sizeof(void *);
552 list->base.collection.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator;
553 cxListStorePointers((CxList *) list);
554 }
555
556 // allocate the array after the real elem_size is known
557 list->data = cxCalloc(allocator, initial_capacity, elem_size);
558 if (list->data == NULL) {
559 cxFree(allocator, list);
560 return NULL;
561 }
562
563 // configure the reallocator
564 list->reallocator.realloc = cx_arl_realloc;
565 list->reallocator.ptr1 = (void *) allocator;
566
567 return (CxList *) list;
568 }
569