ucx: test/test_list.c@28bc3e10ac28 (annotated)

test/test_list.c@28bc3e10ac28 (annotated)

test/test_list.c

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 460: e075009b33b7
child 468: 75ae1dccd101
permissions: -rw-r--r--

add special linked list implementation for storing pointers

 /*
  * 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_EQUAL(nodes[0].prev, NULL)
     CU_ASSERT_PTR_EQUAL(nodes[0].next, NULL)
     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 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_last(void) {
     CU_ASSERT_PTR_NULL(cx_linked_list_last(NULL, -1))
     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_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_last(void) {
     cxTestingAllocatorReset();
     int data;
     CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
     CU_ASSERT_PTR_NULL(cxListLast(list))
     data = 5;
     CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
     CU_ASSERT_EQUAL(*(int *) cxListLast(list), 5)
     data = 47;
     CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
     CU_ASSERT_EQUAL(*(int *) cxListLast(list), 47)
     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_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;
     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_add);
     cu_add_test(suite, test_linked_list_last);
     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_last);
     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);
     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;
     if (CU_basic_run_tests()) {
         exitcode = CU_get_error();
     } else {
         exitcode = CU_get_number_of_failures() == 0 ? 0 : 1;
     }
     CU_cleanup_registry();
     return exitcode;
 }

Mercurial > hg > ucx / annotate

test/test_list.c@28bc3e10ac28 (annotated)

test/test_list.c