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

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

void test_hl_linked_list_add(void) {
    cxTestingAllocatorReset();

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

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

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

    CU_ASSERT_EQUAL(*cxTypedListAt(int, list, 0), 5)
    CU_ASSERT_EQUAL(*cxTypedListAt(int, list, 1), 47)
    CU_ASSERT_EQUAL(*cxTypedListAt(int, 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(cxTypedListLast(int, list))

    data = 5;
    CU_ASSERT_EQUAL(cxTypedListAdd(int, list, &data), 0)
    CU_ASSERT_EQUAL(*cxTypedListLast(int, list), 5)

    data = 47;
    CU_ASSERT_EQUAL(cxTypedListAdd(int, list, &data), 0)
    CU_ASSERT_EQUAL(*cxTypedListLast(int, 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(cxTypedListInsert(int, list, 1, &data), 0)
    CU_ASSERT_EQUAL(list->size, 0)
    CU_ASSERT_EQUAL(cxTypedListInsert(int, list, 0, &data), 0)
    CU_ASSERT_EQUAL(list->size, 1)
    data = 47;
    CU_ASSERT_EQUAL(cxTypedListInsert(int, list, 0, &data), 0)
    CU_ASSERT_EQUAL(list->size, 2)
    data = 13;
    CU_ASSERT_EQUAL(cxTypedListInsert(int, list, 1, &data), 0)
    CU_ASSERT_EQUAL(list->size, 3)
    data = 42;
    CU_ASSERT_EQUAL(cxTypedListInsert(int, list, 3, &data), 0)

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

    CU_ASSERT_EQUAL(*cxTypedListAt(int, list, 0), 47)
    CU_ASSERT_EQUAL(*cxTypedListAt(int, list, 1), 13)
    CU_ASSERT_EQUAL(*cxTypedListAt(int, list, 2), 5)
    CU_ASSERT_EQUAL(*cxTypedListAt(int, 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;
    cxTypedListAdd(int, list, &data);
    data = 47;
    cxTypedListAdd(int, list, &data);
    data = 42;
    cxTypedListAdd(int, list, &data);
    data = 13;
    cxTypedListAdd(int, 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(*cxTypedListAt(int, list, 0), 5)
    CU_ASSERT_EQUAL(*cxTypedListAt(int, list, 1), 47)
    CU_ASSERT_EQUAL(*cxTypedListAt(int, 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(*cxTypedListAt(int, list, 0), 47)
    CU_ASSERT_EQUAL(*cxTypedListAt(int, 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(*cxTypedListAt(int, 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;
    cxTypedListAdd(int, list, &data);
    data = 47;
    cxTypedListAdd(int, list, &data);
    data = 13;
    cxTypedListAdd(int, list, &data);

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

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

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

    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;
}