test/list_tests.c

/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 *
 * Copyright 2017 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 "list_tests.h"
#include <ucx/utils.h>

UCX_TEST(test_ucx_list_append) {
    UcxList *list, *first;
    list = first = ucx_list_append(NULL, (void*)"Hello");
    UCX_TEST_BEGIN
    
    UCX_TEST_ASSERT(strncmp((const char*)list->data, "Hello", 5) == 0,
            "failed");
    
    list = ucx_list_append(list, (void*)" World!");
    
    UCX_TEST_ASSERT(list == first, "does not return first element");
    UCX_TEST_ASSERT(strncmp((const char*)list->next->data, " World!", 7) == 0,
            "failed");
    UCX_TEST_ASSERT(list->next->prev == list, "failed");
    UCX_TEST_ASSERT(list->next->next == NULL, "failed");
    UCX_TEST_END
    
    ucx_list_free(list);
}

UCX_TEST(test_ucx_list_prepend) {
    UcxList *list, *last;
    list = last = ucx_list_prepend(NULL, (void*)" World!");
    UCX_TEST_BEGIN

    list = ucx_list_prepend(list, (void*)"Hello");
    
    UCX_TEST_ASSERT(strncmp((const char*)list->data, "Hello", 5) == 0,
            "failed");
    UCX_TEST_ASSERT(strncmp((const char*)list->next->data, " World!", 7) == 0,
            "failed");
    UCX_TEST_ASSERT(list == last->prev, "does not return first element");
    UCX_TEST_ASSERT(list->next->next == NULL, "failed");
    UCX_TEST_ASSERT(list->prev == NULL, "failed");
    
    UCX_TEST_END
    ucx_list_free(list);
}

UCX_TEST(test_ucx_list_equals) {
    const char *hello = "Hello";
    const char *world = " World!";
    UcxList *list = ucx_list_append(NULL, (void*)hello);
    list = ucx_list_append(list, (void*)world);
    UcxList *list2 = ucx_list_prepend(NULL, (void*)world);
    list2 = ucx_list_prepend(list2, (void*)hello);
    UcxList *list3 = ucx_list_prepend(NULL, (void*)" Welt!");
    list3 = ucx_list_prepend(list3, (void*)"Hallo");
    UcxList *list4 = ucx_list_prepend(NULL, (void*)" World!");
    list4 = ucx_list_prepend(list4, (void*)"Hello");
    UCX_TEST_BEGIN
    
    UCX_TEST_ASSERT(ucx_list_equals(list, list4, ucx_cmp_str, NULL), "failed");
    UCX_TEST_ASSERT(!ucx_list_equals(list, list3, ucx_cmp_str, NULL), "failed");
    UCX_TEST_ASSERT(ucx_list_equals(list, list2, NULL, NULL), "failed");
    
    UCX_TEST_END
    ucx_list_free(list4);
    ucx_list_free(list3);
    ucx_list_free(list2);
    ucx_list_free(list);
}

UCX_TEST(test_ucx_list_concat) {
    UcxList *list = ucx_list_append(NULL, (void*)"Hello");
    list = ucx_list_append(list, (void*)" my ");
    UcxList *list2 = ucx_list_prepend(NULL, (void*)" World!");
    list2 = ucx_list_prepend(list2, (void*)" sweet ");
    UCX_TEST_BEGIN
    
    list = ucx_list_concat(list, list2);
    list = ucx_list_concat(list, NULL);
    list = ucx_list_concat(NULL, list);
    
    UCX_TEST_ASSERT(!strncmp((const char*)list->data, "Hello", 5),
            "failed");
    UCX_TEST_ASSERT(!strncmp((const char*)list->next->data, " my ", 4),
            "failed");
    UCX_TEST_ASSERT(!strncmp((const char*)list->next->next->data, " sweet ", 7),
            "failed");
    UCX_TEST_ASSERT(!strncmp((const char*)ucx_list_last(list)->data,
            " World!", 7), "failed");

    UCX_TEST_ASSERT(list->prev == NULL, "failed");
    
    UCX_TEST_END
    // don't free list2, as it is freed by freeing list;
    ucx_list_free(list);
}

