/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
*
* Copyright 2023 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/tree.h"
#include "cx/test.h"
#include "util_allocator.h"
typedef struct tree_node {
struct tree_node *parent;
struct tree_node *next;
struct tree_node *prev;
struct tree_node *children;
int data;
} tree_node;
typedef struct tree_node2 {
CX_TREE_NODE_BASE(struct tree_node2);
int data;
} tree_node2;
typedef struct tree_node_file {
struct tree_node_file *parent;
struct tree_node_file *next;
struct tree_node_file *prev;
struct tree_node_file *children;
struct tree_node_file *last_child;
const char *path;
} tree_node_file;
static void *tree_node_file_create(
const void *dptr,
void *allocator) {
if (allocator == NULL) allocator = (void*) cxDefaultAllocator;
tree_node_file *node = cxMalloc(allocator, sizeof(tree_node_file));
node->path = dptr;
// intentionally write garbage into the pointers, it's part of the test
node->parent = (void *) 0xf00ba1;
node->next = (void *) 0xf00ba2;
node->prev = (void *) 0xf00ba3;
node->children = (void *) 0xf00ba4;
node->last_child = (void *) 0xf00ba5;
return node;
}
static void *tree_node_file_create_hl(
const void *dptr,
void *tree) {
return tree_node_file_create(dptr, (void*)((CxTree*)tree)->collection.allocator);
}
static int tree_node_file_search(const void *l, const void *r) {
const tree_node_file *left = l;
const tree_node_file *right = r;
size_t len1 = strlen(left->path);
size_t len2 = strlen(right->path);
if (len1 <= len2) {
if (memcmp(left->path, right->path, len1) == 0) {
return (int) (len2 - len1);
} else {
return -1;
}
} else {
return -1;
}
}
static int tree_node_file_search_data(const void *l, const void *d) {
tree_node_file r;
r.path = d;
return tree_node_file_search(l, &r);
}
#define tree_node_layout \
offsetof(tree_node, parent), offsetof(tree_node, children), -1, \
offsetof(tree_node, prev), offsetof(tree_node, next)
#define tree_node_layout_no_prev \
offsetof(tree_node, parent), offsetof(tree_node, children), -1, -1, \
offsetof(tree_node, next)
#define tree_node_full_layout(structname) \
offsetof(structname, parent), offsetof(structname, children),\
offsetof(structname, last_child), \
offsetof(structname, prev), offsetof(structname, next)
#define tree_node2_layout cx_tree_node_base_layout
#define tree_node_file_layout tree_node_full_layout(tree_node_file)
#define tree_children(type) offsetof(type, children), offsetof(type, next)
CX_TEST(test_tree_link_new_child) {
tree_node parent = {0};
tree_node child = {0};
CX_TEST_DO {
cx_tree_link(&parent, &child, tree_node_layout);
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
CX_TEST_ASSERT(parent.parent == NULL);
CX_TEST_ASSERT(parent.children == &child);
CX_TEST_ASSERT(child.parent == &parent);
CX_TEST_ASSERT(child.next == NULL);
CX_TEST_ASSERT(child.prev == NULL);
CX_TEST_ASSERT(child.children == NULL);
}
}
CX_TEST(test_tree_link_add_child) {
tree_node parent = {0};
tree_node child1 = {0};
tree_node child2 = {0};
tree_node child3 = {0};
CX_TEST_DO {
cx_tree_link(&parent, &child1, tree_node_layout);
cx_tree_link(&parent, &child2, tree_node_layout);
cx_tree_link(&parent, &child3, tree_node_layout);
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
CX_TEST_ASSERT(parent.parent == NULL);
CX_TEST_ASSERT(parent.children == &child1);
CX_TEST_ASSERT(child1.parent == &parent);
CX_TEST_ASSERT(child2.parent == &parent);
CX_TEST_ASSERT(child3.parent == &parent);
CX_TEST_ASSERT(child1.children == NULL);
CX_TEST_ASSERT(child2.children == NULL);
CX_TEST_ASSERT(child3.children == NULL);
CX_TEST_ASSERT(child1.prev == NULL);
CX_TEST_ASSERT(child1.next == &child2);
CX_TEST_ASSERT(child2.prev == &child1);
CX_TEST_ASSERT(child2.next == &child3);
CX_TEST_ASSERT(child3.prev == &child2);
CX_TEST_ASSERT(child3.next == NULL);
}
}
CX_TEST(test_tree_link_move_to_other_parent) {
tree_node parent = {0};
tree_node child1 = {0};
tree_node child2 = {0};
tree_node child3 = {0};
cx_tree_link(&parent, &child1, tree_node_layout);
cx_tree_link(&parent, &child2, tree_node_layout);
cx_tree_link(&parent, &child3, tree_node_layout);
CX_TEST_DO {
cx_tree_link(&child3, &child2, tree_node_layout);
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
CX_TEST_ASSERT(parent.parent == NULL);
CX_TEST_ASSERT(parent.children == &child1);
CX_TEST_ASSERT(child1.parent == &parent);
CX_TEST_ASSERT(child2.parent == &child3);
CX_TEST_ASSERT(child3.parent == &parent);
CX_TEST_ASSERT(child1.children == NULL);
CX_TEST_ASSERT(child2.children == NULL);
CX_TEST_ASSERT(child3.children == &child2);
CX_TEST_ASSERT(child1.prev == NULL);
CX_TEST_ASSERT(child1.next == &child3);
CX_TEST_ASSERT(child3.prev == &child1);
CX_TEST_ASSERT(child3.next == NULL);
CX_TEST_ASSERT(child2.prev == NULL);
CX_TEST_ASSERT(child2.next == NULL);
}
}
CX_TEST(test_tree_unlink) {
tree_node parent = {0};
tree_node child1 = {0};
tree_node child2 = {0};
tree_node child3 = {0};
tree_node child4 = {0};
cx_tree_link(&parent, &child1, tree_node_layout);
cx_tree_link(&parent, &child3, tree_node_layout);
cx_tree_link(&parent, &child4, tree_node_layout);
cx_tree_link(&child3, &child2, tree_node_layout);
CX_TEST_DO {
cx_tree_unlink(&child3, tree_node_layout);
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
CX_TEST_ASSERT(parent.parent == NULL);
CX_TEST_ASSERT(parent.children == &child1);
CX_TEST_ASSERT(child1.parent == &parent);
CX_TEST_ASSERT(child1.children == NULL);
CX_TEST_ASSERT(child1.prev == NULL);
CX_TEST_ASSERT(child1.next == &child4);
CX_TEST_ASSERT(child4.parent == &parent);
CX_TEST_ASSERT(child4.children == NULL);
CX_TEST_ASSERT(child4.prev == &child1);
CX_TEST_ASSERT(child4.next == NULL);
// child 3 is unlinked
CX_TEST_ASSERT(child3.parent == NULL);
CX_TEST_ASSERT(child3.prev == NULL);
CX_TEST_ASSERT(child3.next == NULL);
// child 2 is still child of the unlinked child 3
CX_TEST_ASSERT(child3.children == &child2);
CX_TEST_ASSERT(child2.parent == &child3);
CX_TEST_ASSERT(child2.children == NULL);
CX_TEST_ASSERT(child2.prev == NULL);
CX_TEST_ASSERT(child2.next == NULL);
// unlink first child from parent
cx_tree_unlink(&child1, tree_node_layout);
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
CX_TEST_ASSERT(parent.parent == NULL);
CX_TEST_ASSERT(parent.children == &child4);
CX_TEST_ASSERT(child1.parent == NULL);
CX_TEST_ASSERT(child4.parent == &parent);
CX_TEST_ASSERT(child4.children == NULL);
CX_TEST_ASSERT(child4.prev == NULL);
CX_TEST_ASSERT(child4.next == NULL);
}
}
CX_TEST(test_tree_unlink_no_prev) {
tree_node parent = {0};
tree_node child1 = {0};
tree_node child2 = {0};
tree_node child3 = {0};
tree_node child4 = {0};
cx_tree_link(&parent, &child1, tree_node_layout_no_prev);
cx_tree_link(&parent, &child3, tree_node_layout_no_prev);
cx_tree_link(&parent, &child4, tree_node_layout_no_prev);
cx_tree_link(&child3, &child2, tree_node_layout_no_prev);
void * const marker = (void*) 0xc0ffee;
child1.prev = child2.prev = child3.prev = child4.prev = marker;
CX_TEST_DO {
// in contrast to the other test we here remove child 4 instead of 3!
cx_tree_unlink(&child4, tree_node_layout_no_prev);
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
CX_TEST_ASSERT(parent.parent == NULL);
CX_TEST_ASSERT(parent.children == &child1);
CX_TEST_ASSERT(child1.parent == &parent);
CX_TEST_ASSERT(child1.children == NULL);
CX_TEST_ASSERT(child1.prev == marker);
CX_TEST_ASSERT(child1.next == &child3);
// child 4 is unlinked
CX_TEST_ASSERT(child4.parent == NULL);
CX_TEST_ASSERT(child4.children == NULL);
CX_TEST_ASSERT(child4.prev == marker);
CX_TEST_ASSERT(child4.next == NULL);
// unlink first child from parent
cx_tree_unlink(&child1, tree_node_layout_no_prev);
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
CX_TEST_ASSERT(parent.parent == NULL);
CX_TEST_ASSERT(parent.children == &child3);
CX_TEST_ASSERT(child1.parent == NULL);
CX_TEST_ASSERT(child3.parent == &parent);
CX_TEST_ASSERT(child3.children == &child2);
CX_TEST_ASSERT(child3.prev == marker);
CX_TEST_ASSERT(child3.next == NULL);
}
}
CX_TEST(test_tree2_link_new_child) {
tree_node2 parent = {0};
tree_node2 child = {0};
CX_TEST_DO {
cx_tree_link(&parent, &child, tree_node2_layout);
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
CX_TEST_ASSERT(parent.parent == NULL);
CX_TEST_ASSERT(parent.children == &child);
CX_TEST_ASSERT(parent.last_child == &child);
CX_TEST_ASSERT(child.parent == &parent);
CX_TEST_ASSERT(child.next == NULL);
CX_TEST_ASSERT(child.prev == NULL);
CX_TEST_ASSERT(child.children == NULL);
CX_TEST_ASSERT(child.last_child == NULL);
}
}
CX_TEST(test_tree2_link_add_child) {
tree_node2 parent = {0};
tree_node2 child1 = {0};
tree_node2 child2 = {0};
tree_node2 child3 = {0};
CX_TEST_DO {
cx_tree_link(&parent, &child1, tree_node2_layout);
cx_tree_link(&parent, &child2, tree_node2_layout);
cx_tree_link(&parent, &child3, tree_node2_layout);
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
CX_TEST_ASSERT(parent.parent == NULL);
CX_TEST_ASSERT(parent.children == &child1);
CX_TEST_ASSERT(parent.last_child == &child3);
CX_TEST_ASSERT(child1.parent == &parent);
CX_TEST_ASSERT(child2.parent == &parent);
CX_TEST_ASSERT(child3.parent == &parent);
CX_TEST_ASSERT(child1.children == NULL);
CX_TEST_ASSERT(child2.children == NULL);
CX_TEST_ASSERT(child3.children == NULL);
CX_TEST_ASSERT(child1.last_child == NULL);
CX_TEST_ASSERT(child2.last_child == NULL);
CX_TEST_ASSERT(child3.last_child == NULL);
CX_TEST_ASSERT(child1.prev == NULL);
CX_TEST_ASSERT(child1.next == &child2);
CX_TEST_ASSERT(child2.prev == &child1);
CX_TEST_ASSERT(child2.next == &child3);
CX_TEST_ASSERT(child3.prev == &child2);
CX_TEST_ASSERT(child3.next == NULL);
}
}
CX_TEST(test_tree2_link_move_to_other_parent) {
tree_node2 parent = {0};
tree_node2 child1 = {0};
tree_node2 child2 = {0};
tree_node2 child3 = {0};
cx_tree_link(&parent, &child1, tree_node2_layout);
cx_tree_link(&parent, &child2, tree_node2_layout);
cx_tree_link(&parent, &child3, tree_node2_layout);
CX_TEST_DO {
cx_tree_link(&child3, &child2, tree_node2_layout);
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
CX_TEST_ASSERT(parent.parent == NULL);
CX_TEST_ASSERT(parent.children == &child1);
CX_TEST_ASSERT(parent.last_child == &child3);
CX_TEST_ASSERT(child1.parent == &parent);
CX_TEST_ASSERT(child2.parent == &child3);
CX_TEST_ASSERT(child3.parent == &parent);
CX_TEST_ASSERT(child1.children == NULL);
CX_TEST_ASSERT(child2.children == NULL);
CX_TEST_ASSERT(child3.children == &child2);
CX_TEST_ASSERT(child1.last_child == NULL);
CX_TEST_ASSERT(child2.last_child == NULL);
CX_TEST_ASSERT(child3.last_child == &child2);
CX_TEST_ASSERT(child1.prev == NULL);
CX_TEST_ASSERT(child1.next == &child3);
CX_TEST_ASSERT(child3.prev == &child1);
CX_TEST_ASSERT(child3.next == NULL);
CX_TEST_ASSERT(child2.prev == NULL);
CX_TEST_ASSERT(child2.next == NULL);
}
}
CX_TEST(test_tree2_unlink) {
tree_node2 parent = {0};
tree_node2 child1 = {0};
tree_node2 child2 = {0};
tree_node2 child3 = {0};
cx_tree_link(&parent, &child1, tree_node2_layout);
cx_tree_link(&parent, &child3, tree_node2_layout);
cx_tree_link(&child3, &child2, tree_node2_layout);
CX_TEST_DO {
cx_tree_unlink(&child3, tree_node2_layout);
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
CX_TEST_ASSERT(parent.parent == NULL);
CX_TEST_ASSERT(parent.children == &child1);
CX_TEST_ASSERT(parent.last_child == &child1);
CX_TEST_ASSERT(child1.parent == &parent);
CX_TEST_ASSERT(child1.children == NULL);
CX_TEST_ASSERT(child1.last_child == NULL);
CX_TEST_ASSERT(child1.prev == NULL);
CX_TEST_ASSERT(child1.next == NULL);
// child 3 is unlinked
CX_TEST_ASSERT(child3.parent == NULL);
CX_TEST_ASSERT(child3.prev == NULL);
CX_TEST_ASSERT(child3.next == NULL);
// child 2 is still child of the unlinked child 3
CX_TEST_ASSERT(child3.children == &child2);
CX_TEST_ASSERT(child3.last_child == &child2);
CX_TEST_ASSERT(child2.parent == &child3);
CX_TEST_ASSERT(child2.children == NULL);
CX_TEST_ASSERT(child2.last_child == NULL);
CX_TEST_ASSERT(child2.prev == NULL);
CX_TEST_ASSERT(child2.next == NULL);
// unlink last child from parent
cx_tree_unlink(&child1, tree_node2_layout);
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
CX_TEST_ASSERT(parent.parent == NULL);
CX_TEST_ASSERT(parent.children == NULL);
CX_TEST_ASSERT(parent.last_child == NULL);
CX_TEST_ASSERT(child1.parent == NULL);
}
}
static int test_tree_search_function(const void *n, const void *d) {
const tree_node *node = n;
int data = *((const int *)d);
if (data < node->data) return -1;
else if (data == node->data) return 0;
else return data - node->data;
}
CX_TEST(test_tree_search) {
tree_node root = {0};
tree_node a = {0};
tree_node b = {0};
tree_node c = {0};
tree_node aa = {0};
tree_node ab = {0};
tree_node ba = {0};
tree_node ca = {0};
tree_node cb = {0};
tree_node cc = {0};
tree_node cba = {0};
int testdata[] = {0, 10, 14, 18, 20, 25, 30, 32, 34, 36, 40};
tree_node* testnodes[] = {&root, &a, &aa, &ab, &b, &ba, &c, &ca, &cb, &cba, &cc};
for (unsigned i = 0 ; i <= 10 ; i++) {
testnodes[i]->data = testdata[i];
}
cx_tree_link(&root, &a, tree_node_layout);
cx_tree_link(&root, &b, tree_node_layout);
cx_tree_link(&root, &c, tree_node_layout);
cx_tree_link(&a, &aa, tree_node_layout);
cx_tree_link(&a, &ab, tree_node_layout);
cx_tree_link(&b, &ba, tree_node_layout);
cx_tree_link(&c, &ca, tree_node_layout);
cx_tree_link(&c, &cb, tree_node_layout);
cx_tree_link(&c, &cc, tree_node_layout);
cx_tree_link(&cb, &cba, tree_node_layout);
int s;
int r;
tree_node *n;
CX_TEST_DO {
for (unsigned i = 0 ; i <= 10 ; i++) {
s = testdata[i];
r = cx_tree_search_data(&root, 0, &s, test_tree_search_function,
(void **) &n, tree_children(tree_node));
CX_TEST_ASSERT(r == 0);
CX_TEST_ASSERT(n == testnodes[i]);
}
s = -5;
r = cx_tree_search_data(&root, 0, &s, test_tree_search_function,
(void **) &n, tree_children(tree_node));
CX_TEST_ASSERT(r < 0);
CX_TEST_ASSERT(n == NULL);
s = 26;
r = cx_tree_search_data(&root, 0, &s, test_tree_search_function,
(void **) &n, tree_children(tree_node));
CX_TEST_ASSERT(r > 0);
CX_TEST_ASSERT(n == &ba);
s = 35;
r = cx_tree_search_data(&root, 0, &s, test_tree_search_function,
(void **) &n, tree_children(tree_node));
CX_TEST_ASSERT(r > 0);
CX_TEST_ASSERT(n == &cb);
s = 38;
r = cx_tree_search_data(&root, 0, &s, test_tree_search_function,
(void **) &n, tree_children(tree_node));
CX_TEST_ASSERT(r > 0);
CX_TEST_ASSERT(n == &cba);
s = 42;
r = cx_tree_search_data(&root, 0, &s, test_tree_search_function,
(void **) &n, tree_children(tree_node));
CX_TEST_ASSERT(r > 0);
CX_TEST_ASSERT(n == &cc);
}
}
CX_TEST(test_tree_search_with_max_depth) {
tree_node_file root = {0};
root.path = "/";
tree_node_file usr = {0};
usr.path = "/usr/";
cx_tree_link(&root, &usr, tree_node_file_layout);
tree_node_file home = {0};
home.path = "/home/";
cx_tree_link(&root, &home, tree_node_file_layout);
tree_node_file doe = {0};
doe.path = "/home/doe/";
cx_tree_link(&home, &doe, tree_node_file_layout);
tree_node_file lib = {0};
lib.path = "/usr/lib/";
cx_tree_link(&usr, &lib, tree_node_file_layout);
tree_node_file modules = {0};
modules.path = "/usr/lib/modules/";
cx_tree_link(&lib, &modules, tree_node_file_layout);
CX_TEST_DO {
int result;
void *found;
result = cx_tree_search_data(
&root, 1, "/",
tree_node_file_search_data, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERTM(result == 0, "root not found");
CX_TEST_ASSERT(found == &root);
result = cx_tree_search_data(
&root, 1, "/usr/",
tree_node_file_search_data, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERT(result > 0);
CX_TEST_ASSERT(found == &root);
result = cx_tree_search_data(
&root, 2, "/usr/",
tree_node_file_search_data, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERT(result == 0);
CX_TEST_ASSERT(found == &usr);
result = cx_tree_search_data(
&root, 2, "/usr/lib/",
tree_node_file_search_data, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERT(result > 0);
CX_TEST_ASSERT(found == &usr);
result = cx_tree_search_data(
&root, 3, "/usr/lib/",
tree_node_file_search_data, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERTM(result == 0, "lib not found");
CX_TEST_ASSERT(found == &lib);
result = cx_tree_search_data(
&root, 1, "/home/",
tree_node_file_search_data, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERT(result > 0);
CX_TEST_ASSERT(found == &root);
result = cx_tree_search_data(
&root, 2, "/home/",
tree_node_file_search_data, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERTM(result == 0, "home not found");
CX_TEST_ASSERT(found == &home);
result = cx_tree_search_data(
&root, 2, "/home/doe/",
tree_node_file_search_data, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERT(result > 0);
CX_TEST_ASSERT(found == &home);
result = cx_tree_search_data(
&root, 3, "/home/doe/",
tree_node_file_search_data, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERTM(result == 0, "doe not found");
CX_TEST_ASSERT(found == &doe);
result = cx_tree_search_data(
&root, 3, "/usr/lib/modules/",
tree_node_file_search_data, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERT(result > 0);
CX_TEST_ASSERT(found == &lib);
result = cx_tree_search_data(
&root, 4, "/usr/lib/modules/",
tree_node_file_search_data, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERTM(result == 0, "modules not found (start=root)");
CX_TEST_ASSERT(found == &modules);
result = cx_tree_search_data(
&usr, 3, "/usr/lib/modules/",
tree_node_file_search_data, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERTM(result == 0, "modules not found (start=usr)");
CX_TEST_ASSERT(found == &modules);
}
}
CX_TEST(test_tree_iterator_create_and_dispose) {
tree_node root;
CX_TEST_DO {
CxTreeIterator iter = cx_tree_iterator(&root, false, tree_children(tree_node));
CX_TEST_ASSERT(!iter.visit_on_exit);
CX_TEST_ASSERT(!iter.exiting);
CX_TEST_ASSERT(iter.counter == 1);
CX_TEST_ASSERT(iter.node == &root);
CX_TEST_ASSERT(!iter.base.allow_remove);
CX_TEST_ASSERT(!iter.base.remove);
CX_TEST_ASSERT(iter.stack != NULL);
CX_TEST_ASSERT(iter.stack_capacity > 0);
CX_TEST_ASSERT(iter.stack_size == 1);
CX_TEST_ASSERT(iter.depth == 1);
CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next));
CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children));
cxTreeIteratorDispose(&iter);
CX_TEST_ASSERT(iter.stack == NULL);
}
}
CX_TEST(test_tree_iterator_create_for_empty_tree) {
CX_TEST_DO {
CxTreeIterator iter = cx_tree_iterator(NULL, false, tree_children(tree_node));
CX_TEST_ASSERT(!iter.visit_on_exit);
CX_TEST_ASSERT(!iter.exiting);
CX_TEST_ASSERT(iter.counter == 0);
CX_TEST_ASSERT(iter.node == NULL);
CX_TEST_ASSERT(!iter.base.allow_remove);
CX_TEST_ASSERT(!iter.base.remove);
CX_TEST_ASSERT(iter.stack == NULL);
CX_TEST_ASSERT(iter.stack_capacity == 0);
CX_TEST_ASSERT(iter.stack_size == 0);
CX_TEST_ASSERT(iter.depth == 0);
CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next));
CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children));
CX_TEST_ASSERT(!cxIteratorValid(iter));
// disposing this iterator should also be harmless
cxTreeIteratorDispose(&iter);
}
}
CX_TEST(test_tree_iterator_basic_only_enter) {
tree_node root = {0};
tree_node a = {0};
tree_node b = {0};
tree_node c = {0};
tree_node aa = {0};
tree_node ab = {0};
tree_node ba = {0};
tree_node ca = {0};
tree_node cb = {0};
tree_node cc = {0};
tree_node cba = {0};
tree_node* expected_order[] = {
&root,
&a, &aa, &ab,
&b, &ba,
&c, &ca, &cb, &cba, &cc,
};
tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
cx_tree_link(&root, &a, tree_node_layout);
cx_tree_link(&root, &b, tree_node_layout);
cx_tree_link(&root, &c, tree_node_layout);
cx_tree_link(&a, &aa, tree_node_layout);
cx_tree_link(&a, &ab, tree_node_layout);
cx_tree_link(&b, &ba, tree_node_layout);
cx_tree_link(&c, &ca, tree_node_layout);
cx_tree_link(&c, &cb, tree_node_layout);
cx_tree_link(&c, &cc, tree_node_layout);
cx_tree_link(&cb, &cba, tree_node_layout);
CX_TEST_DO {
CxTreeIterator iter = cx_tree_iterator(&root, false, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(node->data == 0);
node->data++;
actual_order[chk] = node;
chk++;
CX_TEST_ASSERT(node == iter.node);
CX_TEST_ASSERT(!iter.exiting);
if (node == &root) {
CX_TEST_ASSERT(iter.depth == 1);
} else if (node == &a || node == &b || node == &c) {
CX_TEST_ASSERT(iter.depth == 2);
} else if (node == &cba) {
CX_TEST_ASSERT(iter.depth == 4);
} else {
CX_TEST_ASSERT(iter.depth == 3);
}
}
CX_TEST_ASSERT(iter.counter == 11);
CX_TEST_ASSERT(chk == 11);
for (unsigned i = 0 ; i < chk ; i++) {
CX_TEST_ASSERT(actual_order[i] == expected_order[i]);
CX_TEST_ASSERT(actual_order[i]->data == 1);
}
CX_TEST_ASSERT(iter.stack == NULL);
}
}
CX_TEST(test_tree_iterator_basic_enter_and_exit) {
tree_node root = {0};
tree_node a = {0};
tree_node b = {0};
tree_node c = {0};
tree_node aa = {0};
tree_node ab = {0};
tree_node ba = {0};
tree_node ca = {0};
tree_node cb = {0};
tree_node cc = {0};
tree_node cba = {0};
cx_tree_link(&root, &a, tree_node_layout);
cx_tree_link(&root, &b, tree_node_layout);
cx_tree_link(&root, &c, tree_node_layout);
cx_tree_link(&a, &aa, tree_node_layout);
cx_tree_link(&a, &ab, tree_node_layout);
cx_tree_link(&b, &ba, tree_node_layout);
cx_tree_link(&c, &ca, tree_node_layout);
cx_tree_link(&c, &cb, tree_node_layout);
cx_tree_link(&c, &cc, tree_node_layout);
cx_tree_link(&cb, &cba, tree_node_layout);
CX_TEST_DO {
CxTreeIterator iter = cx_tree_iterator(&root, true, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(iter.exiting || node->data == 0);
node->data++;
chk++;
CX_TEST_ASSERT(node == iter.node);
if (node == &root) {
CX_TEST_ASSERT(iter.depth == 1);
} else if (node == &a || node == &b || node == &c) {
CX_TEST_ASSERT(iter.depth == 2);
} else if (node == &cba) {
CX_TEST_ASSERT(iter.depth == 4);
} else {
CX_TEST_ASSERT(iter.depth == 3);
}
}
CX_TEST_ASSERT(iter.counter == 11);
CX_TEST_ASSERT(chk == 22);
CX_TEST_ASSERT(iter.stack == NULL);
CX_TEST_ASSERT(root.data == 2);
CX_TEST_ASSERT(a.data == 2);
CX_TEST_ASSERT(b.data == 2);
CX_TEST_ASSERT(c.data == 2);
CX_TEST_ASSERT(aa.data == 2);
CX_TEST_ASSERT(ab.data == 2);
CX_TEST_ASSERT(ba.data == 2);
CX_TEST_ASSERT(ca.data == 2);
CX_TEST_ASSERT(cb.data == 2);
CX_TEST_ASSERT(cc.data == 2);
CX_TEST_ASSERT(cba.data == 2);
}
}
CX_TEST(test_tree_iterator_subtree_enter_and_exit) {
tree_node root = { 0 };
tree_node a = { 0 };
tree_node b = { 0 };
tree_node c = { 0 };
tree_node aa = { 0 };
tree_node ab = { 0 };
tree_node ba = { 0 };
tree_node ca = { 0 };
tree_node cb = { 0 };
tree_node cc = { 0 };
tree_node cba = { 0 };
cx_tree_link(&root, &a, tree_node_layout);
cx_tree_link(&root, &b, tree_node_layout);
cx_tree_link(&root, &c, tree_node_layout);
cx_tree_link(&a, &aa, tree_node_layout);
cx_tree_link(&a, &ab, tree_node_layout);
cx_tree_link(&b, &ba, tree_node_layout);
cx_tree_link(&c, &ca, tree_node_layout);
cx_tree_link(&c, &cb, tree_node_layout);
cx_tree_link(&c, &cc, tree_node_layout);
cx_tree_link(&cb, &cba, tree_node_layout);
CX_TEST_DO{
CxTreeIterator iter = cx_tree_iterator(&b, true, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(iter.exiting || node->data == 0);
node->data++;
chk++;
CX_TEST_ASSERT(node == iter.node);
if (node == &b) {
CX_TEST_ASSERT(iter.depth == 1);
} else if (node == &ba) {
CX_TEST_ASSERT(iter.depth == 2);
}
}
CX_TEST_ASSERT(iter.counter == 2);
CX_TEST_ASSERT(chk == 4);
CX_TEST_ASSERT(iter.stack == NULL);
CX_TEST_ASSERT(root.data == 0);
CX_TEST_ASSERT(a.data == 0);
CX_TEST_ASSERT(b.data == 2);
CX_TEST_ASSERT(c.data == 0);
CX_TEST_ASSERT(aa.data == 0);
CX_TEST_ASSERT(ab.data == 0);
CX_TEST_ASSERT(ba.data == 2);
CX_TEST_ASSERT(ca.data == 0);
CX_TEST_ASSERT(cb.data == 0);
CX_TEST_ASSERT(cc.data == 0);
CX_TEST_ASSERT(cba.data == 0);
// now perform with other subtree
iter = cx_tree_iterator(&c, true, tree_children(tree_node));
chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(iter.exiting || node->data == 0);
node->data++;
chk++;
CX_TEST_ASSERT(node == iter.node);
if (node == &c) {
CX_TEST_ASSERT(iter.depth == 1);
} else if (node == &ca || node == &cb || node == &cc) {
CX_TEST_ASSERT(iter.depth == 2);
} else if (node == &cba) {
CX_TEST_ASSERT(iter.depth == 3);
}
}
CX_TEST_ASSERT(iter.counter == 5);
CX_TEST_ASSERT(chk == 10);
CX_TEST_ASSERT(iter.stack == NULL);
CX_TEST_ASSERT(root.data == 0);
CX_TEST_ASSERT(a.data == 0);
CX_TEST_ASSERT(b.data == 2);
CX_TEST_ASSERT(c.data == 2);
CX_TEST_ASSERT(aa.data == 0);
CX_TEST_ASSERT(ab.data == 0);
CX_TEST_ASSERT(ba.data == 2);
CX_TEST_ASSERT(ca.data == 2);
CX_TEST_ASSERT(cb.data == 2);
CX_TEST_ASSERT(cc.data == 2);
CX_TEST_ASSERT(cba.data == 2);
}
}
typedef struct test_xml_node {
struct tree_node base;
const char *name;
} test_xml_node;
CX_TEST(test_tree_iterator_xml) {
test_xml_node project = {0};
test_xml_node config = {0};
test_xml_node var1 = {0};
test_xml_node var2 = {0};
test_xml_node var3 = {0};
test_xml_node dependency1 = {0};
test_xml_node dependency1make = {0};
test_xml_node dependency2 = {0};
test_xml_node dependency2lang = {0};
test_xml_node dependency2make = {0};
test_xml_node target = {0};
test_xml_node target_feature = {0};
test_xml_node target_feature_dependencies = {0};
test_xml_node target_dependencies = {0};
project.name = "project";
config.name = "config";
var1.name = "var";
var2.name = "var";
var3.name = "var";
dependency1.name = "dependency";
dependency1make.name = "make";
dependency2.name = "dependency";
dependency2lang.name = "lang";
dependency2make.name = "make";
target.name = "target";
target_feature.name = "feature";
target_dependencies.name = "dependencies";
target_feature_dependencies.name = "dependencies";
cx_tree_link(&project, &config, tree_node_layout);
cx_tree_link(&project, &dependency1, tree_node_layout);
cx_tree_link(&project, &dependency2, tree_node_layout);
cx_tree_link(&project, &target, tree_node_layout);
cx_tree_link(&config, &var1, tree_node_layout);
cx_tree_link(&config, &var2, tree_node_layout);
cx_tree_link(&config, &var3, tree_node_layout);
cx_tree_link(&dependency1, &dependency1make, tree_node_layout);
cx_tree_link(&dependency2, &dependency2lang, tree_node_layout);
cx_tree_link(&dependency2, &dependency2make, tree_node_layout);
cx_tree_link(&target, &target_feature, tree_node_layout);
cx_tree_link(&target, &target_dependencies, tree_node_layout);
cx_tree_link(&target_feature, &target_feature_dependencies, tree_node_layout);
const char *expected =
"<project><config><var></var><var></var><var></var></config>"
"<dependency><make></make></dependency><dependency><lang></lang><make></make></dependency>"
"<target><feature><dependencies></dependencies></feature><dependencies></dependencies></target></project>";
char *actual = malloc(512);
CX_TEST_DO {
CxTreeIterator iter = cx_tree_iterator(&project, true, tree_children(tree_node));
size_t i = 0;
cx_foreach(test_xml_node*, node, iter) {
size_t len = strlen(node->name);
actual[i++] = '<';
if (iter.exiting) {
actual[i++] = '/';
}
memcpy(actual+i, node->name, len);
i += len;
actual[i++] = '>';
}
actual[i] = '\0';
CX_TEST_ASSERT(0 == strcmp(expected, actual));
}
free(actual);
}
CX_TEST(test_tree_iterator_free_nodes) {
CxTestingAllocator talloc;
cx_testing_allocator_init(&talloc);
CxAllocator *alloc = &talloc.base;
CX_TEST_DO {
tree_node *root = cxCalloc(alloc, 1, sizeof(tree_node));
tree_node *a = cxCalloc(alloc, 1, sizeof(tree_node));
tree_node *b = cxCalloc(alloc, 1, sizeof(tree_node));
tree_node *c = cxCalloc(alloc, 1, sizeof(tree_node));
tree_node *aa = cxCalloc(alloc, 1, sizeof(tree_node));
tree_node *ab = cxCalloc(alloc, 1, sizeof(tree_node));
tree_node *ba = cxCalloc(alloc, 1, sizeof(tree_node));
tree_node *ca = cxCalloc(alloc, 1, sizeof(tree_node));
tree_node *cb = cxCalloc(alloc, 1, sizeof(tree_node));
tree_node *cc = cxCalloc(alloc, 1, sizeof(tree_node));
tree_node *cba = cxCalloc(alloc, 1, sizeof(tree_node));
cx_tree_link(root, a, tree_node_layout);
cx_tree_link(root, b, tree_node_layout);
cx_tree_link(root, c, tree_node_layout);
cx_tree_link(a, aa, tree_node_layout);
cx_tree_link(a, ab, tree_node_layout);
cx_tree_link(b, ba, tree_node_layout);
cx_tree_link(c, ca, tree_node_layout);
cx_tree_link(c, cb, tree_node_layout);
cx_tree_link(c, cc, tree_node_layout);
cx_tree_link(cb, cba, tree_node_layout);
CxTreeIterator iter = cx_tree_iterator(root, true, tree_children(tree_node));
cx_foreach(tree_node *, node, iter) {
if (iter.exiting) {
cxFree(alloc,node);
}
}
CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
}
cx_testing_allocator_destroy(&talloc);
}
CX_TEST(test_tree_visitor_create_and_dispose) {
tree_node root = {0};
tree_node child = {0};
tree_node child2 = {0};
cx_tree_link(&root, &child, tree_node_layout);
cx_tree_link(&root, &child2, tree_node_layout);
CX_TEST_DO {
CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node));
CX_TEST_ASSERT(iter.counter == 1);
CX_TEST_ASSERT(iter.node == &root);
CX_TEST_ASSERT(!iter.base.allow_remove);
CX_TEST_ASSERT(!iter.base.remove);
CX_TEST_ASSERT(iter.depth == 1);
CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next));
CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children));
cxIteratorNext(iter);
CX_TEST_ASSERT(iter.queue_next != NULL);
CX_TEST_ASSERT(iter.queue_last != NULL);
CX_TEST_ASSERT(iter.queue_next->node == &child2);
CX_TEST_ASSERT(iter.queue_last->node == &child2);
cxTreeVisitorDispose(&iter);
CX_TEST_ASSERT(iter.queue_next == NULL);
CX_TEST_ASSERT(iter.queue_last == NULL);
}
}
CX_TEST(test_tree_visitor) {
tree_node root = {0};
tree_node a = {0};
tree_node b = {0};
tree_node c = {0};
tree_node aa = {0};
tree_node ab = {0};
tree_node ba = {0};
tree_node ca = {0};
tree_node cb = {0};
tree_node cc = {0};
tree_node cba = {0};
tree_node* expected_order[] = {
&root,
&a, &b, &c,
&aa, &ab, &ba, &ca, &cb, &cc,
&cba
};
tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
cx_tree_link(&root, &a, tree_node_layout);
cx_tree_link(&root, &b, tree_node_layout);
cx_tree_link(&root, &c, tree_node_layout);
cx_tree_link(&a, &aa, tree_node_layout);
cx_tree_link(&a, &ab, tree_node_layout);
cx_tree_link(&b, &ba, tree_node_layout);
cx_tree_link(&c, &ca, tree_node_layout);
cx_tree_link(&c, &cb, tree_node_layout);
cx_tree_link(&c, &cc, tree_node_layout);
cx_tree_link(&cb, &cba, tree_node_layout);
CX_TEST_DO {
CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(node->data == 0);
node->data++;
actual_order[chk] = node;
chk++;
CX_TEST_ASSERT(node == iter.node);
if (node == &root) {
CX_TEST_ASSERT(iter.depth == 1);
} else if (node == &a || node == &b || node == &c) {
CX_TEST_ASSERT(iter.depth == 2);
} else if (node == &cba) {
CX_TEST_ASSERT(iter.depth == 4);
} else {
CX_TEST_ASSERT(iter.depth == 3);
}
}
CX_TEST_ASSERT(iter.counter == 11);
CX_TEST_ASSERT(chk == 11);
for (unsigned i = 0 ; i < chk ; i++) {
CX_TEST_ASSERT(actual_order[i] == expected_order[i]);
CX_TEST_ASSERT(actual_order[i]->data == 1);
}
CX_TEST_ASSERT(iter.queue_next == NULL);
CX_TEST_ASSERT(iter.queue_last == NULL);
}
}
CX_TEST(test_tree_visitor_no_children) {
tree_node root = {0};
CX_TEST_DO {
CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(node == iter.node);
chk++;
}
CX_TEST_ASSERT(iter.counter == 1);
CX_TEST_ASSERT(chk == 1);
CX_TEST_ASSERT(iter.queue_next == NULL);
CX_TEST_ASSERT(iter.queue_last == NULL);
}
}
CX_TEST(test_tree_visitor_no_branching) {
tree_node root = {0};
tree_node a = {0};
tree_node b = {0};
tree_node c = {0};
tree_node* expected_order[] = {
&root, &a, &b, &c
};
tree_node* actual_order[4];
cx_tree_link(&root, &a, tree_node_layout);
cx_tree_link(&a, &b, tree_node_layout);
cx_tree_link(&b, &c, tree_node_layout);
CX_TEST_DO {
CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(node == iter.node);
CX_TEST_ASSERT(node->data == 0);
node->data++;
actual_order[chk] = node;
chk++;
}
CX_TEST_ASSERT(iter.counter == 4);
CX_TEST_ASSERT(chk == 4);
CX_TEST_ASSERT(iter.queue_next == NULL);
CX_TEST_ASSERT(iter.queue_last == NULL);
for (unsigned i = 0 ; i < chk ; i++) {
CX_TEST_ASSERT(actual_order[i] == expected_order[i]);
CX_TEST_ASSERT(actual_order[i]->data == 1);
}
}
}
CX_TEST(test_tree_visitor_subtree) {
tree_node root = {0};
tree_node a = {0};
tree_node b = {0};
tree_node c = {0};
tree_node ba = {0};
tree_node bb = {0};
tree_node bc = {0};
tree_node bba = {0};
tree_node* expected_order[] = {
&b, &ba, &bb, &bc, &bba
};
tree_node* actual_order[5];
cx_tree_link(&root, &a, tree_node_layout);
cx_tree_link(&root, &b, tree_node_layout);
cx_tree_link(&root, &c, tree_node_layout);
cx_tree_link(&b, &ba, tree_node_layout);
cx_tree_link(&b, &bb, tree_node_layout);
cx_tree_link(&b, &bc, tree_node_layout);
cx_tree_link(&bb, &bba, tree_node_layout);
CX_TEST_DO {
CxTreeVisitor iter = cx_tree_visitor(&b, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(node == iter.node);
CX_TEST_ASSERT(node->data == 0);
node->data++;
actual_order[chk] = node;
chk++;
}
CX_TEST_ASSERT(iter.counter == 5);
CX_TEST_ASSERT(chk == 5);
CX_TEST_ASSERT(iter.queue_next == NULL);
CX_TEST_ASSERT(iter.queue_last == NULL);
for (unsigned i = 0 ; i < chk ; i++) {
CX_TEST_ASSERT(actual_order[i] == expected_order[i]);
CX_TEST_ASSERT(actual_order[i]->data == 1);
}
}
}
CX_TEST(test_tree_visitor_continue) {
tree_node root = {0};
tree_node a = {0};
tree_node b = {0};
tree_node c = {0};
tree_node aa = {0};
tree_node ab = {0};
tree_node ba = {0};
tree_node ca = {0};
tree_node cb = {0};
tree_node cc = {0};
tree_node cba = {0};
tree_node* expected_order[] = {
&root,
&a, &b, &c,
&aa, &ab, &ba
};
tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
cx_tree_link(&root, &a, tree_node_layout);
cx_tree_link(&root, &b, tree_node_layout);
cx_tree_link(&root, &c, tree_node_layout);
cx_tree_link(&a, &aa, tree_node_layout);
cx_tree_link(&a, &ab, tree_node_layout);
cx_tree_link(&b, &ba, tree_node_layout);
cx_tree_link(&c, &ca, tree_node_layout);
cx_tree_link(&c, &cb, tree_node_layout);
cx_tree_link(&c, &cc, tree_node_layout);
cx_tree_link(&cb, &cba, tree_node_layout);
CX_TEST_DO {
CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(node->data == 0);
node->data++;
actual_order[chk] = node;
chk++;
CX_TEST_ASSERT(node == iter.node);
if (node == &root) {
CX_TEST_ASSERT(iter.depth == 1);
} else if (node == &a || node == &b || node == &c) {
CX_TEST_ASSERT(iter.depth == 2);
} else {
CX_TEST_ASSERT(iter.depth == 3);
}
if (node == &c) {
cxTreeVisitorContinue(iter);
}
}
CX_TEST_ASSERT(iter.counter == 7);
CX_TEST_ASSERT(chk == 7);
for (unsigned i = 0 ; i < chk ; i++) {
CX_TEST_ASSERT(actual_order[i] == expected_order[i]);
CX_TEST_ASSERT(actual_order[i]->data == 1);
}
CX_TEST_ASSERT(ca.data == 0);
CX_TEST_ASSERT(cb.data == 0);
CX_TEST_ASSERT(cc.data == 0);
CX_TEST_ASSERT(cba.data == 0);
CX_TEST_ASSERT(iter.queue_next == NULL);
CX_TEST_ASSERT(iter.queue_last == NULL);
}
}
CX_TEST(test_tree_iterator_continue) {
tree_node root = {0};
tree_node a = {0};
tree_node b = {0};
tree_node c = {0};
tree_node aa = {0};
tree_node ab = {0};
tree_node ba = {0};
tree_node ca = {0};
tree_node cb = {0};
tree_node cc = {0};
tree_node cba = {0};
tree_node *expected_order[] = {
&root,
&a, &aa, &ab,
&b, &ba,
&c,
};
tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
cx_tree_link(&root, &a, tree_node_layout);
cx_tree_link(&root, &b, tree_node_layout);
cx_tree_link(&root, &c, tree_node_layout);
cx_tree_link(&a, &aa, tree_node_layout);
cx_tree_link(&a, &ab, tree_node_layout);
cx_tree_link(&b, &ba, tree_node_layout);
cx_tree_link(&c, &ca, tree_node_layout);
cx_tree_link(&c, &cb, tree_node_layout);
cx_tree_link(&c, &cc, tree_node_layout);
cx_tree_link(&cb, &cba, tree_node_layout);
CX_TEST_DO {
CxTreeIterator iter = cx_tree_iterator(&root, false, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(node->data == 0);
node->data++;
actual_order[chk] = node;
chk++;
CX_TEST_ASSERT(node == iter.node);
CX_TEST_ASSERT(!iter.exiting);
if (node == &root) {
CX_TEST_ASSERT(iter.depth == 1);
} else if (node == &a || node == &b || node == &c) {
CX_TEST_ASSERT(iter.depth == 2);
} else {
CX_TEST_ASSERT(iter.depth == 3);
}
if (node == &c) {
cxTreeIteratorContinue(iter);
}
}
CX_TEST_ASSERT(iter.counter == 7);
CX_TEST_ASSERT(chk == 7);
for (unsigned i = 0 ; i < chk ; i++) {
CX_TEST_ASSERT(actual_order[i] == expected_order[i]);
CX_TEST_ASSERT(actual_order[i]->data == 1);
}
CX_TEST_ASSERT(ca.data == 0);
CX_TEST_ASSERT(cb.data == 0);
CX_TEST_ASSERT(cc.data == 0);
CX_TEST_ASSERT(cba.data == 0);
CX_TEST_ASSERT(iter.stack == NULL);
}
}
CX_TEST(test_tree_iterator_continue_with_exit) {
tree_node root = {0};
tree_node a = {0};
tree_node b = {0};
tree_node c = {0};
tree_node aa = {0};
tree_node ab = {0};
tree_node ba = {0};
tree_node ca = {0};
tree_node cb = {0};
tree_node cc = {0};
tree_node cba = {0};
cx_tree_link(&root, &a, tree_node_layout);
cx_tree_link(&root, &b, tree_node_layout);
cx_tree_link(&root, &c, tree_node_layout);
cx_tree_link(&a, &aa, tree_node_layout);
cx_tree_link(&a, &ab, tree_node_layout);
cx_tree_link(&b, &ba, tree_node_layout);
cx_tree_link(&c, &ca, tree_node_layout);
cx_tree_link(&c, &cb, tree_node_layout);
cx_tree_link(&c, &cc, tree_node_layout);
cx_tree_link(&cb, &cba, tree_node_layout);
CX_TEST_DO {
CxTreeIterator iter = cx_tree_iterator(&root, true, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(iter.exiting || node->data == 0);
node->data++;
chk++;
CX_TEST_ASSERT(node == iter.node);
if (node == &root) {
CX_TEST_ASSERT(iter.depth == 1);
} else if (node == &a || node == &b || node == &c) {
CX_TEST_ASSERT(iter.depth == 2);
} else {
CX_TEST_ASSERT(iter.depth == 3);
}
if (node == &c) {
cxTreeIteratorContinue(iter);
}
}
CX_TEST_ASSERT(iter.counter == 7);
CX_TEST_ASSERT(chk == 14);
CX_TEST_ASSERT(iter.stack == NULL);
CX_TEST_ASSERT(root.data == 2);
CX_TEST_ASSERT(a.data == 2);
CX_TEST_ASSERT(b.data == 2);
CX_TEST_ASSERT(c.data == 2);
CX_TEST_ASSERT(aa.data == 2);
CX_TEST_ASSERT(ab.data == 2);
CX_TEST_ASSERT(ba.data == 2);
CX_TEST_ASSERT(ca.data == 0);
CX_TEST_ASSERT(cb.data == 0);
CX_TEST_ASSERT(cc.data == 0);
CX_TEST_ASSERT(cba.data == 0);
}
}
CX_TEST(test_tree_add_one) {
CxTestingAllocator talloc;
cx_testing_allocator_init(&talloc);
CxAllocator *alloc = &talloc.base;
tree_node_file root = {0};
root.path = "/";
tree_node_file usr = {0};
usr.path = "/usr/";
cx_tree_link(&root, &usr, tree_node_file_layout);
tree_node_file home = {0};
home.path = "/home/";
cx_tree_link(&root, &home, tree_node_file_layout);
tree_node_file lib = {0};
lib.path = "/usr/lib/";
cx_tree_link(&usr, &lib, tree_node_file_layout);
CX_TEST_DO {
tree_node_file *foo;
int result;
result = cx_tree_add(
"/home/foo/",
tree_node_file_search,
tree_node_file_create, alloc,
(void **) &foo, &root,
tree_node_file_layout
);
CX_TEST_ASSERT(result == 0);
CX_TEST_ASSERT(foo != NULL);
const char *bar_path = "/home/foo/bar/";
void *failed;
size_t added = cx_tree_add_array(
bar_path, 1, sizeof(const char *),
tree_node_file_search,
tree_node_file_create, alloc,
&failed, &root,
tree_node_file_layout
);
CX_TEST_ASSERT(added == 1);
CX_TEST_ASSERT(failed == NULL);
tree_node_file *bar = foo->children;
CX_TEST_ASSERT(bar != NULL);
CX_TEST_ASSERT(bar->parent == foo);
CX_TEST_ASSERT(bar->path == bar_path);
CX_TEST_ASSERT(foo->parent == &home);
tree_node_file *new_node;
result = cx_tree_add(
"newroot",
tree_node_file_search,
tree_node_file_create, alloc,
(void **) &new_node, &root,
tree_node_file_layout
);
CX_TEST_ASSERT(0 != result);
CX_TEST_ASSERT(NULL != new_node);
CX_TEST_ASSERT(new_node->children == NULL);
CX_TEST_ASSERT(new_node->parent == NULL);
CX_TEST_ASSERT(talloc.alloc_total == 3);
cxFree(alloc, foo);
cxFree(alloc, bar);
cxFree(alloc, new_node);
CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
}
cx_testing_allocator_destroy(&talloc);
}
CX_TEST(test_tree_add_one_existing) {
CxTestingAllocator talloc;
cx_testing_allocator_init(&talloc);
CxAllocator *alloc = &talloc.base;
tree_node_file root = {0};
root.path = "/";
tree_node_file usr = {0};
usr.path = "/usr/";
cx_tree_link(&root, &usr, tree_node_file_layout);
tree_node_file home = {0};
home.path = "/home/";
cx_tree_link(&root, &home, tree_node_file_layout);
tree_node_file lib = {0};
lib.path = "/usr/lib/";
cx_tree_link(&usr, &lib, tree_node_file_layout);
CX_TEST_DO {
tree_node_file *node;
int result = cx_tree_add(
"/usr/lib/",
tree_node_file_search,
tree_node_file_create, alloc,
(void **) &node, &root,
tree_node_file_layout
);
CX_TEST_ASSERT(result == 0);
CX_TEST_ASSERT(node != &lib);
CX_TEST_ASSERT(node->prev == &lib);
CX_TEST_ASSERT(lib.next == node);
CX_TEST_ASSERT(node->parent == &usr);
CX_TEST_ASSERT(talloc.alloc_total == 1);
cxFree(alloc, node);
CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
}
cx_testing_allocator_destroy(&talloc);
}
CX_TEST(test_tree_add_one_no_match) {
tree_node_file root = {0};
root.path = "/mnt/";
CX_TEST_DO {
tree_node_file *node = NULL;
int result = cx_tree_add(
"/usr/lib/",
tree_node_file_search,
tree_node_file_create, NULL,
(void **) &node, &root,
tree_node_file_layout
);
CX_TEST_ASSERT(result != 0);
CX_TEST_ASSERT(node != NULL);
CX_TEST_ASSERT(node->parent == NULL);
CX_TEST_ASSERT(node->children == NULL);
cxFreeDefault(node);
node = NULL;
size_t added = cx_tree_add_array(
"/", 1, sizeof(const char *),
tree_node_file_search,
tree_node_file_create, NULL,
(void **) &node, &root,
tree_node_file_layout
);
CX_TEST_ASSERT(added == 0);
CX_TEST_ASSERT(node != NULL);
CX_TEST_ASSERT(node->parent == NULL);
CX_TEST_ASSERT(node->children == NULL);
cxFreeDefault(node);
}
}
CX_TEST(test_tree_add_duplicate_root) {
tree_node_file root = {0};
root.path = "/";
CX_TEST_DO {
tree_node_file *node;
int result = cx_tree_add(
"/",
tree_node_file_search,
tree_node_file_create, NULL,
(void **) &node, &root,
tree_node_file_layout
);
CX_TEST_ASSERT(result == 0);
CX_TEST_ASSERT(root.children == node);
CX_TEST_ASSERT(node->parent == &root);
cxFreeDefault(node);
}
}
CX_TEST(test_tree_add_zero) {
CxTestingAllocator talloc;
cx_testing_allocator_init(&talloc);
CxAllocator *alloc = &talloc.base;
tree_node_file root = {0};
root.path = "/";
CX_TEST_DO {
void *failed;
size_t processed = cx_tree_add_array(
(void *) 0xc0ffee, 0, sizeof(void *),
tree_node_file_search,
tree_node_file_create, alloc,
&failed, &root, tree_node_file_layout
);
CX_TEST_ASSERT(failed == NULL);
CX_TEST_ASSERT(processed == 0);
CX_TEST_ASSERT(talloc.alloc_total == 0);
CxIterator iter = cxIterator(NULL, sizeof(void *), 0, false);
processed = cx_tree_add_iter(
cxIteratorRef(iter),
10, // deliberately specify more than the iter has
tree_node_file_search,
tree_node_file_create, alloc,
&failed, &root, tree_node_file_layout
);
CX_TEST_ASSERT(processed == 0);
CX_TEST_ASSERT(failed == NULL);
CX_TEST_ASSERT(talloc.alloc_total == 0);
CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
}
cx_testing_allocator_destroy(&talloc);
}
CX_TEST(test_tree_add_many) {
// adds many elements to an existing tree
CxTestingAllocator talloc;
cx_testing_allocator_init(&talloc);
CxAllocator *alloc = &talloc.base;
tree_node_file root = {0};
root.path = "/";
tree_node_file usr = {0};
usr.path = "/usr/";
cx_tree_link(&root, &usr, tree_node_file_layout);
tree_node_file home = {0};
home.path = "/home/";
cx_tree_link(&root, &home, tree_node_file_layout);
tree_node_file lib = {0};
lib.path = "/usr/lib/";
cx_tree_link(&usr, &lib, tree_node_file_layout);
CX_TEST_DO {
void *failed;
const char *paths[] = {
"/home/foo/",
"/home/foo/bar",
"/usr/lib64/",
"/usr/lib/foo.so"
};
size_t processed = cx_tree_add_array(
paths, 4, sizeof(const char *),
tree_node_file_search,
tree_node_file_create, alloc,
&failed, &root, tree_node_file_layout
);
CX_TEST_ASSERT(failed == NULL);
CX_TEST_ASSERT(processed == 4);
CX_TEST_ASSERT(talloc.alloc_total == 4);
CX_TEST_ASSERT(home.children == home.last_child);
tree_node_file *foo = home.children;
CX_TEST_ASSERT(foo != NULL && foo->path == paths[0]);
CX_TEST_ASSERT(foo->children == foo->last_child);
tree_node_file *bar = foo->children;
CX_TEST_ASSERT(bar != NULL && bar->path == paths[1]);
CX_TEST_ASSERT(usr.children != usr.last_child);
tree_node_file *lib64 = usr.last_child;
CX_TEST_ASSERT(lib64 != NULL);
CX_TEST_ASSERT(lib64->path == paths[2]);
CX_TEST_ASSERT(lib64->prev == &lib);
CX_TEST_ASSERT(lib64->parent == &usr);
CX_TEST_ASSERT(lib.children != NULL);
tree_node_file *libfoo = lib.children;
CX_TEST_ASSERT(libfoo != NULL && libfoo->path == paths[3]);
cxFree(alloc, foo);
cxFree(alloc, bar);
cxFree(alloc, lib64);
cxFree(alloc, libfoo);
CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
}
cx_testing_allocator_destroy(&talloc);
}
CX_TEST(test_tree_add_many_but_not_all) {
CxTestingAllocator talloc;
cx_testing_allocator_init(&talloc);
CxAllocator *alloc = &talloc.base;
tree_node_file root = {0};
root.path = "/";
tree_node_file usr = {0};
usr.path = "/usr/";
cx_tree_link(&root, &usr, tree_node_file_layout);
tree_node_file home = {0};
home.path = "/home/";
cx_tree_link(&root, &home, tree_node_file_layout);
tree_node_file lib = {0};
lib.path = "/usr/lib/";
cx_tree_link(&usr, &lib, tree_node_file_layout);
CX_TEST_DO {
void *failed;
const char *paths[] = {
"/home/foo/",
"/home/foo/bar",
"/usr/lib64/",
"/usr/lib/foo.so"
};
// create iterator for 4 elements, but choose to insert only 3 of them
CxIterator iter = cxIterator(paths, sizeof(const char*), 4, false);
size_t processed = cx_tree_add_iter(
cxIteratorRef(iter), 3,
tree_node_file_search,
tree_node_file_create, alloc,
&failed, &root, tree_node_file_layout
);
CX_TEST_ASSERT(cxIteratorValid(iter));
CX_TEST_ASSERT(cxIteratorCurrent(iter) == &paths[3]);
CX_TEST_ASSERT(failed == NULL);
CX_TEST_ASSERT(processed == 3);
CX_TEST_ASSERT(talloc.alloc_total == 3);
CX_TEST_ASSERT(home.children == home.last_child);
tree_node_file *foo = home.children;
CX_TEST_ASSERT(foo != NULL && foo->path == paths[0]);
CX_TEST_ASSERT(foo->children == foo->last_child);
tree_node_file *bar = foo->children;
CX_TEST_ASSERT(bar != NULL && bar->path == paths[1]);
CX_TEST_ASSERT(usr.children != usr.last_child);
tree_node_file *lib64 = usr.last_child;
CX_TEST_ASSERT(lib64 != NULL);
CX_TEST_ASSERT(lib64->path == paths[2]);
CX_TEST_ASSERT(lib64->prev == &lib);
CX_TEST_ASSERT(lib64->parent == &usr);
CX_TEST_ASSERT(lib.children == NULL);
cxFree(alloc, foo);
cxFree(alloc, bar);
cxFree(alloc, lib64);
CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
}
cx_testing_allocator_destroy(&talloc);
}
CX_TEST(test_tree_add_many_with_dupl_and_no_match) {
CxTestingAllocator talloc;
cx_testing_allocator_init(&talloc);
CxAllocator *alloc = &talloc.base;
tree_node_file root = {0};
root.path = "/mnt/";
CX_TEST_DO {
tree_node_file *failed;
const char *paths[] = {
"/mnt/sdcard/",
"/mnt/foo/",
"/mnt/sdcard/",
"/home/",
"/usr/"
};
size_t processed = cx_tree_add_array(
paths, 5, sizeof(const char *),
tree_node_file_search,
tree_node_file_create, alloc,
(void **) &failed, &root, tree_node_file_layout
);
CX_TEST_ASSERT(processed == 3);
CX_TEST_ASSERT(failed != NULL);
CX_TEST_ASSERT(failed->parent == NULL);
CX_TEST_ASSERT(failed->children == NULL);
CX_TEST_ASSERT(strcmp(failed->path, "/home/") == 0);
cxFree(alloc, failed);
CX_TEST_ASSERT(root.children != root.last_child);
CX_TEST_ASSERT(strcmp(root.children->path, "/mnt/sdcard/") == 0);
CX_TEST_ASSERT(strcmp(root.last_child->path, "/mnt/sdcard/") == 0);
CX_TEST_ASSERT(strcmp(root.children->next->path, "/mnt/foo/") == 0);
CX_TEST_ASSERT(strcmp(root.last_child->prev->path, "/mnt/foo/") == 0);
CxTreeIterator iter = cx_tree_iterator(
&root, true,
offsetof(tree_node_file, children),
offsetof(tree_node_file, next)
);
cx_foreach(tree_node_file *, node, iter) {
if (iter.exiting) {
if (node != &root) {
cxFree(alloc, node);
}
}
}
CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
}
cx_testing_allocator_destroy(&talloc);
}
static CX_TEST_SUBROUTINE(test_tree_add_create_from_array_impl,
CxAllocator *alloc, const char **paths) {
tree_node_file root = {0};
root.path = "/";
void *failed;
size_t processed = cx_tree_add_array(
paths, 10, sizeof(const char *),
tree_node_file_search,
tree_node_file_create, alloc,
&failed, &root, tree_node_file_layout
);
CX_TEST_ASSERT(failed == NULL);
CX_TEST_ASSERT(processed == 10);
const char *exp_order[] = {
"/",
"/usr/",
"/usr/lib/",
"/usr/lib/libbumm.so",
"/home/",
"/home/foo/",
"/var/",
"/var/www/",
"/var/www/vhosts/",
"/var/www/vhosts/live/",
"/var/www/vhosts/live/htdocs/"
};
unsigned exp_depth[] = {
1,
2,
3,
4,
2,
3,
2,
3,
4,
5,
6
};
CxTreeIterator iter = cx_tree_iterator(
&root, true,
offsetof(tree_node_file, children),
offsetof(tree_node_file, next)
);
cx_foreach(tree_node_file *, node, iter) {
if (iter.exiting) {
if (node != &root) {
cxFree(alloc, node);
}
} else {
CX_TEST_ASSERT(iter.counter <= 11);
CX_TEST_ASSERT(iter.depth == exp_depth[iter.counter - 1]);
CX_TEST_ASSERT(strcmp(node->path, exp_order[iter.counter - 1]) == 0);
}
}
}
CX_TEST(test_tree_add_create_from_array) {
// creates an entirely new tree from an array
CxTestingAllocator talloc;
cx_testing_allocator_init(&talloc);
CxAllocator *alloc = &talloc.base;
CX_TEST_DO {
const char *paths[] = {
"/usr/",
"/home/",
"/usr/lib/",
"/usr/lib/libbumm.so",
"/var/",
"/var/www/",
"/var/www/vhosts/",
"/var/www/vhosts/live/",
"/var/www/vhosts/live/htdocs/",
"/home/foo/"
};
const char *scrambled_paths[] = {
"/usr/",
"/home/",
"/var/www/vhosts/live/",
"/usr/lib/",
"/var/",
"/var/www/",
"/usr/lib/libbumm.so",
"/var/www/vhosts/",
"/var/www/vhosts/live/htdocs/",
"/home/foo/"
};
// no matter how the original array is sorted,
// the resulting tree should be the same
CX_TEST_CALL_SUBROUTINE(test_tree_add_create_from_array_impl, alloc,
paths);
CX_TEST_CALL_SUBROUTINE(test_tree_add_create_from_array_impl, alloc,
scrambled_paths);
CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
}
cx_testing_allocator_destroy(&talloc);
}
CX_TEST(test_tree_high_create) {
CxTestingAllocator talloc;
cx_testing_allocator_init(&talloc);
CX_TEST_DO {
CxTree *tree = cxTreeCreate(
&talloc.base,
tree_node_file_create_hl,
tree_node_file_search,
tree_node_file_search_data,
tree_node_file_layout
);
CX_TEST_ASSERT(tree->cl != NULL);
CX_TEST_ASSERT(tree->collection.allocator == &talloc.base);
CX_TEST_ASSERT(tree->node_create == tree_node_file_create_hl);
CX_TEST_ASSERT(tree->search == tree_node_file_search);
CX_TEST_ASSERT(tree->search_data == tree_node_file_search_data);
CX_TEST_ASSERT(tree->collection.size == 0);
CX_TEST_ASSERT(tree->collection.simple_destructor == NULL);
CX_TEST_ASSERT(tree->collection.advanced_destructor == (cx_destructor_func2) cxFree);
CX_TEST_ASSERT(tree->collection.destructor_data == &talloc.base);
CX_TEST_ASSERT(tree->collection.store_pointer == false);
CX_TEST_ASSERT(tree->collection.sorted == false);
CX_TEST_ASSERT(tree->root == NULL);
CX_TEST_ASSERT(tree->loc_parent == offsetof(tree_node_file, parent));
CX_TEST_ASSERT(tree->loc_children == offsetof(tree_node_file, children));
CX_TEST_ASSERT(tree->loc_last_child == offsetof(tree_node_file, last_child));
CX_TEST_ASSERT(tree->loc_prev == offsetof(tree_node_file, prev));
CX_TEST_ASSERT(tree->loc_next == offsetof(tree_node_file, next));
CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));
CX_TEST_ASSERT(talloc.alloc_total == 1);
cxTreeFree(tree);
CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
}
cx_testing_allocator_destroy(&talloc);
}
CX_TEST(test_tree_high_create_simple) {
CX_TEST_DO {
CxTree *tree = cxTreeCreateSimple(
NULL, // shall fall back to the default allocator
tree_node_file_create_hl,
tree_node_file_search,
tree_node_file_search_data
);
CX_TEST_ASSERT(tree->cl != NULL);
CX_TEST_ASSERT(tree->collection.allocator == cxDefaultAllocator);
CX_TEST_ASSERT(tree->node_create == tree_node_file_create_hl);
CX_TEST_ASSERT(tree->search == tree_node_file_search);
CX_TEST_ASSERT(tree->search_data == tree_node_file_search_data);
CX_TEST_ASSERT(tree->collection.size == 0);
CX_TEST_ASSERT(tree->collection.simple_destructor == NULL);
CX_TEST_ASSERT(tree->collection.advanced_destructor == (cx_destructor_func2) cxFree);
CX_TEST_ASSERT(tree->collection.destructor_data == cxDefaultAllocator);
CX_TEST_ASSERT(tree->root == NULL);
CX_TEST_ASSERT(tree->loc_parent == offsetof(struct cx_tree_node_base_s, parent));
CX_TEST_ASSERT(tree->loc_children == offsetof(struct cx_tree_node_base_s, children));
CX_TEST_ASSERT(tree->loc_last_child == offsetof(struct cx_tree_node_base_s, last_child));
CX_TEST_ASSERT(tree->loc_prev == offsetof(struct cx_tree_node_base_s, prev));
CX_TEST_ASSERT(tree->loc_next == offsetof(struct cx_tree_node_base_s, next));
cxTreeFree(tree);
}
}
CX_TEST(test_tree_high_create_wrapped) {
tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0};
cx_tree_link(&root, &child1, tree_node_layout);
cx_tree_link(&root, &child2, tree_node_layout);
cx_tree_link(&child1, &child3, tree_node_layout);
CX_TEST_DO {
CxTree *tree = cxTreeCreateWrapped(NULL, &root, tree_node_layout);
CX_TEST_ASSERT(tree->cl != NULL);
CX_TEST_ASSERT(tree->collection.allocator == cxDefaultAllocator);
CX_TEST_ASSERT(tree->node_create == NULL);
CX_TEST_ASSERT(tree->search == NULL);
CX_TEST_ASSERT(tree->search_data == NULL);
CX_TEST_ASSERT(tree->root == &root);
CX_TEST_ASSERT(tree->collection.size == 4);
CX_TEST_ASSERT(tree->collection.simple_destructor == NULL);
CX_TEST_ASSERT(tree->collection.advanced_destructor == NULL);
CX_TEST_ASSERT(tree->collection.destructor_data == NULL);
CX_TEST_ASSERT(tree->loc_parent == offsetof(tree_node, parent));
CX_TEST_ASSERT(tree->loc_children == offsetof(tree_node, children));
CX_TEST_ASSERT(tree->loc_last_child == -1);
CX_TEST_ASSERT(tree->loc_prev == offsetof(tree_node, prev));
CX_TEST_ASSERT(tree->loc_next == offsetof(tree_node, next));
cxTreeFree(tree);
}
}
CX_TEST(test_tree_high_tree_depth) {
tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0};
cx_tree_link(&root, &child1, tree_node_layout);
cx_tree_link(&root, &child2, tree_node_layout);
cx_tree_link(&child1, &child3, tree_node_layout);
CxTree *tree = cxTreeCreateWrapped(cxDefaultAllocator, &root, tree_node_layout);
CX_TEST_DO {
CX_TEST_ASSERT(cxTreeDepth(tree) == 3);
CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &root) == 3);
CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child1) == 2);
CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child2) == 1);
CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child3) == 1);
CxTree *empty = cxTreeCreate(
cxDefaultAllocator,
tree_node_file_create_hl,
tree_node_file_search,
tree_node_file_search_data,
tree_node_file_layout
);
CX_TEST_ASSERT(cxTreeDepth(empty) == 0);
cxTreeFree(empty);
}
cxTreeFree(tree);
}
CX_TEST(test_tree_high_set_parent) {
tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0};
CxTree *tree = cxTreeCreateWrapped(cxDefaultAllocator, &root, tree_node_layout);
CX_TEST_DO {
cxTreeSetParent(tree, &root, &child1);
cxTreeSetParent(tree, &root, &child2);
cxTreeSetParent(tree, &child1, &child3);
CX_TEST_ASSERT(cxTreeDepth(tree) == 3);
CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &root) == 3);
CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child1) == 2);
CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child2) == 1);
CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child3) == 1);
cxTreeSetParent(tree, &child2, &child3);
CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &root) == 3);
CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child1) == 1);
CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child2) == 2);
CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child3) == 1);
CxTree *empty = cxTreeCreate(
cxDefaultAllocator,
tree_node_file_create_hl,
tree_node_file_search,
tree_node_file_search_data,
tree_node_file_layout
);
CX_TEST_ASSERT(cxTreeDepth(empty) == 0);
cxTreeFree(empty);
}
cxTreeFree(tree);
}
CX_TEST(test_tree_high_insert_one) {
CxTestingAllocator talloc;
cx_testing_allocator_init(&talloc);
CxAllocator *alloc = &talloc.base;
CX_TEST_DO {
CxTree *tree = cxTreeCreate(
alloc, tree_node_file_create_hl,
tree_node_file_search, tree_node_file_search_data,
tree_node_file_layout
);
int result = 0;
result |= cxTreeInsert(tree, "/");
result |= cxTreeInsert(tree, "/usr/");
result |= cxTreeInsert(tree, "/home/");
result |= cxTreeInsert(tree, "/usr/lib/");
result |= cxTreeInsert(tree, "/home/foo/");
CX_TEST_ASSERT(result == 0);
CX_TEST_ASSERT(1 == cxTreeInsertArray(tree, "/home/foo/bar/", sizeof(const char*), 1));
CX_TEST_ASSERT(cxTreeSize(tree) == 6);
CX_TEST_ASSERT(0 != cxTreeInsert(tree, "newroot"));
CX_TEST_ASSERT(cxTreeSize(tree) == 6);
CX_TEST_ASSERT(talloc.alloc_total == 8);
CX_TEST_ASSERT(talloc.free_total == 1); // the one that could not be added
cxTreeFree(tree);
CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
}
cx_testing_allocator_destroy(&talloc);
}
CX_TEST(test_tree_high_insert_many) {
CxTestingAllocator talloc;
cx_testing_allocator_init(&talloc);
CxAllocator *alloc = &talloc.base;
CX_TEST_DO {
CxTree *tree = cxTreeCreate(
alloc, tree_node_file_create_hl,
tree_node_file_search, tree_node_file_search_data,
tree_node_file_layout
);
const char *paths[] = {
"/",
"/usr/",
"/home/",
"/usr/lib/",
"/home/foo/",
"/home/foo/bar/",
"newroot"
};
CX_TEST_ASSERT(6 == cxTreeInsertArray(tree, paths, sizeof(const char*), 7));
CX_TEST_ASSERT(cxTreeSize(tree) == 6);
CX_TEST_ASSERT(talloc.alloc_total == 8);
CX_TEST_ASSERT(talloc.free_total == 1); // the one that could not be added
cxTreeFree(tree);
CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
}
cx_testing_allocator_destroy(&talloc);
}
static void test_tree_remove_node_relink_mock(
void *node,
cx_attr_unused const void *oldp,
cx_attr_unused const void *newp
) {
tree_node_file * n = node;
// this function fakes the relink logic in below test
if (strcmp(n->path, "/usr/share/") == 0) {
n->path = "/share/";
} else if (strcmp(n->path, "/usr/lib/") == 0) {
n->path = "/lib/";
}
}
CX_TEST(test_tree_high_add_find_remove_nodes) {
CxTestingAllocator talloc;
cx_testing_allocator_init(&talloc);
CxAllocator *alloc = &talloc.base;
CX_TEST_DO {
CxTree *tree = cxTreeCreate(
alloc, tree_node_file_create_hl,
tree_node_file_search, tree_node_file_search_data,
tree_node_file_layout
);
const char *paths[] = {
"/",
"/usr/",
"/home/",
"/usr/lib/",
"/home/foo/",
"/home/foo/bar/"
};
cxTreeInsertArray(tree, paths, sizeof(const char*), 6);
tree_node_file *foo = cxTreeFind(tree, "/home/foo/");
CX_TEST_ASSERT(NULL != foo);
CX_TEST_ASSERT(0 == strcmp("/home/foo/", foo->path));
CX_TEST_ASSERT(NULL != foo->parent);
CX_TEST_ASSERT(0 == strcmp("/home/", foo->parent->path));
CX_TEST_ASSERT(cxTreeSize(tree) == 6);
CX_TEST_ASSERT(0 == cxTreeAddChild(tree, foo->parent, "/home/baz/"));
tree_node_file *baz = cxTreeFind(tree, "/home/baz/");
CX_TEST_ASSERT(NULL != baz);
CX_TEST_ASSERT(0 == strcmp("/home/baz/", baz->path));
CX_TEST_ASSERT(NULL != baz->parent);
CX_TEST_ASSERT(0 == strcmp("/home/", baz->parent->path));
CX_TEST_ASSERT(cxTreeSize(tree) == 7);
tree_node_file *home = cxTreeFind(tree, "/home/");
CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/usr/", foo, 0));
tree_node_file *bar = cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 0);
CX_TEST_ASSERT(NULL != bar);
CX_TEST_ASSERT(0 == strcmp("/home/foo/bar/", bar->path));
CX_TEST_ASSERT(bar->parent == foo);
tree_node_file *share = cxCalloc(alloc, 1, sizeof(tree_node_file));
share->path = "/usr/share/";
tree_node_file *usr = cxTreeFind(tree, "/usr/");
cxTreeAddChildNode(tree, usr, share);
CX_TEST_ASSERT(cxTreeSize(tree) == 8);
cxTreeRemoveSubtree(tree, foo);
CX_TEST_ASSERT(cxTreeSize(tree) == 6);
CX_TEST_ASSERT(foo->children == bar);
CX_TEST_ASSERT(foo->last_child == bar);
CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/"));
CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/bar/"));
CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/bar/"));
CX_TEST_ASSERT(0 == cxTreeRemoveNode(tree, usr, test_tree_remove_node_relink_mock));
CX_TEST_ASSERT(cxTreeSize(tree) == 5);
CX_TEST_ASSERT(usr->parent == NULL);
CX_TEST_ASSERT(usr->children == NULL);
CX_TEST_ASSERT(usr->last_child == NULL);
CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/"));
CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/lib/"));
CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/share/"));
tree_node_file *relinked_share = cxTreeFind(tree, "/share/");
tree_node_file *relinked_lib = cxTreeFind(tree, "/lib/");
CX_TEST_ASSERT(relinked_share != NULL);
CX_TEST_ASSERT(relinked_share->parent == tree->root);
CX_TEST_ASSERT(relinked_lib != NULL);
CX_TEST_ASSERT(relinked_lib->parent == tree->root);
CX_TEST_ASSERT(NULL != cxTreeFind(tree, "/home/"));
cxTreeFree(tree);
// we are not done yet, because we need to free the removed stuff
CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));
cxFree(alloc, usr);
// for the subtree, we use a little trick and wrap it in a new tree
CxTree *foo_tree = cxTreeCreateWrapped(alloc, foo, tree_node_file_layout);
foo_tree->collection.allocator = alloc;
cxDefineAdvancedDestructor(foo_tree, cxFree, alloc);
cxTreeFree(foo_tree);
CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
}
cx_testing_allocator_destroy(&talloc);
}
CX_TEST(test_tree_high_add_find_destroy_nodes) {
CxTestingAllocator talloc;
cx_testing_allocator_init(&talloc);
CxAllocator *alloc = &talloc.base;
CX_TEST_DO {
CxTree *tree = cxTreeCreate(
alloc, tree_node_file_create_hl,
tree_node_file_search, tree_node_file_search_data,
tree_node_file_layout
);
const char *paths[] = {
"/",
"/usr/",
"/home/",
"/usr/lib/",
"/home/foo/",
"/home/foo/bar/"
};
cxTreeInsertArray(tree, paths, sizeof(const char*), 6);
tree_node_file *foo = cxTreeFind(tree, "/home/foo/");
CX_TEST_ASSERT(NULL != foo);
CX_TEST_ASSERT(0 == strcmp("/home/foo/", foo->path));
CX_TEST_ASSERT(NULL != foo->parent);
CX_TEST_ASSERT(0 == strcmp("/home/", foo->parent->path));
CX_TEST_ASSERT(cxTreeSize(tree) == 6);
CX_TEST_ASSERT(0 == cxTreeAddChild(tree, foo->parent, "/home/baz/"));
tree_node_file *baz = cxTreeFind(tree, "/home/baz/");
CX_TEST_ASSERT(NULL != baz);
CX_TEST_ASSERT(0 == strcmp("/home/baz/", baz->path));
CX_TEST_ASSERT(NULL != baz->parent);
CX_TEST_ASSERT(0 == strcmp("/home/", baz->parent->path));
CX_TEST_ASSERT(cxTreeSize(tree) == 7);
tree_node_file *home = cxTreeFind(tree, "/home/");
CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/usr/", foo, 0));
tree_node_file *bar = cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 0);
CX_TEST_ASSERT(NULL != bar);
CX_TEST_ASSERT(0 == strcmp("/home/foo/bar/", bar->path));
CX_TEST_ASSERT(bar->parent == foo);
tree_node_file *share = cxCalloc(alloc, 1, sizeof(tree_node_file));
share->path = "/usr/share/";
tree_node_file *usr = cxTreeFind(tree, "/usr/");
cxTreeAddChildNode(tree, usr, share);
CX_TEST_ASSERT(cxTreeSize(tree) == 8);
cxTreeDestroySubtree(tree, foo);
CX_TEST_ASSERT(cxTreeSize(tree) == 6);
CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/"));
CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/bar/"));
CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/bar/"));
CX_TEST_ASSERT(0 == cxTreeDestroyNode(tree, usr, test_tree_remove_node_relink_mock));
CX_TEST_ASSERT(cxTreeSize(tree) == 5);
CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/"));
CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/lib/"));
CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/share/"));
tree_node_file *relinked_share = cxTreeFind(tree, "/share/");
tree_node_file *relinked_lib = cxTreeFind(tree, "/lib/");
CX_TEST_ASSERT(relinked_share != NULL);
CX_TEST_ASSERT(relinked_share->parent == tree->root);
CX_TEST_ASSERT(relinked_lib != NULL);
CX_TEST_ASSERT(relinked_lib->parent == tree->root);
CX_TEST_ASSERT(NULL != cxTreeFind(tree, "/home/"));
cxTreeFree(tree);
// all memory should be free when using destroy instead of remove
CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
}
cx_testing_allocator_destroy(&talloc);
}
CX_TEST(test_tree_high_remove_or_destroy_root) {
CxTestingAllocator talloc;
cx_testing_allocator_init(&talloc);
CxAllocator *alloc = &talloc.base;
CX_TEST_DO {
CxTree *tree = cxTreeCreate(
alloc, tree_node_file_create_hl,
tree_node_file_search, tree_node_file_search_data,
tree_node_file_layout
);
const char *paths[] = {
"/",
"/usr/",
"/home/",
"/usr/lib/",
"/home/foo/",
"/home/foo/bar/"
};
cxTreeInsertArray(tree, paths, sizeof(const char*), 6);
void *root = tree->root;
CX_TEST_ASSERT(0 != cxTreeRemoveNode(tree, root, NULL));
CX_TEST_ASSERT(tree->root == root);
CX_TEST_ASSERT(cxTreeSize(tree) == 6);
CX_TEST_ASSERT(0 != cxTreeDestroyNode(tree, root, NULL));
CX_TEST_ASSERT(tree->root == root);
CX_TEST_ASSERT(cxTreeSize(tree) == 6);
cxTreeRemoveSubtree(tree, root);
CX_TEST_ASSERT(cxTreeSize(tree) == 0);
CX_TEST_ASSERT(tree->root == NULL);
CX_TEST_ASSERT(cxTreeDepth(tree) == 0);
cxTreeFree(tree);
CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));
CxTree *w = cxTreeCreateWrapped(alloc, root, tree_node_file_layout);
cxDefineAdvancedDestructor(w, cxFree, alloc);
cxTreeDestroySubtree(w, w->root);
CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));
cxTreeFree(w);
CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
}
cx_testing_allocator_destroy(&talloc);
}
static void test_tree_high_simple_destructor_func(void *node) {
((tree_node *)node)->data++;
}
CX_TEST(test_tree_high_simple_destructor) {
tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0};
cx_tree_link(&root, &child1, tree_node_layout);
cx_tree_link(&root, &child2, tree_node_layout);
cx_tree_link(&child1, &child3, tree_node_layout);
CX_TEST_DO {
CxTree *tree = cxTreeCreateWrapped(cxDefaultAllocator, &root, tree_node_layout);
cxDefineDestructor(tree,test_tree_high_simple_destructor_func);
cxTreeDestroyNode(tree, &child1, NULL);
cxTreeFree(tree);
CX_TEST_ASSERT(root.data == 1);
CX_TEST_ASSERT(child1.data == 1);
CX_TEST_ASSERT(child2.data == 1);
CX_TEST_ASSERT(child3.data == 1);
}
}
CX_TEST(test_tree_high_iterator) {
CxTree *tree = cxTreeCreate(
NULL, tree_node_file_create_hl,
tree_node_file_search, tree_node_file_search_data,
tree_node_file_layout
);
cxTreeInsert(tree, "/");
cxTreeInsert(tree, "/etc");
cxTreeInsert(tree, "/home");
cxTreeInsert(tree, "/home/jane");
cxTreeInsert(tree, "/usr");
cxTreeInsert(tree, "/usr/local");
cxTreeInsert(tree, "/usr/local/lib");
cxTreeInsert(tree, "/var");
cxTreeInsert(tree, "/var/lib");
CX_TEST_DO {
const char *expected_order[] = {
"/",
"/etc",
"/home",
"/home/jane",
"/usr",
"/usr/local",
"/usr/local/lib",
"/var",
"/var/lib",
};
const char *actual_order[9];
CxTreeIterator iter = cxTreeIterate(tree, false);
cx_foreach(tree_node_file*, p, iter) {
actual_order[iter.counter-1] = p->path;
}
CX_TEST_ASSERT(iter.counter == 9);
for (unsigned i = 0; i < 9; i++) {
CX_TEST_ASSERT(strcmp(expected_order[i], actual_order[i]) == 0);
}
}
cxTreeFree(tree);
}
CX_TEST(test_tree_high_visitor) {
CxTree *tree = cxTreeCreate(
NULL, tree_node_file_create_hl,
tree_node_file_search, tree_node_file_search_data,
tree_node_file_layout
);
cxTreeInsert(tree, "/");
cxTreeInsert(tree, "/etc");
cxTreeInsert(tree, "/home");
cxTreeInsert(tree, "/home/jane");
cxTreeInsert(tree, "/usr");
cxTreeInsert(tree, "/usr/local");
cxTreeInsert(tree, "/usr/local/lib");
cxTreeInsert(tree, "/var");
cxTreeInsert(tree, "/var/lib");
CX_TEST_DO {
const char *expected_order[] = {
"/",
"/etc",
"/home",
"/usr",
"/var",
"/home/jane",
"/usr/local",
"/var/lib",
"/usr/local/lib",
};
const char *actual_order[9];
CxTreeVisitor iter = cxTreeVisit(tree);
cx_foreach(tree_node_file*, p, iter) {
actual_order[iter.counter-1] = p->path;
}
CX_TEST_ASSERT(iter.counter == 9);
for (unsigned i = 0; i < 9; i++) {
CX_TEST_ASSERT(strcmp(expected_order[i], actual_order[i]) == 0);
}
}
cxTreeFree(tree);
}
CxTestSuite *cx_test_suite_tree_low_level(void) {
CxTestSuite *suite = cx_test_suite_new("tree (low level)");
cx_test_register(suite, test_tree_link_new_child);
cx_test_register(suite, test_tree_link_add_child);
cx_test_register(suite, test_tree_link_move_to_other_parent);
cx_test_register(suite, test_tree_unlink);
cx_test_register(suite, test_tree_unlink_no_prev);
cx_test_register(suite, test_tree2_link_new_child);
cx_test_register(suite, test_tree2_link_add_child);
cx_test_register(suite, test_tree2_link_move_to_other_parent);
cx_test_register(suite, test_tree2_unlink);
cx_test_register(suite, test_tree_search);
cx_test_register(suite, test_tree_search_with_max_depth);
cx_test_register(suite, test_tree_iterator_create_and_dispose);
cx_test_register(suite, test_tree_iterator_create_for_empty_tree);
cx_test_register(suite, test_tree_iterator_basic_only_enter);
cx_test_register(suite, test_tree_iterator_basic_enter_and_exit);
cx_test_register(suite, test_tree_iterator_subtree_enter_and_exit);
cx_test_register(suite, test_tree_iterator_xml);
cx_test_register(suite, test_tree_iterator_free_nodes);
cx_test_register(suite, test_tree_visitor_create_and_dispose);
cx_test_register(suite, test_tree_visitor);
cx_test_register(suite, test_tree_visitor_no_children);
cx_test_register(suite, test_tree_visitor_no_branching);
cx_test_register(suite, test_tree_visitor_subtree);
cx_test_register(suite, test_tree_visitor_continue);
cx_test_register(suite, test_tree_iterator_continue);
cx_test_register(suite, test_tree_iterator_continue_with_exit);
cx_test_register(suite, test_tree_add_one);
cx_test_register(suite, test_tree_add_one_existing);
cx_test_register(suite, test_tree_add_one_no_match);
cx_test_register(suite, test_tree_add_duplicate_root);
cx_test_register(suite, test_tree_add_zero);
cx_test_register(suite, test_tree_add_many);
cx_test_register(suite, test_tree_add_many_but_not_all);
cx_test_register(suite, test_tree_add_many_with_dupl_and_no_match);
cx_test_register(suite, test_tree_add_create_from_array);
return suite;
}
CxTestSuite *cx_test_suite_tree_high_level(void) {
CxTestSuite *suite = cx_test_suite_new("tree (high level)");
cx_test_register(suite, test_tree_high_create);
cx_test_register(suite, test_tree_high_create_simple);
cx_test_register(suite, test_tree_high_create_wrapped);
cx_test_register(suite, test_tree_high_tree_depth);
cx_test_register(suite, test_tree_high_set_parent);
cx_test_register(suite, test_tree_high_insert_one);
cx_test_register(suite, test_tree_high_insert_many);
cx_test_register(suite, test_tree_high_add_find_remove_nodes);
cx_test_register(suite, test_tree_high_add_find_destroy_nodes);
cx_test_register(suite, test_tree_high_remove_or_destroy_root);
cx_test_register(suite, test_tree_high_simple_destructor);
cx_test_register(suite, test_tree_high_iterator);
cx_test_register(suite, test_tree_high_visitor);
return suite;
}