src/array_list.c@de5d3ee6435f
src/array_list.c
Wed, 16 Nov 2022 22:27:46 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Wed, 16 Nov 2022 22:27:46 +0100
- changeset 610
- de5d3ee6435f
- parent 607
- 2d99e978dc34
- child 611
- 77efa5163ae5
- permissions
- -rw-r--r--
#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.
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 */
29 #include "cx/array_list.h"
30 #include <assert.h>
31 #include <string.h>
33 /* LOW LEVEL ARRAY LIST FUNCTIONS */
35 enum cx_array_coppy_result cx_array_copy(
36 void **target,
37 size_t *size,
38 size_t *capacity,
39 size_t index,
40 void const *src,
41 size_t elem_size,
42 size_t elem_count,
43 struct cx_array_reallocator_s *reallocator
44 ) {
45 /* assert pointers */
46 assert(target != NULL);
47 assert(size != NULL);
48 assert(src != NULL);
50 /* determine capacity */
51 size_t cap = capacity == NULL ? *size : *capacity;
53 /* check if resize is required */
54 size_t newsize = index + elem_count;
55 bool needrealloc = newsize > cap;
57 /* reallocate if possible */
58 if (needrealloc) {
59 /* a reallocator and a capacity variable must be available */
60 if (reallocator == NULL || capacity == NULL) {
61 return CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED;
62 }
64 /* increase capacity linearly */
65 cap += 16;
67 /* perform reallocation */
68 void *newmem = reallocator->realloc(
69 *target, cap, elem_size, reallocator
70 );
71 if (newmem == NULL) {
72 return CX_ARRAY_COPY_REALLOC_FAILED;
73 }
75 /* store new pointer and capacity */
76 *target = newmem;
77 *capacity = cap;
78 }
80 /* determine target pointer */
81 char *start = *target;
82 start += index * elem_size;
84 /* copy elements and set new size */
85 memcpy(start, src, elem_count * elem_size);
86 *size = newsize;
88 /* return successfully */
89 return CX_ARRAY_COPY_SUCCESS;
90 }
92 /* HIGH LEVEL ARRAY LIST FUNCTIONS */
94 typedef struct {
95 struct cx_list_s base;
96 void *data;
97 struct cx_array_reallocator_s reallocator;
98 } cx_array_list;
100 static void *cx_arl_realloc(
101 void *array,
102 size_t capacity,
103 size_t elem_size,
104 struct cx_array_reallocator_s *alloc
105 ) {
106 /* retrieve the pointer to the list allocator */
107 CxAllocator const *al = alloc->ptr1;
109 /* use the list allocator to reallocate the memory */
110 return cxRealloc(al, array, capacity * elem_size);
111 }
113 static void cx_arl_destructor(struct cx_list_s *list) {
114 cx_array_list *arl = (cx_array_list *) list;
115 cxFree(list->allocator, arl->data);
116 }
118 static int cx_arl_add(
119 struct cx_list_s *list,
120 void const *elem
121 ) {
122 cx_array_list *arl = (cx_array_list *) list;
123 return cx_array_copy(
124 &arl->data,
125 &list->size,
126 &list->capacity,
127 list->size,
128 elem,
129 list->itemsize,
130 1,
131 &arl->reallocator
132 );
133 }
135 static int cx_arl_insert(
136 struct cx_list_s *list,
137 size_t index,
138 void const *elem
139 ) {
140 return 1;
141 }
143 static int cx_arl_insert_iter(
144 struct cx_iterator_s *iter,
145 void const *elem,
146 int prepend
147 ) {
148 return 1;
149 }
151 static int cx_arl_remove(
152 struct cx_list_s *list,
153 size_t index
154 ) {
155 return 1;
156 }
158 static void *cx_arl_at(
159 struct cx_list_s const *list,
160 size_t index
161 ) {
162 if (index < list->size) {
163 cx_array_list const *arl = (cx_array_list const *) list;
164 char *space = arl->data;
165 return space + index * list->itemsize;
166 } else {
167 return NULL;
168 }
169 }
171 static size_t cx_arl_find(
172 struct cx_list_s const *list,
173 void const *elem
174 ) {
175 return 0;
176 }
178 static void cx_arl_sort(struct cx_list_s *list) {
180 }
182 static int cx_arl_compare(
183 struct cx_list_s const *list,
184 struct cx_list_s const *other
185 ) {
187 }
189 static void cx_arl_reverse(struct cx_list_s *list) {
191 }
193 static struct cx_iterator_s cx_arl_iterator(
194 struct cx_list_s *list,
195 size_t index
196 ) {
197 struct cx_iterator_s iter;
199 return iter;
200 }
202 static cx_list_class cx_array_list_class = {
203 cx_arl_destructor,
204 cx_arl_add,
205 cx_arl_insert,
206 cx_arl_insert_iter,
207 cx_arl_remove,
208 cx_arl_at,
209 cx_arl_find,
210 cx_arl_sort,
211 cx_arl_compare,
212 cx_arl_reverse,
213 cx_arl_iterator,
214 };
216 CxList *cxArrayListCreate(
217 CxAllocator const *allocator,
218 CxListComparator comparator,
219 size_t item_size,
220 size_t initial_capacity
221 ) {
222 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list));
223 if (list == NULL) return NULL;
225 list->data = cxCalloc(allocator, initial_capacity, item_size);
226 if (list->data == NULL) {
227 cxFree(allocator, list);
228 return NULL;
229 }
231 list->base.cl = &cx_array_list_class;
232 list->base.allocator = allocator;
233 list->base.cmpfunc = comparator;
234 list->base.itemsize = item_size;
235 list->base.capacity = initial_capacity;
237 /* configure the reallocator */
238 list->reallocator.realloc = cx_arl_realloc;
239 list->reallocator.ptr1 = (void *) allocator;
241 return (CxList *) list;
242 }
