comparison: ucx/list.c
ucx/list.c
- changeset 1040
- 473d8cb58a6c
- parent 1016
- ccde46662db7
equal
deleted
inserted
replaced
| 1039:6691e007cef7 | 1040:473d8cb58a6c |
|---|---|
| 29 #include "cx/list.h" | 29 #include "cx/list.h" |
| 30 | 30 |
| 31 #include <string.h> | 31 #include <string.h> |
| 32 #include <assert.h> | 32 #include <assert.h> |
| 33 | 33 |
| 34 // we don't want to include the full array_list.h. | |
| 35 // therefore, we only forward declare the one function we want to use | |
| 36 CX_EXPORT void cx_array_qsort_c(void *array, size_t nmemb, size_t size, | |
| 37 cx_compare_func2 fn, void *context); | |
| 38 | |
| 39 | |
| 34 int cx_list_compare_wrapper(const void *l, const void *r, void *c) { | 40 int cx_list_compare_wrapper(const void *l, const void *r, void *c) { |
| 35 CxList *list = c; | 41 CxList *list = c; |
| 36 const void *left; | 42 const void *left; |
| 37 const void *right; | 43 const void *right; |
| 38 if (cxCollectionStoresPointers(list)) { | 44 if (cxCollectionStoresPointers(list)) { |
| 55 | 61 |
| 56 #define cx_list_compare_wrapper(l, r, c) cx_list_compare_wrapper(l, r, (void*)c) | 62 #define cx_list_compare_wrapper(l, r, c) cx_list_compare_wrapper(l, r, (void*)c) |
| 57 | 63 |
| 58 // <editor-fold desc="empty list implementation"> | 64 // <editor-fold desc="empty list implementation"> |
| 59 | 65 |
| 60 static void cx_emptyl_noop(cx_attr_unused CxList *list) { | 66 static void cx_emptyl_noop(CX_UNUSED CxList *list) { |
| 61 // this is a noop, but MUST be implemented | 67 // this is a noop, but MUST be implemented |
| 62 } | 68 } |
| 63 | 69 |
| 64 static void *cx_emptyl_at( | 70 static void *cx_emptyl_at( |
| 65 cx_attr_unused const struct cx_list_s *list, | 71 CX_UNUSED const struct cx_list_s *list, |
| 66 cx_attr_unused size_t index | 72 CX_UNUSED size_t index |
| 67 ) { | 73 ) { |
| 68 return NULL; | 74 return NULL; |
| 69 } | 75 } |
| 70 | 76 |
| 71 static size_t cx_emptyl_find_remove( | 77 static size_t cx_emptyl_find_remove( |
| 72 cx_attr_unused struct cx_list_s *list, | 78 CX_UNUSED struct cx_list_s *list, |
| 73 cx_attr_unused const void *elem, | 79 CX_UNUSED const void *elem, |
| 74 cx_attr_unused bool remove | 80 CX_UNUSED bool remove |
| 75 ) { | 81 ) { |
| 76 return 0; | 82 return 0; |
| 77 } | 83 } |
| 78 | 84 |
| 79 static bool cx_emptyl_iter_valid(cx_attr_unused const void *iter) { | 85 static bool cx_emptyl_iter_valid(CX_UNUSED const void *iter) { |
| 80 return false; | 86 return false; |
| 81 } | 87 } |
| 82 | 88 |
| 83 static CxIterator cx_emptyl_iterator( | 89 static CxIterator cx_emptyl_iterator( |
| 84 const struct cx_list_s *list, | 90 const struct cx_list_s *list, |
| 85 size_t index, | 91 size_t index, |
| 86 cx_attr_unused bool backwards | 92 CX_UNUSED bool backwards |
| 87 ) { | 93 ) { |
| 88 CxIterator iter = {0}; | 94 CxIterator iter = {0}; |
| 89 iter.src_handle = (void*) list; | 95 iter.src_handle = (void*) list; |
| 90 iter.index = index; | 96 iter.index = index; |
| 91 iter.base.valid = cx_emptyl_iter_valid; | 97 iter.base.valid = cx_emptyl_iter_valid; |
| 139 size_t n | 145 size_t n |
| 140 ) { | 146 ) { |
| 141 const char *src = data; | 147 const char *src = data; |
| 142 size_t i = 0; | 148 size_t i = 0; |
| 143 for (; i < n; i++) { | 149 for (; i < n; i++) { |
| 144 if (NULL == list->cl->insert_element(list, index + i, src) | 150 if (NULL == list->cl->insert_element(list, index + i, src)) { |
| 145 ) { | |
| 146 return i; // LCOV_EXCL_LINE | 151 return i; // LCOV_EXCL_LINE |
| 147 } | 152 } |
| 148 if (src != NULL) { | 153 if (src != NULL) { |
| 149 src += list->collection.elem_size; | 154 src += list->collection.elem_size; |
| 150 } | 155 } |
| 281 size_t n | 286 size_t n |
| 282 ) { | 287 ) { |
| 283 return cx_list_default_insert_sorted_impl(list, sorted_data, n, false); | 288 return cx_list_default_insert_sorted_impl(list, sorted_data, n, false); |
| 284 } | 289 } |
| 285 | 290 |
| 286 // TODO: remove this hack once we have a solution for qsort() / qsort_s() | |
| 287 static _Thread_local CxList *cx_hack_for_qsort_list; | |
| 288 static int cx_hack_cmp_for_qsort(const void *l, const void *r) { | |
| 289 return cx_list_compare_wrapper(l, r, cx_hack_for_qsort_list); | |
| 290 } | |
| 291 | |
| 292 void cx_list_default_sort(struct cx_list_s *list) { | 291 void cx_list_default_sort(struct cx_list_s *list) { |
| 293 size_t elem_size = list->collection.elem_size; | 292 size_t elem_size = list->collection.elem_size; |
| 294 size_t list_size = list->collection.size; | 293 size_t list_size = list->collection.size; |
| 295 void *tmp = cxMallocDefault(elem_size * list_size); | 294 void *tmp = cxMallocDefault(elem_size * list_size); |
| 296 if (tmp == NULL) abort(); // LCOV_EXCL_LINE | 295 if (tmp == NULL) abort(); // LCOV_EXCL_LINE |
| 302 memcpy(loc, src, elem_size); | 301 memcpy(loc, src, elem_size); |
| 303 loc += elem_size; | 302 loc += elem_size; |
| 304 } | 303 } |
| 305 | 304 |
| 306 // qsort | 305 // qsort |
| 307 // TODO: qsort_s() is not as nice as we thought | 306 cx_array_qsort_c(tmp, list_size, elem_size, cx_list_compare_wrapper, list); |
| 308 cx_hack_for_qsort_list = list; | |
| 309 qsort(tmp, list_size, elem_size, cx_hack_cmp_for_qsort); | |
| 310 | 307 |
| 311 // copy elements back | 308 // copy elements back |
| 312 loc = tmp; | 309 loc = tmp; |
| 313 for (size_t i = 0; i < list_size; i++) { | 310 for (size_t i = 0; i < list_size; i++) { |
| 314 void *dest = list->cl->at(list, i); | 311 void *dest = list->cl->at(list, i); |
| 337 memcpy(jp, tmp, elem_size); | 334 memcpy(jp, tmp, elem_size); |
| 338 | 335 |
| 339 cxFreeDefault(tmp); | 336 cxFreeDefault(tmp); |
| 340 | 337 |
| 341 return 0; | 338 return 0; |
| 339 } | |
| 340 | |
| 341 static int cx_list_cmpfunc2_safe_memcmp(const void *a, const void *b, void *c) { | |
| 342 // it is not safe to store a pointer to the size in the list | |
| 343 // because the entire list structure might get reallocated | |
| 344 size_t elem_size = (size_t)(uintptr_t)c; | |
| 345 return memcmp(a, b, elem_size); | |
| 342 } | 346 } |
| 343 | 347 |
| 344 void cx_list_init( | 348 void cx_list_init( |
| 345 struct cx_list_s *list, | 349 struct cx_list_s *list, |
| 346 struct cx_list_class_s *cl, | 350 struct cx_list_class_s *cl, |
| 352 list->collection.size = 0; | 356 list->collection.size = 0; |
| 353 list->collection.sorted = false; // should be set by the implementation | 357 list->collection.sorted = false; // should be set by the implementation |
| 354 if (elem_size > 0) { | 358 if (elem_size > 0) { |
| 355 list->collection.elem_size = elem_size; | 359 list->collection.elem_size = elem_size; |
| 356 list->collection.simple_cmp = NULL; | 360 list->collection.simple_cmp = NULL; |
| 357 list->collection.advanced_cmp = cx_acmp_memcmp; | 361 list->collection.advanced_cmp = cx_list_cmpfunc2_safe_memcmp; |
| 358 list->collection.cmp_data = &list->collection.elem_size; | 362 list->collection.cmp_data = (void*)(uintptr_t)list->collection.elem_size; |
| 359 list->collection.store_pointer = false; | 363 list->collection.store_pointer = false; |
| 360 } else { | 364 } else { |
| 361 list->collection.elem_size = sizeof(void *); | 365 list->collection.elem_size = sizeof(void *); |
| 362 list->collection.simple_cmp = cx_cmp_ptr; | 366 list->collection.simple_cmp = cx_cmp_ptr; |
| 363 list->collection.advanced_cmp = NULL; | 367 list->collection.advanced_cmp = NULL; |
