Mercurial > hg > toolkit / file comparison

comparison: ucx/array_list.c

ucx/array_list.c

branch
newapi
changeset 253
087cc9216f28
parent 187
24ce2c326d85
equal deleted inserted replaced
252:7d176764756d 253:087cc9216f28
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE. 26 * POSSIBILITY OF SUCH DAMAGE.
27 */ 27 */
28 28
29 #include "cx/array_list.h" 29 #include "cx/array_list.h"
30 #include "cx/compare.h"
30 #include <assert.h> 31 #include <assert.h>
31 #include <string.h> 32 #include <string.h>
32 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
33 // LOW LEVEL ARRAY LIST FUNCTIONS 51 // LOW LEVEL ARRAY LIST FUNCTIONS
34 52
35 enum cx_array_copy_result cx_array_copy( 53 enum cx_array_result cx_array_copy(
36 void **target, 54 void **target,
37 size_t *size, 55 size_t *size,
38 size_t *capacity, 56 size_t *capacity,
39 size_t index, 57 size_t index,
40 void const *src, 58 void const *src,
57 75
58 // reallocate if possible 76 // reallocate if possible
59 if (needrealloc) { 77 if (needrealloc) {
60 // a reallocator and a capacity variable must be available 78 // a reallocator and a capacity variable must be available
61 if (reallocator == NULL || capacity == NULL) { 79 if (reallocator == NULL || capacity == NULL) {
62 return CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED; 80 return CX_ARRAY_REALLOC_NOT_SUPPORTED;
63 } 81 }
64 82
65 // check, if we need to repair the src pointer 83 // check, if we need to repair the src pointer
66 uintptr_t targetaddr = (uintptr_t) *target; 84 uintptr_t targetaddr = (uintptr_t) *target;
67 uintptr_t srcaddr = (uintptr_t) src; 85 uintptr_t srcaddr = (uintptr_t) src;
75 // perform reallocation 93 // perform reallocation
76 void *newmem = reallocator->realloc( 94 void *newmem = reallocator->realloc(
77 *target, cap, elem_size, reallocator 95 *target, cap, elem_size, reallocator
78 ); 96 );
79 if (newmem == NULL) { 97 if (newmem == NULL) {
80 return CX_ARRAY_COPY_REALLOC_FAILED; 98 return CX_ARRAY_REALLOC_FAILED;
81 } 99 }
82 100
83 // repair src pointer, if necessary 101 // repair src pointer, if necessary
84 if (repairsrc) { 102 if (repairsrc) {
85 src = ((char *) newmem) + (srcaddr - targetaddr); 103 src = ((char *) newmem) + (srcaddr - targetaddr);
97 // copy elements and set new size 115 // copy elements and set new size
98 memmove(start, src, elem_count * elem_size); 116 memmove(start, src, elem_count * elem_size);
99 *size = newsize; 117 *size = newsize;
100 118
101 // return successfully 119 // return successfully
102 return CX_ARRAY_COPY_SUCCESS; 120 return CX_ARRAY_SUCCESS;
103 } 121 }
104 122
105 #ifndef CX_ARRAY_SWAP_SBO_SIZE 123 #ifndef CX_ARRAY_SWAP_SBO_SIZE
106 #define CX_ARRAY_SWAP_SBO_SIZE 128 124 #define CX_ARRAY_SWAP_SBO_SIZE 128
107 #endif 125 #endif
126 unsigned cx_array_swap_sbo_size = CX_ARRAY_SWAP_SBO_SIZE;
108 127
109 void cx_array_swap( 128 void cx_array_swap(
110 void *arr, 129 void *arr,
111 size_t elem_size, 130 size_t elem_size,
112 size_t idx1, 131 size_t idx1,
206 char const *first_to_move = (char const *) arl->data; 225 char const *first_to_move = (char const *) arl->data;
207 first_to_move += index * list->item_size; 226 first_to_move += index * list->item_size;
208 size_t elems_to_move = list->size - index; 227 size_t elems_to_move = list->size - index;
209 size_t start_of_moved = index + n; 228 size_t start_of_moved = index + n;
210 229
211 if (CX_ARRAY_COPY_SUCCESS != cx_array_copy( 230 if (CX_ARRAY_SUCCESS != cx_array_copy(
212 &arl->data, 231 &arl->data,
213 &list->size, 232 &list->size,
214 &arl->capacity, 233 &arl->capacity,
215 start_of_moved, 234 start_of_moved,
216 first_to_move, 235 first_to_move,
226 // note that if we had to move the elements, the following operation 245 // note that if we had to move the elements, the following operation
227 // is guaranteed to succeed, because we have the memory already allocated 246 // is guaranteed to succeed, because we have the memory already allocated
228 // therefore, it is impossible to leave this function with an invalid array 247 // therefore, it is impossible to leave this function with an invalid array
229 248
230 // place the new elements 249 // place the new elements
231 if (CX_ARRAY_COPY_SUCCESS == cx_array_copy( 250 if (CX_ARRAY_SUCCESS == cx_array_copy(
232 &arl->data, 251 &arl->data,
233 &list->size, 252 &list->size,
234 &arl->capacity, 253 &arl->capacity,
235 index, 254 index,
236 array, 255 array,
306 ((char *) arl->data) + (index + 1) * list->item_size, 325 ((char *) arl->data) + (index + 1) * list->item_size,
307 list->item_size, 326 list->item_size,
308 list->size - index - 1, 327 list->size - index - 1,
309 &arl->reallocator 328 &arl->reallocator
310 ); 329 );
311 if (result == 0) { 330
312 // decrease the size 331 // cx_array_copy cannot fail, array cannot grow
313 list->size--; 332 assert(result == 0);
314 } 333
315 return result; 334 // decrease the size
335 list->size--;
336
337 return 0;
316 } 338 }
317 339
318 static void cx_arl_clear(struct cx_list_s *list) { 340 static void cx_arl_clear(struct cx_list_s *list) {
319 if (list->size == 0) return; 341 if (list->size == 0) return;
320 342
360 } else { 382 } else {
361 return NULL; 383 return NULL;
362 } 384 }
363 } 385 }
364 386
365 static ssize_t cx_arl_find( 387 static ssize_t cx_arl_find_remove(
366 struct cx_list_s const *list, 388 struct cx_list_s *list,
367 void const *elem 389 void const *elem,
390 bool remove
368 ) { 391 ) {
369 assert(list->cmpfunc != NULL); 392 assert(list->cmpfunc != NULL);
370 assert(list->size < SIZE_MAX / 2); 393 assert(list->size < SIZE_MAX / 2);
371 char *cur = ((cx_array_list const *) list)->data; 394 char *cur = ((cx_array_list const *) list)->data;
372 395
373 for (ssize_t i = 0; i < (ssize_t) list->size; i++) { 396 for (ssize_t i = 0; i < (ssize_t) list->size; i++) {
374 if (0 == list->cmpfunc(elem, cur)) { 397 if (0 == list->cmpfunc(elem, cur)) {
375 return i; 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 }
376 } 407 }
377 cur += list->item_size; 408 cur += list->item_size;
378 } 409 }
379 410
380 return -1; 411 return -1;
498 cx_arl_insert_iter, 529 cx_arl_insert_iter,
499 cx_arl_remove, 530 cx_arl_remove,
500 cx_arl_clear, 531 cx_arl_clear,
501 cx_arl_swap, 532 cx_arl_swap,
502 cx_arl_at, 533 cx_arl_at,
503 cx_arl_find, 534 cx_arl_find_remove,
504 cx_arl_sort, 535 cx_arl_sort,
505 cx_arl_compare, 536 cx_arl_compare,
506 cx_arl_reverse, 537 cx_arl_reverse,
507 cx_arl_iterator, 538 cx_arl_iterator,
508 }; 539 };
520 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list)); 551 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list));
521 if (list == NULL) return NULL; 552 if (list == NULL) return NULL;
522 553
523 list->base.cl = &cx_array_list_class; 554 list->base.cl = &cx_array_list_class;
524 list->base.allocator = allocator; 555 list->base.allocator = allocator;
525 list->base.cmpfunc = comparator;
526 list->capacity = initial_capacity; 556 list->capacity = initial_capacity;
527 557
528 if (item_size > 0) { 558 if (item_size > 0) {
529 list->base.item_size = item_size; 559 list->base.item_size = item_size;
560 list->base.cmpfunc = comparator;
530 } else { 561 } else {
531 item_size = sizeof(void *); 562 item_size = sizeof(void *);
563 list->base.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator;
532 cxListStorePointers((CxList *) list); 564 cxListStorePointers((CxList *) list);
533 } 565 }
534 566
535 // allocate the array after the real item_size is known 567 // allocate the array after the real item_size is known
536 list->data = cxCalloc(allocator, initial_capacity, item_size); 568 list->data = cxCalloc(allocator, initial_capacity, item_size);

Mercurial Repository: toolkit

mercurial