# HG changeset patch # User Mike Becker # Date 1725194923 -7200 # Node ID f4ce7df9cff04c73a5c5765fd5bbe45c1ba55810 # Parent ee84ac776cbcb78763a7b6271635dd63dfcaf02e add stupid default implementation for high level insertion sort relates to #418 diff -r ee84ac776cbc -r f4ce7df9cff0 src/array_list.c --- a/src/array_list.c Thu Aug 29 21:30:52 2024 +0200 +++ b/src/array_list.c Sun Sep 01 14:48:43 2024 +0200 @@ -521,6 +521,7 @@ cx_arl_destructor, cx_arl_insert_element, cx_arl_insert_array, + cx_list_default_insert_sorted, cx_arl_insert_iter, cx_arl_remove, cx_arl_clear, diff -r ee84ac776cbc -r f4ce7df9cff0 src/cx/list.h --- a/src/cx/list.h Thu Aug 29 21:30:52 2024 +0200 +++ b/src/cx/list.h Sun Sep 01 14:48:43 2024 +0200 @@ -98,6 +98,17 @@ ); /** + * Member function for inserting sorted elements into a sorted list. + * + * @see cx_list_default_insert_sorted() + */ + size_t (*insert_sorted)( + struct cx_list_s *list, + void const *sorted_data, + size_t n + ); + + /** * Member function for inserting an element relative to an iterator position. */ int (*insert_iter)( @@ -200,6 +211,29 @@ ); /** + * Default implementation of a sorted insert. + * + * This function uses the array insert function to insert consecutive groups + * of sorted data. + * + * The source data \em must already be sorted wrt. the list's compare function. + * + * Use this in your own list class if you do not want to implement an optimized + * version for your list. + * + * @param list the list + * @param sorted_data a pointer to the array of pre-sorted data to insert + * @param n the number of elements to insert + * @return the number of elements actually inserted + */ +__attribute__((__nonnull__)) +size_t cx_list_default_insert_sorted( + struct cx_list_s *list, + void const *sorted_data, + size_t n +); + +/** * Default unoptimized sort implementation. * * This function will copy all data to an array, sort the array with standard @@ -345,6 +379,22 @@ } /** + * Inserts an item into a sorted list. + * + * @param list the list + * @param elem a pointer to the element to add + * @return zero on success, non-zero on memory allocation failure + */ +__attribute__((__nonnull__)) +static inline int cxListInsertSorted( + CxList *list, + void const *elem +) { + void const *data = list->collection.store_pointer ? &elem : elem; + return list->cl->insert_sorted(list, data, 1) == 0; +} + +/** * Inserts multiple items to the list at the specified index. * If \p index equals the list size, this is effectively cxListAddArray(). * @@ -374,6 +424,32 @@ } /** + * Inserts a sorted array into a sorted list. + * + * This method is usually more efficient than inserting each element separately, + * because consecutive chunks of sorted data are inserted in one pass. + * + * If there is not enough memory to add all elements, the returned value is + * less than \p n. + * + * If this list is storing pointers instead of objects \p array is expected to + * be an array of pointers. + * + * @param list the list + * @param array a pointer to the elements to add + * @param n the number of elements to add + * @return the number of added elements + */ +__attribute__((__nonnull__)) +static inline size_t cxListInsertSortedArray( + CxList *list, + void const *array, + size_t n +) { + return list->cl->insert_sorted(list, array, n); +} + +/** * Inserts an element after the current location of the specified iterator. * * The used iterator remains operational, but all other active iterators should diff -r ee84ac776cbc -r f4ce7df9cff0 src/linked_list.c --- a/src/linked_list.c Thu Aug 29 21:30:52 2024 +0200 +++ b/src/linked_list.c Sun Sep 01 14:48:43 2024 +0200 @@ -927,6 +927,7 @@ cx_ll_destructor, cx_ll_insert_element, cx_ll_insert_array, + cx_list_default_insert_sorted, cx_ll_insert_iter, cx_ll_remove, cx_ll_clear, diff -r ee84ac776cbc -r f4ce7df9cff0 src/list.c --- a/src/list.c Thu Aug 29 21:30:52 2024 +0200 +++ b/src/list.c Sun Sep 01 14:48:43 2024 +0200 @@ -79,6 +79,17 @@ return list->climpl->insert_array(list, index, array, n); } +static size_t cx_pl_insert_sorted( + struct cx_list_s *list, + void const *array, + size_t n +) { + cx_pl_hack_cmpfunc(list); + size_t result = list->climpl->insert_sorted(list, array, n); + cx_pl_unhack_cmpfunc(list); + return result; +} + static int cx_pl_insert_iter( struct cx_iterator_s *iter, void const *elem, @@ -167,6 +178,7 @@ cx_pl_destructor, cx_pl_insert_element, cx_pl_insert_array, + cx_pl_insert_sorted, cx_pl_insert_iter, cx_pl_remove, cx_pl_clear, @@ -239,6 +251,7 @@ NULL, NULL, NULL, + NULL, cx_emptyl_noop, NULL, cx_emptyl_at, @@ -290,6 +303,21 @@ return i; } +size_t cx_list_default_insert_sorted( + struct cx_list_s *list, + void const *sorted_data, + size_t n +) { + size_t elem_size = list->collection.elem_size; + cx_compare_func cmp = list->collection.cmpfunc; + char const *src = sorted_data; + + size_t r = cx_list_default_insert_array(list, 0, src, n); + cx_list_default_sort(list); + + return r; +} + void cx_list_default_sort(struct cx_list_s *list) { size_t elem_size = list->collection.elem_size; size_t list_size = list->collection.size; diff -r ee84ac776cbc -r f4ce7df9cff0 tests/test_list.c --- a/tests/test_list.c Thu Aug 29 21:30:52 2024 +0200 +++ b/tests/test_list.c Sun Sep 01 14:48:43 2024 +0200 @@ -962,6 +962,7 @@ cx_list_class const *cl = list->climpl == NULL ? list->cl : list->climpl; memcpy(defaulted_cl, cl, sizeof(cx_list_class)); defaulted_cl->insert_array = cx_list_default_insert_array; + defaulted_cl->insert_sorted = cx_list_default_insert_sorted; defaulted_cl->sort = cx_list_default_sort; defaulted_cl->swap = cx_list_default_swap; defaulted_cl->compare = NULL; @@ -1099,6 +1100,54 @@ CX_TEST_ASSERT(*(int *) cxListAt(list, 9) == 42); }) +roll_out_test_combos_with_defaulted_funcs(insert_sorted, { + int d1 = 50; + int d2 = 80; + int d3 = 60; + int d4 = 40; + int d5 = 70; + int d6a[6] = array_init(52, 54, 56, 62, 64, 75); + int d7a[6] = array_init(51, 57, 58, 65, 77, 78); + int d8 = 90; + int *d6ptr[6]; + int *d7ptr[6]; + cx_for_n(i, 6) + { + d6ptr[i] = &d6a[i]; + d7ptr[i] = &d7a[i]; + } + size_t inserted; + int expected[18] = array_init( + 40, 50, 51, 52, 54, 56, 57, 58, 60, + 62, 64, 65, 70, 75, 77, 78, 80, 90 + ); + + CX_TEST_ASSERT(0 == cxListInsertSorted(list, &d1)); + CX_TEST_ASSERT(0 == cxListInsertSorted(list, &d2)); + CX_TEST_ASSERT(0 == cxListInsertSorted(list, &d3)); + CX_TEST_ASSERT(0 == cxListInsertSorted(list, &d4)); + CX_TEST_ASSERT(0 == cxListInsertSorted(list, &d5)); + if (isptrlist) { + inserted = cxListInsertSortedArray(list, d6ptr, 6); + } else { + inserted = cxListInsertSortedArray(list, d6a, 6); + } + CX_TEST_ASSERT(inserted == 6); + if (isptrlist) { + inserted = cxListInsertSortedArray(list, d7ptr, 6); + } else { + inserted = cxListInsertSortedArray(list, d7a, 6); + } + CX_TEST_ASSERT(inserted == 6); + CX_TEST_ASSERT(0 == cxListInsertSorted(list, &d8)); + + CX_TEST_ASSERT(cxListSize(list) == 18); + cx_for_n(i, 18) + { + CX_TEST_ASSERT(*(int *) cxListAt(list, i) == expected[i]); + } +}) + roll_out_test_combos(remove, { const size_t testdata_len = 32; int *testdata = int_test_data_added_to_list(list, isptrlist, testdata_len); @@ -1499,6 +1548,8 @@ cx_test_register(suite, test_list_parl_insert); cx_test_register(suite, test_list_arl_insert_array); cx_test_register(suite, test_list_parl_insert_array); + cx_test_register(suite, test_list_arl_insert_sorted); + cx_test_register(suite, test_list_parl_insert_sorted); cx_test_register(suite, test_list_arl_remove); cx_test_register(suite, test_list_parl_remove); cx_test_register(suite, test_list_arl_find_remove); @@ -1542,6 +1593,8 @@ cx_test_register(suite, test_list_arlm_insert_array); cx_test_register(suite, test_list_parlm_insert_array); + cx_test_register(suite, test_list_arlm_insert_sorted); + cx_test_register(suite, test_list_parlm_insert_sorted); cx_test_register(suite, test_list_arlm_swap); cx_test_register(suite, test_list_parlm_swap); cx_test_register(suite, test_list_arlm_sort); @@ -1589,6 +1642,8 @@ cx_test_register(suite, test_list_pll_insert); cx_test_register(suite, test_list_ll_insert_array); cx_test_register(suite, test_list_pll_insert_array); + cx_test_register(suite, test_list_ll_insert_sorted); + cx_test_register(suite, test_list_pll_insert_sorted); cx_test_register(suite, test_list_ll_remove); cx_test_register(suite, test_list_pll_remove); cx_test_register(suite, test_list_ll_find_remove); @@ -1632,6 +1687,8 @@ cx_test_register(suite, test_list_llm_insert_array); cx_test_register(suite, test_list_pllm_insert_array); + cx_test_register(suite, test_list_llm_insert_sorted); + cx_test_register(suite, test_list_pllm_insert_sorted); cx_test_register(suite, test_list_llm_swap); cx_test_register(suite, test_list_pllm_swap); cx_test_register(suite, test_list_llm_sort);