Mercurial > hg > dav / file comparison

comparison: ucx/array_list.c

ucx/array_list.c

branch
dav-2
changeset 894
e86049631677
parent 891
4d58cbcc9efa
equal deleted inserted replaced
893:38800d479cd4 894:e86049631677
99 size_t elem_size, size_t index, const void *other, size_t n) { 99 size_t elem_size, size_t index, const void *other, size_t n) {
100 // out of bounds and special case check 100 // out of bounds and special case check
101 if (index > array->size) return -1; 101 if (index > array->size) return -1;
102 if (n == 0) return 0; 102 if (n == 0) return 0;
103 103
104 // calculate required capacity
105 size_t req_capacity = array->size + n;
106 if (req_capacity <= array->size) {
107 errno = EOVERFLOW;
108 return -1;
109 }
110
104 // guarantee enough capacity 111 // guarantee enough capacity
105 if (array->capacity < array->size + n) { 112 if (array->capacity < req_capacity) {
106 const size_t new_capacity = cx_array_grow_capacity(array->capacity,array->size + n); 113 const size_t new_capacity = cx_array_grow_capacity(array->capacity,req_capacity);
107 if (cxReallocateArray(allocator, &array->data, new_capacity, elem_size)) { 114 if (cxReallocateArray(allocator, &array->data, new_capacity, elem_size)) {
108 return -1; // LCOV_EXCL_LINE 115 return -1;
109 } 116 }
110 array->capacity = new_capacity; 117 array->capacity = new_capacity;
111 } 118 }
112 119
113 // determine insert position 120 // determine insert position
114 char *dst = array->data; 121 char *dst = array->data;
115 dst += index * elem_size; 122 dst += index * elem_size;
116 123
117 // do we need to move some elements? 124 // do we need to move some elements?
118 if (index < array->size) { 125 size_t elems_to_move = array->size - index;
119 size_t elems_to_move = array->size - index; 126 if (elems_to_move > 0) {
120 char *target = dst + n * elem_size; 127 char *target = dst + n * elem_size;
121 memmove(target, dst, elems_to_move * elem_size); 128 memmove(target, dst, elems_to_move * elem_size);
122 } 129 }
123 130
124 // place the new elements, if any 131 // place the new elements, if any
312 copy_len++; 319 copy_len++;
313 } else if (d == 0) { 320 } else if (d == 0) {
314 left_src += elem_size; 321 left_src += elem_size;
315 skip_len++; 322 skip_len++;
316 } else { 323 } else {
317 break; 324 // should be unreachable because the requirement is
325 // that the source array is sorted
326 break; // LCOV_EXCL_LINE
318 } 327 }
319 } 328 }
320 } 329 }
321 size_t bytes_copied = copy_len * elem_size; 330 size_t bytes_copied = copy_len * elem_size;
322 memcpy(dest, src, bytes_copied); 331 memcpy(dest, src, bytes_copied);
348 cx_compare_func cmp_func, 357 cx_compare_func cmp_func,
349 bool allow_duplicates 358 bool allow_duplicates
350 ) { 359 ) {
351 cx_compare_func_wrapper wrapper = {cmp_func}; 360 cx_compare_func_wrapper wrapper = {cmp_func};
352 return cx_array_insert_sorted_c_(allocator, array, elem_size, sorted_data, 361 return cx_array_insert_sorted_c_(allocator, array, elem_size, sorted_data,
353 n, cx_ccmp_wrap, &wrapper, allow_duplicates); 362 n, cx_cmp_wrap, &wrapper, allow_duplicates);
354 } 363 }
355 364
356 #ifndef WITH_QSORT_R 365 #ifndef WITH_QSORT_R
357 static thread_local cx_compare_func2 cx_array_fn_for_qsort; 366 static cx_thread_local cx_compare_func2 cx_array_fn_for_qsort;
358 static thread_local void *cx_array_context_for_qsort; 367 static cx_thread_local void *cx_array_context_for_qsort;
359 static int cx_array_qsort_wrapper(const void *l, const void *r) { 368 static int cx_array_qsort_wrapper(const void *l, const void *r) {
360 return cx_array_fn_for_qsort(l, r, cx_array_context_for_qsort); 369 return cx_array_fn_for_qsort(l, r, cx_array_context_for_qsort);
370 }
371 #endif
372
373 #if defined(WITH_QSORT_R) && defined(__APPLE__)
374 // macOS uses a different comparefunc signature for qsort_r
375 typedef struct QsortCmpFuncWrapper {
376 cx_compare_func2 fn;
377 void *context;
378 } QsortCmpFuncWrapper;
379
380 static int sort_comparefunc(void *context, const void *left, const void *right){
381 QsortCmpFuncWrapper *w = context;
382 return w->fn(left, right, w->context);
361 } 383 }
362 #endif 384 #endif
363 385
364 void cx_array_qsort_c(void *array, size_t nmemb, size_t size, 386 void cx_array_qsort_c(void *array, size_t nmemb, size_t size,
365 cx_compare_func2 fn, void *context) { 387 cx_compare_func2 fn, void *context) {
366 #ifdef WITH_QSORT_R 388 #ifdef WITH_QSORT_R
389 #ifndef __APPLE__
367 qsort_r(array, nmemb, size, fn, context); 390 qsort_r(array, nmemb, size, fn, context);
391 #else
392 QsortCmpFuncWrapper wrapper;
393 wrapper.fn = fn;
394 wrapper.context = context;
395 qsort_r(array, nmemb, size, &wrapper, sort_comparefunc);
396 #endif
368 #else 397 #else
369 cx_array_fn_for_qsort = fn; 398 cx_array_fn_for_qsort = fn;
370 cx_array_context_for_qsort = context; 399 cx_array_context_for_qsort = context;
371 qsort(array, nmemb, size, cx_array_qsort_wrapper); 400 qsort(array, nmemb, size, cx_array_qsort_wrapper);
372 #endif 401 #endif
576 size_t elem_size, 605 size_t elem_size,
577 const void *elem, 606 const void *elem,
578 cx_compare_func cmp_func 607 cx_compare_func cmp_func
579 ) { 608 ) {
580 cx_compare_func_wrapper wrapper = {cmp_func}; 609 cx_compare_func_wrapper wrapper = {cmp_func};
581 return cx_array_binary_search_inf_c(arr, size, elem_size, elem, cx_ccmp_wrap, &wrapper); 610 return cx_array_binary_search_inf_c(arr, size, elem_size, elem, cx_cmp_wrap, &wrapper);
582 } 611 }
583 612
584 size_t cx_array_binary_search( 613 size_t cx_array_binary_search(
585 const void *arr, 614 const void *arr,
586 size_t size, 615 size_t size,
587 size_t elem_size, 616 size_t elem_size,
588 const void *elem, 617 const void *elem,
589 cx_compare_func cmp_func 618 cx_compare_func cmp_func
590 ) { 619 ) {
591 cx_compare_func_wrapper wrapper = {cmp_func}; 620 cx_compare_func_wrapper wrapper = {cmp_func};
592 return cx_array_binary_search_c(arr, size, elem_size, elem, cx_ccmp_wrap, &wrapper); 621 return cx_array_binary_search_c(arr, size, elem_size, elem, cx_cmp_wrap, &wrapper);
593 } 622 }
594 623
595 size_t cx_array_binary_search_sup( 624 size_t cx_array_binary_search_sup(
596 const void *arr, 625 const void *arr,
597 size_t size, 626 size_t size,
598 size_t elem_size, 627 size_t elem_size,
599 const void *elem, 628 const void *elem,
600 cx_compare_func cmp_func 629 cx_compare_func cmp_func
601 ) { 630 ) {
602 cx_compare_func_wrapper wrapper = {cmp_func}; 631 cx_compare_func_wrapper wrapper = {cmp_func};
603 return cx_array_binary_search_sup_c(arr, size, elem_size, elem, cx_ccmp_wrap, &wrapper); 632 return cx_array_binary_search_sup_c(arr, size, elem_size, elem, cx_cmp_wrap, &wrapper);
604 } 633 }
605 634
606 #ifndef CX_ARRAY_SWAP_SBO_SIZE 635 #ifndef CX_ARRAY_SWAP_SBO_SIZE
607 #define CX_ARRAY_SWAP_SBO_SIZE 128 636 #define CX_ARRAY_SWAP_SBO_SIZE 128
608 #endif 637 #endif
1062 allocator = cxDefaultAllocator; 1091 allocator = cxDefaultAllocator;
1063 } 1092 }
1064 1093
1065 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list)); 1094 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list));
1066 if (list == NULL) return NULL; 1095 if (list == NULL) return NULL;
1067 cx_list_init((CxList*)list, &cx_array_list_class, 1096 cx_list_init((CxList*)list, &cx_array_list_class, allocator, elem_size);
1068 allocator, elem_size);
1069 list->capacity = initial_capacity; 1097 list->capacity = initial_capacity;
1070 1098
1071 // allocate the array after the real elem_size is known 1099 // allocate the array after the real elem_size is known
1072 list->data = cxCalloc(allocator, initial_capacity, 1100 list->data = cxCalloc(allocator, initial_capacity,
1073 list->base.collection.elem_size); 1101 list->base.collection.elem_size);

Mercurial Repository: dav

mercurial