UCX_TEST(test_ucx_list_size) {
    UcxList *list = ucx_list_append(NULL, (void*)"This ");
    list = ucx_list_append(list, (void*)"list ");
    list = ucx_list_append(list, (void*)"has ");
    list = ucx_list_append(list, (void*)"size ");
    list = ucx_list_append(list, (void*)"5!");
    
    UCX_TEST_BEGIN
    
    UCX_TEST_ASSERT(ucx_list_size(list) == 5, "failed");
    list = ucx_list_remove(list, ucx_list_get(list, 2));
    UCX_TEST_ASSERT(ucx_list_size(list) == 4, "failed after removal");
    
    UCX_TEST_END
    ucx_list_free(list);
}

UCX_TEST(test_ucx_list_first) {
    UcxList *list = ucx_list_append(NULL, (void*)"Find ");
    list = ucx_list_append(list, (void*)"the ");
    list = ucx_list_append(list, (void*)"first!");
    
    UCX_TEST_BEGIN
    
    const char* first = (const char*) (ucx_list_first(list)->data);
    
    UCX_TEST_ASSERT(strncmp(first, "Find ", 5) == 0, "failed");
    UCX_TEST_ASSERT(ucx_list_first(list->next->next) == list, "failed");
    UCX_TEST_ASSERT(!ucx_list_first(NULL),
        "does not return NULL on an empty list");
    
    UCX_TEST_END
    ucx_list_free(list);
}

UCX_TEST(test_ucx_list_last) {
    UcxList *list = ucx_list_append(NULL, (void*)"Find ");
    list = ucx_list_append(list, (void*)"the ");
    list = ucx_list_append(list, (void*)"last!");
    
    UCX_TEST_BEGIN
    
    const char* last = (const char*) (ucx_list_last(list->next->next)->data);
    
    UCX_TEST_ASSERT(strncmp(last, "last!", 5) == 0, "failed");
    UCX_TEST_ASSERT(ucx_list_last(list) == list->next->next, "failed");
    UCX_TEST_ASSERT(!ucx_list_last(NULL),
        "does not return NULL on an empty list");
    
    UCX_TEST_END
    ucx_list_free(list);
}

UCX_TEST(test_ucx_list_get) {
    UcxList *list = ucx_list_append(NULL, (void*)"Find ");
    list = ucx_list_append(list, (void*)"the ");
    list = ucx_list_append(list, (void*)"mid!");
    
    UCX_TEST_BEGIN
    
    const char* first = (const char*) (ucx_list_get(list, 0)->data);
    const char* mid = (const char*) (ucx_list_get(list, 1)->data);
    const char* last = (const char*) (ucx_list_get(list, 2)->data);
    
    UCX_TEST_ASSERT(strncmp(first, "Find ", 5) == 0, "failed");
    UCX_TEST_ASSERT(strncmp(mid, "the ", 4) == 0, "failed");
    UCX_TEST_ASSERT(strncmp(last, "mid!", 4) == 0, "failed");
    UCX_TEST_ASSERT(!ucx_list_get(list, -1), "out of bounds (neg)");
    UCX_TEST_ASSERT(!ucx_list_get(list, 3), "out of bounds");
    UCX_TEST_ASSERT(!ucx_list_get(NULL, 0), "empty list");
    
    UCX_TEST_END
    ucx_list_free(list);
}

UCX_TEST(test_ucx_list_indexof) {
    UcxList *list = ucx_list_append(NULL, (void*)"Find ");
    list = ucx_list_append(list, (void*)"the ");
    list = ucx_list_append(list, (void*)"mid!");
    
    UCX_TEST_BEGIN
    
    UCX_TEST_ASSERT(ucx_list_indexof(list, list) == 0, "failed");
    UCX_TEST_ASSERT(ucx_list_indexof(list, list->next) == 1, "failed");
    UCX_TEST_ASSERT(ucx_list_indexof(list, ucx_list_get(list, 2)) == 2,
        "failed");
    
    UcxList *otherlist = ucx_list_append(NULL, (void*) "the ");
    UCX_TEST_ASSERT(ucx_list_indexof(list, otherlist) == -1, "failed");
    UCX_TEST_ASSERT(ucx_list_indexof(NULL, otherlist) == -1, "empty list");

    ucx_list_free(otherlist);
    
    UCX_TEST_END
    ucx_list_free(list);
}

