comparison: src/array_list.c
src/array_list.c
- changeset 1163
- 68ff0839bc6a
- parent 1162
- e3bb67b72d33
equal
deleted
inserted
replaced
| 1162:e3bb67b72d33 | 1163:68ff0839bc6a |
|---|---|
| 859 static size_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 |
| 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 | |
| 868 for (size_t i = 0; i < list->collection.size; i++) { | 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 list->collection.size; // 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 | |
| 884 return list->collection.size; | 894 return list->collection.size; |
| 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); |
