Mercurial > hg > ucx / file revision

 /*

  * 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)

     // 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())

 }

 int main() {

     CU_pSuite suite = NULL;

     if (CUE_SUCCESS != CU_initialize_registry()) {

         return CU_get_error();

     }

     suite = CU_add_suite("low level linked list suite", 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 suite", 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);*/

     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;

 }