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@509: #include "cx/utils.h"
universe@411: #include "test_config.h"
universe@422: #include "util_allocator.h"
universe@398: 
universe@507: static int cmp_int_impl(
universe@486:         int const *l,
universe@486:         int const *r
universe@486: ) {
universe@412:     int left = *l, right = *r;
universe@412:     return left == right ? 0 : (left < right ? -1 : 1);
universe@412: }
universe@412: 
universe@492: #define cmp_int ((CxListComparator) cmp_int_impl)
universe@492: 
universe@486: struct node {
universe@486:     struct node *next;
universe@486:     struct node *prev;
universe@486:     int data;
universe@486: };
universe@486: 
universe@486: #define nd(name) name = {0}
universe@486: 
universe@486: const ptrdiff_t loc_prev = offsetof(struct node, prev);
universe@486: const ptrdiff_t loc_next = offsetof(struct node, next);
universe@486: const ptrdiff_t loc_data = offsetof(struct node, data);
universe@486: 
universe@509: static struct node *create_nodes_test_data(
universe@486:         size_t n,
universe@489:         int const data[]
universe@486: ) {
universe@509:     CU_ASSERT_NOT_EQUAL_FATAL(n, 0)
universe@486:     struct node *begin = calloc(1, sizeof(struct node));
universe@486:     struct node *prev = begin;
universe@486:     if (data) begin->data = data[0];
universe@486:     for (size_t i = 1; i < n; i++) {
universe@486:         struct node *node = calloc(1, sizeof(struct node));
universe@486:         if (data) node->data = data[i];
universe@486:         cx_linked_list_link(prev, node, loc_prev, loc_next);
universe@486:         prev = node;
universe@486:     }
universe@486:     return begin;
universe@486: }
universe@486: 
universe@509: static void destroy_nodes_test_data(struct node *begin) {
universe@486:     struct node *node = begin;
universe@486:     while (node) {
universe@486:         struct node *next = node->next;
universe@486:         free(node);
universe@486:         node = next;
universe@486:     }
universe@486: }
universe@486: 
universe@509: static int *create_ints_test_data(size_t len) {
universe@509:     int *data = malloc(sizeof(int) * len);
universe@509:     cx_for_n (i, len) data[i] = rand(); // NOLINT(cert-msc50-cpp)
universe@509:     return data;
universe@509: }
universe@509: 
universe@482: void test_linked_list_link_unlink(void) {
universe@482: 
universe@486:     struct node nd(a), nd(b), nd(c);
universe@482: 
universe@482:     cx_linked_list_link(&a, &b, loc_prev, loc_next);
universe@482:     CU_ASSERT_PTR_NULL(a.prev)
universe@482:     CU_ASSERT_PTR_EQUAL(a.next, &b)
universe@482:     CU_ASSERT_PTR_EQUAL(b.prev, &a)
universe@482:     CU_ASSERT_PTR_NULL(b.next)
universe@482: 
universe@482:     cx_linked_list_unlink(&a, &b, loc_prev, loc_next);
universe@482:     CU_ASSERT_PTR_NULL(a.prev)
universe@482:     CU_ASSERT_PTR_NULL(a.next)
universe@482:     CU_ASSERT_PTR_NULL(b.prev)
universe@482:     CU_ASSERT_PTR_NULL(b.next)
universe@482: 
universe@482:     cx_linked_list_link(&b, &c, loc_prev, loc_next);
universe@482:     cx_linked_list_link(&a, &b, loc_prev, loc_next);
universe@482:     cx_linked_list_unlink(&b, &c, loc_prev, loc_next);
universe@482:     CU_ASSERT_PTR_NULL(a.prev)
universe@482:     CU_ASSERT_PTR_EQUAL(a.next, &b)
universe@482:     CU_ASSERT_PTR_EQUAL(b.prev, &a)
universe@482:     CU_ASSERT_PTR_NULL(b.next)
universe@482:     CU_ASSERT_PTR_NULL(c.prev)
universe@482:     CU_ASSERT_PTR_NULL(c.next)
universe@482: }
universe@482: 
universe@438: void test_linked_list_at(void) {
universe@486:     struct node nd(a), nd(b), nd(c), nd(d);
universe@486:     cx_linked_list_link(&a, &b, loc_prev, loc_next);
universe@486:     cx_linked_list_link(&b, &c, loc_prev, loc_next);
universe@486:     cx_linked_list_link(&c, &d, loc_prev, loc_next);
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: 
universe@487: void test_linked_list_find(void) {
universe@487:     int data[] = {2, 4, 6, 8};
universe@509:     void *list = create_nodes_test_data(4, data);
universe@487:     int s;
universe@487: 
universe@487:     s = 2;
universe@487:     CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
universe@492:                                         false, cmp_int, &s), 0)
universe@487:     s = 4;
universe@487:     CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
universe@492:                                         false, cmp_int, &s), 1)
universe@487:     s = 6;
universe@487:     CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
universe@492:                                         false, cmp_int, &s), 2)
universe@487:     s = 8;
universe@487:     CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
universe@492:                                         false, cmp_int, &s), 3)
universe@487:     s = 10;
universe@487:     CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
universe@492:                                         false, cmp_int, &s), 4)
universe@487:     s = -2;
universe@487:     CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
universe@492:                                         false, cmp_int, &s), 4)
universe@487: }
universe@487: 
universe@486: void test_linked_list_compare(void) {
universe@486:     int a[] = {2, 4, 6, 8};
universe@486:     int b[] = {2, 4, 6};
universe@486:     int c[] = {2, 4, 6, 9};
universe@486: 
universe@509:     void *la = create_nodes_test_data(4, a);
universe@509:     void *lb = create_nodes_test_data(3, b);
universe@509:     void *lc = create_nodes_test_data(4, c);
universe@486: 
universe@486:     CU_ASSERT_TRUE(0 < cx_linked_list_compare(la, lb, loc_next, loc_data,
universe@492:                                               false, cmp_int)
universe@486:     )
universe@486:     CU_ASSERT_TRUE(0 > cx_linked_list_compare(lb, la, loc_next, loc_data,
universe@492:                                               false, cmp_int)
universe@486:     )
universe@486:     CU_ASSERT_TRUE(0 < cx_linked_list_compare(lc, la, loc_next, loc_data,
universe@492:                                               false, cmp_int)
universe@486:     )
universe@486:     CU_ASSERT_TRUE(0 > cx_linked_list_compare(la, lc, loc_next, loc_data,
universe@492:                                               false, cmp_int)
universe@486:     )
universe@486:     CU_ASSERT_TRUE(0 == cx_linked_list_compare(la, la, loc_next, loc_data,
universe@492:                                                false, cmp_int)
universe@486:     )
universe@486: 
universe@509:     destroy_nodes_test_data(la);
universe@509:     destroy_nodes_test_data(lb);
universe@509:     destroy_nodes_test_data(lc);
universe@486: }
universe@486: 
olaf@444: void test_linked_list_add(void) {
olaf@442:     struct node nodes[4];
universe@486:     void *begin, *end;
universe@449: 
olaf@442:     // test with begin, end / prev, next
universe@449:     memset(nodes, 0, 4 * sizeof(struct node));
universe@486:     begin = end = NULL;
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@475:     CU_ASSERT_PTR_NULL(nodes[0].prev)
universe@475:     CU_ASSERT_PTR_NULL(nodes[0].next)
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));
universe@486:     begin = 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: 
universe@475:     // test with end only / prev, next
universe@475:     memset(nodes, 0, 4 * sizeof(struct node));
universe@486:     begin = end = NULL;
universe@475: 
universe@475:     cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]);
universe@475:     CU_ASSERT_PTR_EQUAL(end, &nodes[0])
universe@494:     cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]);
universe@475:     CU_ASSERT_PTR_EQUAL(end, &nodes[1])
universe@475:     CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
universe@475:     CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
universe@475: 
universe@494:     cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[2]);
universe@475:     CU_ASSERT_PTR_EQUAL(end, &nodes[2])
universe@475:     CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2])
universe@475:     CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1])
universe@475: 
olaf@442:     // test with begin, end / next
universe@449:     memset(nodes, 0, 4 * sizeof(struct node));
universe@486:     begin = 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@475: void test_linked_list_prepend(void) {
universe@475:     struct node nodes[4];
universe@486:     void *begin, *end;
universe@475: 
universe@475:     // test with begin, end / prev, next
universe@475:     memset(nodes, 0, 4 * sizeof(struct node));
universe@486:     begin = end = NULL;
universe@475: 
universe@475:     cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]);
universe@475:     CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
universe@475:     CU_ASSERT_PTR_EQUAL(end, &nodes[0])
universe@475:     CU_ASSERT_PTR_NULL(nodes[0].prev)
universe@475:     CU_ASSERT_PTR_NULL(nodes[0].next)
universe@475: 
universe@475:     cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]);
universe@475:     CU_ASSERT_PTR_EQUAL(begin, &nodes[1])
universe@475:     CU_ASSERT_PTR_EQUAL(end, &nodes[0])
universe@475:     CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
universe@475:     CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
universe@475: 
universe@475:     // test with begin only / prev, next
universe@475:     memset(nodes, 0, 4 * sizeof(struct node));
universe@486:     begin = end = NULL;
universe@475: 
universe@475:     cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]);
universe@475:     CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
universe@475:     cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]);
universe@475:     CU_ASSERT_PTR_EQUAL(begin, &nodes[1])
universe@475:     CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
universe@475:     CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
universe@475: 
universe@475:     cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[2]);
universe@475:     CU_ASSERT_PTR_EQUAL(begin, &nodes[2])
universe@475:     CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
universe@475:     CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2])
universe@475: 
universe@475:     // test with end only / prev, next
universe@475:     memset(nodes, 0, 4 * sizeof(struct node));
universe@486:     begin = end = NULL;
universe@475: 
universe@475:     cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]);
universe@475:     CU_ASSERT_PTR_EQUAL(end, &nodes[0])
universe@475:     cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]);
universe@475:     CU_ASSERT_PTR_EQUAL(end, &nodes[0])
universe@475:     CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
universe@475:     CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
universe@475: 
universe@475:     cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[2]);
universe@475:     CU_ASSERT_PTR_EQUAL(end, &nodes[0])
universe@475:     CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
universe@475:     CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2])
universe@475: 
universe@475:     // test with begin, end / next
universe@475:     memset(nodes, 0, 4 * sizeof(struct node));
universe@486:     begin = end = NULL;
universe@475: 
universe@475:     cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]);
universe@475:     CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
universe@475:     CU_ASSERT_PTR_EQUAL(end, &nodes[0])
universe@475:     cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]);
universe@475:     cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]);
universe@475:     CU_ASSERT_PTR_EQUAL(begin, &nodes[2])
universe@475:     CU_ASSERT_PTR_EQUAL(end, &nodes[0])
universe@475:     CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
universe@475:     CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
universe@475:     CU_ASSERT_PTR_NULL(nodes[1].prev)
universe@475:     CU_ASSERT_PTR_NULL(nodes[0].prev)
universe@475: }
universe@475: 
universe@482: void test_linked_list_insert(void) {
universe@482:     struct node nodes[4];
universe@482:     void *begin, *end;
universe@482: 
universe@482:     // insert mid list
universe@482:     memset(nodes, 0, 4 * sizeof(struct node));
universe@482:     begin = &nodes[0];
universe@482:     end = &nodes[2];
universe@482: 
universe@482:     cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
universe@482:     cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
universe@482: 
universe@482:     cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]);
universe@482:     CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
universe@482:     CU_ASSERT_PTR_EQUAL(end, &nodes[2])
universe@482:     CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[3])
universe@482:     CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[3])
universe@482:     CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[1])
universe@482:     CU_ASSERT_PTR_EQUAL(nodes[3].next, &nodes[2])
universe@482: 
universe@482:     // insert end
universe@482:     memset(nodes, 0, 4 * sizeof(struct node));
universe@482:     begin = &nodes[0];
universe@482:     end = &nodes[2];
universe@482: 
universe@482:     cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
universe@482:     cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
universe@482: 
universe@482:     cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]);
universe@482:     CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
universe@482:     CU_ASSERT_PTR_EQUAL(end, &nodes[3])
universe@482:     CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[3])
universe@482:     CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[2])
universe@482:     CU_ASSERT_PTR_NULL(nodes[3].next)
universe@482: 
universe@482:     // insert begin
universe@482:     memset(nodes, 0, 4 * sizeof(struct node));
universe@482:     begin = &nodes[0];
universe@482:     end = &nodes[2];
universe@482: 
universe@482:     cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
universe@482:     cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
universe@482: 
universe@482:     cx_linked_list_insert(&begin, &end, loc_prev, loc_next, NULL, &nodes[3]);
universe@482:     CU_ASSERT_PTR_EQUAL(begin, &nodes[3])
universe@482:     CU_ASSERT_PTR_EQUAL(end, &nodes[2])
universe@482:     CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[3])
universe@482:     CU_ASSERT_PTR_NULL(nodes[3].prev)
universe@482:     CU_ASSERT_PTR_EQUAL(nodes[3].next, &nodes[0])
universe@482: }
universe@482: 
universe@482: void test_linked_list_insert_chain(void) {
universe@482:     struct node nodes[5];
universe@482:     void *begin, *end;
universe@482: 
universe@482:     // insert mid list
universe@482:     memset(nodes, 0, 5 * sizeof(struct node));
universe@482:     begin = &nodes[0];
universe@482:     end = &nodes[2];
universe@482: 
universe@482:     cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
universe@482:     cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
universe@482:     cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
universe@482: 
universe@482:     cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], NULL);
universe@482:     CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
universe@482:     CU_ASSERT_PTR_EQUAL(end, &nodes[2])
universe@482:     CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[3])
universe@482:     CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[4])
universe@482:     CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[1])
universe@482:     CU_ASSERT_PTR_EQUAL(nodes[4].next, &nodes[2])
universe@482: 
universe@482:     // insert end
universe@482:     memset(nodes, 0, 5 * sizeof(struct node));
universe@482:     begin = &nodes[0];
universe@482:     end = &nodes[2];
universe@482: 
universe@482:     cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
universe@482:     cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
universe@482:     cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
universe@482: 
universe@482:     cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], NULL);
universe@482:     CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
universe@482:     CU_ASSERT_PTR_EQUAL(end, &nodes[4])
universe@482:     CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[3])
universe@482:     CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[2])
universe@482:     CU_ASSERT_PTR_NULL(nodes[4].next)
universe@482: 
universe@482:     // insert begin
universe@482:     memset(nodes, 0, 5 * sizeof(struct node));
universe@482:     begin = &nodes[0];
universe@482:     end = &nodes[2];
universe@482: 
universe@482:     cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
universe@482:     cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
universe@482:     cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
universe@482: 
universe@482:     cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, NULL, &nodes[3], NULL);
universe@482:     CU_ASSERT_PTR_EQUAL(begin, &nodes[3])
universe@482:     CU_ASSERT_PTR_EQUAL(end, &nodes[2])
universe@482:     CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[4])
universe@482:     CU_ASSERT_PTR_NULL(nodes[3].prev)
universe@482:     CU_ASSERT_PTR_EQUAL(nodes[4].next, &nodes[0])
universe@482: }
universe@482: 
universe@475: void test_linked_list_first(void) {
universe@509:     struct node *begin = create_nodes_test_data(3, NULL);
universe@486:     CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin, loc_prev), begin)
universe@486:     CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin->next, loc_prev), begin)
universe@486:     CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin->next->next, loc_prev), begin)
universe@509:     destroy_nodes_test_data(begin);
universe@475: }
universe@475: 
universe@456: void test_linked_list_last(void) {
universe@509:     struct node *begin = create_nodes_test_data(3, NULL);
universe@486:     struct node *end = begin->next->next;
universe@486:     CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin, loc_next), end)
universe@486:     CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin->next, loc_next), end)
universe@486:     CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin->next->next, loc_next), end)
universe@509:     destroy_nodes_test_data(begin);
universe@456: }
universe@456: 
universe@473: void test_linked_list_prev(void) {
universe@509:     struct node *begin = create_nodes_test_data(3, NULL);
universe@486:     CU_ASSERT_PTR_NULL(cx_linked_list_prev(begin, loc_next, begin))
universe@486:     CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(begin, loc_next, begin->next), begin)
universe@486:     CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(begin, loc_next, begin->next->next), begin->next)
universe@509:     destroy_nodes_test_data(begin);
universe@473: }
universe@473: 
universe@473: void test_linked_list_remove(void) {
universe@486:     void *begin, *end;
universe@473: 
universe@486:     int data[] = {2, 4, 6};
universe@509:     begin = create_nodes_test_data(3, data);
universe@486:     struct node *first = begin;
universe@486:     struct node *second = first->next;
universe@486:     struct node *third = second->next;
universe@486:     end = third;
universe@473: 
universe@486:     cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second);
universe@486:     CU_ASSERT_PTR_EQUAL(begin, first)
universe@486:     CU_ASSERT_PTR_EQUAL(end, third)
universe@486:     CU_ASSERT_PTR_NULL(first->prev)
universe@486:     CU_ASSERT_PTR_EQUAL(first->next, third)
universe@486:     CU_ASSERT_PTR_EQUAL(third->prev, first)
universe@486:     CU_ASSERT_PTR_NULL(third->next)
universe@473: 
universe@486:     cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third);
universe@486:     CU_ASSERT_PTR_EQUAL(begin, first)
universe@486:     CU_ASSERT_PTR_EQUAL(end, first)
universe@486:     CU_ASSERT_PTR_NULL(first->prev)
universe@486:     CU_ASSERT_PTR_NULL(first->next)
universe@473: 
universe@486:     cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first);
universe@473:     CU_ASSERT_PTR_NULL(begin)
universe@473:     CU_ASSERT_PTR_NULL(end)
universe@486: 
universe@486:     free(first);
universe@486:     free(second);
universe@486:     free(third);
universe@473: }
universe@473: 
universe@468: void test_linked_list_size(void) {
universe@486:     struct node *list;
universe@468: 
universe@486:     CU_ASSERT_PTR_EQUAL(cx_linked_list_size(NULL, loc_next), 0)
universe@468: 
universe@509:     list = create_nodes_test_data(5, NULL);
universe@486:     CU_ASSERT_EQUAL(cx_linked_list_size(list, loc_next), 5)
universe@509:     destroy_nodes_test_data(list);
universe@486: 
universe@509:     list = create_nodes_test_data(13, NULL);
universe@486:     CU_ASSERT_EQUAL(cx_linked_list_size(list, loc_next), 13)
universe@509:     destroy_nodes_test_data(list);
universe@468: }
universe@468: 
universe@468: void test_linked_list_sort(void) {
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@509:     void *begin = create_nodes_test_data(100, scrambled);
universe@486:     void *end = cx_linked_list_last(begin, loc_next);
universe@468: 
universe@486:     cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data,
universe@492:                         false, cmp_int);
universe@468: 
universe@468:     struct node *check = begin;
universe@468:     struct node *check_last = NULL;
universe@486:     CU_ASSERT_PTR_NULL(check->prev)
universe@486:     CU_ASSERT_EQUAL(check->data, expected[0])
universe@509:     cx_for_n (i, 100) {
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@486:     CU_ASSERT_PTR_EQUAL(end, check_last)
universe@486: 
universe@509:     destroy_nodes_test_data(begin);
universe@468: }
universe@468: 
universe@473: void test_linked_list_reverse(void) {
universe@486:     void *begin, *end;
universe@473: 
universe@486:     int data[] = {2, 4, 6, 8};
universe@486:     int reversed[] = {8, 6, 4, 2};
universe@473: 
universe@509:     void *list = create_nodes_test_data(4, data);
universe@509:     void *expected = create_nodes_test_data(4, reversed);
universe@473: 
universe@486:     begin = list;
universe@486:     end = cx_linked_list_last(list, loc_next);
universe@473: 
universe@486:     cx_linked_list_reverse(&begin, &end, loc_prev, loc_next);
universe@486:     CU_ASSERT_PTR_EQUAL(end, list)
universe@486:     CU_ASSERT_PTR_EQUAL(begin, cx_linked_list_first(end, loc_prev))
universe@486:     CU_ASSERT_TRUE(0 == cx_linked_list_compare(begin, expected, loc_next, loc_data,
universe@492:                                                0, cmp_int))
universe@473: 
universe@509:     destroy_nodes_test_data(begin);
universe@509:     destroy_nodes_test_data(expected);
universe@473: }
universe@456: 
universe@507: static void verify_linked_list_create(CxList *list) {
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_PTR_EQUAL(list->cmpfunc, cmp_int)
universe@455: 
universe@503:     cxListDestroy(list);
universe@506: }
universe@506: 
universe@506: void test_hl_linked_list_create(void) {
universe@506:     CxList *list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
universe@506:     CU_ASSERT_EQUAL(list->itemsize, sizeof(int))
universe@507:     verify_linked_list_create(list);
universe@455: }
universe@455: 
universe@498: void test_hl_ptr_linked_list_create(void) {
universe@500:     CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
universe@498:     CU_ASSERT_EQUAL(list->itemsize, sizeof(void *))
universe@507:     verify_linked_list_create(list);
universe@498: }
universe@498: 
universe@488: void test_hl_linked_list_from_array(void) {
universe@488:     int data[] = {2, 4, 5, 7, 10, 15};
universe@488: 
universe@500:     CxList *expected = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
universe@509:     cx_for_n (i, 5) cxListAdd(expected, &data[i]);
universe@488: 
universe@500:     CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), 5, data);
universe@488: 
universe@488:     CU_ASSERT_TRUE(0 == cxListCompare(list, expected))
universe@491: 
universe@503:     cxListDestroy(list);
universe@503:     cxListDestroy(expected);
universe@488: }
universe@488: 
universe@507: static void verify_hl_linked_list_add(
universe@507:         CxList *list,
universe@507:         int data[],
universe@507:         size_t len,
universe@507:         bool write_through
universe@507: ) {
universe@509:     cx_for_n (i, len) CU_ASSERT_EQUAL(cxListAdd(list, &data[i]), 0)
universe@507:     CU_ASSERT_EQUAL(list->size, len)
universe@507:     CU_ASSERT_TRUE(list->capacity >= list->size)
universe@509:     cx_for_n (i, len) CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), data[i])
universe@509:     cx_for_n (i, len) ++data[i];
universe@507:     if (write_through) {
universe@509:         cx_for_n (i, len) CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), data[i])
universe@507:     } else {
universe@509:         cx_for_n (i, len) CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), data[i] - 1)
universe@507:     }
universe@507:     cxListDestroy(list);
universe@507: }
universe@507: 
universe@459: void test_hl_linked_list_add(void) {
universe@500:     CxList *list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
universe@507:     int data[] = {5, 47, 13, 9, 18, 1, 42};
universe@507:     verify_hl_linked_list_add(list, data, sizeof(data) / sizeof(int), false);
universe@459: }
universe@459: 
universe@498: void test_hl_ptr_linked_list_add(void) {
universe@500:     CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
universe@509:     int data[] = {5, 47, 84, 13, 9, 18, 90, 1, 42};
universe@507:     verify_hl_linked_list_add(list, data, sizeof(data) / sizeof(int), true);
universe@498: }
universe@498: 
universe@509: static void verify_hl_linked_list_insert(CxList *list) {
universe@498:     int a = 5, b = 47, c = 13, d = 42;
universe@498: 
universe@498:     CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &a), 0)
universe@498:     CU_ASSERT_EQUAL(list->size, 0)
universe@498:     CU_ASSERT_EQUAL(cxListInsert(list, 0, &a), 0)
universe@498:     CU_ASSERT_EQUAL(list->size, 1)
universe@498:     CU_ASSERT_EQUAL(cxListInsert(list, 0, &b), 0)
universe@498:     CU_ASSERT_EQUAL(list->size, 2)
universe@498:     CU_ASSERT_EQUAL(cxListInsert(list, 1, &c), 0)
universe@498:     CU_ASSERT_EQUAL(list->size, 3)
universe@498:     CU_ASSERT_EQUAL(cxListInsert(list, 3, &d), 0)
universe@498: 
universe@498:     CU_ASSERT_EQUAL(list->size, 4)
universe@498:     CU_ASSERT_TRUE(list->capacity >= list->size)
universe@498: 
universe@498:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
universe@498:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
universe@498:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
universe@498:     CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
universe@498: 
universe@503:     cxListDestroy(list);
universe@498: }
universe@498: 
universe@509: void test_hl_linked_list_insert(void) {
universe@509:     verify_hl_linked_list_insert(cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int)));
universe@509: }
universe@459: 
universe@509: void test_hl_ptr_linked_list_insert(void) {
universe@509:     verify_hl_linked_list_insert(cxPointerLinkedListCreate(cxTestingAllocator, cmp_int));
universe@509: }
universe@509: 
universe@509: static void verify_hl_linked_list_remove(CxList *list) {
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@503:     cxListDestroy(list);
universe@459: }
universe@459: 
universe@509: void test_hl_linked_list_remove(void) {
universe@509:     int data[] = {5, 47, 42, 13};
universe@509:     CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int,
universe@509:                                          sizeof(int), 4, data);
universe@509:     verify_hl_linked_list_remove(list);
universe@509: }
universe@509: 
universe@498: void test_hl_ptr_linked_list_remove(void) {
universe@498:     int a = 5, b = 47, c = 42, d = 13;
universe@500:     CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
universe@498:     cxListAdd(list, &a);
universe@498:     cxListAdd(list, &b);
universe@498:     cxListAdd(list, &c);
universe@498:     cxListAdd(list, &d);
universe@509:     verify_hl_linked_list_remove(list);
universe@509: }
universe@498: 
universe@509: static void verify_hl_linked_list_at(
universe@509:         CxList *list,
universe@509:         size_t len,
universe@509:         int *data
universe@509: ) {
universe@509:     CU_ASSERT_EQUAL(list->size, len)
universe@509:     cx_for_n (i, len) CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), data[i])
universe@509:     CU_ASSERT_PTR_NULL(cxListAt(list, len))
universe@509:     free(data);
universe@503:     cxListDestroy(list);
universe@498: }
universe@498: 
universe@479: void test_hl_linked_list_at(void) {
universe@509:     size_t len = 100;
universe@509:     int *data = create_ints_test_data(len);
universe@500:     CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int,
universe@509:                                          sizeof(int), len, data);
universe@509:     verify_hl_linked_list_at(list, len, data);
universe@479: }
universe@479: 
universe@498: void test_hl_ptr_linked_list_at(void) {
universe@509:     size_t len = 250;
universe@509:     int *data = create_ints_test_data(len);
universe@500:     CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
universe@509:     cx_for_n (i, len) cxListAdd(list, &data[i]);
universe@509:     verify_hl_linked_list_at(list, len, data);
universe@509: }
universe@498: 
universe@509: static void verify_hl_linked_list_find(
universe@509:         CxList *list,
universe@509:         size_t len,
universe@509:         int *data
universe@509: ) {
universe@509:     cx_for_n (attempt, 100) {
universe@509:         size_t exp = rand() % len; // NOLINT(cert-msc50-cpp)
universe@509:         int val = data[exp];
universe@509:         cx_for_n (i, exp) {
universe@509:             if (data[i] == val) {
universe@509:                 exp = i;
universe@509:                 break;
universe@509:             }
universe@509:         }
universe@509:         CU_ASSERT_EQUAL(cxListFind(list, &val), exp)
universe@509:     }
universe@509:     free(data);
universe@503:     cxListDestroy(list);
universe@498: }
universe@498: 
universe@459: void test_hl_linked_list_find(void) {
universe@509:     size_t len = 100;
universe@509:     int *data = create_ints_test_data(len);
universe@509:     CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), len, data);
universe@509:     verify_hl_linked_list_find(list, len, data);
universe@459: }
universe@459: 
universe@498: void test_hl_ptr_linked_list_find(void) {
universe@509:     size_t len = 250;
universe@509:     int *data = create_ints_test_data(len);
universe@500:     CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
universe@509:     cx_for_n (i, len) cxListAdd(list, &data[i]);
universe@509:     verify_hl_linked_list_find(list, len, data);
universe@509: }
universe@498: 
universe@509: struct sort_test_data {
universe@509:     size_t len;
universe@509:     int *data;
universe@509:     int *sorted;
universe@509: };
universe@498: 
universe@509: static struct sort_test_data create_sort_test_data(void) {
universe@509:     size_t len = 1000;
universe@509:     int *data = create_ints_test_data(len);
universe@509:     int *sorted = malloc(sizeof(int) * len);
universe@509:     memcpy(sorted, data, sizeof(int) * len);
universe@509:     qsort(sorted, len, sizeof(int), cmp_int);
universe@509:     struct sort_test_data s = {len, data, sorted};
universe@509:     return s;
universe@509: }
universe@498: 
universe@509: static void free_sort_test_data(struct sort_test_data s) {
universe@509:     free(s.data);
universe@509:     free(s.sorted);
universe@509: }
universe@498: 
universe@509: static void verify_hl_linked_list_sort(
universe@509:         CxList *list,
universe@509:         struct sort_test_data td
universe@509: ) {
universe@509:     cxListSort(list);
universe@509:     cx_for_n (i, td.len) CU_ASSERT_EQUAL_FATAL(*(int *) cxListAt(list, i), td.sorted[i])
universe@509:     free_sort_test_data(td);
universe@503:     cxListDestroy(list);
universe@498: }
universe@498: 
universe@469: void test_hl_linked_list_sort(void) {
universe@509:     struct sort_test_data td = create_sort_test_data();
universe@509:     CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), td.len, td.data);
universe@509:     verify_hl_linked_list_sort(list, td);
universe@469: }
universe@469: 
universe@498: void test_hl_ptr_linked_list_sort(void) {
universe@509:     struct sort_test_data td = create_sort_test_data();
universe@500:     CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
universe@509:     cx_for_n (i, td.len) cxListAdd(list, &td.data[i]);
universe@509:     verify_hl_linked_list_sort(list, td);
universe@498: }
universe@498: 
universe@509: void verify_hl_linked_list_iterator(CxList *list) {
universe@494:     int i = 0;
universe@496:     CxIterator iter = cxListBegin(list);
universe@497:     cx_foreach(int*, x, iter) {
universe@495:         CU_ASSERT_EQUAL(iter.index, (size_t) (i + 1) / 2)
universe@494:         CU_ASSERT_EQUAL(*x, i)
universe@497:         if (*x % 2 == 1) iter.remove = true;
universe@494:         i++;
universe@494:     }
universe@494:     CU_ASSERT_EQUAL(i, 10)
universe@495:     CU_ASSERT_EQUAL_FATAL(list->size, 5)
universe@509:     cx_for_n(j, 5) CU_ASSERT_EQUAL(*(int *) cxListAt(list, j), (int) j * 2)
universe@503:     cxListDestroy(list);
universe@494: }
universe@494: 
universe@494: void test_hl_linked_list_iterator(void) {
universe@500:     CxList *list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
universe@509:     cx_for_n (i, 10) cxListAdd(list, &i);
universe@509:     verify_hl_linked_list_iterator(list);
universe@494: }
universe@494: 
universe@494: void test_hl_ptr_linked_list_iterator(void) {
universe@500:     CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
universe@494:     int data[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
universe@509:     cx_for_n (i, 10) cxListAdd(list, &data[i]);
universe@509:     verify_hl_linked_list_iterator(list);
universe@494: }
universe@494: 
universe@509: static void verify_hl_linked_list_insert_via_iterator(
universe@509:         CxList *list,
universe@509:         int *testdata
universe@509: ) {
universe@499:     CxIterator iter = cxListIterator(list, 2);
universe@499:     CU_ASSERT_EQUAL(iter.index, 2)
universe@499:     CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
universe@509:     size_t i = 4;
universe@499: 
universe@509:     ++i;
universe@509:     cxListInsertAfter(&iter, &testdata[i]);
universe@499:     CU_ASSERT_EQUAL(iter.index, 2)
universe@499:     CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
universe@509:     ++i;
universe@509:     cxListInsertBefore(&iter, &testdata[i]);
universe@499:     CU_ASSERT_EQUAL(iter.index, 3)
universe@499:     CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
universe@499: 
universe@499:     iter = cxListBegin(list);
universe@509:     ++i;
universe@509:     cxListInsertBefore(&iter, &testdata[i]);
universe@499:     CU_ASSERT_EQUAL(iter.index, 1)
universe@499:     CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 0)
universe@499:     iter = cxListIterator(list, list->size);
universe@509:     ++i;
universe@509:     cxListInsertBefore(&iter, &testdata[i]);
universe@499:     CU_ASSERT_EQUAL(iter.index, 9)
universe@499:     CU_ASSERT_FALSE(cxIteratorValid(&iter))
universe@499:     iter = cxListIterator(list, list->size);
universe@509:     ++i;
universe@509:     cxListInsertAfter(&iter, &testdata[i]);
universe@499:     CU_ASSERT_EQUAL(iter.index, 10)
universe@499:     CU_ASSERT_FALSE(cxIteratorValid(&iter))
universe@499: 
universe@499:     int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50};
universe@509:     cx_for_n (j, 10) CU_ASSERT_EQUAL(*(int *) cxListAt(list, j), expdata[j])
universe@509:     cxListDestroy(list);
universe@509: }
universe@499: 
universe@509: void test_hl_linked_list_insert_via_iterator(void) {
universe@509:     int testdata[] = {0, 1, 2, 3, 4, 10, 20, 30, 40, 50};
universe@509:     // only add the first five elements, the remaining five will be inserted
universe@509:     CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), 5, testdata);
universe@509:     verify_hl_linked_list_insert_via_iterator(list, testdata);
universe@499: }
universe@499: 
universe@499: void test_hl_ptr_linked_list_insert_via_iterator(void) {
universe@499:     int testdata[] = {0, 1, 2, 3, 4, 10, 20, 30, 40, 50};
universe@500:     CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
universe@509:     // only add the first five elements, the remaining five will be inserted
universe@509:     cx_for_n (i, 5) cxListAdd(list, &testdata[i]);
universe@509:     verify_hl_linked_list_insert_via_iterator(list, testdata);
universe@506: }
universe@506: 
universe@506: static void test_setup_allocator(void) {
universe@506:     cxTestingAllocatorReset();
universe@506: }
universe@506: 
universe@506: static void test_verify_allocator(void) {
universe@499:     CU_ASSERT_TRUE(cxTestingAllocatorVerify())
universe@499: }
universe@499: 
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@482:     cu_add_test(suite, test_linked_list_link_unlink);
universe@455:     cu_add_test(suite, test_linked_list_at);
universe@487:     cu_add_test(suite, test_linked_list_find);
universe@486:     cu_add_test(suite, test_linked_list_compare);
universe@475:     cu_add_test(suite, test_linked_list_prepend);
universe@455:     cu_add_test(suite, test_linked_list_add);
universe@482:     cu_add_test(suite, test_linked_list_insert);
universe@482:     cu_add_test(suite, test_linked_list_insert_chain);
universe@475:     cu_add_test(suite, test_linked_list_first);
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@506:     suite = CU_add_suite_with_setup_and_teardown(
universe@506:             "high level linked list", NULL, NULL,
universe@506:             test_setup_allocator, test_verify_allocator);
universe@455: 
universe@456:     cu_add_test(suite, test_hl_linked_list_create);
universe@488:     cu_add_test(suite, test_hl_linked_list_from_array);
universe@456:     cu_add_test(suite, test_hl_linked_list_add);
universe@456:     cu_add_test(suite, test_hl_linked_list_insert);
universe@456:     cu_add_test(suite, test_hl_linked_list_remove);
universe@479:     cu_add_test(suite, test_hl_linked_list_at);
universe@459:     cu_add_test(suite, test_hl_linked_list_find);
universe@469:     cu_add_test(suite, test_hl_linked_list_sort);
universe@494:     cu_add_test(suite, test_hl_linked_list_iterator);
universe@499:     cu_add_test(suite, test_hl_linked_list_insert_via_iterator);
universe@413: 
universe@506:     suite = CU_add_suite_with_setup_and_teardown(
universe@506:             "high level pointer linked list", NULL, NULL,
universe@506:             test_setup_allocator, test_verify_allocator);
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_insert);
universe@466:     cu_add_test(suite, test_hl_ptr_linked_list_remove);
universe@479:     cu_add_test(suite, test_hl_ptr_linked_list_at);
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@494:     cu_add_test(suite, test_hl_ptr_linked_list_iterator);
universe@499:     cu_add_test(suite, test_hl_ptr_linked_list_insert_via_iterator);
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: }