changeset
add special linked list implementation for storing pointers
Tue, 05 Oct 2021 13:03:45 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Tue, 05 Oct 2021 13:03:45 +0200
- changeset 466
- 28bc3e10ac28
- parent 465
- 1e3cb39815f8
- child 467
- 95e42a963520
add special linked list implementation for storing pointers
| src/cx/linked_list.h | file | annotate | diff | comparison | revisions | |
| src/linked_list.c | file | annotate | diff | comparison | revisions | |
| test/test_list.c | file | annotate | diff | comparison | revisions |
--- a/src/cx/linked_list.h Tue Oct 05 12:25:23 2021 +0200 +++ b/src/cx/linked_list.h Tue Oct 05 13:03:45 2021 +0200 @@ -45,8 +45,36 @@ extern "C" { #endif +/** + * Allocates a linked list for storing elements with \p item_size bytes each. + * + * Elements added to the list are copied. + * + * @param allocator the allocator for allocating the list nodes + * @param comparator the comparator for the elements + * @param item_size the size of each element in bytes + * @return the created list + */ CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size); +/** + * Allocates a linked list for storing pointers. + * + * If you want to store the elements directly in this list, use cxLinkedListCreate(). + * + * @param allocator the allocator for allocating the list nodes + * @param comparator the comparator for the elements + * @return the created list + */ +CxList cxPointerLinkedListCreate(CxAllocator allocator, CxListComparator comparator); + +/** + * Deallocates the memory of the entire list. + * + * \attention If this is a pointer list, the memory the pointers are referring to is \em not freed. + * + * @param list the list + */ void cxLinkedListDestroy(CxList list); size_t cxLinkedListRecalculateSize(CxList list);
--- a/src/linked_list.c Tue Oct 05 12:25:23 2021 +0200 +++ b/src/linked_list.c Tue Oct 05 13:03:45 2021 +0200 @@ -172,6 +172,14 @@ return cx_ll_insert(list, list->size, elem); } +static int cx_pll_insert(cx_list_s *list, size_t index, void *elem) { + return cx_ll_insert(list, index, &elem); +} + +static int cx_pll_add(cx_list_s *list, void *elem) { + return cx_ll_insert(list, list->size, &elem); +} + static int cx_ll_remove(cx_list_s *list, size_t index) { cx_linked_list *ll = (cx_linked_list *) list; cx_linked_list_node *node = cx_ll_node_at(ll, index); @@ -205,7 +213,13 @@ static void *cx_ll_at(cx_list_s *list, size_t index) { cx_linked_list *ll = (cx_linked_list *) list; cx_linked_list_node *node = cx_ll_node_at(ll, index); - return node == NULL ? NULL : &node->payload; + return node == NULL ? NULL : node->payload; +} + +static void *cx_pll_at(cx_list_s *list, size_t index) { + cx_linked_list *ll = (cx_linked_list *) list; + cx_linked_list_node *node = cx_ll_node_at(ll, index); + return node == NULL ? NULL : *(void**)node->payload; } static size_t cx_ll_find(cx_list_s *list, void *elem) { @@ -224,10 +238,32 @@ return index; } +static size_t cx_pll_find(cx_list_s *list, void *elem) { + CxListComparator cmp = list->cmpfunc; + cx_linked_list *ll = (cx_linked_list *) list; + + size_t index; + cx_linked_list_node *node = ll->begin; + for (index = 0; index < list->size; index++) { + void *current = *(void**)node->payload; + if (cmp(current, elem) == 0) { + return index; + } + node = node->next; + } + return index; +} + static void *cx_ll_last(cx_list_s *list) { cx_linked_list *ll = (cx_linked_list *) list; cx_linked_list_node *last = ll->end; - return last == NULL ? NULL : &last->payload; + return last == NULL ? NULL : last->payload; +} + +static void *cx_pll_last(cx_list_s *list) { + cx_linked_list *ll = (cx_linked_list *) list; + cx_linked_list_node *last = ll->end; + return last == NULL ? NULL : *(void**)last->payload; } static cx_list_class cx_linked_list_class = { @@ -239,6 +275,15 @@ cx_ll_last }; +static cx_list_class cx_pointer_linked_list_class = { + cx_pll_add, + cx_pll_insert, + cx_ll_remove, + cx_pll_at, + cx_pll_find, + cx_pll_last +}; + CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) { cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list)); if (list == NULL) @@ -257,6 +302,24 @@ return (CxList) list; } +CxList cxPointerLinkedListCreate(CxAllocator allocator, CxListComparator comparator) { + cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list)); + if (list == NULL) + return NULL; + + list->base.cl = &cx_pointer_linked_list_class; + list->base.allocator = allocator; + list->base.cmpfunc = comparator; + list->base.itemsize = sizeof(void*); + list->base.capacity = SIZE_MAX; + list->base.size = 0; + + list->begin = NULL; + list->end = NULL; + + return (CxList) list; +} + void cxLinkedListDestroy(CxList list) { cx_linked_list *ll = (cx_linked_list *) list;
--- a/test/test_list.c Tue Oct 05 12:25:23 2021 +0200 +++ b/test/test_list.c Tue Oct 05 13:03:45 2021 +0200 @@ -158,19 +158,7 @@ CU_ASSERT_EQUAL(list->itemsize, sizeof(int)) CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int) - // assume this structure for a linked list - struct ll_check { - cx_list_s base; - void *begin; - void *end; - }; - - struct ll_check *actual = (struct ll_check *) list; - CU_ASSERT_PTR_NULL(actual->begin) - CU_ASSERT_PTR_NULL(actual->end) - cxLinkedListDestroy(list); - CU_ASSERT_TRUE(cxTestingAllocatorVerify()) } @@ -190,9 +178,9 @@ CU_ASSERT_EQUAL(list->size, 3) CU_ASSERT_TRUE(list->capacity >= list->size) - CU_ASSERT_EQUAL(*(int*)cxListAt(list, 0), 5) - CU_ASSERT_EQUAL(*(int*)cxListAt(list, 1), 47) - CU_ASSERT_EQUAL(*(int*)cxListAt(list, 2), 13) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13) cxLinkedListDestroy(list); CU_ASSERT_TRUE(cxTestingAllocatorVerify()) @@ -208,11 +196,11 @@ data = 5; CU_ASSERT_EQUAL(cxListAdd(list, &data), 0) - CU_ASSERT_EQUAL(*(int*)cxListLast(list), 5) + CU_ASSERT_EQUAL(*(int *) cxListLast(list), 5) data = 47; CU_ASSERT_EQUAL(cxListAdd(list, &data), 0) - CU_ASSERT_EQUAL(*(int*)cxListLast(list), 47) + CU_ASSERT_EQUAL(*(int *) cxListLast(list), 47) cxLinkedListDestroy(list); CU_ASSERT_TRUE(cxTestingAllocatorVerify()) @@ -241,10 +229,10 @@ CU_ASSERT_EQUAL(list->size, 4) CU_ASSERT_TRUE(list->capacity >= list->size) - CU_ASSERT_EQUAL(*(int*)cxListAt(list, 0), 47) - CU_ASSERT_EQUAL(*(int*)cxListAt(list, 1), 13) - CU_ASSERT_EQUAL(*(int*)cxListAt(list, 2), 5) - CU_ASSERT_EQUAL(*(int*)cxListAt(list, 3), 42) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42) cxLinkedListDestroy(list); CU_ASSERT_TRUE(cxTestingAllocatorVerify()) @@ -273,20 +261,20 @@ CU_ASSERT_EQUAL(cxListRemove(list, 2), 0) CU_ASSERT_EQUAL(list->size, 3) CU_ASSERT_TRUE(list->capacity >= list->size) - CU_ASSERT_EQUAL(*(int*)cxListAt(list, 0), 5) - CU_ASSERT_EQUAL(*(int*)cxListAt(list, 1), 47) - CU_ASSERT_EQUAL(*(int*)cxListAt(list, 2), 13) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13) CU_ASSERT_EQUAL(cxListRemove(list, 0), 0) CU_ASSERT_EQUAL(list->size, 2) CU_ASSERT_TRUE(list->capacity >= list->size) - CU_ASSERT_EQUAL(*(int*)cxListAt(list, 0), 47) - CU_ASSERT_EQUAL(*(int*)cxListAt(list, 1), 13) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13) CU_ASSERT_EQUAL(cxListRemove(list, 1), 0) CU_ASSERT_EQUAL(list->size, 1) CU_ASSERT_TRUE(list->capacity >= list->size) - CU_ASSERT_EQUAL(*(int*)cxListAt(list, 0), 47) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47) CU_ASSERT_EQUAL(cxListRemove(list, 0), 0) CU_ASSERT_EQUAL(list->size, 0) @@ -329,6 +317,171 @@ CU_ASSERT_TRUE(cxTestingAllocatorVerify()) } +void test_hl_ptr_linked_list_create(void) { + cxTestingAllocatorReset(); + + CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int); + + CU_ASSERT_EQUAL(list->size, 0) + CU_ASSERT_EQUAL(list->capacity, (size_t) -1) + CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator) + CU_ASSERT_EQUAL(list->itemsize, sizeof(void *)) + CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int) + + cxLinkedListDestroy(list); + CU_ASSERT_TRUE(cxTestingAllocatorVerify()) +} + +void test_hl_ptr_linked_list_add(void) { + cxTestingAllocatorReset(); + + CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int); + + int a = 5, b = 47, c = 13; + + CU_ASSERT_EQUAL(cxListAdd(list, &a), 0) + CU_ASSERT_EQUAL(cxListAdd(list, &b), 0) + CU_ASSERT_EQUAL(cxListAdd(list, &c), 0) + + CU_ASSERT_EQUAL(list->size, 3) + CU_ASSERT_TRUE(list->capacity >= list->size) + + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13) + + a = 9; + b = 10; + c = 11; + + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 9) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 10) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 11) + + cxLinkedListDestroy(list); + CU_ASSERT_TRUE(cxTestingAllocatorVerify()) +} + +void test_hl_ptr_linked_list_last(void) { + cxTestingAllocatorReset(); + + CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int); + CU_ASSERT_PTR_NULL(cxListLast(list)) + + int a = 5, b = 47; + + CU_ASSERT_EQUAL(cxListAdd(list, &a), 0) + CU_ASSERT_EQUAL(*(int *) cxListLast(list), 5) + CU_ASSERT_EQUAL(cxListAdd(list, &b), 0) + CU_ASSERT_EQUAL(*(int *) cxListLast(list), 47) + + cxLinkedListDestroy(list); + CU_ASSERT_TRUE(cxTestingAllocatorVerify()) +} + +void test_hl_ptr_linked_list_insert(void) { + cxTestingAllocatorReset(); + + CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int); + + int a = 5, b = 47, c = 13, d = 42; + + CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &a), 0) + CU_ASSERT_EQUAL(list->size, 0) + CU_ASSERT_EQUAL(cxListInsert(list, 0, &a), 0) + CU_ASSERT_EQUAL(list->size, 1) + CU_ASSERT_EQUAL(cxListInsert(list, 0, &b), 0) + CU_ASSERT_EQUAL(list->size, 2) + CU_ASSERT_EQUAL(cxListInsert(list, 1, &c), 0) + CU_ASSERT_EQUAL(list->size, 3) + CU_ASSERT_EQUAL(cxListInsert(list, 3, &d), 0) + + CU_ASSERT_EQUAL(list->size, 4) + CU_ASSERT_TRUE(list->capacity >= list->size) + + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42) + + cxLinkedListDestroy(list); + CU_ASSERT_TRUE(cxTestingAllocatorVerify()) +} + +void test_hl_ptr_linked_list_remove(void) { + cxTestingAllocatorReset(); + + int a = 5, b = 47, c = 42, d = 13; + CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int); + + cxListAdd(list, &a); + cxListAdd(list, &b); + cxListAdd(list, &c); + cxListAdd(list, &d); + + CU_ASSERT_EQUAL(list->size, 4) + CU_ASSERT_TRUE(list->capacity >= list->size) + + CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0) + + CU_ASSERT_EQUAL(cxListRemove(list, 2), 0) + CU_ASSERT_EQUAL(list->size, 3) + CU_ASSERT_TRUE(list->capacity >= list->size) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13) + + CU_ASSERT_EQUAL(cxListRemove(list, 0), 0) + CU_ASSERT_EQUAL(list->size, 2) + CU_ASSERT_TRUE(list->capacity >= list->size) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13) + + CU_ASSERT_EQUAL(cxListRemove(list, 1), 0) + CU_ASSERT_EQUAL(list->size, 1) + CU_ASSERT_TRUE(list->capacity >= list->size) + CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47) + + CU_ASSERT_EQUAL(cxListRemove(list, 0), 0) + CU_ASSERT_EQUAL(list->size, 0) + CU_ASSERT_TRUE(list->capacity >= list->size) + + CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0) + + cxLinkedListDestroy(list); + CU_ASSERT_TRUE(cxTestingAllocatorVerify()) +} + +void test_hl_ptr_linked_list_find(void) { + cxTestingAllocatorReset(); + + int a = 5, b = 47, c = 13, criteria; + CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int); + + cxListAdd(list, &a); + cxListAdd(list, &b); + cxListAdd(list, &c); + + CU_ASSERT_EQUAL(list->size, 3) + CU_ASSERT_TRUE(list->capacity >= list->size) + + criteria = 5; + CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0) + criteria = 47; + CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1) + criteria = 13; + CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2) + criteria = 9000; + CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3) + criteria = -5; + CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3) + b = -5; + CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1) + + cxLinkedListDestroy(list); + CU_ASSERT_TRUE(cxTestingAllocatorVerify()) +} + int main() { CU_pSuite suite = NULL; @@ -351,6 +504,15 @@ cu_add_test(suite, test_hl_linked_list_remove); cu_add_test(suite, test_hl_linked_list_find); + suite = CU_add_suite("high level pointer linked list", NULL, NULL); + + cu_add_test(suite, test_hl_ptr_linked_list_create); + cu_add_test(suite, test_hl_ptr_linked_list_add); + cu_add_test(suite, test_hl_ptr_linked_list_last); + 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_basic_set_mode(UCX_CU_BRM); int exitcode;