UCX_TEST(test_ucx_list_find) {
    const char* teststr = "string!";
    UcxList *l = ucx_list_append(NULL, (void*)"find ");
    l = ucx_list_append(l, (void*)"some ");
    l = ucx_list_append(l, (void*)teststr);
    
    UCX_TEST_BEGIN
    
    UCX_TEST_ASSERT(ucx_list_find(l,(void*)"some ",ucx_cmp_str,NULL) == 1,
        "doesn't find string");
    UCX_TEST_ASSERT(ucx_list_find(l,(void*)"a",ucx_cmp_str,NULL) == -1,
        "finds non-existing string");
    
    UCX_TEST_ASSERT(ucx_list_find(l,(void*)teststr,NULL,NULL) == 2,
        "doesn't find integer without cmp_func");
    
    UCX_TEST_ASSERT(ucx_list_find(NULL, (void*)"some ",ucx_cmp_str,NULL) == -1,
        "empty list");
    
    UCX_TEST_END
    ucx_list_free(l);
}

UCX_TEST(test_ucx_list_contains) {
    UcxList *l = ucx_list_append(NULL, (void*)"Contains ");
    l = ucx_list_append(l, (void*)"a ");
    l = ucx_list_append(l, (void*)"string!");
    
    UCX_TEST_BEGIN
    
    UCX_TEST_ASSERT(ucx_list_contains(l,(void*)"a ",ucx_cmp_str,NULL),
        "false negative");
    UCX_TEST_ASSERT(!ucx_list_contains(l,(void*)"a",ucx_cmp_str,NULL),
        "false positive");
    
    UCX_TEST_END
    ucx_list_free(l);
}

UCX_TEST(test_ucx_list_remove) {
    UcxList *list = ucx_list_append(NULL, (void*)"Hello");
    list = ucx_list_append(list, (void*)"fucking");
    list = ucx_list_append(list, (void*)"World!");
    
    UcxList *list2 = ucx_list_append(NULL, (void*)"A");
    list2 = ucx_list_append(list2, (void*)"B");
    list2 = ucx_list_append(list2, (void*)"C");
    list2 = ucx_list_append(list2, (void*)"D");
    list2 = ucx_list_append(list2, (void*)"E");
    list2 = ucx_list_append(list2, (void*)"F");
    list2 = ucx_list_append(list2, (void*)"G");
    
    UCX_TEST_BEGIN
    
    list = ucx_list_remove(list, ucx_list_get(list, 1));
    
    UCX_TEST_ASSERT(strncmp((const char*)list->data, "Hello", 5) == 0,
            "failed");
    UCX_TEST_ASSERT(strncmp((const char*)list->next->data, "World!", 7) == 0,
            "failed");
    UCX_TEST_ASSERT(list->next->next == NULL, "failed");
    
    // remove first element: B, C, D, E, F, G
    list2 = ucx_list_remove(list2, list2);
    
    UCX_TEST_ASSERT(ucx_list_size(list2) == 6, "list2 has wrong size");
    UCX_TEST_ASSERT(strncmp((const char*)list2->data, "B", 1) == 0,
            "wrong first element");
    UCX_TEST_ASSERT(strncmp((const char*)ucx_list_get(list2, 5)->data, "G", 1)
            == 0, "wrong last element");
    
    // remove second element: B, D, E, F, G
    list2 = ucx_list_remove(list2, list2->next);
    
    UCX_TEST_ASSERT(ucx_list_size(list2) == 5, "list2 has wrong size");
    UCX_TEST_ASSERT(strncmp((const char*)list2->next->data, "D", 1) == 0,
            "wrong second element");
    
    UcxList *last = ucx_list_get(list2, 4);
    list2 = ucx_list_remove(list2, last->prev);
    
    UCX_TEST_ASSERT(ucx_list_size(list2) == 4, "list2 has wrong size");
    UCX_TEST_ASSERT(strncmp((const char*)last->prev->data, "E", 1) == 0,
            "wrong element");
    
    // remove last element: B, D, E, F
    list2 = ucx_list_remove(list2, last);
    UCX_TEST_ASSERT(ucx_list_size(list2) == 3, "list2 has wrong size");
    UCX_TEST_ASSERT(strncmp((const char*)ucx_list_get(list2, 2)->data, "E", 1)
            == 0, "wrong last element");
    
    UCX_TEST_ASSERT(strncmp((const char*)list2->data, "B", 1) == 0,
            "wrong element");
    
    list2 = ucx_list_remove(list2, list2);
    UCX_TEST_ASSERT(ucx_list_size(list2) == 2, "list2 has wrong size");
    list2 = ucx_list_remove(list2, list2);
    UCX_TEST_ASSERT(ucx_list_size(list2) == 1, "list2 has wrong size");
    list2 = ucx_list_remove(list2, list2);
    UCX_TEST_ASSERT(list2 == NULL, "list2 is not null");
    
    UCX_TEST_END
    ucx_list_free(list);
}

