Mercurial > hg > webserver / file comparison

comparison: src/ucx/array_list.c

src/ucx/array_list.c

changeset 438
22eca559aded
parent 436
1260fad21be7
child 490
d218607f5a7e
equal deleted inserted replaced
437:545010bc5e71 438:22eca559aded
29 #include "cx/array_list.h" 29 #include "cx/array_list.h"
30 #include <assert.h> 30 #include <assert.h>
31 #include <string.h> 31 #include <string.h>
32 #include <stdint.h> 32 #include <stdint.h>
33 33
34 /* LOW LEVEL ARRAY LIST FUNCTIONS */ 34 // LOW LEVEL ARRAY LIST FUNCTIONS
35 35
36 enum cx_array_copy_result cx_array_copy( 36 enum cx_array_copy_result cx_array_copy(
37 void **target, 37 void **target,
38 size_t *size, 38 size_t *size,
39 size_t *capacity, 39 size_t *capacity,
41 void const *src, 41 void const *src,
42 size_t elem_size, 42 size_t elem_size,
43 size_t elem_count, 43 size_t elem_count,
44 struct cx_array_reallocator_s *reallocator 44 struct cx_array_reallocator_s *reallocator
45 ) { 45 ) {
46 /* assert pointers */ 46 // assert pointers
47 assert(target != NULL); 47 assert(target != NULL);
48 assert(size != NULL); 48 assert(size != NULL);
49 assert(src != NULL); 49 assert(src != NULL);
50 50
51 /* determine capacity */ 51 // determine capacity
52 size_t cap = capacity == NULL ? *size : *capacity; 52 size_t cap = capacity == NULL ? *size : *capacity;
53 53
54 /* check if resize is required */ 54 // check if resize is required
55 size_t newsize = index + elem_count; 55 size_t minsize = index + elem_count;
56 size_t newsize = *size < minsize ? minsize : *size;
56 bool needrealloc = newsize > cap; 57 bool needrealloc = newsize > cap;
57 58
58 /* reallocate if possible */ 59 // reallocate if possible
59 if (needrealloc) { 60 if (needrealloc) {
60 /* a reallocator and a capacity variable must be available */ 61 // a reallocator and a capacity variable must be available
61 if (reallocator == NULL || capacity == NULL) { 62 if (reallocator == NULL || capacity == NULL) {
62 return CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED; 63 return CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED;
63 } 64 }
64 65
65 /* check, if we need to repair the src pointer */ 66 // check, if we need to repair the src pointer
66 uintptr_t targetaddr = (uintptr_t) *target; 67 uintptr_t targetaddr = (uintptr_t) *target;
67 uintptr_t srcaddr = (uintptr_t) src; 68 uintptr_t srcaddr = (uintptr_t) src;
68 bool repairsrc = targetaddr <= srcaddr 69 bool repairsrc = targetaddr <= srcaddr
69 && srcaddr < targetaddr + cap * elem_size; 70 && srcaddr < targetaddr + cap * elem_size;
70 71
71 /* increase capacity linearly */ 72 // calculate new capacity (next number divisible by 16)
72 cap += 16; 73 cap = newsize - (newsize % 16) + 16;
73 74 assert(cap > newsize);
74 /* perform reallocation */ 75
76 // perform reallocation
75 void *newmem = reallocator->realloc( 77 void *newmem = reallocator->realloc(
76 *target, cap, elem_size, reallocator 78 *target, cap, elem_size, reallocator
77 ); 79 );
78 if (newmem == NULL) { 80 if (newmem == NULL) {
79 return CX_ARRAY_COPY_REALLOC_FAILED; 81 return CX_ARRAY_COPY_REALLOC_FAILED;
80 } 82 }
81 83
82 /* repair src pointer, if necessary */ 84 // repair src pointer, if necessary
83 if (repairsrc) { 85 if (repairsrc) {
84 src = ((char *) newmem) + (srcaddr - targetaddr); 86 src = ((char *) newmem) + (srcaddr - targetaddr);
85 } 87 }
86 88
87 /* store new pointer and capacity */ 89 // store new pointer and capacity
88 *target = newmem; 90 *target = newmem;
89 *capacity = cap; 91 *capacity = cap;
90 } 92 }
91 93
92 /* determine target pointer */ 94 // determine target pointer
93 char *start = *target; 95 char *start = *target;
94 start += index * elem_size; 96 start += index * elem_size;
95 97
96 /* copy elements and set new size */ 98 // copy elements and set new size
97 memmove(start, src, elem_count * elem_size); 99 memmove(start, src, elem_count * elem_size);
98 *size = newsize; 100 *size = newsize;
99 101
100 /* return successfully */ 102 // return successfully
101 return CX_ARRAY_COPY_SUCCESS; 103 return CX_ARRAY_COPY_SUCCESS;
102 } 104 }
103 105
104 /* HIGH LEVEL ARRAY LIST FUNCTIONS */ 106 #define CX_ARRAY_SWAP_SBO_SIZE 512
107
108 void cx_array_swap(
109 void *arr,
110 size_t elem_size,
111 size_t idx1,
112 size_t idx2
113 ) {
114 // short circuit
115 if (idx1 == idx2) return;
116
117 char sbo_mem[CX_ARRAY_SWAP_SBO_SIZE];
118 void *tmp;
119
120 // decide if we can use the local buffer
121 if (elem_size > CX_ARRAY_SWAP_SBO_SIZE) {
122 tmp = malloc(elem_size);
123 // we don't want to enforce error handling
124 if (tmp == NULL) abort();
125 } else {
126 tmp = sbo_mem;
127 }
128
129 // calculate memory locations
130 char *left = arr, *right = arr;
131 left += idx1 * elem_size;
132 right += idx2 * elem_size;
133
134 // three-way swap
135 memcpy(tmp, left, elem_size);
136 memcpy(left, right, elem_size);
137 memcpy(right, tmp, elem_size);
138
139 // free dynamic memory, if it was needed
140 if (tmp != sbo_mem) {
141 free(tmp);
142 }
143 }
144
145 // HIGH LEVEL ARRAY LIST FUNCTIONS
105 146
106 typedef struct { 147 typedef struct {
107 struct cx_list_s base; 148 struct cx_list_s base;
108 void *data; 149 void *data;
109 struct cx_array_reallocator_s reallocator; 150 struct cx_array_reallocator_s reallocator;
113 void *array, 154 void *array,
114 size_t capacity, 155 size_t capacity,
115 size_t elem_size, 156 size_t elem_size,
116 struct cx_array_reallocator_s *alloc 157 struct cx_array_reallocator_s *alloc
117 ) { 158 ) {
118 /* retrieve the pointer to the list allocator */ 159 // retrieve the pointer to the list allocator
119 CxAllocator const *al = alloc->ptr1; 160 CxAllocator const *al = alloc->ptr1;
120 161
121 /* use the list allocator to reallocate the memory */ 162 // use the list allocator to reallocate the memory
122 return cxRealloc(al, array, capacity * elem_size); 163 return cxRealloc(al, array, capacity * elem_size);
123 } 164 }
124 165
125 static void cx_arl_destructor(struct cx_list_s *list) { 166 static void cx_arl_destructor(struct cx_list_s *list) {
126 cx_array_list *arl = (cx_array_list *) list; 167 cx_array_list *arl = (cx_array_list *) list;
142 1, 183 1,
143 &arl->reallocator 184 &arl->reallocator
144 ); 185 );
145 } 186 }
146 187
188 static size_t cx_arl_add_array(
189 struct cx_list_s *list,
190 void const *array,
191 size_t n
192 ) {
193 cx_array_list *arl = (cx_array_list *) list;
194 if (CX_ARRAY_COPY_SUCCESS == cx_array_copy(
195 &arl->data,
196 &list->size,
197 &list->capacity,
198 list->size,
199 array,
200 list->itemsize,
201 n,
202 &arl->reallocator
203 )) {
204 return n;
205 } else {
206 // array list implementation is "all or nothing"
207 return 0;
208 }
209 }
210
147 static int cx_arl_insert( 211 static int cx_arl_insert(
148 struct cx_list_s *list, 212 struct cx_list_s *list,
149 size_t index, 213 size_t index,
150 void const *elem 214 void const *elem
151 ) { 215 ) {
154 } else if (index == list->size) { 218 } else if (index == list->size) {
155 return cx_arl_add(list, elem); 219 return cx_arl_add(list, elem);
156 } else { 220 } else {
157 cx_array_list *arl = (cx_array_list *) list; 221 cx_array_list *arl = (cx_array_list *) list;
158 222
159 /* move elements starting at index to the right */ 223 // move elements starting at index to the right
160 if (cx_array_copy( 224 if (cx_array_copy(
161 &arl->data, 225 &arl->data,
162 &list->size, 226 &list->size,
163 &list->capacity, 227 &list->capacity,
164 index + 1, 228 index + 1,
168 &arl->reallocator 232 &arl->reallocator
169 )) { 233 )) {
170 return 1; 234 return 1;
171 } 235 }
172 236
173 /* place the element */ 237 // place the element
174 memcpy(((char *) arl->data) + index * list->itemsize, 238 memcpy(((char *) arl->data) + index * list->itemsize,
175 elem, list->itemsize); 239 elem, list->itemsize);
176 240
177 return 0; 241 return 0;
178 } 242 }
179 } 243 }
180 244
181 static int cx_arl_insert_iter( 245 static int cx_arl_insert_iter(
182 struct cx_iterator_s *iter, 246 struct cx_mut_iterator_s *iter,
183 void const *elem, 247 void const *elem,
184 int prepend 248 int prepend
185 ) { 249 ) {
186 return 1; 250 struct cx_list_s *list = iter->src_handle;
251 if (iter->index < list->size) {
252 int result = cx_arl_insert(
253 list,
254 iter->index + 1 - prepend,
255 elem
256 );
257 if (result == 0 && prepend != 0) {
258 iter->index++;
259 iter->elem_handle = ((char *) iter->elem_handle) + list->itemsize;
260 }
261 return result;
262 } else {
263 int result = cx_arl_add(list, elem);
264 iter->index = list->size;
265 return result;
266 }
187 } 267 }
188 268
189 static int cx_arl_remove( 269 static int cx_arl_remove(
190 struct cx_list_s *list, 270 struct cx_list_s *list,
191 size_t index 271 size_t index
192 ) { 272 ) {
193 /* out-of-bounds check */ 273 // out-of-bounds check
194 if (index >= list->size) { 274 if (index >= list->size) {
195 return 1; 275 return 1;
196 } 276 }
197 277
278 // short-circuit removal of last element
279 if (index == list->size - 1) {
280 list->size--;
281 return 0;
282 }
283
284 // just move the elements starting at index to the left
198 cx_array_list *arl = (cx_array_list *) list; 285 cx_array_list *arl = (cx_array_list *) list;
199
200 /* just move the elements starting at index to the left */
201 int result = cx_array_copy( 286 int result = cx_array_copy(
202 &arl->data, 287 &arl->data,
203 &list->size, 288 &list->size,
204 &list->capacity, 289 &list->capacity,
205 index, 290 index,
206 ((char *) arl->data) + (index + 1) * list->itemsize, 291 ((char *) arl->data) + (index + 1) * list->itemsize,
207 list->itemsize, 292 list->itemsize,
208 list->size - index, 293 list->size - index - 1,
209 &arl->reallocator 294 &arl->reallocator
210 ); 295 );
211 if (result == 0) { 296 if (result == 0) {
212 /* decrease the size */ 297 // decrease the size
213 list->size--; 298 list->size--;
214 } 299 }
215 return result; 300 return result;
216 } 301 }
217 302
254 339
255 static int cx_arl_compare( 340 static int cx_arl_compare(
256 struct cx_list_s const *list, 341 struct cx_list_s const *list,
257 struct cx_list_s const *other 342 struct cx_list_s const *other
258 ) { 343 ) {
259 344 if (list->size == other->size) {
345 char const *left = ((cx_array_list const *) list)->data;
346 char const *right = ((cx_array_list const *) other)->data;
347 for (size_t i = 0; i < list->size; i++) {
348 int d = list->cmpfunc(left, right);
349 if (d != 0) {
350 return d;
351 }
352 left += list->itemsize;
353 right += other->itemsize;
354 }
355 return 0;
356 } else {
357 return list->size < other->size ? -1 : 1;
358 }
260 } 359 }
261 360
262 static void cx_arl_reverse(struct cx_list_s *list) { 361 static void cx_arl_reverse(struct cx_list_s *list) {
263 362 if (list->size < 2) return;
264 } 363 void *data = ((cx_array_list const *) list)->data;
265 364 size_t half = list->size / 2;
266 static bool cx_arl_iter_valid(struct cx_iterator_s const *iter) { 365 for (size_t i = 0; i < half; i++) {
366 cx_array_swap(data, list->itemsize, i, list->size - 1 - i);
367 }
368 }
369
370 static bool cx_arl_iter_valid(void const *it) {
371 struct cx_iterator_s const *iter = it;
267 struct cx_list_s const *list = iter->src_handle; 372 struct cx_list_s const *list = iter->src_handle;
268 return iter->index < list->size; 373 return iter->index < list->size;
269 } 374 }
270 375
271 static void *cx_arl_iter_current(struct cx_iterator_s const *iter) { 376 static void *cx_arl_iter_current(void const *it) {
377 struct cx_iterator_s const *iter = it;
272 return iter->elem_handle; 378 return iter->elem_handle;
273 } 379 }
274 380
275 static void cx_arl_iter_next(struct cx_iterator_s *iter) { 381 static void cx_arl_iter_next(void *it) {
276 if (iter->remove) { 382 struct cx_iterator_base_s *itbase = it;
277 iter->remove = false; 383 if (itbase->remove) {
384 struct cx_mut_iterator_s *iter = it;
385 itbase->remove = false;
278 cx_arl_remove(iter->src_handle, iter->index); 386 cx_arl_remove(iter->src_handle, iter->index);
279 } else { 387 } else {
388 struct cx_iterator_s *iter = it;
280 iter->index++; 389 iter->index++;
281 iter->elem_handle = cx_arl_at(iter->src_handle, iter->index); 390 iter->elem_handle =
391 ((char *) iter->elem_handle)
392 + ((struct cx_list_s const *) iter->src_handle)->itemsize;
393 }
394 }
395
396 static bool cx_arl_iter_flag_rm(void *it) {
397 struct cx_iterator_base_s *iter = it;
398 if (iter->mutating) {
399 iter->remove = true;
400 return true;
401 } else {
402 return false;
282 } 403 }
283 } 404 }
284 405
285 static struct cx_iterator_s cx_arl_iterator( 406 static struct cx_iterator_s cx_arl_iterator(
286 struct cx_list_s *list, 407 struct cx_list_s const *list,
287 size_t index 408 size_t index
288 ) { 409 ) {
289 struct cx_iterator_s iter; 410 struct cx_iterator_s iter;
290 411
291 iter.index = index; 412 iter.index = index;
292 iter.src_handle = list; 413 iter.src_handle = list;
293 iter.elem_handle = cx_arl_at(list, index); 414 iter.elem_handle = cx_arl_at(list, index);
294 iter.valid = cx_arl_iter_valid; 415 iter.base.valid = cx_arl_iter_valid;
295 iter.current = cx_arl_iter_current; 416 iter.base.current = cx_arl_iter_current;
296 iter.next = cx_arl_iter_next; 417 iter.base.next = cx_arl_iter_next;
297 iter.remove = false; 418 iter.base.flag_removal = cx_arl_iter_flag_rm;
298 419 iter.base.remove = false;
420 iter.base.mutating = false;
421
422 return iter;
423 }
424
425 static struct cx_mut_iterator_s cx_arl_mut_iterator(
426 struct cx_list_s *list,
427 size_t index
428 ) {
429 CxIterator it = cx_arl_iterator(list, index);
430 it.base.mutating = true;
431
432 // we know the iterators share the same memory layout
433 CxMutIterator iter;
434 memcpy(&iter, &it, sizeof(CxMutIterator));
299 return iter; 435 return iter;
300 } 436 }
301 437
302 static cx_list_class cx_array_list_class = { 438 static cx_list_class cx_array_list_class = {
303 cx_arl_destructor, 439 cx_arl_destructor,
304 cx_arl_add, 440 cx_arl_add,
441 cx_arl_add_array,
305 cx_arl_insert, 442 cx_arl_insert,
306 cx_arl_insert_iter, 443 cx_arl_insert_iter,
307 cx_arl_remove, 444 cx_arl_remove,
308 cx_arl_at, 445 cx_arl_at,
309 cx_arl_find, 446 cx_arl_find,
310 cx_arl_sort, 447 cx_arl_sort,
311 cx_arl_compare, 448 cx_arl_compare,
312 cx_arl_reverse, 449 cx_arl_reverse,
313 cx_arl_iterator, 450 cx_arl_iterator,
451 cx_arl_mut_iterator,
314 }; 452 };
315 453
316 CxList *cxArrayListCreate( 454 CxList *cxArrayListCreate(
317 CxAllocator const *allocator, 455 CxAllocator const *allocator,
318 CxListComparator comparator, 456 CxListComparator comparator,
332 list->base.allocator = allocator; 470 list->base.allocator = allocator;
333 list->base.cmpfunc = comparator; 471 list->base.cmpfunc = comparator;
334 list->base.itemsize = item_size; 472 list->base.itemsize = item_size;
335 list->base.capacity = initial_capacity; 473 list->base.capacity = initial_capacity;
336 474
337 /* configure the reallocator */ 475 // configure the reallocator
338 list->reallocator.realloc = cx_arl_realloc; 476 list->reallocator.realloc = cx_arl_realloc;
339 list->reallocator.ptr1 = (void *) allocator; 477 list->reallocator.ptr1 = (void *) allocator;
340 478
341 return (CxList *) list; 479 return (CxList *) list;
342 } 480 }

Mercurial Repository: webserver

mercurial