universe@390: /*
universe@390:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
universe@390:  *
universe@390:  * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
universe@390:  *
universe@390:  * Redistribution and use in source and binary forms, with or without
universe@390:  * modification, are permitted provided that the following conditions are met:
universe@390:  *
universe@390:  *   1. Redistributions of source code must retain the above copyright
universe@390:  *      notice, this list of conditions and the following disclaimer.
universe@390:  *
universe@390:  *   2. Redistributions in binary form must reproduce the above copyright
universe@390:  *      notice, this list of conditions and the following disclaimer in the
universe@390:  *      documentation and/or other materials provided with the distribution.
universe@390:  *
universe@390:  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
universe@390:  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
universe@390:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
universe@390:  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
universe@390:  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
universe@390:  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
universe@390:  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
universe@390:  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
universe@390:  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
universe@390:  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
universe@390:  * POSSIBILITY OF SUCH DAMAGE.
universe@390:  */
universe@390: 
universe@398: #include "cx/linked_list.h"
universe@411: #include "test_config.h"
universe@422: #include "util_allocator.h"
universe@398: 
universe@412: int cmp_int(int const *l, int const *r) {
universe@412:     int left = *l, right = *r;
universe@412:     return left == right ? 0 : (left < right ? -1 : 1);
universe@412: }
universe@412: 
universe@438: void test_linked_list_at(void) {
universe@438:     struct node {
universe@438:         void *next;
universe@438:         void *prev;
universe@438:     };
universe@438:     const ptrdiff_t loc_prev = offsetof(struct node, prev);
universe@438:     const ptrdiff_t loc_next = offsetof(struct node, next);
universe@438: 
universe@438:     struct node a, b, c, d;
universe@438:     a.prev = NULL;
universe@438:     a.next = &b;
universe@438:     b.prev = &a;
universe@438:     b.next = &c;
universe@438:     c.prev = &b;
universe@438:     c.next = &d;
universe@438:     d.prev = &c;
universe@438:     d.next = NULL;
universe@438: 
universe@449:     CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 0), &a)
universe@449:     CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 1), &b)
universe@449:     CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 2), &c)
universe@449:     CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 3), &d)
universe@449:     CU_ASSERT_PTR_NULL(cx_linked_list_at(&a, 0, loc_next, 4))
universe@438: 
universe@449:     CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_prev, 0), &a)
universe@449:     CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 1), &b)
universe@449:     CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 2), &c)
universe@449:     CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 3), &d)
universe@449:     CU_ASSERT_PTR_NULL(cx_linked_list_at(&b, 1, loc_next, 4))
universe@438: 
universe@449:     CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&d, 3, loc_prev, 0), &a)
universe@449:     CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&d, 3, loc_prev, 1), &b)
universe@438: }
universe@438: 
olaf@444: void test_linked_list_add(void) {
olaf@442:     struct node {
olaf@442:         void *prev;
olaf@442:         void *next;
olaf@442:     };
universe@449: 
olaf@442:     struct node nodes[4];
universe@449: 
olaf@442:     // test with begin, end / prev, next
universe@449:     memset(nodes, 0, 4 * sizeof(struct node));
olaf@442:     void *begin = NULL;
olaf@442:     void *end = NULL;
universe@449: 
olaf@442:     ptrdiff_t loc_prev = offsetof(struct node, prev);
olaf@442:     ptrdiff_t loc_next = offsetof(struct node, next);
universe@449: 
universe@453:     cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]);
universe@449:     CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
universe@449:     CU_ASSERT_PTR_EQUAL(end, &nodes[0])
universe@449:     CU_ASSERT_PTR_EQUAL(nodes[0].prev, NULL)
universe@449:     CU_ASSERT_PTR_EQUAL(nodes[0].next, NULL)
universe@449: 
universe@453:     cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]);
universe@449:     CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
universe@449:     CU_ASSERT_PTR_EQUAL(end, &nodes[1])
universe@449:     CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
universe@449:     CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
universe@449: 
olaf@442:     // test with begin only / prev, next
universe@449:     memset(nodes, 0, 4 * sizeof(struct node));
olaf@442:     begin = NULL;
olaf@442:     end = NULL;
universe@449: 
universe@453:     cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]);
universe@449:     CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
universe@453:     cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]);
universe@449:     CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
universe@449:     CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
universe@449:     CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
universe@449: 
universe@453:     cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[2]);
universe@449:     CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2])
universe@449:     CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1])
universe@449: 
olaf@442:     // test with begin, end / next
universe@449:     memset(nodes, 0, 4 * sizeof(struct node));
olaf@442:     begin = NULL;
olaf@442:     end = NULL;
universe@449: 
universe@453:     cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]);
universe@449:     CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
universe@449:     CU_ASSERT_PTR_EQUAL(end, &nodes[0])
universe@453:     cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]);
universe@449:     CU_ASSERT_PTR_EQUAL(end, &nodes[1])
universe@449:     CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
universe@449:     CU_ASSERT_PTR_NULL(nodes[1].prev)
olaf@442: }
olaf@442: 
universe@456: void test_linked_list_last(void) {
universe@456:     CU_ASSERT_PTR_NULL(cx_linked_list_last(NULL, 0))
universe@455: 
universe@456:     struct node {
universe@456:         int data;
universe@456:         void *next;
universe@456:     };
universe@456:     ptrdiff_t loc = offsetof(struct node, next);
universe@456: 
universe@456:     struct node third = {3, NULL};
universe@456:     struct node second = {2, &third};
universe@456:     struct node first = {1, &second};
universe@456: 
universe@456:     CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&first, loc), &third)
universe@456:     CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&second, loc), &third)
universe@456:     CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&third, loc), &third)
universe@456: }
universe@456: 
universe@473: void test_linked_list_prev(void) {
universe@473:     struct node {
universe@473:         void *next;
universe@473:     };
universe@473:     ptrdiff_t loc = offsetof(struct node, next);
universe@473: 
universe@473:     struct node third = {NULL};
universe@473:     struct node second = {&third};
universe@473:     struct node first = {&second};
universe@473: 
universe@473:     CU_ASSERT_PTR_NULL(cx_linked_list_prev(&first, loc, &first))
universe@473:     CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(&first, loc, &second), &first)
universe@473:     CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(&first, loc, &third), &second)
universe@473: }
universe@473: 
universe@473: void test_linked_list_remove(void) {
universe@473:     struct node {
universe@473:         void *next;
universe@473:     };
universe@473:     struct dnode {
universe@473:         void *next;
universe@473:         void *prev;
universe@473:     };
universe@473:     ptrdiff_t loc = offsetof(struct node, next);
universe@473:     ptrdiff_t ploc = offsetof(struct dnode, prev);
universe@473: 
universe@473:     void *begin;
universe@473:     void *end;
universe@473:     void *result;
universe@473: 
universe@473:     // single linked list
universe@473:     struct node third = {NULL};
universe@473:     struct node second = {&third};
universe@473:     struct node first = {&second};
universe@473:     begin = &first;
universe@473: 
universe@473:     result = cx_linked_list_remove(&begin, NULL, -1, loc, &second);
universe@473:     CU_ASSERT_PTR_EQUAL(result, &first)
universe@473:     CU_ASSERT_PTR_EQUAL(begin, &first)
universe@473:     CU_ASSERT_PTR_EQUAL(first.next, &third)
universe@473:     CU_ASSERT_PTR_NULL(second.next)
universe@473:     CU_ASSERT_PTR_NULL(third.next)
universe@473: 
universe@473:     result = cx_linked_list_remove(&begin, NULL, -1, loc, &first);
universe@473:     CU_ASSERT_PTR_EQUAL(result, &third)
universe@473:     CU_ASSERT_PTR_EQUAL(begin, &third)
universe@473:     CU_ASSERT_PTR_NULL(first.next)
universe@473:     CU_ASSERT_PTR_NULL(third.next)
universe@473: 
universe@473:     result = cx_linked_list_remove(&begin, NULL, -1, loc, &third);
universe@473:     CU_ASSERT_PTR_NULL(result)
universe@473:     CU_ASSERT_PTR_NULL(begin)
universe@473:     CU_ASSERT_PTR_NULL(third.next)
universe@473: 
universe@473:     // doubly linked list
universe@473:     struct dnode dthird = {NULL , NULL};
universe@473:     struct dnode dsecond = {&dthird, NULL};
universe@473:     struct dnode dfirst = {&dsecond, NULL};
universe@473:     dthird.prev = &dsecond;
universe@473:     dsecond.prev = &dfirst;
universe@473:     begin = &dfirst;
universe@473:     end = &dthird;
universe@473: 
universe@473:     result = cx_linked_list_remove(&begin, &end, ploc, loc, &dsecond);
universe@473:     CU_ASSERT_PTR_EQUAL(result, &dfirst)
universe@473:     CU_ASSERT_PTR_EQUAL(begin, &dfirst)
universe@473:     CU_ASSERT_PTR_EQUAL(end, &dthird)
universe@473:     CU_ASSERT_PTR_NULL(dfirst.prev)
universe@473:     CU_ASSERT_PTR_EQUAL(dfirst.next, &dthird)
universe@473:     CU_ASSERT_PTR_NULL(dsecond.prev)
universe@473:     CU_ASSERT_PTR_NULL(dsecond.next)
universe@473:     CU_ASSERT_PTR_EQUAL(dthird.prev, &dfirst)
universe@473:     CU_ASSERT_PTR_NULL(dthird.next)
universe@473: 
universe@473:     result = cx_linked_list_remove(&begin, &end, ploc, loc, &dthird);
universe@473:     CU_ASSERT_PTR_EQUAL(result, &dfirst)
universe@473:     CU_ASSERT_PTR_EQUAL(begin, &dfirst)
universe@473:     CU_ASSERT_PTR_EQUAL(end, &dfirst)
universe@473:     CU_ASSERT_PTR_NULL(dfirst.prev)
universe@473:     CU_ASSERT_PTR_NULL(dfirst.next)
universe@473:     CU_ASSERT_PTR_NULL(dthird.prev)
universe@473:     CU_ASSERT_PTR_NULL(dthird.next)
universe@473: 
universe@473:     result = cx_linked_list_remove(&begin, &end, ploc, loc, &dfirst);
universe@473:     CU_ASSERT_PTR_NULL(result)
universe@473:     CU_ASSERT_PTR_NULL(begin)
universe@473:     CU_ASSERT_PTR_NULL(end)
universe@473:     CU_ASSERT_PTR_NULL(dfirst.next)
universe@473:     CU_ASSERT_PTR_NULL(dfirst.prev)
universe@473: }
universe@473: 
universe@468: void test_linked_list_size(void) {
universe@468:     struct node {
universe@468:         void *next;
universe@468:     };
universe@468:     ptrdiff_t loc = offsetof(struct node, next);
universe@468: 
universe@468:     struct node first = {NULL};
universe@468:     struct node second = {NULL};
universe@468:     struct node third = {NULL};
universe@468: 
universe@468:     CU_ASSERT_PTR_EQUAL(cx_linked_list_size(NULL, loc), 0)
universe@468:     CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 1)
universe@468:     first.next = &second;
universe@468:     CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 2)
universe@468:     second.next = &third;
universe@468:     CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 3)
universe@468:     CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&second, loc), 2)
universe@468: }
universe@468: 
universe@468: void test_linked_list_sort(void) {
universe@468:     struct node {
universe@468:         void *prev;
universe@468:         void *next;
universe@468:         int data;
universe@468:     };
universe@468: 
universe@468:     int expected[] = {
universe@468:             14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
universe@468:             894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
universe@468:             1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
universe@468:             2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
universe@468:             3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
universe@468:             4785, 4791, 4801, 4859, 4903, 4973
universe@468:     };
universe@468:     int scrambled[] = {
universe@468:             759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
universe@468:             2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
universe@468:             2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
universe@468:             894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
universe@468:             3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
universe@468:             4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
universe@468:     };
universe@468: 
universe@468:     struct node *nodes = calloc(100, sizeof(struct node));
universe@468:     for (int i = 0; i < 100; i++) {
universe@468:         nodes[i].prev = i == 0 ? NULL : &nodes[i - 1];
universe@468:         nodes[i].next = i == 99 ? NULL : &nodes[i + 1];
universe@468:         nodes[i].data = scrambled[i];
universe@468:     }
universe@468: 
universe@468:     struct node *begin = &nodes[0];
universe@468:     struct node *end = &nodes[99];
universe@468: 
universe@468:     cx_linked_list_sort((void **) &begin, (void **) &end,
universe@468:                         offsetof(struct node, prev),
universe@468:                         offsetof(struct node, next),
universe@468:                         offsetof(struct node, data),
universe@468:                         0, (CxListComparator) cmp_int);
universe@468: 
universe@468:     CU_ASSERT_PTR_NULL(begin->prev)
universe@468:     CU_ASSERT_EQUAL(begin->data, expected[0])
universe@468:     struct node *check = begin;
universe@468:     struct node *check_last = NULL;
universe@473:     for (int i = 0; i < 100; i++) {
universe@468:         CU_ASSERT_EQUAL(check->data, expected[i])
universe@468:         CU_ASSERT_PTR_EQUAL(check->prev, check_last)
universe@468:         if (i < 99) {
universe@468:             CU_ASSERT_PTR_NOT_NULL(check->next)
universe@468:         }
universe@468:         check_last = check;
universe@468:         check = check->next;
universe@468:     }
universe@468:     CU_ASSERT_PTR_NULL(check)
universe@468:     CU_ASSERT_EQUAL(end->data, expected[99])
universe@468: }
universe@468: 
universe@473: void test_linked_list_reverse(void) {
universe@473:     struct node {
universe@473:         void *next;
universe@473:     };
universe@473:     struct dnode {
universe@473:         void *next;
universe@473:         void *prev;
universe@473:     };
universe@473:     ptrdiff_t loc = offsetof(struct node, next);
universe@473:     ptrdiff_t ploc = offsetof(struct dnode, prev);
universe@473: 
universe@473:     void *begin;
universe@473:     void *end;
universe@473: 
universe@473:     // single linked list
universe@473:     struct node third = {NULL};
universe@473:     struct node second = {&third};
universe@473:     struct node first = {&second};
universe@473:     begin = &first;
universe@473: 
universe@473:     cx_linked_list_reverse(&begin, NULL, -1, loc);
universe@473:     CU_ASSERT_PTR_EQUAL(begin, &third)
universe@473:     CU_ASSERT_PTR_EQUAL(third.next, &second)
universe@473:     CU_ASSERT_PTR_EQUAL(second.next, &first)
universe@473:     CU_ASSERT_PTR_NULL(first.next)
universe@473: 
universe@473:     // doubly linked list
universe@473:     struct dnode dthird = {NULL , NULL};
universe@473:     struct dnode dsecond = {&dthird, NULL};
universe@473:     struct dnode dfirst = {&dsecond, NULL};
universe@473:     dthird.prev = &dsecond;
universe@473:     dsecond.prev = &dfirst;
universe@473:     begin = &dfirst;
universe@473:     end = &dthird;
universe@473: 
universe@473:     cx_linked_list_reverse(&begin, &end, ploc, loc);
universe@473:     CU_ASSERT_PTR_EQUAL(begin, &dthird)
universe@473:     CU_ASSERT_PTR_EQUAL(end, &dfirst)
universe@473:     CU_ASSERT_PTR_EQUAL(dthird.next, &dsecond)
universe@473:     CU_ASSERT_PTR_EQUAL(dsecond.next, &dfirst)
universe@473:     CU_ASSERT_PTR_NULL(dfirst.next)
universe@473:     CU_ASSERT_PTR_NULL(dthird.prev)
universe@473:     CU_ASSERT_PTR_EQUAL(dsecond.prev, &dthird)
universe@473:     CU_ASSERT_PTR_EQUAL(dfirst.prev, &dsecond)
universe@473: }
universe@456: 
universe@456: void test_hl_linked_list_create(void) {
universe@455:     cxTestingAllocatorReset();
universe@455: 
universe@455:     CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
universe@455: 
universe@455:     CU_ASSERT_EQUAL(list->size, 0)
universe@455:     CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
universe@455:     CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
universe@455:     CU_ASSERT_EQUAL(list->itemsize, sizeof(int))
universe@455:     CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
universe@455: 
universe@455:     cxLinkedListDestroy(list);
universe@455:     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
universe@455: }
universe@455: 
universe@459: void test_hl_linked_list_add(void) {
universe@459:     cxTestingAllocatorReset();
universe@459: 
universe@459:     int data;
universe@459:     CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
universe@459: 
universe@459:     data = 5;
universe@460:     CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
universe@459:     data = 47;
universe@460:     CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
universe@459:     data = 13;
universe@460:     CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
universe@459: 
universe@459:     CU_ASSERT_EQUAL(list->size, 3)
universe@459:     CU_ASSERT_TRUE(list->capacity >= list->size)
universe@459: 
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
universe@459: 
universe@459:     cxLinkedListDestroy(list);
universe@459:     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
universe@459: }
universe@459: 
universe@459: void test_hl_linked_list_last(void) {
universe@459:     cxTestingAllocatorReset();
universe@459: 
universe@459:     int data;
universe@459:     CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
universe@459: 
universe@460:     CU_ASSERT_PTR_NULL(cxListLast(list))
universe@459: 
universe@459:     data = 5;
universe@460:     CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListLast(list), 5)
universe@459: 
universe@459:     data = 47;
universe@460:     CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListLast(list), 47)
universe@459: 
universe@459:     cxLinkedListDestroy(list);
universe@459:     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
universe@459: }
universe@459: 
universe@459: void test_hl_linked_list_insert(void) {
universe@459:     cxTestingAllocatorReset();
universe@459: 
universe@459:     int data;
universe@459:     CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
universe@459: 
universe@459:     data = 5;
universe@460:     CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &data), 0)
universe@459:     CU_ASSERT_EQUAL(list->size, 0)
universe@460:     CU_ASSERT_EQUAL(cxListInsert(list, 0, &data), 0)
universe@459:     CU_ASSERT_EQUAL(list->size, 1)
universe@459:     data = 47;
universe@460:     CU_ASSERT_EQUAL(cxListInsert(list, 0, &data), 0)
universe@459:     CU_ASSERT_EQUAL(list->size, 2)
universe@459:     data = 13;
universe@460:     CU_ASSERT_EQUAL(cxListInsert(list, 1, &data), 0)
universe@459:     CU_ASSERT_EQUAL(list->size, 3)
universe@459:     data = 42;
universe@460:     CU_ASSERT_EQUAL(cxListInsert(list, 3, &data), 0)
universe@459: 
universe@459:     CU_ASSERT_EQUAL(list->size, 4)
universe@459:     CU_ASSERT_TRUE(list->capacity >= list->size)
universe@459: 
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
universe@459: 
universe@459:     cxLinkedListDestroy(list);
universe@459:     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
universe@459: }
universe@459: 
universe@459: void test_hl_linked_list_remove(void) {
universe@459:     cxTestingAllocatorReset();
universe@459: 
universe@459:     int data;
universe@459:     CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
universe@459: 
universe@459:     data = 5;
universe@460:     cxListAdd(list, &data);
universe@459:     data = 47;
universe@460:     cxListAdd(list, &data);
universe@459:     data = 42;
universe@460:     cxListAdd(list, &data);
universe@459:     data = 13;
universe@460:     cxListAdd(list, &data);
universe@459: 
universe@459:     CU_ASSERT_EQUAL(list->size, 4)
universe@459:     CU_ASSERT_TRUE(list->capacity >= list->size)
universe@459: 
universe@459:     CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)
universe@459: 
universe@459:     CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
universe@459:     CU_ASSERT_EQUAL(list->size, 3)
universe@459:     CU_ASSERT_TRUE(list->capacity >= list->size)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
universe@459: 
universe@459:     CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
universe@459:     CU_ASSERT_EQUAL(list->size, 2)
universe@459:     CU_ASSERT_TRUE(list->capacity >= list->size)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
universe@459: 
universe@459:     CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
universe@459:     CU_ASSERT_EQUAL(list->size, 1)
universe@459:     CU_ASSERT_TRUE(list->capacity >= list->size)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
universe@459: 
universe@459:     CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
universe@459:     CU_ASSERT_EQUAL(list->size, 0)
universe@459:     CU_ASSERT_TRUE(list->capacity >= list->size)
universe@459: 
universe@459:     CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
universe@459: 
universe@459:     cxLinkedListDestroy(list);
universe@459:     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
universe@459: }
universe@459: 
universe@459: void test_hl_linked_list_find(void) {
universe@459:     cxTestingAllocatorReset();
universe@459: 
universe@459:     int data, criteria;
universe@459:     CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
universe@459: 
universe@459:     data = 5;
universe@460:     cxListAdd(list, &data);
universe@459:     data = 47;
universe@460:     cxListAdd(list, &data);
universe@459:     data = 13;
universe@460:     cxListAdd(list, &data);
universe@459: 
universe@459:     CU_ASSERT_EQUAL(list->size, 3)
universe@459:     CU_ASSERT_TRUE(list->capacity >= list->size)
universe@459: 
universe@459:     criteria = 5;
universe@460:     CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0)
universe@459:     criteria = 47;
universe@460:     CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
universe@459:     criteria = 13;
universe@460:     CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2)
universe@459:     criteria = 9000;
universe@460:     CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
universe@459:     criteria = -5;
universe@460:     CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
universe@459: 
universe@459:     cxLinkedListDestroy(list);
universe@459:     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
universe@459: }
universe@459: 
universe@469: void test_hl_linked_list_sort(void) {
universe@469:     int expected[] = {
universe@469:             14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
universe@469:             894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
universe@469:             1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
universe@469:             2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
universe@469:             3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
universe@469:             4785, 4791, 4801, 4859, 4903, 4973
universe@469:     };
universe@469:     int scrambled[] = {
universe@469:             759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
universe@469:             2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
universe@469:             2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
universe@469:             894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
universe@469:             3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
universe@469:             4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
universe@469:     };
universe@469: 
universe@469:     cxTestingAllocatorReset();
universe@469: 
universe@469:     CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
universe@469: 
universe@473:     for (int i = 0; i < 100; i++) {
universe@469:         cxListAdd(list, &scrambled[i]);
universe@469:     }
universe@469: 
universe@469:     cxListSort(list);
universe@469: 
universe@473:     for (int i = 0; i < 100; i++) {
universe@473:         CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i])
universe@469:     }
universe@469: 
universe@469:     cxLinkedListDestroy(list);
universe@469:     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
universe@469: }
universe@469: 
universe@466: void test_hl_ptr_linked_list_create(void) {
universe@466:     cxTestingAllocatorReset();
universe@466: 
universe@466:     CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
universe@466: 
universe@466:     CU_ASSERT_EQUAL(list->size, 0)
universe@466:     CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
universe@466:     CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
universe@466:     CU_ASSERT_EQUAL(list->itemsize, sizeof(void *))
universe@466:     CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
universe@466: 
universe@466:     cxLinkedListDestroy(list);
universe@466:     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
universe@466: }
universe@466: 
universe@466: void test_hl_ptr_linked_list_add(void) {
universe@466:     cxTestingAllocatorReset();
universe@466: 
universe@466:     CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
universe@466: 
universe@466:     int a = 5, b = 47, c = 13;
universe@466: 
universe@466:     CU_ASSERT_EQUAL(cxListAdd(list, &a), 0)
universe@466:     CU_ASSERT_EQUAL(cxListAdd(list, &b), 0)
universe@466:     CU_ASSERT_EQUAL(cxListAdd(list, &c), 0)
universe@466: 
universe@466:     CU_ASSERT_EQUAL(list->size, 3)
universe@466:     CU_ASSERT_TRUE(list->capacity >= list->size)
universe@466: 
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
universe@466: 
universe@466:     a = 9;
universe@466:     b = 10;
universe@466:     c = 11;
universe@466: 
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 9)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 10)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 11)
universe@466: 
universe@466:     cxLinkedListDestroy(list);
universe@466:     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
universe@466: }
universe@466: 
universe@466: void test_hl_ptr_linked_list_last(void) {
universe@466:     cxTestingAllocatorReset();
universe@466: 
universe@466:     CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
universe@466:     CU_ASSERT_PTR_NULL(cxListLast(list))
universe@466: 
universe@466:     int a = 5, b = 47;
universe@466: 
universe@466:     CU_ASSERT_EQUAL(cxListAdd(list, &a), 0)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListLast(list), 5)
universe@466:     CU_ASSERT_EQUAL(cxListAdd(list, &b), 0)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListLast(list), 47)
universe@466: 
universe@466:     cxLinkedListDestroy(list);
universe@466:     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
universe@466: }
universe@466: 
universe@466: void test_hl_ptr_linked_list_insert(void) {
universe@466:     cxTestingAllocatorReset();
universe@466: 
universe@466:     CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
universe@466: 
universe@466:     int a = 5, b = 47, c = 13, d = 42;
universe@466: 
universe@466:     CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &a), 0)
universe@466:     CU_ASSERT_EQUAL(list->size, 0)
universe@466:     CU_ASSERT_EQUAL(cxListInsert(list, 0, &a), 0)
universe@466:     CU_ASSERT_EQUAL(list->size, 1)
universe@466:     CU_ASSERT_EQUAL(cxListInsert(list, 0, &b), 0)
universe@466:     CU_ASSERT_EQUAL(list->size, 2)
universe@466:     CU_ASSERT_EQUAL(cxListInsert(list, 1, &c), 0)
universe@466:     CU_ASSERT_EQUAL(list->size, 3)
universe@466:     CU_ASSERT_EQUAL(cxListInsert(list, 3, &d), 0)
universe@466: 
universe@466:     CU_ASSERT_EQUAL(list->size, 4)
universe@466:     CU_ASSERT_TRUE(list->capacity >= list->size)
universe@466: 
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
universe@466: 
universe@466:     cxLinkedListDestroy(list);
universe@466:     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
universe@466: }
universe@466: 
universe@466: void test_hl_ptr_linked_list_remove(void) {
universe@466:     cxTestingAllocatorReset();
universe@466: 
universe@466:     int a = 5, b = 47, c = 42, d = 13;
universe@466:     CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
universe@466: 
universe@466:     cxListAdd(list, &a);
universe@466:     cxListAdd(list, &b);
universe@466:     cxListAdd(list, &c);
universe@466:     cxListAdd(list, &d);
universe@466: 
universe@466:     CU_ASSERT_EQUAL(list->size, 4)
universe@466:     CU_ASSERT_TRUE(list->capacity >= list->size)
universe@466: 
universe@466:     CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)
universe@466: 
universe@466:     CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
universe@466:     CU_ASSERT_EQUAL(list->size, 3)
universe@466:     CU_ASSERT_TRUE(list->capacity >= list->size)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
universe@466: 
universe@466:     CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
universe@466:     CU_ASSERT_EQUAL(list->size, 2)
universe@466:     CU_ASSERT_TRUE(list->capacity >= list->size)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
universe@466: 
universe@466:     CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
universe@466:     CU_ASSERT_EQUAL(list->size, 1)
universe@466:     CU_ASSERT_TRUE(list->capacity >= list->size)
universe@466:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
universe@466: 
universe@466:     CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
universe@466:     CU_ASSERT_EQUAL(list->size, 0)
universe@466:     CU_ASSERT_TRUE(list->capacity >= list->size)
universe@466: 
universe@466:     CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
universe@466: 
universe@466:     cxLinkedListDestroy(list);
universe@466:     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
universe@466: }
universe@466: 
universe@466: void test_hl_ptr_linked_list_find(void) {
universe@466:     cxTestingAllocatorReset();
universe@466: 
universe@466:     int a = 5, b = 47, c = 13, criteria;
universe@466:     CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
universe@466: 
universe@466:     cxListAdd(list, &a);
universe@466:     cxListAdd(list, &b);
universe@466:     cxListAdd(list, &c);
universe@466: 
universe@466:     CU_ASSERT_EQUAL(list->size, 3)
universe@466:     CU_ASSERT_TRUE(list->capacity >= list->size)
universe@466: 
universe@466:     criteria = 5;
universe@466:     CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0)
universe@466:     criteria = 47;
universe@466:     CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
universe@466:     criteria = 13;
universe@466:     CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2)
universe@466:     criteria = 9000;
universe@466:     CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
universe@466:     criteria = -5;
universe@466:     CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
universe@466:     b = -5;
universe@466:     CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
universe@466: 
universe@466:     cxLinkedListDestroy(list);
universe@466:     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
universe@466: }
universe@466: 
universe@469: void test_hl_ptr_linked_list_sort(void) {
universe@469:     int expected[] = {
universe@469:             14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
universe@469:             894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
universe@469:             1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
universe@469:             2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
universe@469:             3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
universe@469:             4785, 4791, 4801, 4859, 4903, 4973
universe@469:     };
universe@469:     int scrambled[] = {
universe@469:             759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
universe@469:             2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
universe@469:             2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
universe@469:             894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
universe@469:             3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
universe@469:             4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
universe@469:     };
universe@469: 
universe@469:     cxTestingAllocatorReset();
universe@469: 
universe@469:     CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
universe@469: 
universe@473:     for (int i = 0; i < 100; i++) {
universe@469:         cxListAdd(list, &scrambled[i]);
universe@469:     }
universe@469: 
universe@469:     cxListSort(list);
universe@469: 
universe@473:     for (int i = 0; i < 100; i++) {
universe@473:         CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i])
universe@469:     }
universe@469: 
universe@469:     cxLinkedListDestroy(list);
universe@469:     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
universe@469: }
universe@469: 
universe@390: int main() {
universe@411:     CU_pSuite suite = NULL;
universe@449: 
universe@411:     if (CUE_SUCCESS != CU_initialize_registry()) {
universe@411:         return CU_get_error();
universe@411:     }
universe@411: 
universe@459:     suite = CU_add_suite("low level linked list", NULL, NULL);
universe@449: 
universe@455:     cu_add_test(suite, test_linked_list_at);
universe@455:     cu_add_test(suite, test_linked_list_add);
universe@456:     cu_add_test(suite, test_linked_list_last);
universe@473:     cu_add_test(suite, test_linked_list_prev);
universe@473:     cu_add_test(suite, test_linked_list_remove);
universe@468:     cu_add_test(suite, test_linked_list_size);
universe@468:     cu_add_test(suite, test_linked_list_sort);
universe@473:     cu_add_test(suite, test_linked_list_reverse);
universe@455: 
universe@459:     suite = CU_add_suite("high level linked list", NULL, NULL);
universe@455: 
universe@456:     cu_add_test(suite, test_hl_linked_list_create);
universe@456:     cu_add_test(suite, test_hl_linked_list_add);
universe@456:     cu_add_test(suite, test_hl_linked_list_last);
universe@456:     cu_add_test(suite, test_hl_linked_list_insert);
universe@456:     cu_add_test(suite, test_hl_linked_list_remove);
universe@459:     cu_add_test(suite, test_hl_linked_list_find);
universe@469:     cu_add_test(suite, test_hl_linked_list_sort);
universe@413: 
universe@466:     suite = CU_add_suite("high level pointer linked list", NULL, NULL);
universe@466: 
universe@466:     cu_add_test(suite, test_hl_ptr_linked_list_create);
universe@466:     cu_add_test(suite, test_hl_ptr_linked_list_add);
universe@466:     cu_add_test(suite, test_hl_ptr_linked_list_last);
universe@466:     cu_add_test(suite, test_hl_ptr_linked_list_insert);
universe@466:     cu_add_test(suite, test_hl_ptr_linked_list_remove);
universe@466:     cu_add_test(suite, test_hl_ptr_linked_list_find);
universe@469:     cu_add_test(suite, test_hl_ptr_linked_list_sort);
universe@466: 
universe@411:     CU_basic_set_mode(UCX_CU_BRM);
universe@411: 
universe@411:     int exitcode;
universe@411:     if (CU_basic_run_tests()) {
universe@411:         exitcode = CU_get_error();
universe@411:     } else {
universe@411:         exitcode = CU_get_number_of_failures() == 0 ? 0 : 1;
universe@411:     }
universe@411:     CU_cleanup_registry();
universe@411:     return exitcode;
universe@390: }