# HG changeset patch # User Mike Becker # Date 1633522219 -7200 # Node ID 0458bff0b1cdb5e425f3d5bf57f0f8231fc4032c # Parent 75ae1dccd1012a618ac07cb9d0361030fe0f1f03 add high level list sort and inlines method invocation functions diff -r 75ae1dccd101 -r 0458bff0b1cd src/CMakeLists.txt --- a/src/CMakeLists.txt Tue Oct 05 16:33:11 2021 +0200 +++ b/src/CMakeLists.txt Wed Oct 06 14:10:19 2021 +0200 @@ -1,6 +1,5 @@ set(sources allocator.c - list.c linked_list.c tree.c ) diff -r 75ae1dccd101 -r 0458bff0b1cd src/cx/list.h --- a/src/cx/list.h Tue Oct 05 16:33:11 2021 +0200 +++ b/src/cx/list.h Wed Oct 06 14:10:19 2021 +0200 @@ -87,6 +87,11 @@ * Member function for retrieving the last element. */ void *(*last)(cx_list_s *list); + + /** + * Member function for sorting the list in place. + */ + void (*sort)(cx_list_s *list); } cx_list_class; /** @@ -136,7 +141,9 @@ * @param elem a pointer to the element to add * @return zero on success, non-zero on memory allocation failure */ -int cxListAdd(CxList list, void *elem); +static inline int cxListAdd(CxList list, void *elem) { + return list->cl->add(list, elem); +} /** * Inserts an item at the specified index. @@ -154,7 +161,9 @@ * @return zero on success, non-zero on memory allocation failure * or when the index is out of bounds */ -int cxListInsert(CxList list, size_t index, void *elem); +static inline int cxListInsert(CxList list, size_t index, void *elem) { + return list->cl->insert(list, index, elem); +} /** * Removes the element at the specified index. @@ -162,7 +171,9 @@ * @param index the index of the element * @return zero on success, non-zero if the index is out of bounds */ -int cxListRemove(CxList list, size_t index); +static inline int cxListRemove(CxList list, size_t index) { + return list->cl->remove(list, index); +} /** * Returns a pointer to the element at the specified index. @@ -171,7 +182,9 @@ * @param index the index of the element * @return a pointer to the element or \c NULL if the index is out of bounds */ -void *cxListAt(CxList list, size_t index); +static inline void *cxListAt(CxList list, size_t index) { + return list->cl->at(list, index); +} /** * Returns the index of the first element that equals \p elem. @@ -182,7 +195,9 @@ * @param elem the element to find * @return the index of the element or \c (size+1) if the element is not found */ -size_t cxListFind(CxList list, void *elem); +static inline size_t cxListFind(CxList list, void *elem) { + return list->cl->find(list, elem); +} /** * Returns a pointer to the last element of the list. @@ -194,7 +209,20 @@ * @param list the list * @return a pointer to the last element or \c NULL if the list is empty */ -void *cxListLast(CxList list); +static inline void *cxListLast(CxList list) { + return list->cl->last(list); +} + +/** + * Sorts the list in place. + * + * \remark The underlying sort algorithm is implementation defined. + * + * @param list the list + */ +static inline void cxListSort(CxList list) { + list->cl->sort(list); +} #ifdef __cplusplus } /* extern "C" */ diff -r 75ae1dccd101 -r 0458bff0b1cd src/linked_list.c --- a/src/linked_list.c Tue Oct 05 16:33:11 2021 +0200 +++ b/src/linked_list.c Wed Oct 06 14:10:19 2021 +0200 @@ -212,6 +212,7 @@ #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev) #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next) +#define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload) typedef struct { cx_list_s base; @@ -380,13 +381,28 @@ return last == NULL ? NULL : *(void **) last->payload; } +static void cx_ll_sort(cx_list_s *list) { + cx_linked_list *ll = (cx_linked_list *) list; + cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, + CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, + 0, list->cmpfunc); +} + +static void cx_pll_sort(cx_list_s *list) { + cx_linked_list *ll = (cx_linked_list *) list; + cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, + CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, + 1, list->cmpfunc); +} + static cx_list_class cx_linked_list_class = { cx_ll_add, cx_ll_insert, cx_ll_remove, cx_ll_at, cx_ll_find, - cx_ll_last + cx_ll_last, + cx_ll_sort }; static cx_list_class cx_pointer_linked_list_class = { @@ -395,7 +411,8 @@ cx_ll_remove, cx_pll_at, cx_pll_find, - cx_pll_last + cx_pll_last, + cx_pll_sort }; CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) { diff -r 75ae1dccd101 -r 0458bff0b1cd src/list.c --- a/src/list.c Tue Oct 05 16:33:11 2021 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,53 +0,0 @@ -/* - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are met: - * - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE - * POSSIBILITY OF SUCH DAMAGE. - */ - -#include "cx/list.h" - -int cxListAdd(CxList list, void *elem) { - return list->cl->add(list, elem); -} - -int cxListInsert(CxList list, size_t index, void *elem) { - return list->cl->insert(list, index, elem); -} - -int cxListRemove(CxList list, size_t index) { - return list->cl->remove(list, index); -} - -void *cxListAt(CxList list, size_t index) { - return list->cl->at(list, index); -} - -size_t cxListFind(CxList list, void *elem) { - return list->cl->find(list, elem); -} - -void *cxListLast(CxList list) { - return list->cl->last(list); -} diff -r 75ae1dccd101 -r 0458bff0b1cd test/test_list.c --- a/test/test_list.c Tue Oct 05 16:33:11 2021 +0200 +++ b/test/test_list.c Wed Oct 06 14:10:19 2021 +0200 @@ -393,6 +393,42 @@ CU_ASSERT_TRUE(cxTestingAllocatorVerify()) } +void test_hl_linked_list_sort(void) { + int expected[] = { + 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880, + 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894, + 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797, + 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677, + 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681, + 4785, 4791, 4801, 4859, 4903, 4973 + }; + int scrambled[] = { + 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079, + 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888, + 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300, + 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424, + 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973, + 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681 + }; + + cxTestingAllocatorReset(); + + CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int)); + + for (int i = 0 ; i < 100 ; i++) { + cxListAdd(list, &scrambled[i]); + } + + cxListSort(list); + + for (int i = 0 ; i < 100 ; i++) { + CU_ASSERT_EQUAL(*(int*)cxListAt(list, i), expected[i]) + } + + cxLinkedListDestroy(list); + CU_ASSERT_TRUE(cxTestingAllocatorVerify()) +} + void test_hl_ptr_linked_list_create(void) { cxTestingAllocatorReset(); @@ -558,6 +594,42 @@ CU_ASSERT_TRUE(cxTestingAllocatorVerify()) } +void test_hl_ptr_linked_list_sort(void) { + int expected[] = { + 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880, + 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894, + 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797, + 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677, + 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681, + 4785, 4791, 4801, 4859, 4903, 4973 + }; + int scrambled[] = { + 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079, + 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888, + 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300, + 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424, + 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973, + 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681 + }; + + cxTestingAllocatorReset(); + + CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int); + + for (int i = 0 ; i < 100 ; i++) { + cxListAdd(list, &scrambled[i]); + } + + cxListSort(list); + + for (int i = 0 ; i < 100 ; i++) { + CU_ASSERT_EQUAL(*(int*)cxListAt(list, i), expected[i]) + } + + cxLinkedListDestroy(list); + CU_ASSERT_TRUE(cxTestingAllocatorVerify()) +} + int main() { CU_pSuite suite = NULL; @@ -581,6 +653,7 @@ cu_add_test(suite, test_hl_linked_list_insert); cu_add_test(suite, test_hl_linked_list_remove); cu_add_test(suite, test_hl_linked_list_find); + cu_add_test(suite, test_hl_linked_list_sort); suite = CU_add_suite("high level pointer linked list", NULL, NULL); @@ -590,6 +663,7 @@ cu_add_test(suite, test_hl_ptr_linked_list_insert); cu_add_test(suite, test_hl_ptr_linked_list_remove); cu_add_test(suite, test_hl_ptr_linked_list_find); + cu_add_test(suite, test_hl_ptr_linked_list_sort); CU_basic_set_mode(UCX_CU_BRM);