test/test_list.c@60ff4561dc04
test/test_list.c
Mon, 20 Dec 2021 11:17:06 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Mon, 20 Dec 2021 11:17:06 +0100
- changeset 476
- 60ff4561dc04
- parent 475
- 31bf97fdbf71
- child 478
- 599770bb6314
- permissions
- -rw-r--r--
change contract of cx_linked_list_remove()
also use cx_linked_list_remove() in high level API
/* * 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/linked_list.h" #include "test_config.h" #include "util_allocator.h" int cmp_int(int const *l, int const *r) { int left = *l, right = *r; return left == right ? 0 : (left < right ? -1 : 1); } void test_linked_list_at(void) { struct node { void *next; void *prev; }; const ptrdiff_t loc_prev = offsetof(struct node, prev); const ptrdiff_t loc_next = offsetof(struct node, next); struct node a, b, c, d; a.prev = NULL; a.next = &b; b.prev = &a; b.next = &c; c.prev = &b; c.next = &d; d.prev = &c; d.next = NULL; CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 0), &a) CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 1), &b) CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 2), &c) CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 3), &d) CU_ASSERT_PTR_NULL(cx_linked_list_at(&a, 0, loc_next, 4)) CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_prev, 0), &a) CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 1), &b) CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 2), &c) CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 3), &d) CU_ASSERT_PTR_NULL(cx_linked_list_at(&b, 1, loc_next, 4)) CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&d, 3, loc_prev, 0), &a) CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&d, 3, loc_prev, 1), &b) } void test_linked_list_add(void) { struct node { void *prev; void *next; }; struct node nodes[4]; // test with begin, end / prev, next memset(nodes, 0, 4 * sizeof(struct node)); void *begin = NULL; void *end = NULL; ptrdiff_t loc_prev = offsetof(struct node, prev); ptrdiff_t loc_next = offsetof(struct node, next); cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]); CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) CU_ASSERT_PTR_EQUAL(end, &nodes[0]) CU_ASSERT_PTR_NULL(nodes[0].prev) CU_ASSERT_PTR_NULL(nodes[0].next) cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]); CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) CU_ASSERT_PTR_EQUAL(end, &nodes[1]) CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1]) CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0]) // test with begin only / prev, next memset(nodes, 0, 4 * sizeof(struct node)); begin = NULL; end = NULL; cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]); CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]); CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1]) CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0]) cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[2]); CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2]) CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1]) // test with end only / prev, next memset(nodes, 0, 4 * sizeof(struct node)); begin = NULL; end = NULL; cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]); CU_ASSERT_PTR_EQUAL(end, &nodes[0]) cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]); CU_ASSERT_PTR_EQUAL(end, &nodes[1]) CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1]) CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0]) cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[2]); CU_ASSERT_PTR_EQUAL(end, &nodes[2]) CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2]) CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1]) // test with begin, end / next memset(nodes, 0, 4 * sizeof(struct node)); begin = NULL; end = NULL; cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]); CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) CU_ASSERT_PTR_EQUAL(end, &nodes[0]) cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]); CU_ASSERT_PTR_EQUAL(end, &nodes[1]) CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1]) CU_ASSERT_PTR_NULL(nodes[1].prev) } void test_linked_list_prepend(void) { struct node { void *prev; void *next; }; struct node nodes[4]; // test with begin, end / prev, next memset(nodes, 0, 4 * sizeof(struct node)); void *begin = NULL; void *end = NULL; ptrdiff_t loc_prev = offsetof(struct node, prev); ptrdiff_t loc_next = offsetof(struct node, next); cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]); CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) CU_ASSERT_PTR_EQUAL(end, &nodes[0]) CU_ASSERT_PTR_NULL(nodes[0].prev) CU_ASSERT_PTR_NULL(nodes[0].next) cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]); CU_ASSERT_PTR_EQUAL(begin, &nodes[1]) CU_ASSERT_PTR_EQUAL(end, &nodes[0]) CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0]) CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1]) // test with begin only / prev, next memset(nodes, 0, 4 * sizeof(struct node)); begin = NULL; end = NULL; cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]); CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]); CU_ASSERT_PTR_EQUAL(begin, &nodes[1]) CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0]) CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1]) cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[2]); CU_ASSERT_PTR_EQUAL(begin, &nodes[2]) CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1]) CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2]) // test with end only / prev, next memset(nodes, 0, 4 * sizeof(struct node)); begin = NULL; end = NULL; cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]); CU_ASSERT_PTR_EQUAL(end, &nodes[0]) cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]); CU_ASSERT_PTR_EQUAL(end, &nodes[0]) CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0]) CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1]) cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[2]); CU_ASSERT_PTR_EQUAL(end, &nodes[0]) CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1]) CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2]) // test with begin, end / next memset(nodes, 0, 4 * sizeof(struct node)); begin = NULL; end = NULL; cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]); CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) CU_ASSERT_PTR_EQUAL(end, &nodes[0]) cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]); cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]); CU_ASSERT_PTR_EQUAL(begin, &nodes[2]) CU_ASSERT_PTR_EQUAL(end, &nodes[0]) CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0]) CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1]) CU_ASSERT_PTR_NULL(nodes[1].prev) CU_ASSERT_PTR_NULL(nodes[0].prev) } void test_linked_list_first(void) { CU_ASSERT_PTR_NULL(cx_linked_list_first(NULL, 0)) struct node { int data; void *prev; }; ptrdiff_t loc = offsetof(struct node, prev); struct node first = {1, NULL}; struct node second = {2, &first}; struct node third = {3, &second}; CU_ASSERT_PTR_EQUAL(cx_linked_list_first(&first, loc), &first) CU_ASSERT_PTR_EQUAL(cx_linked_list_first(&second, loc), &first) CU_ASSERT_PTR_EQUAL(cx_linked_list_first(&third, loc), &first) } void test_linked_list_last(void) { CU_ASSERT_PTR_NULL(cx_linked_list_last(NULL, 0)) struct node { int data; void *next; }; ptrdiff_t loc = offsetof(struct node, next); struct node third = {3, NULL}; struct node second = {2, &third}; struct node first = {1, &second}; CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&first, loc), &third) CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&second, loc), &third) CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&third, loc), &third) } void test_linked_list_prev(void) { struct node { void *next; }; ptrdiff_t loc = offsetof(struct node, next); struct node third = {NULL}; struct node second = {&third}; struct node first = {&second}; CU_ASSERT_PTR_NULL(cx_linked_list_prev(&first, loc, &first)) CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(&first, loc, &second), &first) CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(&first, loc, &third), &second) } void test_linked_list_remove(void) { struct node { void *next; }; struct dnode { void *next; void *prev; }; ptrdiff_t loc = offsetof(struct node, next); ptrdiff_t ploc = offsetof(struct dnode, prev); void *begin; void *end; // single linked list struct node third = {NULL}; struct node second = {&third}; struct node first = {&second}; begin = &first; cx_linked_list_remove(&begin, NULL, -1, loc, &second); CU_ASSERT_PTR_EQUAL(begin, &first) CU_ASSERT_PTR_EQUAL(first.next, &third) CU_ASSERT_PTR_NULL(third.next) cx_linked_list_remove(&begin, NULL, -1, loc, &first); CU_ASSERT_PTR_EQUAL(begin, &third) CU_ASSERT_PTR_NULL(third.next) cx_linked_list_remove(&begin, NULL, -1, loc, &third); CU_ASSERT_PTR_NULL(begin) // doubly linked list struct dnode dthird = {NULL , NULL}; struct dnode dsecond = {&dthird, NULL}; struct dnode dfirst = {&dsecond, NULL}; dthird.prev = &dsecond; dsecond.prev = &dfirst; begin = &dfirst; end = &dthird; cx_linked_list_remove(&begin, &end, ploc, loc, &dsecond); CU_ASSERT_PTR_EQUAL(begin, &dfirst) CU_ASSERT_PTR_EQUAL(end, &dthird) CU_ASSERT_PTR_NULL(dfirst.prev) CU_ASSERT_PTR_EQUAL(dfirst.next, &dthird) CU_ASSERT_PTR_EQUAL(dthird.prev, &dfirst) CU_ASSERT_PTR_NULL(dthird.next) cx_linked_list_remove(&begin, &end, ploc, loc, &dthird); CU_ASSERT_PTR_EQUAL(begin, &dfirst) CU_ASSERT_PTR_EQUAL(end, &dfirst) CU_ASSERT_PTR_NULL(dfirst.prev) CU_ASSERT_PTR_NULL(dfirst.next) cx_linked_list_remove(&begin, &end, ploc, loc, &dfirst); CU_ASSERT_PTR_NULL(begin) CU_ASSERT_PTR_NULL(end) } void test_linked_list_size(void) { struct node { void *next; }; ptrdiff_t loc = offsetof(struct node, next); struct node first = {NULL}; struct node second = {NULL}; struct node third = {NULL}; CU_ASSERT_PTR_EQUAL(cx_linked_list_size(NULL, loc), 0) CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 1) first.next = &second; CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 2) second.next = &third; CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 3) CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&second, loc), 2) } void test_linked_list_sort(void) { struct node { void *prev; void *next; int data; }; 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 }; struct node *nodes = calloc(100, sizeof(struct node)); for (int i = 0; i < 100; i++) { nodes[i].prev = i == 0 ? NULL : &nodes[i - 1]; nodes[i].next = i == 99 ? NULL : &nodes[i + 1]; nodes[i].data = scrambled[i]; } struct node *begin = &nodes[0]; struct node *end = &nodes[99]; cx_linked_list_sort((void **) &begin, (void **) &end, offsetof(struct node, prev), offsetof(struct node, next), offsetof(struct node, data), 0, (CxListComparator) cmp_int); CU_ASSERT_PTR_NULL(begin->prev) CU_ASSERT_EQUAL(begin->data, expected[0]) struct node *check = begin; struct node *check_last = NULL; for (int i = 0; i < 100; i++) { CU_ASSERT_EQUAL(check->data, expected[i]) CU_ASSERT_PTR_EQUAL(check->prev, check_last) if (i < 99) { CU_ASSERT_PTR_NOT_NULL(check->next) } check_last = check; check = check->next; } CU_ASSERT_PTR_NULL(check) CU_ASSERT_EQUAL(end->data, expected[99]) } void test_linked_list_reverse(void) { struct node { void *next; }; struct dnode { void *next; void *prev; }; ptrdiff_t loc = offsetof(struct node, next); ptrdiff_t ploc = offsetof(struct dnode, prev); void *begin; void *end; // single linked list struct node third = {NULL}; struct node second = {&third}; struct node first = {&second}; begin = &first; cx_linked_list_reverse(&begin, NULL, -1, loc); CU_ASSERT_PTR_EQUAL(begin, &third) CU_ASSERT_PTR_EQUAL(third.next, &second) CU_ASSERT_PTR_EQUAL(second.next, &first) CU_ASSERT_PTR_NULL(first.next) // doubly linked list struct dnode dthird = {NULL , NULL}; struct dnode dsecond = {&dthird, NULL}; struct dnode dfirst = {&dsecond, NULL}; dthird.prev = &dsecond; dsecond.prev = &dfirst; begin = &dfirst; end = &dthird; cx_linked_list_reverse(&begin, &end, ploc, loc); CU_ASSERT_PTR_EQUAL(begin, &dthird) CU_ASSERT_PTR_EQUAL(end, &dfirst) CU_ASSERT_PTR_EQUAL(dthird.next, &dsecond) CU_ASSERT_PTR_EQUAL(dsecond.next, &dfirst) CU_ASSERT_PTR_NULL(dfirst.next) CU_ASSERT_PTR_NULL(dthird.prev) CU_ASSERT_PTR_EQUAL(dsecond.prev, &dthird) CU_ASSERT_PTR_EQUAL(dfirst.prev, &dsecond) } void test_hl_linked_list_create(void) { cxTestingAllocatorReset(); CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(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(int)) CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int) cxLinkedListDestroy(list); CU_ASSERT_TRUE(cxTestingAllocatorVerify()) } void test_hl_linked_list_add(void) { cxTestingAllocatorReset(); int data; CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int)); data = 5; CU_ASSERT_EQUAL(cxListAdd(list, &data), 0) data = 47; CU_ASSERT_EQUAL(cxListAdd(list, &data), 0) data = 13; CU_ASSERT_EQUAL(cxListAdd(list, &data), 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) cxLinkedListDestroy(list); CU_ASSERT_TRUE(cxTestingAllocatorVerify()) } void test_hl_linked_list_insert(void) { cxTestingAllocatorReset(); int data; CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int)); data = 5; CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &data), 0) CU_ASSERT_EQUAL(list->size, 0) CU_ASSERT_EQUAL(cxListInsert(list, 0, &data), 0) CU_ASSERT_EQUAL(list->size, 1) data = 47; CU_ASSERT_EQUAL(cxListInsert(list, 0, &data), 0) CU_ASSERT_EQUAL(list->size, 2) data = 13; CU_ASSERT_EQUAL(cxListInsert(list, 1, &data), 0) CU_ASSERT_EQUAL(list->size, 3) data = 42; CU_ASSERT_EQUAL(cxListInsert(list, 3, &data), 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_linked_list_remove(void) { cxTestingAllocatorReset(); int data; CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int)); data = 5; cxListAdd(list, &data); data = 47; cxListAdd(list, &data); data = 42; cxListAdd(list, &data); data = 13; cxListAdd(list, &data); 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_linked_list_find(void) { cxTestingAllocatorReset(); int data, criteria; CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int)); data = 5; cxListAdd(list, &data); data = 47; cxListAdd(list, &data); data = 13; cxListAdd(list, &data); 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) cxLinkedListDestroy(list); 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(); 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_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()) } 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; if (CUE_SUCCESS != CU_initialize_registry()) { return CU_get_error(); } suite = CU_add_suite("low level linked list", NULL, NULL); cu_add_test(suite, test_linked_list_at); cu_add_test(suite, test_linked_list_prepend); cu_add_test(suite, test_linked_list_add); cu_add_test(suite, test_linked_list_first); cu_add_test(suite, test_linked_list_last); cu_add_test(suite, test_linked_list_prev); cu_add_test(suite, test_linked_list_remove); cu_add_test(suite, test_linked_list_size); cu_add_test(suite, test_linked_list_sort); cu_add_test(suite, test_linked_list_reverse); suite = CU_add_suite("high level linked list", NULL, NULL); cu_add_test(suite, test_hl_linked_list_create); cu_add_test(suite, test_hl_linked_list_add); 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); 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_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); int exitcode; if (CU_basic_run_tests()) { exitcode = CU_get_error(); } else { exitcode = CU_get_number_of_failures() == 0 ? 0 : 1; } CU_cleanup_registry(); return exitcode; }