UCX_TEST(test_ucx_list_clone) {
   
    char *hello = (char*)malloc(6);
    char *world = (char*)malloc(8);
    
    memcpy(hello, "Hello", 6);
    memcpy(world, " World!", 8);
    
    UcxList *list = ucx_list_append(NULL, hello);
    list = ucx_list_append(list, world);
    
    UcxList *copy = ucx_list_clone(list, ucx_strcpy, NULL);
    UCX_TEST_BEGIN

    UCX_TEST_ASSERT(ucx_list_equals(list, copy, ucx_cmp_str, NULL), "failed");
    UCX_TEST_ASSERT(hello != copy->data, "first element is no copy");
    UCX_TEST_ASSERT(world != copy->next->data, "second element is no copy");

    UCX_TEST_END
    
    ucx_list_free_content(copy, free);

    free(world);
    free(hello);
    ucx_list_free(list);
    ucx_list_free(copy);
}

UCX_TEST(test_ucx_list_sort) {
    UcxList *list = ucx_list_append(NULL, (void*)"this");
    list = ucx_list_append(list, (void*)"is");
    list = ucx_list_append(list, (void*)"a");
    list = ucx_list_append(list, (void*)"test");
    list = ucx_list_append(list, (void*)"for");
    list = ucx_list_append(list, (void*)"partial");
    list = ucx_list_append(list, (void*)"correctness");
    list = ucx_list_append(list, (void*)"of");
    list = ucx_list_append(list, (void*)"the");
    list = ucx_list_append(list, (void*)"sort");
    list = ucx_list_append(list, (void*)"function");
    list = ucx_list_append(list, (void*)"that");
    list = ucx_list_append(list, (void*)"shall");
    list = ucx_list_append(list, (void*)"pass");
    list = ucx_list_append(list, (void*)"this");
    list = ucx_list_append(list, (void*)"test");

    UcxList *expected = ucx_list_append(NULL, (void*)"a");
    expected = ucx_list_append(expected, (void*)"correctness");
    expected = ucx_list_append(expected, (void*)"for");
    expected = ucx_list_append(expected, (void*)"function");
    expected = ucx_list_append(expected, (void*)"is");
    expected = ucx_list_append(expected, (void*)"of");
    expected = ucx_list_append(expected, (void*)"partial");
    expected = ucx_list_append(expected, (void*)"pass");
    expected = ucx_list_append(expected, (void*)"shall");
    expected = ucx_list_append(expected, (void*)"sort");
    expected = ucx_list_append(expected, (void*)"test");
    expected = ucx_list_append(expected, (void*)"test");
    expected = ucx_list_append(expected, (void*)"that");
    expected = ucx_list_append(expected, (void*)"the");
    expected = ucx_list_append(expected, (void*)"this");
    expected = ucx_list_append(expected, (void*)"this");

    list = ucx_list_sort(list, ucx_cmp_str, NULL);

    UCX_TEST_BEGIN
    UCX_TEST_ASSERT(
            ucx_list_equals(list, expected, ucx_cmp_str, NULL), "failed");
    UCX_TEST_ASSERT(ucx_list_size(list) == 16, "list has now a wrong size");
    UcxList *l = list;
    UCX_TEST_ASSERT(l->prev == NULL, "prev field of first entry is not null");
    while (l->next != NULL) {
        UCX_TEST_ASSERT(l->next->prev == l, "next or prev pointer corrupted");
        l = l->next;
    }
    UCX_TEST_ASSERT(!ucx_list_sort(NULL, ucx_cmp_str, NULL),
        "failed to sort empty list");
    UCX_TEST_END

    ucx_list_free(expected);
    ucx_list_free(list);
}

