comparison: ucx/array_list.c
ucx/array_list.c
- changeset 854
- 1c8401ece69e
- parent 852
- 83fdf679df99
equal
deleted
inserted
replaced
| 853:2ad93ebdc8d9 | 854:1c8401ece69e |
|---|---|
| 854 } else { | 854 } else { |
| 855 return NULL; | 855 return NULL; |
| 856 } | 856 } |
| 857 } | 857 } |
| 858 | 858 |
| 859 static ssize_t cx_arl_find_remove( | 859 static size_t cx_arl_find_remove( |
| 860 struct cx_list_s *list, | 860 struct cx_list_s *list, |
| 861 const void *elem, | 861 const void *elem, |
| 862 bool remove | 862 bool remove |
| 863 ) { | 863 ) { |
| 864 assert(list != NULL); | |
| 864 assert(list->collection.cmpfunc != NULL); | 865 assert(list->collection.cmpfunc != NULL); |
| 865 assert(list->collection.size < SIZE_MAX / 2); | 866 if (list->collection.size == 0) return 0; |
| 866 char *cur = ((const cx_array_list *) list)->data; | 867 char *cur = ((const cx_array_list *) list)->data; |
| 867 | 868 |
| 868 for (ssize_t i = 0; i < (ssize_t) list->collection.size; i++) { | 869 // optimize with binary search, when sorted |
| 870 if (list->collection.sorted) { | |
| 871 size_t i = cx_array_binary_search( | |
| 872 cur, | |
| 873 list->collection.size, | |
| 874 list->collection.elem_size, | |
| 875 elem, | |
| 876 list->collection.cmpfunc | |
| 877 ); | |
| 878 if (remove && i < list->collection.size) { | |
| 879 cx_arl_remove(list, i, 1, NULL); | |
| 880 } | |
| 881 return i; | |
| 882 } | |
| 883 | |
| 884 // fallback: linear search | |
| 885 for (size_t i = 0; i < list->collection.size; i++) { | |
| 869 if (0 == list->collection.cmpfunc(elem, cur)) { | 886 if (0 == list->collection.cmpfunc(elem, cur)) { |
| 870 if (remove) { | 887 if (remove) { |
| 871 if (1 == cx_arl_remove(list, i, 1, NULL)) { | 888 cx_arl_remove(list, i, 1, NULL); |
| 872 return i; | |
| 873 } else { | |
| 874 // should be unreachable | |
| 875 return -1; // LCOV_EXCL_LINE | |
| 876 } | |
| 877 } else { | |
| 878 return i; | |
| 879 } | 889 } |
| 890 return i; | |
| 880 } | 891 } |
| 881 cur += list->collection.elem_size; | 892 cur += list->collection.elem_size; |
| 882 } | 893 } |
| 883 | 894 return list->collection.size; |
| 884 return -1; | |
| 885 } | 895 } |
| 886 | 896 |
| 887 static void cx_arl_sort(struct cx_list_s *list) { | 897 static void cx_arl_sort(struct cx_list_s *list) { |
| 888 assert(list->collection.cmpfunc != NULL); | 898 assert(list->collection.cmpfunc != NULL); |
| 889 qsort(((cx_array_list *) list)->data, | 899 qsort(((cx_array_list *) list)->data, |
| 1011 allocator = cxDefaultAllocator; | 1021 allocator = cxDefaultAllocator; |
| 1012 } | 1022 } |
| 1013 | 1023 |
| 1014 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list)); | 1024 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list)); |
| 1015 if (list == NULL) return NULL; | 1025 if (list == NULL) return NULL; |
| 1016 | 1026 cx_list_init((CxList*)list, &cx_array_list_class, |
| 1017 list->base.cl = &cx_array_list_class; | 1027 allocator, comparator, elem_size); |
| 1018 list->base.collection.allocator = allocator; | |
| 1019 list->capacity = initial_capacity; | 1028 list->capacity = initial_capacity; |
| 1020 | 1029 |
| 1021 if (elem_size > 0) { | |
| 1022 list->base.collection.elem_size = elem_size; | |
| 1023 list->base.collection.cmpfunc = comparator; | |
| 1024 } else { | |
| 1025 elem_size = sizeof(void *); | |
| 1026 list->base.collection.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator; | |
| 1027 cxListStorePointers((CxList *) list); | |
| 1028 } | |
| 1029 | |
| 1030 // allocate the array after the real elem_size is known | 1030 // allocate the array after the real elem_size is known |
| 1031 list->data = cxCalloc(allocator, initial_capacity, elem_size); | 1031 list->data = cxCalloc(allocator, initial_capacity, |
| 1032 list->base.collection.elem_size); | |
| 1032 if (list->data == NULL) { // LCOV_EXCL_START | 1033 if (list->data == NULL) { // LCOV_EXCL_START |
| 1033 cxFree(allocator, list); | 1034 cxFree(allocator, list); |
| 1034 return NULL; | 1035 return NULL; |
| 1035 } // LCOV_EXCL_STOP | 1036 } // LCOV_EXCL_STOP |
| 1036 | 1037 |
