Wed, 16 Nov 2022 22:27:46 +0100
#219 array list: implement add and at
Add uses the low level cx_array_copy function which is
now also implemented, but not tested by individual unit
tests.
src/array_list.c | file | annotate | diff | comparison | revisions | |
src/cx/array_list.h | file | annotate | diff | comparison | revisions | |
test/test_list.cpp | file | annotate | diff | comparison | revisions |
1.1 --- a/src/array_list.c Sun Nov 13 13:29:15 2022 +0100 1.2 +++ b/src/array_list.c Wed Nov 16 22:27:46 2022 +0100 1.3 @@ -27,20 +27,91 @@ 1.4 */ 1.5 1.6 #include "cx/array_list.h" 1.7 +#include <assert.h> 1.8 +#include <string.h> 1.9 1.10 /* LOW LEVEL ARRAY LIST FUNCTIONS */ 1.11 1.12 +enum cx_array_coppy_result cx_array_copy( 1.13 + void **target, 1.14 + size_t *size, 1.15 + size_t *capacity, 1.16 + size_t index, 1.17 + void const *src, 1.18 + size_t elem_size, 1.19 + size_t elem_count, 1.20 + struct cx_array_reallocator_s *reallocator 1.21 +) { 1.22 + /* assert pointers */ 1.23 + assert(target != NULL); 1.24 + assert(size != NULL); 1.25 + assert(src != NULL); 1.26 1.27 + /* determine capacity */ 1.28 + size_t cap = capacity == NULL ? *size : *capacity; 1.29 + 1.30 + /* check if resize is required */ 1.31 + size_t newsize = index + elem_count; 1.32 + bool needrealloc = newsize > cap; 1.33 + 1.34 + /* reallocate if possible */ 1.35 + if (needrealloc) { 1.36 + /* a reallocator and a capacity variable must be available */ 1.37 + if (reallocator == NULL || capacity == NULL) { 1.38 + return CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED; 1.39 + } 1.40 + 1.41 + /* increase capacity linearly */ 1.42 + cap += 16; 1.43 + 1.44 + /* perform reallocation */ 1.45 + void *newmem = reallocator->realloc( 1.46 + *target, cap, elem_size, reallocator 1.47 + ); 1.48 + if (newmem == NULL) { 1.49 + return CX_ARRAY_COPY_REALLOC_FAILED; 1.50 + } 1.51 + 1.52 + /* store new pointer and capacity */ 1.53 + *target = newmem; 1.54 + *capacity = cap; 1.55 + } 1.56 + 1.57 + /* determine target pointer */ 1.58 + char *start = *target; 1.59 + start += index * elem_size; 1.60 + 1.61 + /* copy elements and set new size */ 1.62 + memcpy(start, src, elem_count * elem_size); 1.63 + *size = newsize; 1.64 + 1.65 + /* return successfully */ 1.66 + return CX_ARRAY_COPY_SUCCESS; 1.67 +} 1.68 1.69 /* HIGH LEVEL ARRAY LIST FUNCTIONS */ 1.70 1.71 typedef struct { 1.72 struct cx_list_s base; 1.73 void *data; 1.74 + struct cx_array_reallocator_s reallocator; 1.75 } cx_array_list; 1.76 1.77 +static void *cx_arl_realloc( 1.78 + void *array, 1.79 + size_t capacity, 1.80 + size_t elem_size, 1.81 + struct cx_array_reallocator_s *alloc 1.82 +) { 1.83 + /* retrieve the pointer to the list allocator */ 1.84 + CxAllocator const *al = alloc->ptr1; 1.85 + 1.86 + /* use the list allocator to reallocate the memory */ 1.87 + return cxRealloc(al, array, capacity * elem_size); 1.88 +} 1.89 + 1.90 static void cx_arl_destructor(struct cx_list_s *list) { 1.91 - cx_array_list *arl = (cx_array_list*) list; 1.92 + cx_array_list *arl = (cx_array_list *) list; 1.93 cxFree(list->allocator, arl->data); 1.94 } 1.95 1.96 @@ -48,7 +119,17 @@ 1.97 struct cx_list_s *list, 1.98 void const *elem 1.99 ) { 1.100 - return 1; 1.101 + cx_array_list *arl = (cx_array_list *) list; 1.102 + return cx_array_copy( 1.103 + &arl->data, 1.104 + &list->size, 1.105 + &list->capacity, 1.106 + list->size, 1.107 + elem, 1.108 + list->itemsize, 1.109 + 1, 1.110 + &arl->reallocator 1.111 + ); 1.112 } 1.113 1.114 static int cx_arl_insert( 1.115 @@ -74,11 +155,17 @@ 1.116 return 1; 1.117 } 1.118 1.119 -static void * cx_arl_at( 1.120 +static void *cx_arl_at( 1.121 struct cx_list_s const *list, 1.122 size_t index 1.123 ) { 1.124 - return NULL; 1.125 + if (index < list->size) { 1.126 + cx_array_list const *arl = (cx_array_list const *) list; 1.127 + char *space = arl->data; 1.128 + return space + index * list->itemsize; 1.129 + } else { 1.130 + return NULL; 1.131 + } 1.132 } 1.133 1.134 static size_t cx_arl_find( 1.135 @@ -147,5 +234,9 @@ 1.136 list->base.itemsize = item_size; 1.137 list->base.capacity = initial_capacity; 1.138 1.139 + /* configure the reallocator */ 1.140 + list->reallocator.realloc = cx_arl_realloc; 1.141 + list->reallocator.ptr1 = (void *) allocator; 1.142 + 1.143 return (CxList *) list; 1.144 }
2.1 --- a/src/cx/array_list.h Sun Nov 13 13:29:15 2022 +0100 2.2 +++ b/src/cx/array_list.h Wed Nov 16 22:27:46 2022 +0100 2.3 @@ -89,6 +89,15 @@ 2.4 }; 2.5 2.6 /** 2.7 + * Return codes for cx_array_copy(). 2.8 + */ 2.9 +enum cx_array_coppy_result { 2.10 + CX_ARRAY_COPY_SUCCESS, 2.11 + CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED, 2.12 + CX_ARRAY_COPY_REALLOC_FAILED, 2.13 +}; 2.14 + 2.15 +/** 2.16 * Copies elements from one array to another. 2.17 * 2.18 * The elements are copied to the \p target array at the specified \p index, 2.19 @@ -110,9 +119,9 @@ 2.20 * @param elem_count the number of elements to copy 2.21 * @param reallocator the array re-allocator to use, or \c NULL 2.22 * if re-allocation shall not happen 2.23 - * @return zero on success, non-zero on failure 2.24 + * @return zero on success, non-zero error code on failure 2.25 */ 2.26 -int cx_array_copy( 2.27 +enum cx_array_coppy_result cx_array_copy( 2.28 void **target, 2.29 size_t *size, 2.30 size_t *capacity, 2.31 @@ -120,7 +129,7 @@ 2.32 void const *src, 2.33 size_t elem_size, 2.34 size_t elem_count, 2.35 - struct cx_array_reallocator_s const *reallocator 2.36 + struct cx_array_reallocator_s *reallocator 2.37 ) __attribute__((__nonnull__(1, 2, 5))); 2.38 2.39 /**
3.1 --- a/test/test_list.cpp Sun Nov 13 13:29:15 2022 +0100 3.2 +++ b/test/test_list.cpp Wed Nov 16 22:27:46 2022 +0100 3.3 @@ -827,7 +827,6 @@ 3.4 } 3.5 3.6 TEST_F(ArrayList, cxListAdd) { 3.7 - ASSERT_EQ(1,0); // TODO: remove when implemented 3.8 CxList *list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 8)); 3.9 verifyAdd(list, false); 3.10 } 3.11 @@ -867,7 +866,6 @@ 3.12 } 3.13 3.14 TEST_F(ArrayList, cxListAt) { 3.15 - ASSERT_EQ(1,0); // TODO: remove when implemented 3.16 verifyAt(arrayListFromTestData()); 3.17 } 3.18