UCX_TEST(test_ucx_list_union) {
    UcxList *left = ucx_list_append(NULL, (void*)"this");
    left = ucx_list_append(left, (void*)"is");
    left = ucx_list_append(left, (void*)"a");
    left = ucx_list_append(left, (void*)"test");

    UcxList *right = ucx_list_append(NULL, (void*)"to");
    right = ucx_list_append(right, (void*)"test");
    right = ucx_list_append(right, (void*)"set");
    right = ucx_list_append(right, (void*)"operations");
    
    UcxList *expected = ucx_list_append(NULL, (void*)"this");
    expected = ucx_list_append(expected, (void*)"is");
    expected = ucx_list_append(expected, (void*)"a");
    expected = ucx_list_append(expected, (void*)"test");
    expected = ucx_list_append(expected, (void*)"to");
    expected = ucx_list_append(expected, (void*)"set");
    expected = ucx_list_append(expected, (void*)"operations");

    UcxList* result = ucx_list_union(left, right, ucx_cmp_str,
            NULL, NULL, NULL);

    UCX_TEST_BEGIN
    UCX_TEST_ASSERT(ucx_list_equals(result, expected,
            ucx_cmp_str, NULL), "failed");
    UCX_TEST_END

    ucx_list_free(result);
    ucx_list_free(expected);
    ucx_list_free(right);
    ucx_list_free(left);
}

UCX_TEST(test_ucx_list_intersection) {
    UcxList *left = ucx_list_append(NULL, (void*)"this");
    left = ucx_list_append(left, (void*)"is");
    left = ucx_list_append(left, (void*)"a");
    left = ucx_list_append(left, (void*)"test");

    UcxList *right = ucx_list_append(NULL, (void*)"to");
    right = ucx_list_append(right, (void*)"test");
    right = ucx_list_append(right, (void*)"a");
    right = ucx_list_append(right, (void*)"set");
    right = ucx_list_append(right, (void*)"operation");
    
    UcxList *expected = ucx_list_append(NULL, (void*)"a");
    expected = ucx_list_append(expected, (void*)"test");

    UcxList* result = ucx_list_intersection(left, right, ucx_cmp_str,
            NULL, NULL, NULL);

    UCX_TEST_BEGIN
    UCX_TEST_ASSERT(ucx_list_equals(result, expected,
            ucx_cmp_str, NULL), "failed");
    UCX_TEST_END

    ucx_list_free(result);
    ucx_list_free(expected);
    ucx_list_free(right);
    ucx_list_free(left);
}

UCX_TEST(test_ucx_list_difference) {
    UcxList *left = ucx_list_append(NULL, (void*)"this");
    left = ucx_list_append(left, (void*)"is");
    left = ucx_list_append(left, (void*)"a");
    left = ucx_list_append(left, (void*)"test");

    UcxList *right = ucx_list_append(NULL, (void*)"to");
    right = ucx_list_append(right, (void*)"test");
    right = ucx_list_append(right, (void*)"this");
    right = ucx_list_append(right, (void*)"set");
    right = ucx_list_append(right, (void*)"operations");
    
    UcxList *expected = ucx_list_append(NULL, (void*)"is");
    expected = ucx_list_append(expected, (void*)"a");
    
    UcxList* result = ucx_list_difference(left, right, ucx_cmp_str,
            NULL, NULL, NULL);

    UCX_TEST_BEGIN
    UCX_TEST_ASSERT(ucx_list_equals(result, expected,
            ucx_cmp_str, NULL), "failed");
    UCX_TEST_END

    ucx_list_free(result);
    ucx_list_free(expected);
    ucx_list_free(right);
    ucx_list_free(left);
}