ucx: tests/test_list.c@04aa3913c0e3

     1 /*

     2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.

     3  *

     4  * Copyright 2023 Mike Becker, Olaf Wintermann All rights reserved.

     5  *

     6  * Redistribution and use in source and binary forms, with or without

     7  * modification, are permitted provided that the following conditions are met:

     8  *

     9  *   1. Redistributions of source code must retain the above copyright

    10  *      notice, this list of conditions and the following disclaimer.

    11  *

    12  *   2. Redistributions in binary form must reproduce the above copyright

    13  *      notice, this list of conditions and the following disclaimer in the

    14  *      documentation and/or other materials provided with the distribution.

    15  *

    16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

    17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

    18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

    19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE

    20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR

    21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF

    22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS

    23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN

    24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

    25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE

    26  * POSSIBILITY OF SUCH DAMAGE.

    27  */

    29 #include "cx/test.h"

    30 #include "util_allocator.h"

    31 #include "cx/compare.h"

    33 #include "cx/array_list.h"

    34 #include "cx/linked_list.h"

    36 #include <stdarg.h>

    38 typedef struct node {

    39     struct node *next;

    40     struct node *prev;

    41     int data;

    42 } node;

    44 const ptrdiff_t loc_prev = offsetof(struct node, prev);

    45 const ptrdiff_t loc_next = offsetof(struct node, next);

    46 const ptrdiff_t loc_data = offsetof(struct node, data);

    48 static node *create_nodes_test_data(size_t len) {

    49     node *begin = calloc(1, sizeof(node));

    50     void *prev = begin;

    51     for (size_t i = 1; i < len; i++) {

    52         node *n = calloc(1, sizeof(node));

    53         cx_linked_list_link(prev, n, loc_prev, loc_next);

    54         prev = n;

    55     }

    56     return begin;

    57 }

    59 void assign_nodes_test_data(node *n, ...) {

    60     va_list ap;

    61     va_start(ap, n);

    62     while (n != NULL) {

    63         n->data = va_arg(ap, int);

    64         n = n->next;

    65     }

    66     va_end(ap);

    67 }

    69 static void destroy_nodes_test_data(node *n) {

    70     while (n != NULL) {

    71         void *next = n->next;

    72         free(n);

    73         n = next;

    74     }

    75 }

    77 static int *int_test_data(size_t len) {

    78     int *data = malloc(len*sizeof(int));

    79     for (size_t i = 0 ; i < len ; i++) {

    80         data[i] = rand(); // NOLINT(*-msc50-cpp)

    81     }

    82     return data;

    83 }

    85 CX_TEST(test_linked_list_link_unlink) {

    86     node a = {0}, b = {0}, c = {0};

    88     CX_TEST_DO {

    89         cx_linked_list_link(&a, &b, loc_prev, loc_next);

    90         CX_TEST_ASSERT(a.prev == NULL);

    91         CX_TEST_ASSERT(a.next == &b);

    92         CX_TEST_ASSERT(b.prev == &a);

    93         CX_TEST_ASSERT(b.next == NULL);

    95         cx_linked_list_unlink(&a, &b, loc_prev, loc_next);

    96         CX_TEST_ASSERT(a.prev == NULL);

    97         CX_TEST_ASSERT(a.next == NULL);

    98         CX_TEST_ASSERT(b.prev == NULL);

    99         CX_TEST_ASSERT(b.next == NULL);

   101         cx_linked_list_link(&b, &c, loc_prev, loc_next);

   102         cx_linked_list_link(&a, &b, loc_prev, loc_next);

   103         cx_linked_list_unlink(&b, &c, loc_prev, loc_next);

   104         CX_TEST_ASSERT(a.prev == NULL);

   105         CX_TEST_ASSERT(a.next == &b);

   106         CX_TEST_ASSERT(b.prev == &a);

   107         CX_TEST_ASSERT(b.next == NULL);

   108         CX_TEST_ASSERT(c.prev == NULL);

   109         CX_TEST_ASSERT(c.next == NULL);

   110     }

   111 }

   113 CX_TEST(test_linked_list_at) {

   114     node a = {0}, b = {0}, c = {0}, d = {0};

   116     cx_linked_list_link(&a, &b, loc_prev, loc_next);

   117     cx_linked_list_link(&b, &c, loc_prev, loc_next);

   118     cx_linked_list_link(&c, &d, loc_prev, loc_next);

   120     CX_TEST_DO {

   121         CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 0) == &a);

   122         CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 1) == &b);

   123         CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 2) == &c);

   124         CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 3) == &d);

   125         CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 4) == NULL);

   126         CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_prev, 0) == &a);

   127         CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 1) == &b);

   128         CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 2) == &c);

   129         CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 3) == &d);

   130         CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 4) == NULL);

   131         CX_TEST_ASSERT(cx_linked_list_at(&d, 3, loc_prev, 0) == &a);

   132         CX_TEST_ASSERT(cx_linked_list_at(&d, 3, loc_prev, 1) == &b);

   133     }

   134 }

   136 CX_TEST(test_linked_list_find) {

   137     void *list = create_nodes_test_data(4);

   138     assign_nodes_test_data(list, 2, 4, 6, 8);

   139     CX_TEST_DO {

   140         int s;

   141         s = 2;

   142         CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 0);

   143         s = 4;

   144         CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 1);

   145         s = 6;

   146         CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 2);

   147         s = 8;

   148         CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 3);

   149         s = 10;

   150         CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) < 0);

   151         s = -2;

   152         CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) < 0);

   153     }

   154     destroy_nodes_test_data(list);

   155 }

   157 CX_TEST(test_linked_list_compare) {

   158     void *la = create_nodes_test_data(4);

   159     void *lb = create_nodes_test_data(3);

   160     void *lc = create_nodes_test_data(4);

   161     assign_nodes_test_data(la, 2, 4, 6, 8);

   162     assign_nodes_test_data(lb, 2, 4, 6);

   163     assign_nodes_test_data(lc, 2, 4, 6, 9);

   164     CX_TEST_DO {

   165         CX_TEST_ASSERT(cx_linked_list_compare(la, lb, loc_next, loc_data, cx_cmp_int) > 0);

   166         CX_TEST_ASSERT(cx_linked_list_compare(lb, la, loc_next, loc_data, cx_cmp_int) < 0);

   167         CX_TEST_ASSERT(cx_linked_list_compare(lc, la, loc_next, loc_data, cx_cmp_int) > 0);

   168         CX_TEST_ASSERT(cx_linked_list_compare(la, lc, loc_next, loc_data, cx_cmp_int) < 0);

   169         CX_TEST_ASSERT(cx_linked_list_compare(la, la, loc_next, loc_data, cx_cmp_int) == 0);

   170     }

   171     destroy_nodes_test_data(la);

   172     destroy_nodes_test_data(lb);

   173     destroy_nodes_test_data(lc);

   174 }

   176 CX_TEST(test_linked_list_add) {

   177     node nodes[4];

   178     void *begin, *end;

   179     CX_TEST_DO {

   180         // test with begin, end / prev, next

   181         memset(nodes, 0, sizeof(node)*4);

   182         end = begin = NULL;

   184         cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]);

   185         CX_TEST_ASSERT(begin == &nodes[0]);

   186         CX_TEST_ASSERT(end == &nodes[0]);

   187         CX_TEST_ASSERT(nodes[0].prev == NULL);

   188         CX_TEST_ASSERT(nodes[0].next == NULL);

   190         cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]);

   191         CX_TEST_ASSERT(begin == &nodes[0]);

   192         CX_TEST_ASSERT(end == &nodes[1]);

   193         CX_TEST_ASSERT(nodes[0].next == &nodes[1]);

   194         CX_TEST_ASSERT(nodes[1].prev == &nodes[0]);

   196         // test with begin only / prev, next

   197         memset(nodes, 0, sizeof(node)*4);

   198         end = begin = NULL;

   200         cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]);

   201         CX_TEST_ASSERT(begin == &nodes[0]);

   202         cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]);

   203         CX_TEST_ASSERT(begin == &nodes[0]);

   204         CX_TEST_ASSERT(nodes[0].next == &nodes[1]);

   205         CX_TEST_ASSERT(nodes[1].prev == &nodes[0]);

   207         cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[2]);

   208         CX_TEST_ASSERT(nodes[1].next == &nodes[2]);

   209         CX_TEST_ASSERT(nodes[2].prev == &nodes[1]);

   211         // test with end only / prev, next

   212         memset(nodes, 0, sizeof(node)*4);

   213         end = begin = NULL;

   215         cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]);

   216         CX_TEST_ASSERT(end == &nodes[0]);

   217         cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]);

   218         CX_TEST_ASSERT(end == &nodes[1]);

   219         CX_TEST_ASSERT(nodes[0].next == &nodes[1]);

   220         CX_TEST_ASSERT(nodes[1].prev == &nodes[0]);

   222         cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[2]);

   223         CX_TEST_ASSERT(end == &nodes[2]);

   224         CX_TEST_ASSERT(nodes[1].next == &nodes[2]);

   225         CX_TEST_ASSERT(nodes[2].prev == &nodes[1]);

   227         // test with begin, end / next

   228         memset(nodes, 0, sizeof(node)*4);

   229         end = begin = NULL;

   231         cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]);

   232         CX_TEST_ASSERT(begin == &nodes[0]);

   233         CX_TEST_ASSERT(end == &nodes[0]);

   234         cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]);

   235         CX_TEST_ASSERT(end == &nodes[1]);

   236         CX_TEST_ASSERT(nodes[0].next == &nodes[1]);

   237         CX_TEST_ASSERT(nodes[1].prev == NULL);

   238     }

   239 }

   241 CX_TEST(test_linked_list_prepend) {

   242     node nodes[4];

   243     void *begin, *end;

   244     CX_TEST_DO {

   245         // test with begin, end / prev, next

   246         memset(nodes, 0, sizeof(node) * 4);

   247         end = begin = NULL;

   249         cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]);

   250         CX_TEST_ASSERT(begin == &nodes[0]);

   251         CX_TEST_ASSERT(end == &nodes[0]);

   252         CX_TEST_ASSERT(nodes[0].prev == NULL);

   253         CX_TEST_ASSERT(nodes[0].next == NULL);

   255         cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]);

   256         CX_TEST_ASSERT(begin == &nodes[1]);

   257         CX_TEST_ASSERT(end == &nodes[0]);

   258         CX_TEST_ASSERT(nodes[1].next == &nodes[0]);

   259         CX_TEST_ASSERT(nodes[0].prev == &nodes[1]);

   261         // test with begin only / prev, next

   262         memset(nodes, 0, sizeof(node) * 4);

   263         end = begin = NULL;

   265         cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]);

   266         CX_TEST_ASSERT(begin == &nodes[0]);

   267         cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]);

   268         CX_TEST_ASSERT(begin == &nodes[1]);

   269         CX_TEST_ASSERT(nodes[1].next == &nodes[0]);

   270         CX_TEST_ASSERT(nodes[0].prev == &nodes[1]);

   272         cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[2]);

   273         CX_TEST_ASSERT(begin == &nodes[2]);

   274         CX_TEST_ASSERT(nodes[2].next == &nodes[1]);

   275         CX_TEST_ASSERT(nodes[1].prev == &nodes[2]);

   277         // test with end only / prev, next

   278         memset(nodes, 0, sizeof(node) * 4);

   279         end = begin = NULL;

   281         cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]);

   282         CX_TEST_ASSERT(end == &nodes[0]);

   283         cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]);

   284         CX_TEST_ASSERT(end == &nodes[0]);

   285         CX_TEST_ASSERT(nodes[1].next == &nodes[0]);

   286         CX_TEST_ASSERT(nodes[0].prev == &nodes[1]);

   288         cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[2]);

   289         CX_TEST_ASSERT(end == &nodes[0]);

   290         CX_TEST_ASSERT(nodes[2].next == &nodes[1]);

   291         CX_TEST_ASSERT(nodes[1].prev == &nodes[2]);

   293         // test with begin, end / next

   294         memset(nodes, 0, sizeof(node) * 4);

   295         end = begin = NULL;

   297         cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]);

   298         CX_TEST_ASSERT(begin == &nodes[0]);

   299         CX_TEST_ASSERT(end == &nodes[0]);

   300         cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]);

   301         cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]);

   302         CX_TEST_ASSERT(begin == &nodes[2]);

   303         CX_TEST_ASSERT(end == &nodes[0]);

   304         CX_TEST_ASSERT(nodes[1].next == &nodes[0]);

   305         CX_TEST_ASSERT(nodes[2].next == &nodes[1]);

   306         CX_TEST_ASSERT(nodes[1].prev == NULL);

   307         CX_TEST_ASSERT(nodes[0].prev == NULL);

   308     }

   309 }

   311 CX_TEST(test_linked_list_insert) {

   312     node nodes[4];

   313     void *begin, *end;

   314     CX_TEST_DO {

   315         // insert mid list

   316         memset(nodes, 0, sizeof(node) * 4);

   317         begin = &nodes[0];

   318         end = &nodes[2];

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

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

   323         cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]);

   324         CX_TEST_ASSERT(begin == &nodes[0]);

   325         CX_TEST_ASSERT(end == &nodes[2]);

   326         CX_TEST_ASSERT(nodes[1].next == &nodes[3]);

   327         CX_TEST_ASSERT(nodes[2].prev == &nodes[3]);

   328         CX_TEST_ASSERT(nodes[3].prev == &nodes[1]);

   329         CX_TEST_ASSERT(nodes[3].next == &nodes[2]);

   331         // insert end

   332         memset(nodes, 0, sizeof(node) * 4);

   333         begin = &nodes[0];

   334         end = &nodes[2];

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

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

   339         cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]);

   340         CX_TEST_ASSERT(begin == &nodes[0]);

   341         CX_TEST_ASSERT(end == &nodes[3]);

   342         CX_TEST_ASSERT(nodes[2].next == &nodes[3]);

   343         CX_TEST_ASSERT(nodes[3].prev == &nodes[2]);

   344         CX_TEST_ASSERT(nodes[3].next == NULL);

   346         // insert begin

   347         memset(nodes, 0, sizeof(node) * 4);

   348         begin = &nodes[0];

   349         end = &nodes[2];

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

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

   354         cx_linked_list_insert(&begin, &end, loc_prev, loc_next, NULL, &nodes[3]);

   355         CX_TEST_ASSERT(begin == &nodes[3]);

   356         CX_TEST_ASSERT(end == &nodes[2]);

   357         CX_TEST_ASSERT(nodes[0].prev == &nodes[3]);

   358         CX_TEST_ASSERT(nodes[3].prev == NULL);

   359         CX_TEST_ASSERT(nodes[3].next == &nodes[0]);

   360     }

   361 }

   363 CX_TEST(test_linked_list_insert_chain) {

   364     node nodes[5];

   365     void *begin, *end;

   366     CX_TEST_DO {

   367         // insert mid list

   368         memset(nodes, 0, sizeof(node) * 5);

   369         begin = &nodes[0]; end = &nodes[2];

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

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

   373         cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);

   375         cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], NULL);

   376         CX_TEST_ASSERT(begin == &nodes[0]);

   377         CX_TEST_ASSERT(end == &nodes[2]);

   378         CX_TEST_ASSERT(nodes[1].next == &nodes[3]);

   379         CX_TEST_ASSERT(nodes[2].prev == &nodes[4]);

   380         CX_TEST_ASSERT(nodes[3].prev == &nodes[1]);

   381         CX_TEST_ASSERT(nodes[4].next == &nodes[2]);

   383         // insert end

   384         memset(nodes, 0, sizeof(node) * 5);

   385         begin = &nodes[0]; end = &nodes[2];

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

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

   389         cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);

   391         cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], NULL);

   392         CX_TEST_ASSERT(begin == &nodes[0]);

   393         CX_TEST_ASSERT(end == &nodes[4]);

   394         CX_TEST_ASSERT(nodes[2].next == &nodes[3]);

   395         CX_TEST_ASSERT(nodes[3].prev == &nodes[2]);

   396         CX_TEST_ASSERT(nodes[4].next == NULL);

   398         // insert begin

   399         memset(nodes, 0, sizeof(node) * 5);

   400         begin = &nodes[0]; end = &nodes[2];

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

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

   404         cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);

   406         cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, NULL, &nodes[3], NULL);

   407         CX_TEST_ASSERT(begin == &nodes[3]);

   408         CX_TEST_ASSERT(end == &nodes[2]);

   409         CX_TEST_ASSERT(nodes[0].prev == &nodes[4]);

   410         CX_TEST_ASSERT(nodes[3].prev == NULL);

   411         CX_TEST_ASSERT(nodes[4].next == &nodes[0]);

   412     }

   413 }

   415 CX_TEST(test_linked_list_first) {

   416     node *testdata = create_nodes_test_data(3);

   417     void *begin = testdata;

   418     CX_TEST_DO {

   419         CX_TEST_ASSERT(begin == cx_linked_list_first(testdata, loc_prev));

   420         CX_TEST_ASSERT(begin == cx_linked_list_first(testdata->next, loc_prev));

   421         CX_TEST_ASSERT(begin == cx_linked_list_first(testdata->next->next, loc_prev));

   422     }

   423     destroy_nodes_test_data(testdata);

   424 }

   426 CX_TEST(test_linked_list_last) {

   427     node *testdata = create_nodes_test_data(3);

   428     void *end = testdata->next->next;

   429     CX_TEST_DO {

   430         CX_TEST_ASSERT(end == cx_linked_list_last(testdata, loc_next));

   431         CX_TEST_ASSERT(end == cx_linked_list_last(testdata->next, loc_next));

   432         CX_TEST_ASSERT(end == cx_linked_list_last(testdata->next->next, loc_next));

   433     }

   434     destroy_nodes_test_data(testdata);

   435 }

   437 CX_TEST(test_linked_list_prev) {

   438     node *testdata = create_nodes_test_data(3);

   439     CX_TEST_DO {

   440         CX_TEST_ASSERT(cx_linked_list_prev(testdata, loc_next, testdata) == NULL);

   441         CX_TEST_ASSERT(cx_linked_list_prev(testdata, loc_next, testdata->next) == testdata);

   442         CX_TEST_ASSERT(cx_linked_list_prev(testdata, loc_next, testdata->next->next) == testdata->next);

   443     }

   444     destroy_nodes_test_data(testdata);

   445 }

   447 CX_TEST(test_linked_list_remove) {

   448     node *testdata = create_nodes_test_data(3);

   449     assign_nodes_test_data(testdata, 2, 4, 6);

   450     node *first = testdata;

   451     node *second = first->next;

   452     node *third = second->next;

   453     void *begin = testdata;

   454     void *end = third;

   456     CX_TEST_DO {

   457         cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second);

   458         CX_TEST_ASSERT(begin == first);

   459         CX_TEST_ASSERT(end == third);

   460         CX_TEST_ASSERT(first->prev == NULL);

   461         CX_TEST_ASSERT(first->next == third);

   462         CX_TEST_ASSERT(third->prev == first);

   463         CX_TEST_ASSERT(third->next == NULL);

   465         cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third);

   466         CX_TEST_ASSERT(begin == first);

   467         CX_TEST_ASSERT(end == first);

   468         CX_TEST_ASSERT(first->prev == NULL);

   469         CX_TEST_ASSERT(first->next == NULL);

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

   472         CX_TEST_ASSERT(begin == NULL);

   473         CX_TEST_ASSERT(end == NULL);

   474     }

   475     // list is not intact anymore, we have to free nodes individually

   476     free(first);

   477     free(second);

   478     free(third);

   479 }

   481 CX_TEST(test_linked_list_size) {

   482     node *td5 = create_nodes_test_data(5);

   483     node *td13 = create_nodes_test_data(13);

   484     CX_TEST_DO {

   485         CX_TEST_ASSERT(cx_linked_list_size(NULL, loc_next) == 0);

   486         CX_TEST_ASSERT(cx_linked_list_size(td5, loc_next) == 5);

   487         CX_TEST_ASSERT(cx_linked_list_size(td13, loc_next) == 13);

   488     }

   489     destroy_nodes_test_data(td5);

   490     destroy_nodes_test_data(td13);

   491 }

   493 CX_TEST(test_linked_list_sort_empty) {

   494     void *begin = NULL;

   495     CX_TEST_DO {

   496         // cannot assert something, we can just test that it does not crash

   497         cx_linked_list_sort(&begin, NULL, loc_prev, loc_next, loc_data, cx_cmp_int);

   498         CX_TEST_ASSERT(true);

   499     }

   500 }

   502 CX_TEST(test_linked_list_sort) {

   503     const size_t len = 1500;

   504     int *testdata = int_test_data(len);

   505     void *scrambled = create_nodes_test_data(len);

   506     node *n = scrambled;

   507     for (size_t i = 0; i < len; i++) {

   508         n->data = testdata[i];

   509         n = n->next;

   510     }

   511     int *sorted = malloc(len*sizeof(int));

   512     memcpy(sorted, testdata, len*sizeof(int));

   513     qsort(sorted, len, sizeof(int), cx_cmp_int);

   515     void *begin = scrambled;

   516     void *end = cx_linked_list_last(begin, loc_next);

   518     CX_TEST_DO {

   519         cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data, cx_cmp_int);

   520         node *check = begin;

   521         node *check_last = NULL;

   522         for (size_t i = 0; i < len; i++) {

   523             CX_TEST_ASSERT(check->data == sorted[i]);

   524             CX_TEST_ASSERT(check->prev == check_last);

   525             if (i < len - 1) {

   526                 CX_TEST_ASSERT(check->next != NULL);

   527             }

   528             check_last = check;

   529             check = check->next;

   530         }

   531         CX_TEST_ASSERT(check == NULL);

   532         CX_TEST_ASSERT(end == check_last);

   533     }

   534     destroy_nodes_test_data(begin);

   535     free(sorted);

   536     free(testdata);

   537 }

   539 CX_TEST(test_linked_list_reverse) {

   540     void *testdata = create_nodes_test_data(4);

   541     void *expected = create_nodes_test_data(4);

   542     assign_nodes_test_data(testdata, 2, 4, 6, 8);

   543     assign_nodes_test_data(expected, 8, 6, 4, 2);

   544     void *begin = testdata;

   545     CX_TEST_DO {

   546         void *end = cx_linked_list_last(begin, loc_next);

   547         void *orig_begin = begin, *orig_end = end;

   549         cx_linked_list_reverse(&begin, &end, loc_prev, loc_next);

   550         CX_TEST_ASSERT(end == orig_begin);

   551         CX_TEST_ASSERT(begin == orig_end);

   552         CX_TEST_ASSERT(0 == cx_linked_list_compare(begin, expected, loc_next, loc_data, cx_cmp_int));

   553     }

   554     destroy_nodes_test_data(begin);

   555     destroy_nodes_test_data(expected);

   556 }

   559 CX_TEST(test_empty_list_size) {

   560     CX_TEST_DO {

   561         CX_TEST_ASSERT(cxEmptyList->size == 0);

   562         CX_TEST_ASSERT(cxListSize(cxEmptyList) == 0);

   563     }

   564 }

   566 CX_TEST(test_empty_list_iterator) {

   567     CxList *list = cxEmptyList;

   569     CxIterator it1 = cxListIterator(list);

   570     CxIterator it2 = cxListBackwardsIterator(list);

   571     CxMutIterator it3 = cxListMutIterator(list);

   572     CxMutIterator it4 = cxListMutBackwardsIterator(list);

   574     CX_TEST_DO {

   575         CX_TEST_ASSERT(!cxIteratorValid(it1));

   576         CX_TEST_ASSERT(!cxIteratorValid(it2));

   577         CX_TEST_ASSERT(!cxIteratorValid(it3));

   578         CX_TEST_ASSERT(!cxIteratorValid(it4));

   580         int c = 0;

   581         cx_foreach(void*, data, it1) c++;

   582         cx_foreach(void*, data, it2) c++;

   583         cx_foreach(void*, data, it3) c++;

   584         cx_foreach(void*, data, it4) c++;

   585         CX_TEST_ASSERT(c == 0);

   586     }

   587 }

   589 CX_TEST(test_empty_list_noops) {

   590     CX_TEST_DO {

   591         CxList copy = *cxEmptyList;

   592         cxListSort(cxEmptyList);

   593         cxListClear(cxEmptyList);

   594         cxListDestroy(cxEmptyList);

   595         CX_TEST_ASSERT(0 == memcmp(&copy, cxEmptyList, sizeof(CxList))); // NOLINT(*-suspicious-memory-comparison)

   596     }

   597 }

   599 CX_TEST(test_empty_list_at) {

   600     CX_TEST_DO {

   601         CX_TEST_ASSERT(cxListAt(cxEmptyList, 0) == NULL);

   602         CX_TEST_ASSERT(cxListAt(cxEmptyList, 1) == NULL);

   603     }

   604 }

   606 CX_TEST(test_empty_list_find) {

   607     int x = 42, y = 1337;

   608     CX_TEST_DO {

   609         CX_TEST_ASSERT(cxListFind(cxEmptyList, &x) < 0);

   610         CX_TEST_ASSERT(cxListFind(cxEmptyList, &y) < 0);

   611     }

   612 }

   614 CX_TEST(test_empty_list_compare) {

   615     CxList *empty = cxEmptyList;

   616     CxList *ll = cxLinkedListCreateSimple(sizeof(int));

   617     CxList *al = cxArrayListCreateSimple(sizeof(int), 8);

   618     int x = 5;

   619     CX_TEST_DO {

   620         CX_TEST_ASSERT(0 == cxListCompare(empty, cxEmptyList));

   621         CX_TEST_ASSERT(0 == cxListCompare(ll, cxEmptyList));

   622         CX_TEST_ASSERT(0 == cxListCompare(al, cxEmptyList));

   623         CX_TEST_ASSERT(0 == cxListCompare(cxEmptyList, ll));

   624         CX_TEST_ASSERT(0 == cxListCompare(cxEmptyList, al));

   626         cxListAdd(ll, &x);

   627         cxListAdd(al, &x);

   629         CX_TEST_ASSERT(0 < cxListCompare(ll, cxEmptyList));

   630         CX_TEST_ASSERT(0 < cxListCompare(al, cxEmptyList));

   631         CX_TEST_ASSERT(0 > cxListCompare(cxEmptyList, ll));

   632         CX_TEST_ASSERT(0 > cxListCompare(cxEmptyList, al));

   633     }

   634     cxListDestroy(ll);

   635     cxListDestroy(al);

   636 }

   638 CX_TEST(test_list_ll_create) {

   639     CxTestingAllocator talloc;

   640     cx_testing_allocator_init(&talloc);

   641     CxAllocator *alloc = &talloc.base;

   642     CX_TEST_DO {

   643         CxList *list = cxLinkedListCreate(alloc, cx_cmp_int, sizeof(int));

   644         CX_TEST_ASSERT(list != NULL);

   645         CX_TEST_ASSERT(list->item_size == sizeof(int));

   646         CX_TEST_ASSERT(list->simple_destructor == NULL);

   647         CX_TEST_ASSERT(list->advanced_destructor == NULL);

   648         CX_TEST_ASSERT(list->destructor_data == NULL);

   649         CX_TEST_ASSERT(cxListSize(list) == 0);

   650         CX_TEST_ASSERT(list->allocator == alloc);

   651         CX_TEST_ASSERT(list->cmpfunc == cx_cmp_int);

   652         CX_TEST_ASSERT(!cxListIsStoringPointers(list));

   653         cxListDestroy(list);

   654         CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));

   655     }

   656     cx_testing_allocator_destroy(&talloc);

   657 }

   659 CX_TEST(test_list_ll_create_simple) {

   660     CxList *list = cxLinkedListCreateSimple(sizeof(int));

   661     CX_TEST_DO {

   662         CX_TEST_ASSERT(list != NULL);

   663         CX_TEST_ASSERT(list->item_size == sizeof(int));

   664         CX_TEST_ASSERT(list->simple_destructor == NULL);

   665         CX_TEST_ASSERT(list->advanced_destructor == NULL);

   666         CX_TEST_ASSERT(list->destructor_data == NULL);

   667         CX_TEST_ASSERT(cxListSize(list) == 0);

   668         CX_TEST_ASSERT(list->allocator == cxDefaultAllocator);

   669         CX_TEST_ASSERT(list->cmpfunc == NULL);

   670         CX_TEST_ASSERT(!cxListIsStoringPointers(list));

   671     }

   672     cxListDestroy(list);

   673 }

   675 CX_TEST(test_list_ll_store_pointers) {

   676     CxList *list = cxLinkedListCreateSimple(47);

   677     CX_TEST_DO {

   678         CX_TEST_ASSERT(!cxListIsStoringPointers(list));

   679         cxListStorePointers(list);

   680         CX_TEST_ASSERT(list->item_size == sizeof(void *));

   681         CX_TEST_ASSERT(list->cl != NULL);

   682         CX_TEST_ASSERT(list->climpl != NULL);

   683         CX_TEST_ASSERT(cxListIsStoringPointers(list));

   684         cxListStoreObjects(list);

   685         CX_TEST_ASSERT(list->cl != NULL);

   686         CX_TEST_ASSERT(list->climpl == NULL);

   687         CX_TEST_ASSERT(!cxListIsStoringPointers(list));

   688     }

   689     cxListDestroy(list);

   690 }

   692 CX_TEST(test_list_ll_create_simple_for_pointers) {

   693     CxList *list = cxLinkedListCreateSimple(CX_STORE_POINTERS);

   694     CX_TEST_DO {

   695         CX_TEST_ASSERT(list != NULL);

   696         CX_TEST_ASSERT(list->item_size == sizeof(void*));

   697         CX_TEST_ASSERT(list->simple_destructor == NULL);

   698         CX_TEST_ASSERT(list->advanced_destructor == NULL);

   699         CX_TEST_ASSERT(list->destructor_data == NULL);

   700         CX_TEST_ASSERT(cxListSize(list) == 0);

   701         CX_TEST_ASSERT(list->allocator == cxDefaultAllocator);

   702         CX_TEST_ASSERT(list->cmpfunc == cx_cmp_ptr);

   703         CX_TEST_ASSERT(cxListIsStoringPointers(list));

   704     }

   705     cxListDestroy(list);

   706 }

   708 CX_TEST(test_list_arl_create) {

   709     CxTestingAllocator talloc;

   710     cx_testing_allocator_init(&talloc);

   711     CxAllocator *alloc = &talloc.base;

   712     CX_TEST_DO {

   713         CxList *list = cxArrayListCreate(alloc, cx_cmp_int, sizeof(int), 8);

   714         CX_TEST_ASSERT(list != NULL);

   715         CX_TEST_ASSERT(list->item_size == sizeof(int));

   716         CX_TEST_ASSERT(list->simple_destructor == NULL);

   717         CX_TEST_ASSERT(list->advanced_destructor == NULL);

   718         CX_TEST_ASSERT(list->destructor_data == NULL);

   719         CX_TEST_ASSERT(cxListSize(list) == 0);

   720         CX_TEST_ASSERT(list->allocator == alloc);

   721         CX_TEST_ASSERT(list->cmpfunc == cx_cmp_int);

   722         CX_TEST_ASSERT(!cxListIsStoringPointers(list));

   723         cxListDestroy(list);

   724         CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));

   725     }

   726     cx_testing_allocator_destroy(&talloc);

   727 }

   729 CX_TEST(test_list_arl_create_simple) {

   730     CxList *list = cxArrayListCreateSimple(sizeof(int), 8);

   731     CX_TEST_DO {

   732         CX_TEST_ASSERT(list != NULL);

   733         CX_TEST_ASSERT(list->item_size == sizeof(int));

   734         CX_TEST_ASSERT(list->simple_destructor == NULL);

   735         CX_TEST_ASSERT(list->advanced_destructor == NULL);

   736         CX_TEST_ASSERT(list->destructor_data == NULL);

   737         CX_TEST_ASSERT(cxListSize(list) == 0);

   738         CX_TEST_ASSERT(list->allocator == cxDefaultAllocator);

   739         CX_TEST_ASSERT(list->cmpfunc == NULL);

   740         CX_TEST_ASSERT(!cxListIsStoringPointers(list));

   741     }

   742     cxListDestroy(list);

   743 }

   745 CX_TEST(test_list_arl_create_simple_for_pointers) {

   746     CxList *list = cxArrayListCreateSimple(CX_STORE_POINTERS, 8);

   747     CX_TEST_DO {

   748         CX_TEST_ASSERT(list != NULL);

   749         CX_TEST_ASSERT(list->item_size == sizeof(void*));

   750         CX_TEST_ASSERT(list->simple_destructor == NULL);

   751         CX_TEST_ASSERT(list->advanced_destructor == NULL);

   752         CX_TEST_ASSERT(list->destructor_data == NULL);

   753         CX_TEST_ASSERT(cxListSize(list) == 0);

   754         CX_TEST_ASSERT(list->allocator == cxDefaultAllocator);

   755         CX_TEST_ASSERT(list->cmpfunc == cx_cmp_ptr);

   756         CX_TEST_ASSERT(cxListIsStoringPointers(list));

   757     }

   758     cxListDestroy(list);

   759 }

   761 static void test_fake_simple_int_destr(void *elem) {

   762     *(int *) elem = 42;

   763 }

   765 CX_TEST(test_list_pll_destroy_no_destr) {

   766     CxTestingAllocator talloc;

   767     cx_testing_allocator_init(&talloc);

   768     CxAllocator *alloc = &talloc.base;

   769     CX_TEST_DO {

   770         void *item = cxMalloc(alloc, sizeof(int));

   771         CxList *list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS);

   772         cxListAdd(list, item);

   773         CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));

   774         cxListDestroy(list);

   775         // item is not yet freed

   776         CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));

   777         cxFree(alloc, item);

   778         CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));

   779     }

   780     cx_testing_allocator_destroy(&talloc);

   781 }

   783 CX_TEST(test_list_pll_destroy_simple_destr) {

   784     CX_TEST_DO {

   785         int item = 0;

   786         CxList *list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS);

   787         list->simple_destructor = test_fake_simple_int_destr;

   788         cxListAdd(list, &item);

   789         cxListDestroy(list);

   790         CX_TEST_ASSERT(item == 42);

   791     }

   792 }

   794 CX_TEST(test_list_pll_destroy_adv_destr) {

   795     CxTestingAllocator talloc;

   796     cx_testing_allocator_init(&talloc);

   797     CxAllocator *alloc = &talloc.base;

   798     CX_TEST_DO {

   799         void *item = cxMalloc(alloc, sizeof(int));

   800         CxList *list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS);

   801         list->destructor_data = alloc;

   802         list->advanced_destructor = (cx_destructor_func2) cxFree;

   803         cxListAdd(list, item);

   804         CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));

   805         cxListDestroy(list);

   806         CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));

   807     }

   808     cx_testing_allocator_destroy(&talloc);

   809 }

   811 CX_TEST(test_list_parl_destroy_no_destr) {

   812     CxTestingAllocator talloc;

   813     cx_testing_allocator_init(&talloc);

   814     CxAllocator *alloc = &talloc.base;

   815     CX_TEST_DO {

   816         void *item = cxMalloc(alloc, sizeof(int));

   817         CxList *list = cxArrayListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS, 4);

   818         cxListAdd(list, item);

   819         CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));

   820         cxListDestroy(list);

   821         // item is not yet freed

   822         CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));

   823         cxFree(alloc, item);

   824         CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));

   825     }

   826     cx_testing_allocator_destroy(&talloc);

   827 }

   829 CX_TEST(test_list_parl_destroy_simple_destr) {

   830     CX_TEST_DO {

   831         int item = 0;

   832         CxList *list = cxArrayListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS, 4);

   833         list->simple_destructor = test_fake_simple_int_destr;

   834         cxListAdd(list, &item);

   835         cxListDestroy(list);

   836         CX_TEST_ASSERT(item == 42);

   837     }

   838 }

   840 CX_TEST(test_list_parl_destroy_adv_destr) {

   841     CxTestingAllocator talloc;

   842     cx_testing_allocator_init(&talloc);

   843     CxAllocator *alloc = &talloc.base;

   844     CX_TEST_DO {

   845         void *item = cxMalloc(alloc, sizeof(int));

   846         CxList *list = cxArrayListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS, 4);

   847         list->destructor_data = alloc;

   848         list->advanced_destructor = (cx_destructor_func2) cxFree;

   849         cxListAdd(list, item);

   850         CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));

   851         cxListDestroy(list);

   852         CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));

   853     }

   854     cx_testing_allocator_destroy(&talloc);

   855 }

   857 CxTestSuite *cx_test_suite_array_list(void) {

   858     CxTestSuite *suite = cx_test_suite_new("array_list");

   860     cx_test_register(suite, test_list_arl_create);

   861     cx_test_register(suite, test_list_arl_create_simple);

   862     cx_test_register(suite, test_list_arl_create_simple_for_pointers);

   863     cx_test_register(suite, test_list_parl_destroy_no_destr);

   864     cx_test_register(suite, test_list_parl_destroy_simple_destr);

   865     cx_test_register(suite, test_list_parl_destroy_adv_destr);

   867     return suite;

   868 }

   870 CxTestSuite *cx_test_suite_linked_list(void) {

   871     CxTestSuite *suite = cx_test_suite_new("linked_list");

   873     cx_test_register(suite, test_linked_list_link_unlink);

   874     cx_test_register(suite, test_linked_list_at);

   875     cx_test_register(suite, test_linked_list_find);

   876     cx_test_register(suite, test_linked_list_compare);

   877     cx_test_register(suite, test_linked_list_add);

   878     cx_test_register(suite, test_linked_list_prepend);

   879     cx_test_register(suite, test_linked_list_insert);

   880     cx_test_register(suite, test_linked_list_insert_chain);

   881     cx_test_register(suite, test_linked_list_first);

   882     cx_test_register(suite, test_linked_list_last);

   883     cx_test_register(suite, test_linked_list_prev);

   884     cx_test_register(suite, test_linked_list_remove);

   885     cx_test_register(suite, test_linked_list_size);

   886     cx_test_register(suite, test_linked_list_sort_empty);

   887     cx_test_register(suite, test_linked_list_sort);

   888     cx_test_register(suite, test_linked_list_reverse);

   890     cx_test_register(suite, test_list_ll_create);

   891     cx_test_register(suite, test_list_ll_create_simple);

   892     cx_test_register(suite, test_list_ll_store_pointers);

   893     cx_test_register(suite, test_list_ll_create_simple_for_pointers);

   894     cx_test_register(suite, test_list_pll_destroy_no_destr);

   895     cx_test_register(suite, test_list_pll_destroy_simple_destr);

   896     cx_test_register(suite, test_list_pll_destroy_adv_destr);

   898     return suite;

   899 }

   901 CxTestSuite *cx_test_suite_empty_list(void) {

   902     CxTestSuite *suite = cx_test_suite_new("empty list dummy");

   904     cx_test_register(suite, test_empty_list_size);

   905     cx_test_register(suite, test_empty_list_iterator);

   906     cx_test_register(suite, test_empty_list_noops);

   907     cx_test_register(suite, test_empty_list_at);

   908     cx_test_register(suite, test_empty_list_find);

   909     cx_test_register(suite, test_empty_list_compare);

   911     return suite;

   912 }

Mercurial > hg > ucx / file revision

tests/test_list.c@04aa3913c0e3

tests/test_list.c