# HG changeset patch # User Mike Becker # Date 1724959852 -7200 # Node ID ee84ac776cbcb78763a7b6271635dd63dfcaf02e # Parent cdce47f34d489a7f0dfbb110b93fd3fc8887b9e0 add default impl for some list member functions resolves #419 diff -r cdce47f34d48 -r ee84ac776cbc src/cx/list.h --- a/src/cx/list.h Thu Aug 29 20:48:15 2024 +0200 +++ b/src/cx/list.h Thu Aug 29 21:30:52 2024 +0200 @@ -88,6 +88,7 @@ /** * Member function for inserting multiple elements. * Implementors SHOULD see to performant implementations for corner cases. + * @see cx_list_default_insert_array() */ size_t (*insert_array)( struct cx_list_s *list, @@ -120,6 +121,7 @@ /** * Member function for swapping two elements. + * @see cx_list_default_swap() */ int (*swap)( struct cx_list_s *list, @@ -146,11 +148,14 @@ /** * Member function for sorting the list in-place. + * @see cx_list_default_sort() */ void (*sort)(struct cx_list_s *list); /** - * Member function for comparing this list to another list of the same type. + * Optional member function for comparing this list + * to another list of the same type. + * If set to \c NULL, comparison won't be optimized. */ int (*compare)( struct cx_list_s const *list, @@ -173,6 +178,55 @@ }; /** + * Default implementation of an array insert. + * + * This function uses the element insert function for each element of the array. + * + * 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 index the index where to insert the data + * @param data a pointer to the array of 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_array( + struct cx_list_s *list, + size_t index, + void const *data, + size_t n +); + +/** + * Default unoptimized sort implementation. + * + * This function will copy all data to an array, sort the array with standard + * qsort, and then copy the data back to the list memory. + * + * Use this in your own list class if you do not want to implement an optimized + * version for your list. + * + * @param list the list that shall be sorted + */ +__attribute__((__nonnull__)) +void cx_list_default_sort(struct cx_list_s *list); + +/** + * Default unoptimized swap implementation. + * + * Use this in your own list class if you do not want to implement an optimized + * version for your list. + * + * @param list the list in which to swap + * @param i index of one element + * @param j index of the other element + */ +__attribute__((__nonnull__)) +int cx_list_default_swap(struct cx_list_s *list, size_t i, size_t j); + +/** * Common type for all list implementations. */ typedef struct cx_list_s CxList; diff -r cdce47f34d48 -r ee84ac776cbc src/list.c --- a/src/list.c Thu Aug 29 20:48:15 2024 +0200 +++ b/src/list.c Thu Aug 29 21:30:52 2024 +0200 @@ -217,14 +217,6 @@ return -1; } -static int cx_emptyl_compare( - __attribute__((__unused__)) struct cx_list_s const *list, - struct cx_list_s const *other -) { - if (other->collection.size == 0) return 0; - return -1; -} - static bool cx_emptyl_iter_valid(__attribute__((__unused__)) void const *iter) { return false; } @@ -252,7 +244,7 @@ cx_emptyl_at, cx_emptyl_find_remove, cx_emptyl_noop, - cx_emptyl_compare, + NULL, cx_emptyl_noop, cx_emptyl_iterator, }; @@ -276,6 +268,79 @@ // +#define invoke_list_func(name, list, ...) \ + ((list)->climpl == NULL ? (list)->cl->name : (list)->climpl->name) \ + (list, __VA_ARGS__) + +size_t cx_list_default_insert_array( + struct cx_list_s *list, + size_t index, + void const *data, + size_t n +) { + size_t elem_size = list->collection.elem_size; + char const *src = data; + size_t i = 0; + for (; i < n; i++) { + if (0 != invoke_list_func(insert_element, + list, index + i, src + (i * elem_size))) { + return i; + } + } + return i; +} + +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; + void *tmp = malloc(elem_size * list_size); + if (tmp == NULL) abort(); + + // copy elements from source array + char *loc = tmp; + for (size_t i = 0; i < list_size; i++) { + void *src = invoke_list_func(at, list, i); + memcpy(loc, src, elem_size); + loc += elem_size; + } + + // qsort + qsort(tmp, list_size, elem_size, + list->collection.cmpfunc); + + // copy elements back + loc = tmp; + for (size_t i = 0; i < list_size; i++) { + void *dest = invoke_list_func(at, list, i); + memcpy(dest, loc, elem_size); + loc += elem_size; + } + + free(tmp); +} + +int cx_list_default_swap(struct cx_list_s *list, size_t i, size_t j) { + if (i == j) return 0; + if (i >= list->collection.size) return 1; + if (j >= list->collection.size) return 1; + + size_t elem_size = list->collection.elem_size; + + void *tmp = malloc(elem_size); + if (tmp == NULL) return 1; + + void *ip = invoke_list_func(at, list, i); + void *jp = invoke_list_func(at, list, j); + + memcpy(tmp, ip, elem_size); + memcpy(ip, jp, elem_size); + memcpy(jp, tmp, elem_size); + + free(tmp); + + return 0; +} + void cxListDestroy(CxList *list) { list->cl->destructor(list); } @@ -284,17 +349,25 @@ CxList const *list, CxList const *other ) { - if ( - // if one is storing pointers but the other is not - (list->collection.store_pointer ^ other->collection.store_pointer) || + bool cannot_optimize = false; + + // if one is storing pointers but the other is not + cannot_optimize |= list->collection.store_pointer ^ other->collection.store_pointer; + + // if one class is wrapped but the other is not + cannot_optimize |= (list->climpl == NULL) ^ (other->climpl == NULL); - // if one class is wrapped but the other is not - ((list->climpl == NULL) ^ (other->climpl == NULL)) || + // if the compare functions do not match or both are NULL + if (!cannot_optimize) { + cx_compare_func list_cmp = (cx_compare_func) (list->climpl != NULL ? + list->climpl->compare : list->cl->compare); + cx_compare_func other_cmp = (cx_compare_func) (other->climpl != NULL ? + other->climpl->compare : other->cl->compare); + cannot_optimize |= list_cmp != other_cmp; + cannot_optimize |= list_cmp == NULL; + } - // if the resolved compare functions are not the same - ((list->climpl != NULL ? list->climpl->compare : list->cl->compare) != - (other->climpl != NULL ? other->climpl->compare : other->cl->compare)) - ) { + if (cannot_optimize) { // lists are definitely different - cannot use internal compare function if (list->collection.size == other->collection.size) { CxIterator left = list->cl->iterator(list, 0, false); diff -r cdce47f34d48 -r ee84ac776cbc tests/test_list.c --- a/tests/test_list.c Thu Aug 29 20:48:15 2024 +0200 +++ b/tests/test_list.c Thu Aug 29 21:30:52 2024 +0200 @@ -928,9 +928,7 @@ CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));\ } \ cx_testing_allocator_destroy(&talloc); -#define roll_out_test_combos(name, body) \ -static CX_TEST_SUBROUTINE(test_list_verify_##name, CxList *list, \ - __attribute__((__unused__)) bool isptrlist) body \ +#define roll_out_test_invokers(name) \ CX_TEST(test_list_ll_##name) { \ set_up_combo \ CxList *list = cxLinkedListCreate(alloc, cx_cmp_int, sizeof(int)); \ @@ -955,6 +953,61 @@ CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, true); \ tear_down_combo \ } +#define roll_out_test_combos(name, body) \ +static CX_TEST_SUBROUTINE(test_list_verify_##name, CxList *list, \ + __attribute__((__unused__)) bool isptrlist) body \ +roll_out_test_invokers(name) + +static void set_default_class_funcs(CxList *list, cx_list_class *defaulted_cl) { + 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->sort = cx_list_default_sort; + defaulted_cl->swap = cx_list_default_swap; + defaulted_cl->compare = NULL; + if (list->climpl == NULL) { + list->cl = defaulted_cl; + } else { + list->climpl = defaulted_cl; + } +} + +#define do_set_default_class_funcs(list) \ + cx_list_class defaulted_cl; \ + set_default_class_funcs(list, &defaulted_cl) +#define roll_out_test_combos_with_defaulted_funcs(name, body) \ +static CX_TEST_SUBROUTINE(test_list_verify_##name, CxList *list, \ + __attribute__((__unused__)) bool isptrlist) body \ +roll_out_test_invokers(name) \ +CX_TEST(test_list_llm_##name) { \ + set_up_combo \ + CxList *list = cxLinkedListCreate(alloc, cx_cmp_int, sizeof(int)); \ + do_set_default_class_funcs(list); \ + CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, false); \ + tear_down_combo \ +} \ +CX_TEST(test_list_arlm_##name) { \ + set_up_combo \ + CxList *list = cxArrayListCreate(alloc, cx_cmp_int, sizeof(int), 8); \ + do_set_default_class_funcs(list); \ + CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, false); \ + tear_down_combo \ +} \ +CX_TEST(test_list_pllm_##name) { \ + set_up_combo \ + CxList *list = cxLinkedListCreate(alloc, cx_cmp_int, CX_STORE_POINTERS); \ + do_set_default_class_funcs(list); \ + CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, true); \ + tear_down_combo \ +} \ +CX_TEST(test_list_parlm_##name) { \ + set_up_combo \ + CxList *list = cxArrayListCreate(alloc, cx_cmp_int, CX_STORE_POINTERS, 8); \ + do_set_default_class_funcs(list); \ + CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, true); \ + tear_down_combo \ +} + #define array_init(...) {__VA_ARGS__} static inline int *int_test_data_added_to_list(CxList *list, bool isptrlist, size_t len) { @@ -1005,7 +1058,7 @@ CX_TEST_ASSERT(*(int *) cxListAt(list, 3) == 42); }) -roll_out_test_combos(insert_array, { +roll_out_test_combos_with_defaulted_funcs(insert_array, { int a[5] = array_init(5, 47, 11, 13, 42); int b[5] = array_init(9, 18, 72, 50, 7); int *aptr[5]; @@ -1111,7 +1164,7 @@ free(testdata); }) -roll_out_test_combos(swap, { +roll_out_test_combos_with_defaulted_funcs(swap, { int original[16] = array_init(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15); int swapped[16] = array_init(8, 4, 14, 3, 1, 5, 9, 12, 0, 6, 11, 10, 7, 15, 2, 13); @@ -1178,7 +1231,7 @@ free(testdata); }) -roll_out_test_combos(sort, { +roll_out_test_combos_with_defaulted_funcs(sort, { const size_t testdata_len = 250; int *testdata = int_test_data_added_to_list(list, isptrlist, testdata_len); int *expected = malloc(testdata_len*sizeof(int)); @@ -1262,28 +1315,34 @@ CX_TEST_ASSERT(cxIteratorValid(iter)); CX_TEST_ASSERT(iter.index == 2); CX_TEST_ASSERT(*(int *) cxIteratorCurrent(iter) == 2); + CX_TEST_ASSERT(iter.elem_count == 5); cxListInsertAfter(&iter, &newdata[0]); CX_TEST_ASSERT(cxIteratorValid(iter)); CX_TEST_ASSERT(iter.index == 2); CX_TEST_ASSERT(*(int *) cxIteratorCurrent(iter) == 2); + CX_TEST_ASSERT(iter.elem_count == 6); cxListInsertBefore(&iter, &newdata[1]); CX_TEST_ASSERT(cxIteratorValid(iter)); CX_TEST_ASSERT(iter.index == 3); CX_TEST_ASSERT(*(int *) cxIteratorCurrent(iter) == 2); + CX_TEST_ASSERT(iter.elem_count == 7); iter = cxListMutIterator(list); cxListInsertBefore(&iter, &newdata[2]); CX_TEST_ASSERT(cxIteratorValid(iter)); CX_TEST_ASSERT(iter.index == 1); CX_TEST_ASSERT(*(int *) cxIteratorCurrent(iter) == 0); + CX_TEST_ASSERT(iter.elem_count == 8); iter = cxListMutIteratorAt(list, cxListSize(list)); cxListInsertBefore(&iter, &newdata[3]); CX_TEST_ASSERT(!cxIteratorValid(iter)); CX_TEST_ASSERT(iter.index == 9); + CX_TEST_ASSERT(iter.elem_count == 9); iter = cxListMutIteratorAt(list, cxListSize(list)); cxListInsertAfter(&iter, &newdata[4]); CX_TEST_ASSERT(!cxIteratorValid(iter)); CX_TEST_ASSERT(iter.index == 10); + CX_TEST_ASSERT(iter.elem_count == 10); int expdata[] = array_init(30, 0, 1, 20, 2, 10, 3, 4, 40, 50); cx_for_n (j, 10) CX_TEST_ASSERT(*(int *) cxListAt(list, j) == expdata[j]); @@ -1336,6 +1395,20 @@ parl, cxArrayListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS, 50) ) +roll_out_test_combos_with_defaulted_funcs(compare_unoptimized, { + \ + const size_t len = 33; \ + int *testdata = int_test_data_added_to_list(list, isptrlist, len); \ + CxList *other = cxArrayListCreate(cxDefaultAllocator, cx_cmp_int, sizeof(int), 50); \ + do_set_default_class_funcs(other); \ + cx_for_n(i, len) + cxListAdd(other, &testdata[i]); \ + CX_TEST_CALL_SUBROUTINE(test_list_verify_compare, list, other); \ + cxListDestroy(other); \ + free(testdata); \ + +}) + static unsigned destr_test_ctr; static int destr_last_value; @@ -1463,6 +1536,25 @@ return suite; } +CxTestSuite *cx_test_suite_array_list_defaulted_funcs(void) { + CxTestSuite *suite = cx_test_suite_new( + "array_list with defaulted functions"); + + 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_swap); + cx_test_register(suite, test_list_parlm_swap); + cx_test_register(suite, test_list_arlm_sort); + cx_test_register(suite, test_list_parlm_sort); + + cx_test_register(suite, test_list_arl_compare_unoptimized); + cx_test_register(suite, test_list_parl_compare_unoptimized); + cx_test_register(suite, test_list_arlm_compare_unoptimized); + cx_test_register(suite, test_list_parlm_compare_unoptimized); + + return suite; +} + CxTestSuite *cx_test_suite_linked_list(void) { CxTestSuite *suite = cx_test_suite_new("linked_list"); @@ -1534,6 +1626,25 @@ return suite; } +CxTestSuite *cx_test_suite_linked_list_defaulted_funcs(void) { + CxTestSuite *suite = cx_test_suite_new( + "linked_list with defaulted functions"); + + 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_swap); + cx_test_register(suite, test_list_pllm_swap); + cx_test_register(suite, test_list_llm_sort); + cx_test_register(suite, test_list_pllm_sort); + + cx_test_register(suite, test_list_ll_compare_unoptimized); + cx_test_register(suite, test_list_pll_compare_unoptimized); + cx_test_register(suite, test_list_llm_compare_unoptimized); + cx_test_register(suite, test_list_pllm_compare_unoptimized); + + return suite; +} + CxTestSuite *cx_test_suite_empty_list(void) { CxTestSuite *suite = cx_test_suite_new("empty list dummy"); diff -r cdce47f34d48 -r ee84ac776cbc tests/ucxtest.c --- a/tests/ucxtest.c Thu Aug 29 20:48:15 2024 +0200 +++ b/tests/ucxtest.c Thu Aug 29 21:30:52 2024 +0200 @@ -40,6 +40,10 @@ CxTestSuite *cx_test_suite_empty_list(void); CxTestSuite *cx_test_suite_array_list(void); CxTestSuite *cx_test_suite_linked_list(void); + +CxTestSuite *cx_test_suite_array_list_defaulted_funcs(void); + +CxTestSuite *cx_test_suite_linked_list_defaulted_funcs(void); CxTestSuite *cx_test_suite_tree_low_level(void); CxTestSuite *cx_test_suite_mempool(void); CxTestSuite *cx_test_suite_hash_map(void); @@ -65,6 +69,8 @@ cx_test_suite_empty_list(), cx_test_suite_array_list(), cx_test_suite_linked_list(), + cx_test_suite_array_list_defaulted_funcs(), + cx_test_suite_linked_list_defaulted_funcs(), cx_test_suite_tree_low_level(), cx_test_suite_mempool(), cx_test_suite_hash_map()