Mercurial > hg > toolkit / file comparison

comparison: ucx/array_list.c

ucx/array_list.c

changeset 440
7c4b9cba09ca
parent 324
ce13a778654a
equal deleted inserted replaced
439:bf7084544cb1 440:7c4b9cba09ca
28 28
29 #include "cx/array_list.h" 29 #include "cx/array_list.h"
30 #include "cx/compare.h" 30 #include "cx/compare.h"
31 #include <assert.h> 31 #include <assert.h>
32 #include <string.h> 32 #include <string.h>
33 #include <errno.h>
33 34
34 // Default array reallocator 35 // Default array reallocator
35 36
36 static void *cx_array_default_realloc( 37 static void *cx_array_default_realloc(
37 void *array, 38 void *array,
38 size_t capacity, 39 size_t capacity,
39 size_t elem_size, 40 size_t elem_size,
40 __attribute__((__unused__)) struct cx_array_reallocator_s *alloc 41 cx_attr_unused CxArrayReallocator *alloc
41 ) { 42 ) {
42 return realloc(array, capacity * elem_size); 43 size_t n;
43 } 44 if (cx_szmul(capacity, elem_size, &n)) {
44 45 errno = EOVERFLOW;
45 struct cx_array_reallocator_s cx_array_default_reallocator_impl = { 46 return NULL;
47 }
48 return realloc(array, n);
49 }
50
51 CxArrayReallocator cx_array_default_reallocator_impl = {
46 cx_array_default_realloc, NULL, NULL, 0, 0 52 cx_array_default_realloc, NULL, NULL, 0, 0
47 }; 53 };
48 54
49 struct cx_array_reallocator_s *cx_array_default_reallocator = &cx_array_default_reallocator_impl; 55 CxArrayReallocator *cx_array_default_reallocator = &cx_array_default_reallocator_impl;
56
57 // Stack-aware array reallocator
58
59 static void *cx_array_advanced_realloc(
60 void *array,
61 size_t capacity,
62 size_t elem_size,
63 cx_attr_unused CxArrayReallocator *alloc
64 ) {
65 // check for overflow
66 size_t n;
67 if (cx_szmul(capacity, elem_size, &n)) {
68 errno = EOVERFLOW;
69 return NULL;
70 }
71
72 // retrieve the pointer to the actual allocator
73 const CxAllocator *al = alloc->ptr1;
74
75 // check if the array is still located on the stack
76 void *newmem;
77 if (array == alloc->ptr2) {
78 newmem = cxMalloc(al, n);
79 if (newmem != NULL && array != NULL) {
80 memcpy(newmem, array, n);
81 }
82 } else {
83 newmem = cxRealloc(al, array, n);
84 }
85 return newmem;
86 }
87
88 struct cx_array_reallocator_s cx_array_reallocator(
89 const struct cx_allocator_s *allocator,
90 const void *stackmem
91 ) {
92 if (allocator == NULL) {
93 allocator = cxDefaultAllocator;
94 }
95 return (struct cx_array_reallocator_s) {
96 cx_array_advanced_realloc,
97 (void*) allocator, (void*) stackmem,
98 0, 0
99 };
100 }
50 101
51 // LOW LEVEL ARRAY LIST FUNCTIONS 102 // LOW LEVEL ARRAY LIST FUNCTIONS
52 103
53 enum cx_array_result cx_array_copy( 104 static size_t cx_array_align_capacity(
105 size_t cap,
106 size_t alignment,
107 size_t max
108 ) {
109 if (cap > max - alignment) {
110 return cap;
111 } else {
112 return cap - (cap % alignment) + alignment;
113 }
114 }
115
116 int cx_array_reserve(
117 void **array,
118 void *size,
119 void *capacity,
120 unsigned width,
121 size_t elem_size,
122 size_t elem_count,
123 CxArrayReallocator *reallocator
124 ) {
125 // assert pointers
126 assert(array != NULL);
127 assert(size != NULL);
128 assert(capacity != NULL);
129
130 // default reallocator
131 if (reallocator == NULL) {
132 reallocator = cx_array_default_reallocator;
133 }
134
135 // determine size and capacity
136 size_t oldcap;
137 size_t oldsize;
138 size_t max_size;
139 if (width == 0 || width == sizeof(size_t)) {
140 oldcap = *(size_t*) capacity;
141 oldsize = *(size_t*) size;
142 max_size = SIZE_MAX;
143 } else if (width == sizeof(uint16_t)) {
144 oldcap = *(uint16_t*) capacity;
145 oldsize = *(uint16_t*) size;
146 max_size = UINT16_MAX;
147 } else if (width == sizeof(uint8_t)) {
148 oldcap = *(uint8_t*) capacity;
149 oldsize = *(uint8_t*) size;
150 max_size = UINT8_MAX;
151 }
152 #if CX_WORDSIZE == 64
153 else if (width == sizeof(uint32_t)) {
154 oldcap = *(uint32_t*) capacity;
155 oldsize = *(uint32_t*) size;
156 max_size = UINT32_MAX;
157 }
158 #endif
159 else {
160 errno = EINVAL;
161 return 1;
162 }
163
164 // assert that the array is allocated when it has capacity
165 assert(*array != NULL || oldcap == 0);
166
167 // check for overflow
168 if (elem_count > max_size - oldsize) {
169 errno = EOVERFLOW;
170 return 1;
171 }
172
173 // determine new capacity
174 size_t newcap = oldsize + elem_count;
175
176 // reallocate if possible
177 if (newcap > oldcap) {
178 // calculate new capacity (next number divisible by 16)
179 newcap = cx_array_align_capacity(newcap, 16, max_size);
180
181 // perform reallocation
182 void *newmem = reallocator->realloc(
183 *array, newcap, elem_size, reallocator
184 );
185 if (newmem == NULL) {
186 return 1; // LCOV_EXCL_LINE
187 }
188
189 // store new pointer
190 *array = newmem;
191
192 // store new capacity
193 if (width == 0 || width == sizeof(size_t)) {
194 *(size_t*) capacity = newcap;
195 } else if (width == sizeof(uint16_t)) {
196 *(uint16_t*) capacity = (uint16_t) newcap;
197 } else if (width == sizeof(uint8_t)) {
198 *(uint8_t*) capacity = (uint8_t) newcap;
199 }
200 #if CX_WORDSIZE == 64
201 else if (width == sizeof(uint32_t)) {
202 *(uint32_t*) capacity = (uint32_t) newcap;
203 }
204 #endif
205 }
206
207 return 0;
208 }
209
210 int cx_array_copy(
54 void **target, 211 void **target,
55 size_t *size, 212 void *size,
56 size_t *capacity, 213 void *capacity,
214 unsigned width,
57 size_t index, 215 size_t index,
58 const void *src, 216 const void *src,
59 size_t elem_size, 217 size_t elem_size,
60 size_t elem_count, 218 size_t elem_count,
61 struct cx_array_reallocator_s *reallocator 219 CxArrayReallocator *reallocator
62 ) { 220 ) {
63 // assert pointers 221 // assert pointers
64 assert(target != NULL); 222 assert(target != NULL);
65 assert(size != NULL); 223 assert(size != NULL);
224 assert(capacity != NULL);
66 assert(src != NULL); 225 assert(src != NULL);
67 226
68 // determine capacity 227 // default reallocator
69 size_t cap = capacity == NULL ? *size : *capacity; 228 if (reallocator == NULL) {
229 reallocator = cx_array_default_reallocator;
230 }
231
232 // determine size and capacity
233 size_t oldcap;
234 size_t oldsize;
235 size_t max_size;
236 if (width == 0 || width == sizeof(size_t)) {
237 oldcap = *(size_t*) capacity;
238 oldsize = *(size_t*) size;
239 max_size = SIZE_MAX;
240 } else if (width == sizeof(uint16_t)) {
241 oldcap = *(uint16_t*) capacity;
242 oldsize = *(uint16_t*) size;
243 max_size = UINT16_MAX;
244 } else if (width == sizeof(uint8_t)) {
245 oldcap = *(uint8_t*) capacity;
246 oldsize = *(uint8_t*) size;
247 max_size = UINT8_MAX;
248 }
249 #if CX_WORDSIZE == 64
250 else if (width == sizeof(uint32_t)) {
251 oldcap = *(uint32_t*) capacity;
252 oldsize = *(uint32_t*) size;
253 max_size = UINT32_MAX;
254 }
255 #endif
256 else {
257 errno = EINVAL;
258 return 1;
259 }
260
261 // assert that the array is allocated when it has capacity
262 assert(*target != NULL || oldcap == 0);
263
264 // check for overflow
265 if (index > max_size || elem_count > max_size - index) {
266 errno = EOVERFLOW;
267 return 1;
268 }
70 269
71 // check if resize is required 270 // check if resize is required
72 size_t minsize = index + elem_count; 271 size_t minsize = index + elem_count;
73 size_t newsize = *size < minsize ? minsize : *size; 272 size_t newsize = oldsize < minsize ? minsize : oldsize;
74 bool needrealloc = newsize > cap;
75 273
76 // reallocate if possible 274 // reallocate if possible
77 if (needrealloc) { 275 size_t newcap = oldcap;
78 // a reallocator and a capacity variable must be available 276 if (newsize > oldcap) {
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 277 // check, if we need to repair the src pointer
84 uintptr_t targetaddr = (uintptr_t) *target; 278 uintptr_t targetaddr = (uintptr_t) *target;
85 uintptr_t srcaddr = (uintptr_t) src; 279 uintptr_t srcaddr = (uintptr_t) src;
86 bool repairsrc = targetaddr <= srcaddr 280 bool repairsrc = targetaddr <= srcaddr
87 && srcaddr < targetaddr + cap * elem_size; 281 && srcaddr < targetaddr + oldcap * elem_size;
88 282
89 // calculate new capacity (next number divisible by 16) 283 // calculate new capacity (next number divisible by 16)
90 cap = newsize - (newsize % 16) + 16; 284 newcap = cx_array_align_capacity(newsize, 16, max_size);
91 assert(cap > newsize); 285 assert(newcap > newsize);
92 286
93 // perform reallocation 287 // perform reallocation
94 void *newmem = reallocator->realloc( 288 void *newmem = reallocator->realloc(
95 *target, cap, elem_size, reallocator 289 *target, newcap, elem_size, reallocator
96 ); 290 );
97 if (newmem == NULL) { 291 if (newmem == NULL) {
98 return CX_ARRAY_REALLOC_FAILED; 292 return 1;
99 } 293 }
100 294
101 // repair src pointer, if necessary 295 // repair src pointer, if necessary
102 if (repairsrc) { 296 if (repairsrc) {
103 src = ((char *) newmem) + (srcaddr - targetaddr); 297 src = ((char *) newmem) + (srcaddr - targetaddr);
104 } 298 }
105 299
106 // store new pointer and capacity 300 // store new pointer
107 *target = newmem; 301 *target = newmem;
108 *capacity = cap;
109 } 302 }
110 303
111 // determine target pointer 304 // determine target pointer
112 char *start = *target; 305 char *start = *target;
113 start += index * elem_size; 306 start += index * elem_size;
114 307
115 // copy elements and set new size 308 // copy elements and set new size
309 // note: no overflow check here, b/c we cannot get here w/o allocation
116 memmove(start, src, elem_count * elem_size); 310 memmove(start, src, elem_count * elem_size);
117 *size = newsize; 311
312 // if any of size or capacity changed, store them back
313 if (newsize != oldsize || newcap != oldcap) {
314 if (width == 0 || width == sizeof(size_t)) {
315 *(size_t*) capacity = newcap;
316 *(size_t*) size = newsize;
317 } else if (width == sizeof(uint16_t)) {
318 *(uint16_t*) capacity = (uint16_t) newcap;
319 *(uint16_t*) size = (uint16_t) newsize;
320 } else if (width == sizeof(uint8_t)) {
321 *(uint8_t*) capacity = (uint8_t) newcap;
322 *(uint8_t*) size = (uint8_t) newsize;
323 }
324 #if CX_WORDSIZE == 64
325 else if (width == sizeof(uint32_t)) {
326 *(uint32_t*) capacity = (uint32_t) newcap;
327 *(uint32_t*) size = (uint32_t) newsize;
328 }
329 #endif
330 }
118 331
119 // return successfully 332 // return successfully
120 return CX_ARRAY_SUCCESS; 333 return 0;
121 } 334 }
122 335
123 enum cx_array_result cx_array_insert_sorted( 336 int cx_array_insert_sorted(
124 void **target, 337 void **target,
125 size_t *size, 338 size_t *size,
126 size_t *capacity, 339 size_t *capacity,
127 cx_compare_func cmp_func, 340 cx_compare_func cmp_func,
128 const void *sorted_data, 341 const void *sorted_data,
129 size_t elem_size, 342 size_t elem_size,
130 size_t elem_count, 343 size_t elem_count,
131 struct cx_array_reallocator_s *reallocator 344 CxArrayReallocator *reallocator
132 ) { 345 ) {
133 // assert pointers 346 // assert pointers
134 assert(target != NULL); 347 assert(target != NULL);
135 assert(size != NULL); 348 assert(size != NULL);
136 assert(capacity != NULL); 349 assert(capacity != NULL);
137 assert(cmp_func != NULL); 350 assert(cmp_func != NULL);
138 assert(sorted_data != NULL); 351 assert(sorted_data != NULL);
139 assert(reallocator != NULL); 352
353 // default reallocator
354 if (reallocator == NULL) {
355 reallocator = cx_array_default_reallocator;
356 }
140 357
141 // corner case 358 // corner case
142 if (elem_count == 0) return 0; 359 if (elem_count == 0) return 0;
360
361 // overflow check
362 if (elem_count > SIZE_MAX - *size) {
363 errno = EOVERFLOW;
364 return 1;
365 }
143 366
144 // store some counts 367 // store some counts
145 size_t old_size = *size; 368 size_t old_size = *size;
146 size_t needed_capacity = old_size + elem_count; 369 size_t needed_capacity = old_size + elem_count;
147 370
148 // if we need more than we have, try a reallocation 371 // if we need more than we have, try a reallocation
149 if (needed_capacity > *capacity) { 372 if (needed_capacity > *capacity) {
150 size_t new_capacity = needed_capacity - (needed_capacity % 16) + 16; 373 size_t new_capacity = cx_array_align_capacity(needed_capacity, 16, SIZE_MAX);
151 void *new_mem = reallocator->realloc( 374 void *new_mem = reallocator->realloc(
152 *target, new_capacity, elem_size, reallocator 375 *target, new_capacity, elem_size, reallocator
153 ); 376 );
154 if (new_mem == NULL) { 377 if (new_mem == NULL) {
155 // give it up right away, there is no contract 378 // give it up right away, there is no contract
156 // that requires us to insert as much as we can 379 // that requires us to insert as much as we can
157 return CX_ARRAY_REALLOC_FAILED; 380 return 1; // LCOV_EXCL_LINE
158 } 381 }
159 *target = new_mem; 382 *target = new_mem;
160 *capacity = new_capacity; 383 *capacity = new_capacity;
161 } 384 }
162 385
226 } 449 }
227 450
228 // still buffer elements left? 451 // still buffer elements left?
229 // don't worry, we already moved them to the correct place 452 // don't worry, we already moved them to the correct place
230 453
231 return CX_ARRAY_SUCCESS; 454 return 0;
232 } 455 }
233 456
234 size_t cx_array_binary_search_inf( 457 size_t cx_array_binary_search_inf(
235 const void *arr, 458 const void *arr,
236 size_t size, 459 size_t size,
252 if (result < 0) { 475 if (result < 0) {
253 return size; 476 return size;
254 } else if (result == 0) { 477 } else if (result == 0) {
255 return 0; 478 return 0;
256 } 479 }
480
481 // special case: there is only one element and that is smaller
482 if (size == 1) return 0;
257 483
258 // check the last array element 484 // check the last array element
259 result = cmp_func(elem, array + elem_size * (size - 1)); 485 result = cmp_func(elem, array + elem_size * (size - 1));
260 if (result >= 0) { 486 if (result >= 0) {
261 return size - 1; 487 return size - 1;
285 511
286 // report the largest upper bound 512 // report the largest upper bound
287 return result < 0 ? (pivot_index - 1) : pivot_index; 513 return result < 0 ? (pivot_index - 1) : pivot_index;
288 } 514 }
289 515
516 size_t cx_array_binary_search(
517 const void *arr,
518 size_t size,
519 size_t elem_size,
520 const void *elem,
521 cx_compare_func cmp_func
522 ) {
523 size_t index = cx_array_binary_search_inf(
524 arr, size, elem_size, elem, cmp_func
525 );
526 if (index < size &&
527 cmp_func(((const char *) arr) + index * elem_size, elem) == 0) {
528 return index;
529 } else {
530 return size;
531 }
532 }
533
534 size_t cx_array_binary_search_sup(
535 const void *arr,
536 size_t size,
537 size_t elem_size,
538 const void *elem,
539 cx_compare_func cmp_func
540 ) {
541 size_t inf = cx_array_binary_search_inf(
542 arr, size, elem_size, elem, cmp_func
543 );
544 if (inf == size) {
545 // no infimum means, first element is supremum
546 return 0;
547 } else if (cmp_func(((const char *) arr) + inf * elem_size, elem) == 0) {
548 return inf;
549 } else {
550 return inf + 1;
551 }
552 }
553
290 #ifndef CX_ARRAY_SWAP_SBO_SIZE 554 #ifndef CX_ARRAY_SWAP_SBO_SIZE
291 #define CX_ARRAY_SWAP_SBO_SIZE 128 555 #define CX_ARRAY_SWAP_SBO_SIZE 128
292 #endif 556 #endif
293 unsigned cx_array_swap_sbo_size = CX_ARRAY_SWAP_SBO_SIZE; 557 const unsigned cx_array_swap_sbo_size = CX_ARRAY_SWAP_SBO_SIZE;
294 558
295 void cx_array_swap( 559 void cx_array_swap(
296 void *arr, 560 void *arr,
297 size_t elem_size, 561 size_t elem_size,
298 size_t idx1, 562 size_t idx1,
335 599
336 typedef struct { 600 typedef struct {
337 struct cx_list_s base; 601 struct cx_list_s base;
338 void *data; 602 void *data;
339 size_t capacity; 603 size_t capacity;
340 struct cx_array_reallocator_s reallocator; 604 CxArrayReallocator reallocator;
341 } cx_array_list; 605 } cx_array_list;
342
343 static void *cx_arl_realloc(
344 void *array,
345 size_t capacity,
346 size_t elem_size,
347 struct cx_array_reallocator_s *alloc
348 ) {
349 // retrieve the pointer to the list allocator
350 const CxAllocator *al = alloc->ptr1;
351
352 // use the list allocator to reallocate the memory
353 return cxRealloc(al, array, capacity * elem_size);
354 }
355 606
356 static void cx_arl_destructor(struct cx_list_s *list) { 607 static void cx_arl_destructor(struct cx_list_s *list) {
357 cx_array_list *arl = (cx_array_list *) list; 608 cx_array_list *arl = (cx_array_list *) list;
358 609
359 char *ptr = arl->data; 610 char *ptr = arl->data;
392 const char *first_to_move = (const char *) arl->data; 643 const char *first_to_move = (const char *) arl->data;
393 first_to_move += index * list->collection.elem_size; 644 first_to_move += index * list->collection.elem_size;
394 size_t elems_to_move = list->collection.size - index; 645 size_t elems_to_move = list->collection.size - index;
395 size_t start_of_moved = index + n; 646 size_t start_of_moved = index + n;
396 647
397 if (CX_ARRAY_SUCCESS != cx_array_copy( 648 if (cx_array_copy(
398 &arl->data, 649 &arl->data,
399 &list->collection.size, 650 &list->collection.size,
400 &arl->capacity, 651 &arl->capacity,
652 0,
401 start_of_moved, 653 start_of_moved,
402 first_to_move, 654 first_to_move,
403 list->collection.elem_size, 655 list->collection.elem_size,
404 elems_to_move, 656 elems_to_move,
405 &arl->reallocator 657 &arl->reallocator
412 // note that if we had to move the elements, the following operation 664 // note that if we had to move the elements, the following operation
413 // is guaranteed to succeed, because we have the memory already allocated 665 // is guaranteed to succeed, because we have the memory already allocated
414 // therefore, it is impossible to leave this function with an invalid array 666 // therefore, it is impossible to leave this function with an invalid array
415 667
416 // place the new elements 668 // place the new elements
417 if (CX_ARRAY_SUCCESS == cx_array_copy( 669 if (cx_array_copy(
418 &arl->data, 670 &arl->data,
419 &list->collection.size, 671 &list->collection.size,
420 &arl->capacity, 672 &arl->capacity,
673 0,
421 index, 674 index,
422 array, 675 array,
423 list->collection.elem_size, 676 list->collection.elem_size,
424 n, 677 n,
425 &arl->reallocator 678 &arl->reallocator
426 )) { 679 )) {
427 return n;
428 } else {
429 // array list implementation is "all or nothing" 680 // array list implementation is "all or nothing"
430 return 0; 681 return 0;
682 } else {
683 return n;
431 } 684 }
432 } 685 }
433 686
434 static size_t cx_arl_insert_sorted( 687 static size_t cx_arl_insert_sorted(
435 struct cx_list_s *list, 688 struct cx_list_s *list,
437 size_t n 690 size_t n
438 ) { 691 ) {
439 // get a correctly typed pointer to the list 692 // get a correctly typed pointer to the list
440 cx_array_list *arl = (cx_array_list *) list; 693 cx_array_list *arl = (cx_array_list *) list;
441 694
442 if (CX_ARRAY_SUCCESS == cx_array_insert_sorted( 695 if (cx_array_insert_sorted(
443 &arl->data, 696 &arl->data,
444 &list->collection.size, 697 &list->collection.size,
445 &arl->capacity, 698 &arl->capacity,
446 list->collection.cmpfunc, 699 list->collection.cmpfunc,
447 sorted_data, 700 sorted_data,
448 list->collection.elem_size, 701 list->collection.elem_size,
449 n, 702 n,
450 &arl->reallocator 703 &arl->reallocator
451 )) { 704 )) {
452 return n;
453 } else {
454 // array list implementation is "all or nothing" 705 // array list implementation is "all or nothing"
455 return 0; 706 return 0;
707 } else {
708 return n;
456 } 709 }
457 } 710 }
458 711
459 static int cx_arl_insert_element( 712 static int cx_arl_insert_element(
460 struct cx_list_s *list, 713 struct cx_list_s *list,
492 } 745 }
493 return result; 746 return result;
494 } 747 }
495 } 748 }
496 749
497 static int cx_arl_remove( 750 static size_t cx_arl_remove(
498 struct cx_list_s *list, 751 struct cx_list_s *list,
499 size_t index 752 size_t index,
753 size_t num,
754 void *targetbuf
500 ) { 755 ) {
501 cx_array_list *arl = (cx_array_list *) list; 756 cx_array_list *arl = (cx_array_list *) list;
502 757
503 // out-of-bounds check 758 // out-of-bounds check
759 size_t remove;
504 if (index >= list->collection.size) { 760 if (index >= list->collection.size) {
505 return 1; 761 remove = 0;
506 } 762 } else if (index + num > list->collection.size) {
507 763 remove = list->collection.size - index;
508 // content destruction 764 } else {
509 cx_invoke_destructor(list, ((char *) arl->data) + index * list->collection.elem_size); 765 remove = num;
510 766 }
511 // short-circuit removal of last element 767
512 if (index == list->collection.size - 1) { 768 // easy exit
513 list->collection.size--; 769 if (remove == 0) return 0;
514 return 0; 770
515 } 771 // destroy or copy contents
516 772 if (targetbuf == NULL) {
517 // just move the elements starting at index to the left 773 for (size_t idx = index; idx < index + remove; idx++) {
518 int result = cx_array_copy( 774 cx_invoke_destructor(
775 list,
776 ((char *) arl->data) + idx * list->collection.elem_size
777 );
778 }
779 } else {
780 memcpy(
781 targetbuf,
782 ((char *) arl->data) + index * list->collection.elem_size,
783 remove * list->collection.elem_size
784 );
785 }
786
787 // short-circuit removal of last elements
788 if (index + remove == list->collection.size) {
789 list->collection.size -= remove;
790 return remove;
791 }
792
793 // just move the elements to the left
794 cx_array_copy(
519 &arl->data, 795 &arl->data,
520 &list->collection.size, 796 &list->collection.size,
521 &arl->capacity, 797 &arl->capacity,
798 0,
522 index, 799 index,
523 ((char *) arl->data) + (index + 1) * list->collection.elem_size, 800 ((char *) arl->data) + (index + remove) * list->collection.elem_size,
524 list->collection.elem_size, 801 list->collection.elem_size,
525 list->collection.size - index - 1, 802 list->collection.size - index - remove,
526 &arl->reallocator 803 &arl->reallocator
527 ); 804 );
528 805
529 // cx_array_copy cannot fail, array cannot grow
530 assert(result == 0);
531
532 // decrease the size 806 // decrease the size
533 list->collection.size--; 807 list->collection.size -= remove;
534 808
535 return 0; 809 return remove;
536 } 810 }
537 811
538 static void cx_arl_clear(struct cx_list_s *list) { 812 static void cx_arl_clear(struct cx_list_s *list) {
539 if (list->collection.size == 0) return; 813 if (list->collection.size == 0) return;
540 814
592 char *cur = ((const cx_array_list *) list)->data; 866 char *cur = ((const cx_array_list *) list)->data;
593 867
594 for (ssize_t i = 0; i < (ssize_t) list->collection.size; i++) { 868 for (ssize_t i = 0; i < (ssize_t) list->collection.size; i++) {
595 if (0 == list->collection.cmpfunc(elem, cur)) { 869 if (0 == list->collection.cmpfunc(elem, cur)) {
596 if (remove) { 870 if (remove) {
597 if (0 == cx_arl_remove(list, i)) { 871 if (1 == cx_arl_remove(list, i, 1, NULL)) {
598 return i; 872 return i;
599 } else { 873 } else {
600 return -1; 874 // should be unreachable
875 return -1; // LCOV_EXCL_LINE
601 } 876 }
602 } else { 877 } else {
603 return i; 878 return i;
604 } 879 }
605 } 880 }
662 937
663 static void cx_arl_iter_next(void *it) { 938 static void cx_arl_iter_next(void *it) {
664 struct cx_iterator_s *iter = it; 939 struct cx_iterator_s *iter = it;
665 if (iter->base.remove) { 940 if (iter->base.remove) {
666 iter->base.remove = false; 941 iter->base.remove = false;
667 cx_arl_remove(iter->src_handle.m, iter->index); 942 cx_arl_remove(iter->src_handle.m, iter->index, 1, NULL);
668 } else { 943 } else {
669 iter->index++; 944 iter->index++;
670 iter->elem_handle = 945 iter->elem_handle =
671 ((char *) iter->elem_handle) 946 ((char *) iter->elem_handle)
672 + ((const struct cx_list_s *) iter->src_handle.c)->collection.elem_size; 947 + ((const struct cx_list_s *) iter->src_handle.c)->collection.elem_size;
676 static void cx_arl_iter_prev(void *it) { 951 static void cx_arl_iter_prev(void *it) {
677 struct cx_iterator_s *iter = it; 952 struct cx_iterator_s *iter = it;
678 const cx_array_list *list = iter->src_handle.c; 953 const cx_array_list *list = iter->src_handle.c;
679 if (iter->base.remove) { 954 if (iter->base.remove) {
680 iter->base.remove = false; 955 iter->base.remove = false;
681 cx_arl_remove(iter->src_handle.m, iter->index); 956 cx_arl_remove(iter->src_handle.m, iter->index, 1, NULL);
682 } 957 }
683 iter->index--; 958 iter->index--;
684 if (iter->index < list->base.collection.size) { 959 if (iter->index < list->base.collection.size) {
685 iter->elem_handle = ((char *) list->data) 960 iter->elem_handle = ((char *) list->data)
686 + iter->index * list->base.collection.elem_size; 961 + iter->index * list->base.collection.elem_size;
752 cxListStorePointers((CxList *) list); 1027 cxListStorePointers((CxList *) list);
753 } 1028 }
754 1029
755 // allocate the array after the real elem_size is known 1030 // allocate the array after the real elem_size is known
756 list->data = cxCalloc(allocator, initial_capacity, elem_size); 1031 list->data = cxCalloc(allocator, initial_capacity, elem_size);
757 if (list->data == NULL) { 1032 if (list->data == NULL) { // LCOV_EXCL_START
758 cxFree(allocator, list); 1033 cxFree(allocator, list);
759 return NULL; 1034 return NULL;
760 } 1035 } // LCOV_EXCL_STOP
761 1036
762 // configure the reallocator 1037 // configure the reallocator
763 list->reallocator.realloc = cx_arl_realloc; 1038 list->reallocator = cx_array_reallocator(allocator, NULL);
764 list->reallocator.ptr1 = (void *) allocator;
765 1039
766 return (CxList *) list; 1040 return (CxList *) list;
767 } 1041 }

Mercurial Repository: toolkit

mercurial