test/test_list.c

/*
 * 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);
}

struct node {
    struct node *next;
    struct node *prev;
    int data;
};

#define nd(name) name = {0}

const ptrdiff_t loc_prev = offsetof(struct node, prev);
const ptrdiff_t loc_next = offsetof(struct node, next);
const ptrdiff_t loc_data = offsetof(struct node, data);

struct node *create_test_data(
        size_t n,
        const int data[]
) {
    if (n == 0) return NULL;
    struct node *begin = calloc(1, sizeof(struct node));
    struct node *prev = begin;
    if (data) begin->data = data[0];
    for (size_t i = 1; i < n; i++) {
        struct node *node = calloc(1, sizeof(struct node));
        if (data) node->data = data[i];
        cx_linked_list_link(prev, node, loc_prev, loc_next);
        prev = node;
    }
    return begin;
}

void destroy_test_data(struct node *begin) {
    struct node *node = begin;
    while (node) {
        struct node *next = node->next;
        free(node);
        node = next;
    }
}

void test_linked_list_link_unlink(void) {

    struct node nd(a), nd(b), nd(c);

    cx_linked_list_link(&a, &b, loc_prev, loc_next);
    CU_ASSERT_PTR_NULL(a.prev)
    CU_ASSERT_PTR_EQUAL(a.next, &b)
    CU_ASSERT_PTR_EQUAL(b.prev, &a)
    CU_ASSERT_PTR_NULL(b.next)

    cx_linked_list_unlink(&a, &b, loc_prev, loc_next);
    CU_ASSERT_PTR_NULL(a.prev)
    CU_ASSERT_PTR_NULL(a.next)
    CU_ASSERT_PTR_NULL(b.prev)
    CU_ASSERT_PTR_NULL(b.next)

    cx_linked_list_link(&b, &c, loc_prev, loc_next);
    cx_linked_list_link(&a, &b, loc_prev, loc_next);
    cx_linked_list_unlink(&b, &c, loc_prev, loc_next);
    CU_ASSERT_PTR_NULL(a.prev)
    CU_ASSERT_PTR_EQUAL(a.next, &b)
    CU_ASSERT_PTR_EQUAL(b.prev, &a)
    CU_ASSERT_PTR_NULL(b.next)
    CU_ASSERT_PTR_NULL(c.prev)
    CU_ASSERT_PTR_NULL(c.next)
}

void test_linked_list_at(void) {
    struct node nd(a), nd(b), nd(c), nd(d);
    cx_linked_list_link(&a, &b, loc_prev, loc_next);
    cx_linked_list_link(&b, &c, loc_prev, loc_next);
    cx_linked_list_link(&c, &d, loc_prev, loc_next);

    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_compare(void) {
    int a[] = {2, 4, 6, 8};
    int b[] = {2, 4, 6};
    int c[] = {2, 4, 6, 9};

    void *la = create_test_data(4, a);
    void *lb = create_test_data(3, b);
    void *lc = create_test_data(4, c);

    CU_ASSERT_TRUE(0 < cx_linked_list_compare(la, lb, loc_next, loc_data,
                                              0, (CxListComparator) cmp_int)
    )
    CU_ASSERT_TRUE(0 > cx_linked_list_compare(lb, la, loc_next, loc_data,
                                              0, (CxListComparator) cmp_int)
    )
    CU_ASSERT_TRUE(0 < cx_linked_list_compare(lc, la, loc_next, loc_data,
                                              0, (CxListComparator) cmp_int)
    )
    CU_ASSERT_TRUE(0 > cx_linked_list_compare(la, lc, loc_next, loc_data,
                                              0, (CxListComparator) cmp_int)
    )
    CU_ASSERT_TRUE(0 == cx_linked_list_compare(la, la, loc_next, loc_data,
                                               0, (CxListComparator) cmp_int)
    )

    destroy_test_data(la);
    destroy_test_data(lb);
    destroy_test_data(lc);
}

void test_linked_list_add(void) {
    struct node nodes[4];
    void *begin, *end;

    // test with begin, end / prev, next
    memset(nodes, 0, 4 * sizeof(struct node));
    begin = end = NULL;

    cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]);
    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
    CU_ASSERT_PTR_NULL(nodes[0].prev)
    CU_ASSERT_PTR_NULL(nodes[0].next)

    cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]);
    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
    CU_ASSERT_PTR_EQUAL(end, &nodes[1])
    CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
    CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])

    // test with begin only / prev, next
    memset(nodes, 0, 4 * sizeof(struct node));
    begin = end = NULL;

    cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]);
    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
    cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]);
    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
    CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
    CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])

    cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[2]);
    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2])
    CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1])

    // test with end only / prev, next
    memset(nodes, 0, 4 * sizeof(struct node));
    begin = end = NULL;

    cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]);
    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
    cx_linked_list_add(NULL, &end,  loc_prev, loc_next, &nodes[1]);
    CU_ASSERT_PTR_EQUAL(end, &nodes[1])
    CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
    CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])

    cx_linked_list_add(NULL, &end,  loc_prev, loc_next, &nodes[2]);
    CU_ASSERT_PTR_EQUAL(end, &nodes[2])
    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2])
    CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1])

    // test with begin, end / next
    memset(nodes, 0, 4 * sizeof(struct node));
    begin = end = NULL;

    cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]);
    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
    cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]);
    CU_ASSERT_PTR_EQUAL(end, &nodes[1])
    CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
    CU_ASSERT_PTR_NULL(nodes[1].prev)
}

void test_linked_list_prepend(void) {
    struct node nodes[4];
    void *begin, *end;

    // test with begin, end / prev, next
    memset(nodes, 0, 4 * sizeof(struct node));
    begin = end = NULL;

    cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]);
    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
    CU_ASSERT_PTR_NULL(nodes[0].prev)
    CU_ASSERT_PTR_NULL(nodes[0].next)

    cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]);
    CU_ASSERT_PTR_EQUAL(begin, &nodes[1])
    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
    CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])

    // test with begin only / prev, next
    memset(nodes, 0, 4 * sizeof(struct node));
    begin = end = NULL;

    cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]);
    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
    cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]);
    CU_ASSERT_PTR_EQUAL(begin, &nodes[1])
    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
    CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])

    cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[2]);
    CU_ASSERT_PTR_EQUAL(begin, &nodes[2])
    CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
    CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2])

    // test with end only / prev, next
    memset(nodes, 0, 4 * sizeof(struct node));
    begin = end = NULL;

    cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]);
    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
    cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]);
    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
    CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])

    cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[2]);
    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
    CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
    CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2])

    // test with begin, end / next
    memset(nodes, 0, 4 * sizeof(struct node));
    begin = end = NULL;

    cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]);
    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
    cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]);
    cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]);
    CU_ASSERT_PTR_EQUAL(begin, &nodes[2])
    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
    CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
    CU_ASSERT_PTR_NULL(nodes[1].prev)
    CU_ASSERT_PTR_NULL(nodes[0].prev)
}

void test_linked_list_insert(void) {
    struct node nodes[4];
    void *begin, *end;

    // insert mid list
    memset(nodes, 0, 4 * sizeof(struct node));
    begin = &nodes[0];
    end = &nodes[2];

    cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
    cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);

    cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]);
    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
    CU_ASSERT_PTR_EQUAL(end, &nodes[2])
    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[3])
    CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[3])
    CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[1])
    CU_ASSERT_PTR_EQUAL(nodes[3].next, &nodes[2])

    // insert end
    memset(nodes, 0, 4 * sizeof(struct node));
    begin = &nodes[0];
    end = &nodes[2];

    cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
    cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);

    cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]);
    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
    CU_ASSERT_PTR_EQUAL(end, &nodes[3])
    CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[3])
    CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[2])
    CU_ASSERT_PTR_NULL(nodes[3].next)

    // insert begin
    memset(nodes, 0, 4 * sizeof(struct node));
    begin = &nodes[0];
    end = &nodes[2];

    cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
    cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);

    cx_linked_list_insert(&begin, &end, loc_prev, loc_next, NULL, &nodes[3]);
    CU_ASSERT_PTR_EQUAL(begin, &nodes[3])
    CU_ASSERT_PTR_EQUAL(end, &nodes[2])
    CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[3])
    CU_ASSERT_PTR_NULL(nodes[3].prev)
    CU_ASSERT_PTR_EQUAL(nodes[3].next, &nodes[0])
}

void test_linked_list_insert_chain(void) {
    struct node nodes[5];
    void *begin, *end;

    // insert mid list
    memset(nodes, 0, 5 * sizeof(struct node));
    begin = &nodes[0];
    end = &nodes[2];

    cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
    cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
    cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);

    cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], NULL);
    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
    CU_ASSERT_PTR_EQUAL(end, &nodes[2])
    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[3])
    CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[4])
    CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[1])
    CU_ASSERT_PTR_EQUAL(nodes[4].next, &nodes[2])

    // insert end
    memset(nodes, 0, 5 * sizeof(struct node));
    begin = &nodes[0];
    end = &nodes[2];

    cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
    cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
    cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);

    cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], NULL);
    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
    CU_ASSERT_PTR_EQUAL(end, &nodes[4])
    CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[3])
    CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[2])
    CU_ASSERT_PTR_NULL(nodes[4].next)

    // insert begin
    memset(nodes, 0, 5 * sizeof(struct node));
    begin = &nodes[0];
    end = &nodes[2];

    cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
    cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
    cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);

    cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, NULL, &nodes[3], NULL);
    CU_ASSERT_PTR_EQUAL(begin, &nodes[3])
    CU_ASSERT_PTR_EQUAL(end, &nodes[2])
    CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[4])
    CU_ASSERT_PTR_NULL(nodes[3].prev)
    CU_ASSERT_PTR_EQUAL(nodes[4].next, &nodes[0])
}

void test_linked_list_first(void) {
    struct node *begin = create_test_data(3, NULL);
    CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin, loc_prev), begin)
    CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin->next, loc_prev), begin)
    CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin->next->next, loc_prev), begin)
    destroy_test_data(begin);
}

void test_linked_list_last(void) {
    struct node *begin = create_test_data(3, NULL);
    struct node *end = begin->next->next;
    CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin, loc_next), end)
    CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin->next, loc_next), end)
    CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin->next->next, loc_next), end)
    destroy_test_data(begin);
}

void test_linked_list_prev(void) {
    struct node *begin = create_test_data(3, NULL);
    CU_ASSERT_PTR_NULL(cx_linked_list_prev(begin, loc_next, begin))
    CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(begin, loc_next, begin->next), begin)
    CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(begin, loc_next, begin->next->next), begin->next)
    destroy_test_data(begin);
}

void test_linked_list_remove(void) {
    void *begin, *end;

    int data[] = {2, 4, 6};
    begin = create_test_data(3, data);
    struct node *first = begin;
    struct node *second = first->next;
    struct node *third = second->next;
    end = third;

    cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second);
    CU_ASSERT_PTR_EQUAL(begin, first)
    CU_ASSERT_PTR_EQUAL(end, third)
    CU_ASSERT_PTR_NULL(first->prev)
    CU_ASSERT_PTR_EQUAL(first->next, third)
    CU_ASSERT_PTR_EQUAL(third->prev, first)
    CU_ASSERT_PTR_NULL(third->next)

    cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third);
    CU_ASSERT_PTR_EQUAL(begin, first)
    CU_ASSERT_PTR_EQUAL(end, first)
    CU_ASSERT_PTR_NULL(first->prev)
    CU_ASSERT_PTR_NULL(first->next)

    cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first);
    CU_ASSERT_PTR_NULL(begin)
    CU_ASSERT_PTR_NULL(end)

    free(first);
    free(second);
    free(third);
}

void test_linked_list_size(void) {
    struct node *list;

    CU_ASSERT_PTR_EQUAL(cx_linked_list_size(NULL, loc_next), 0)

    list = create_test_data(5, NULL);
    CU_ASSERT_EQUAL(cx_linked_list_size(list, loc_next), 5)
    destroy_test_data(list);

    list = create_test_data(13, NULL);
    CU_ASSERT_EQUAL(cx_linked_list_size(list, loc_next), 13)
    destroy_test_data(list);
}

void test_linked_list_sort(void) {
    int expected[] = {
            14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
            894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
            1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
            2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
            3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
            4785, 4791, 4801, 4859, 4903, 4973
    };
    int scrambled[] = {
            759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
            2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
            2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
            894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
            3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
            4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
    };

    void *begin = create_test_data(100, scrambled);
    void *end = cx_linked_list_last(begin, loc_next);

    cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data,
                        0, (CxListComparator) cmp_int);

    struct node *check = begin;
    struct node *check_last = NULL;
    CU_ASSERT_PTR_NULL(check->prev)
    CU_ASSERT_EQUAL(check->data, expected[0])
    for (int i = 0; i < 100; i++) {
        CU_ASSERT_EQUAL(check->data, expected[i])
        CU_ASSERT_PTR_EQUAL(check->prev, check_last)
        if (i < 99) {
            CU_ASSERT_PTR_NOT_NULL(check->next)
        }
        check_last = check;
        check = check->next;
    }
    CU_ASSERT_PTR_NULL(check)
    CU_ASSERT_PTR_EQUAL(end, check_last)

    destroy_test_data(begin);
}

void test_linked_list_reverse(void) {
    void *begin, *end;

    int data[] = {2, 4, 6, 8};
    int reversed[] = {8, 6, 4, 2};

    void *list = create_test_data(4, data);
    void *expected = create_test_data(4, reversed);

    begin = list;
    end = cx_linked_list_last(list, loc_next);

    cx_linked_list_reverse(&begin, &end, loc_prev, loc_next);
    CU_ASSERT_PTR_EQUAL(end, list)
    CU_ASSERT_PTR_EQUAL(begin, cx_linked_list_first(end, loc_prev))
    CU_ASSERT_TRUE(0 == cx_linked_list_compare(begin, expected, loc_next, loc_data,
                                               0, (CxListComparator) cmp_int))

    destroy_test_data(begin);
    destroy_test_data(expected);
}

void test_hl_linked_list_create(void) {
    cxTestingAllocatorReset();

    CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));

    CU_ASSERT_EQUAL(list->size, 0)
    CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
    CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
    CU_ASSERT_EQUAL(list->itemsize, sizeof(int))
    CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)

    cxLinkedListDestroy(list);
    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
}

void test_hl_linked_list_add(void) {
    cxTestingAllocatorReset();

    int data;
    CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));

    data = 5;
    CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
    data = 47;
    CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
    data = 13;
    CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)

    CU_ASSERT_EQUAL(list->size, 3)
    CU_ASSERT_TRUE(list->capacity >= list->size)

    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)

    cxLinkedListDestroy(list);
    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
}

void test_hl_linked_list_insert(void) {
    cxTestingAllocatorReset();

    int data;
    CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));

    data = 5;
    CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &data), 0)
    CU_ASSERT_EQUAL(list->size, 0)
    CU_ASSERT_EQUAL(cxListInsert(list, 0, &data), 0)
    CU_ASSERT_EQUAL(list->size, 1)
    data = 47;
    CU_ASSERT_EQUAL(cxListInsert(list, 0, &data), 0)
    CU_ASSERT_EQUAL(list->size, 2)
    data = 13;
    CU_ASSERT_EQUAL(cxListInsert(list, 1, &data), 0)
    CU_ASSERT_EQUAL(list->size, 3)
    data = 42;
    CU_ASSERT_EQUAL(cxListInsert(list, 3, &data), 0)

    CU_ASSERT_EQUAL(list->size, 4)
    CU_ASSERT_TRUE(list->capacity >= list->size)

    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)

    cxLinkedListDestroy(list);
    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
}

void test_hl_linked_list_remove(void) {
    cxTestingAllocatorReset();

    int data;
    CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));

    data = 5;
    cxListAdd(list, &data);
    data = 47;
    cxListAdd(list, &data);
    data = 42;
    cxListAdd(list, &data);
    data = 13;
    cxListAdd(list, &data);

    CU_ASSERT_EQUAL(list->size, 4)
    CU_ASSERT_TRUE(list->capacity >= list->size)

    CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)

    CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
    CU_ASSERT_EQUAL(list->size, 3)
    CU_ASSERT_TRUE(list->capacity >= list->size)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)

    CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
    CU_ASSERT_EQUAL(list->size, 2)
    CU_ASSERT_TRUE(list->capacity >= list->size)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)

    CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
    CU_ASSERT_EQUAL(list->size, 1)
    CU_ASSERT_TRUE(list->capacity >= list->size)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)

    CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
    CU_ASSERT_EQUAL(list->size, 0)
    CU_ASSERT_TRUE(list->capacity >= list->size)

    CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)

    cxLinkedListDestroy(list);
    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
}

void test_hl_linked_list_at(void) {
    cxTestingAllocatorReset();

    CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));

    int data;
    data = 5;
    cxListAdd(list, &data);
    data = 47;
    cxListAdd(list, &data);
    data = 13;
    cxListAdd(list, &data);

    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_PTR_NULL(cxListAt(list, 3))

    cxLinkedListDestroy(list);
    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
}

void test_hl_linked_list_find(void) {
    cxTestingAllocatorReset();

    int data, criteria;
    CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));

    data = 5;
    cxListAdd(list, &data);
    data = 47;
    cxListAdd(list, &data);
    data = 13;
    cxListAdd(list, &data);

    CU_ASSERT_EQUAL(list->size, 3)
    CU_ASSERT_TRUE(list->capacity >= list->size)

    criteria = 5;
    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0)
    criteria = 47;
    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
    criteria = 13;
    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2)
    criteria = 9000;
    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
    criteria = -5;
    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)

    cxLinkedListDestroy(list);
    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
}

void test_hl_linked_list_sort(void) {
    int expected[] = {
            14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
            894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
            1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
            2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
            3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
            4785, 4791, 4801, 4859, 4903, 4973
    };
    int scrambled[] = {
            759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
            2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
            2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
            894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
            3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
            4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
    };

    cxTestingAllocatorReset();

    CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));

    for (int i = 0; i < 100; i++) {
        cxListAdd(list, &scrambled[i]);
    }

    cxListSort(list);

    for (int i = 0; i < 100; i++) {
        CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i])
    }

    cxLinkedListDestroy(list);
    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
}

void test_hl_ptr_linked_list_create(void) {
    cxTestingAllocatorReset();

    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);

    CU_ASSERT_EQUAL(list->size, 0)
    CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
    CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
    CU_ASSERT_EQUAL(list->itemsize, sizeof(void *))
    CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)

    cxLinkedListDestroy(list);
    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
}

void test_hl_ptr_linked_list_add(void) {
    cxTestingAllocatorReset();

    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);

    int a = 5, b = 47, c = 13;

    CU_ASSERT_EQUAL(cxListAdd(list, &a), 0)
    CU_ASSERT_EQUAL(cxListAdd(list, &b), 0)
    CU_ASSERT_EQUAL(cxListAdd(list, &c), 0)

    CU_ASSERT_EQUAL(list->size, 3)
    CU_ASSERT_TRUE(list->capacity >= list->size)

    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)

    a = 9;
    b = 10;
    c = 11;

    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 9)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 10)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 11)

    cxLinkedListDestroy(list);
    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
}

void test_hl_ptr_linked_list_insert(void) {
    cxTestingAllocatorReset();

    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);

    int a = 5, b = 47, c = 13, d = 42;

    CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &a), 0)
    CU_ASSERT_EQUAL(list->size, 0)
    CU_ASSERT_EQUAL(cxListInsert(list, 0, &a), 0)
    CU_ASSERT_EQUAL(list->size, 1)
    CU_ASSERT_EQUAL(cxListInsert(list, 0, &b), 0)
    CU_ASSERT_EQUAL(list->size, 2)
    CU_ASSERT_EQUAL(cxListInsert(list, 1, &c), 0)
    CU_ASSERT_EQUAL(list->size, 3)
    CU_ASSERT_EQUAL(cxListInsert(list, 3, &d), 0)

    CU_ASSERT_EQUAL(list->size, 4)
    CU_ASSERT_TRUE(list->capacity >= list->size)

    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)

    cxLinkedListDestroy(list);
    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
}

void test_hl_ptr_linked_list_remove(void) {
    cxTestingAllocatorReset();

    int a = 5, b = 47, c = 42, d = 13;
    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);

    cxListAdd(list, &a);
    cxListAdd(list, &b);
    cxListAdd(list, &c);
    cxListAdd(list, &d);

    CU_ASSERT_EQUAL(list->size, 4)
    CU_ASSERT_TRUE(list->capacity >= list->size)

    CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)

    CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
    CU_ASSERT_EQUAL(list->size, 3)
    CU_ASSERT_TRUE(list->capacity >= list->size)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)

    CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
    CU_ASSERT_EQUAL(list->size, 2)
    CU_ASSERT_TRUE(list->capacity >= list->size)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)

    CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
    CU_ASSERT_EQUAL(list->size, 1)
    CU_ASSERT_TRUE(list->capacity >= list->size)
    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)

    CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
    CU_ASSERT_EQUAL(list->size, 0)
    CU_ASSERT_TRUE(list->capacity >= list->size)

    CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)

    cxLinkedListDestroy(list);
    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
}

void test_hl_ptr_linked_list_at(void) {
    cxTestingAllocatorReset();

    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);

    int a = 5, b = 47, c = 13;
    cxListAdd(list, &a);
    cxListAdd(list, &b);
    cxListAdd(list, &c);

    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_PTR_NULL(cxListAt(list, 3))

    cxLinkedListDestroy(list);
    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
}

void test_hl_ptr_linked_list_find(void) {
    cxTestingAllocatorReset();

    int a = 5, b = 47, c = 13, criteria;
    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);

    cxListAdd(list, &a);
    cxListAdd(list, &b);
    cxListAdd(list, &c);

    CU_ASSERT_EQUAL(list->size, 3)
    CU_ASSERT_TRUE(list->capacity >= list->size)

    criteria = 5;
    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0)
    criteria = 47;
    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
    criteria = 13;
    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2)
    criteria = 9000;
    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
    criteria = -5;
    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
    b = -5;
    CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)

    cxLinkedListDestroy(list);
    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
}

void test_hl_ptr_linked_list_sort(void) {
    int expected[] = {
            14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
            894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
            1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
            2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
            3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
            4785, 4791, 4801, 4859, 4903, 4973
    };
    int scrambled[] = {
            759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
            2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
            2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
            894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
            3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
            4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
    };

    cxTestingAllocatorReset();

    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);

    for (int i = 0; i < 100; i++) {
        cxListAdd(list, &scrambled[i]);
    }

    cxListSort(list);

    for (int i = 0; i < 100; i++) {
        CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i])
    }

    cxLinkedListDestroy(list);
    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
}

int main() {
    CU_pSuite suite = NULL;

    if (CUE_SUCCESS != CU_initialize_registry()) {
        return CU_get_error();
    }

    suite = CU_add_suite("low level linked list", NULL, NULL);

    cu_add_test(suite, test_linked_list_link_unlink);
    cu_add_test(suite, test_linked_list_at);
    cu_add_test(suite, test_linked_list_compare);
    cu_add_test(suite, test_linked_list_prepend);
    cu_add_test(suite, test_linked_list_add);
    cu_add_test(suite, test_linked_list_insert);
    cu_add_test(suite, test_linked_list_insert_chain);
    cu_add_test(suite, test_linked_list_first);
    cu_add_test(suite, test_linked_list_last);
    cu_add_test(suite, test_linked_list_prev);
    cu_add_test(suite, test_linked_list_remove);
    cu_add_test(suite, test_linked_list_size);
    cu_add_test(suite, test_linked_list_sort);
    cu_add_test(suite, test_linked_list_reverse);

    suite = CU_add_suite("high level linked list", NULL, NULL);

    cu_add_test(suite, test_hl_linked_list_create);
    cu_add_test(suite, test_hl_linked_list_add);
    cu_add_test(suite, test_hl_linked_list_insert);
    cu_add_test(suite, test_hl_linked_list_remove);
    cu_add_test(suite, test_hl_linked_list_at);
    cu_add_test(suite, test_hl_linked_list_find);
    cu_add_test(suite, test_hl_linked_list_sort);

    suite = CU_add_suite("high level pointer linked list", NULL, NULL);

    cu_add_test(suite, test_hl_ptr_linked_list_create);
    cu_add_test(suite, test_hl_ptr_linked_list_add);
    cu_add_test(suite, test_hl_ptr_linked_list_insert);
    cu_add_test(suite, test_hl_ptr_linked_list_remove);
    cu_add_test(suite, test_hl_ptr_linked_list_at);
    cu_add_test(suite, test_hl_ptr_linked_list_find);
    cu_add_test(suite, test_hl_ptr_linked_list_sort);

    CU_basic_set_mode(UCX_CU_BRM);

    int exitcode;
    if (CU_basic_run_tests()) {
        exitcode = CU_get_error();
    } else {
        exitcode = CU_get_number_of_failures() == 0 ? 0 : 1;
    }
    CU_cleanup_registry();
    return exitcode;
}