v4.0/tests/test_tree.c

/*
 * 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(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 int tree_node_file_search_func(const void *l, const void *d) {
    const tree_node_file *left = l;
    const char *right = d;
    size_t len1 = strlen(left->path);
    size_t len2 = strlen(right);
    if (len1 <= len2) {
        if (memcmp(left->path, right, len1) == 0) {
            return (int) (len2 - len1);
        } else {
            return -1;
        }
    } else {
        return -1;
    }
}

#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_children(type) offsetof(type, children), offsetof(type, next)

CX_TEST(test_tree_add) {
    tree_node parent = {0};
    tree_node child1 = {0};
    tree_node child2 = {0};
    tree_node child3 = {0};

    CX_TEST_DO {
        cx_tree_add(&parent, &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 == &child1);
        CX_TEST_ASSERT(child1.parent == &parent);
        CX_TEST_ASSERT(child1.next == NULL);
        CX_TEST_ASSERT(child1.prev == NULL);
        CX_TEST_ASSERT(child1.children == NULL);

        cx_tree_add(&parent, &child2, tree_node_layout);
        cx_tree_add(&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_add_move_to_other_parent) {
    tree_node parent = {0};
    tree_node child1 = {0};
    tree_node child2 = {0};
    tree_node child3 = {0};
    cx_tree_add(&parent, &child1, tree_node_layout);
    cx_tree_add(&parent, &child2, tree_node_layout);
    cx_tree_add(&parent, &child3, tree_node_layout);

    CX_TEST_DO {
        cx_tree_add(&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_remove) {
    tree_node parent = {0};
    tree_node child1 = {0};
    tree_node child2 = {0};
    tree_node child3 = {0};
    tree_node child4 = {0};
    cx_tree_add(&parent, &child1, tree_node_layout);
    cx_tree_add(&parent, &child3, tree_node_layout);
    cx_tree_add(&parent, &child4, tree_node_layout);
    cx_tree_add(&child3, &child2, tree_node_layout);

    CX_TEST_DO {
        cx_tree_remove(&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_remove(&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_remove_no_prev) {
    tree_node parent = {0};
    tree_node child1 = {0};
    tree_node child2 = {0};
    tree_node child3 = {0};
    tree_node child4 = {0};
    cx_tree_add(&parent, &child1, tree_node_layout_no_prev);
    cx_tree_add(&parent, &child3, tree_node_layout_no_prev);
    cx_tree_add(&parent, &child4, tree_node_layout_no_prev);
    cx_tree_add(&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_remove(&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_remove(&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_add(&parent, &child, cx_tree_node_layout(tree_node2));
        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_add(&parent, &child1, cx_tree_node_layout(tree_node2));
        cx_tree_add(&parent, &child2, cx_tree_node_layout(tree_node2));
        cx_tree_add(&parent, &child3, cx_tree_node_layout(tree_node2));
        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_add(&parent, &child1, cx_tree_node_layout(tree_node2));
    cx_tree_add(&parent, &child2, cx_tree_node_layout(tree_node2));
    cx_tree_add(&parent, &child3, cx_tree_node_layout(tree_node2));

    CX_TEST_DO {
        cx_tree_add(&child3, &child2, cx_tree_node_layout(tree_node2));

        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_add(&parent, &child1, cx_tree_node_layout(tree_node2));
    cx_tree_add(&parent, &child3, cx_tree_node_layout(tree_node2));
    cx_tree_add(&child3, &child2, cx_tree_node_layout(tree_node2));

    CX_TEST_DO {
        cx_tree_remove(&child3, cx_tree_node_layout(tree_node2));

        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_remove(&child1, cx_tree_node_layout(tree_node2));
        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_add(&root, &a, tree_node_layout);
    cx_tree_add(&root, &b, tree_node_layout);
    cx_tree_add(&root, &c, tree_node_layout);

    cx_tree_add(&a, &aa, tree_node_layout);
    cx_tree_add(&a, &ab, tree_node_layout);

    cx_tree_add(&b, &ba, tree_node_layout);

    cx_tree_add(&c, &ca, tree_node_layout);
    cx_tree_add(&c, &cb, tree_node_layout);
    cx_tree_add(&c, &cc, tree_node_layout);

    cx_tree_add(&cb, &cba, tree_node_layout);

    int s;
    int r;
    tree_node *n;
    CX_TEST_DO {
        // special case: search an empty tree
        n = (void*)0x1337;
        r = cx_tree_search(NULL, 0, &s, test_tree_search_function,
                               (void **) &n, tree_children(tree_node));
        CX_TEST_ASSERT(r < 0);
        CX_TEST_ASSERT(n == NULL);

        // search for the test data (exact matches)
        for (unsigned i = 0 ; i <= 10 ; i++) {
            s = testdata[i];
            r = cx_tree_search(&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(&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(&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(&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(&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(&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_add(&root, &usr, cx_tree_node_layout(tree_node_file));
    tree_node_file home = {0};
    home.path = "/home/";
    cx_tree_add(&root, &home, cx_tree_node_layout(tree_node_file));
    tree_node_file doe = {0};
    doe.path = "/home/doe/";
    cx_tree_add(&home, &doe, cx_tree_node_layout(tree_node_file));
    tree_node_file lib = {0};
    lib.path = "/usr/lib/";
    cx_tree_add(&usr, &lib, cx_tree_node_layout(tree_node_file));
    tree_node_file modules = {0};
    modules.path = "/usr/lib/modules/";
    cx_tree_add(&lib, &modules, cx_tree_node_layout(tree_node_file));

    CX_TEST_DO {
        int result;
        void *found;

        result = cx_tree_search(
                &root, 1, "/",
                tree_node_file_search_func, &found,
                tree_children(tree_node_file)
        );
        CX_TEST_ASSERTM(result == 0, "root not found");
        CX_TEST_ASSERT(found == &root);

        result = cx_tree_search(
                &root, 1, "/usr/",
                tree_node_file_search_func, &found,
                tree_children(tree_node_file)
        );
        CX_TEST_ASSERT(result > 0);
        CX_TEST_ASSERT(found == &root);

        result = cx_tree_search(
                &root, 2, "/usr/",
                tree_node_file_search_func, &found,
                tree_children(tree_node_file)
        );
        CX_TEST_ASSERT(result == 0);
        CX_TEST_ASSERT(found == &usr);

        result = cx_tree_search(
                &root, 2, "/usr/lib/",
                tree_node_file_search_func, &found,
                tree_children(tree_node_file)
        );
        CX_TEST_ASSERT(result > 0);
        CX_TEST_ASSERT(found == &usr);

        result = cx_tree_search(
                &root, 3, "/usr/lib/",
                tree_node_file_search_func, &found,
                tree_children(tree_node_file)
        );
        CX_TEST_ASSERTM(result == 0, "lib not found");
        CX_TEST_ASSERT(found == &lib);

        result = cx_tree_search(
                &root, 1, "/home/",
                tree_node_file_search_func, &found,
                tree_children(tree_node_file)
        );
        CX_TEST_ASSERT(result > 0);
        CX_TEST_ASSERT(found == &root);

        result = cx_tree_search(
                &root, 2, "/home/",
                tree_node_file_search_func, &found,
                tree_children(tree_node_file)
        );
        CX_TEST_ASSERTM(result == 0, "home not found");
        CX_TEST_ASSERT(found == &home);

        result = cx_tree_search(
                &root, 2, "/home/doe/",
                tree_node_file_search_func, &found,
                tree_children(tree_node_file)
        );
        CX_TEST_ASSERT(result > 0);
        CX_TEST_ASSERT(found == &home);

        result = cx_tree_search(
                &root, 3, "/home/doe/",
                tree_node_file_search_func, &found,
                tree_children(tree_node_file)
        );
        CX_TEST_ASSERTM(result == 0, "doe not found");
        CX_TEST_ASSERT(found == &doe);

        result = cx_tree_search(
                &root, 3, "/usr/lib/modules/",
                tree_node_file_search_func, &found,
                tree_children(tree_node_file)
        );
        CX_TEST_ASSERT(result > 0);
        CX_TEST_ASSERT(found == &lib);

        result = cx_tree_search(
                &root, 4, "/usr/lib/modules/",
                tree_node_file_search_func, &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(
                &usr, 3, "/usr/lib/modules/",
                tree_node_file_search_func, &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.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.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_add(&root, &a, tree_node_layout);
    cx_tree_add(&root, &b, tree_node_layout);
    cx_tree_add(&root, &c, tree_node_layout);
    cx_tree_add(&a, &aa, tree_node_layout);
    cx_tree_add(&a, &ab, tree_node_layout);
    cx_tree_add(&b, &ba, tree_node_layout);
    cx_tree_add(&c, &ca, tree_node_layout);
    cx_tree_add(&c, &cb, tree_node_layout);
    cx_tree_add(&c, &cc, tree_node_layout);
    cx_tree_add(&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_add(&root, &a, tree_node_layout);
    cx_tree_add(&root, &b, tree_node_layout);
    cx_tree_add(&root, &c, tree_node_layout);
    cx_tree_add(&a, &aa, tree_node_layout);
    cx_tree_add(&a, &ab, tree_node_layout);
    cx_tree_add(&b, &ba, tree_node_layout);
    cx_tree_add(&c, &ca, tree_node_layout);
    cx_tree_add(&c, &cb, tree_node_layout);
    cx_tree_add(&c, &cc, tree_node_layout);
    cx_tree_add(&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_add(&root, &a, tree_node_layout);
    cx_tree_add(&root, &b, tree_node_layout);
    cx_tree_add(&root, &c, tree_node_layout);
    cx_tree_add(&a, &aa, tree_node_layout);
    cx_tree_add(&a, &ab, tree_node_layout);
    cx_tree_add(&b, &ba, tree_node_layout);
    cx_tree_add(&c, &ca, tree_node_layout);
    cx_tree_add(&c, &cb, tree_node_layout);
    cx_tree_add(&c, &cc, tree_node_layout);
    cx_tree_add(&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_add(&project, &config, tree_node_layout);
    cx_tree_add(&project, &dependency1, tree_node_layout);
    cx_tree_add(&project, &dependency2, tree_node_layout);
    cx_tree_add(&project, &target, tree_node_layout);
    cx_tree_add(&config, &var1, tree_node_layout);
    cx_tree_add(&config, &var2, tree_node_layout);
    cx_tree_add(&config, &var3, tree_node_layout);
    cx_tree_add(&dependency1, &dependency1make, tree_node_layout);
    cx_tree_add(&dependency2, &dependency2lang, tree_node_layout);
    cx_tree_add(&dependency2, &dependency2make, tree_node_layout);
    cx_tree_add(&target, &target_feature, tree_node_layout);
    cx_tree_add(&target, &target_dependencies, tree_node_layout);
    cx_tree_add(&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_add(root, a, tree_node_layout);
        cx_tree_add(root, b, tree_node_layout);
        cx_tree_add(root, c, tree_node_layout);
        cx_tree_add(a, aa, tree_node_layout);
        cx_tree_add(a, ab, tree_node_layout);
        cx_tree_add(b, ba, tree_node_layout);
        cx_tree_add(c, ca, tree_node_layout);
        cx_tree_add(c, cb, tree_node_layout);
        cx_tree_add(c, cc, tree_node_layout);
        cx_tree_add(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_add(&root, &child, tree_node_layout);
    cx_tree_add(&root, &child2, tree_node_layout);
    CX_TEST_DO {
        CxTreeIterator 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);
        cxTreeIteratorDispose(&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_add(&root, &a, tree_node_layout);
    cx_tree_add(&root, &b, tree_node_layout);
    cx_tree_add(&root, &c, tree_node_layout);
    cx_tree_add(&a, &aa, tree_node_layout);
    cx_tree_add(&a, &ab, tree_node_layout);
    cx_tree_add(&b, &ba, tree_node_layout);
    cx_tree_add(&c, &ca, tree_node_layout);
    cx_tree_add(&c, &cb, tree_node_layout);
    cx_tree_add(&c, &cc, tree_node_layout);
    cx_tree_add(&cb, &cba, tree_node_layout);
    CX_TEST_DO {
        CxTreeIterator 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_create_for_empty_tree) {
    CX_TEST_DO {
        CxTreeIterator iter = cx_tree_visitor(NULL, 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.queue_next == NULL);
        CX_TEST_ASSERT(iter.queue_last == 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_visitor_no_children) {
    tree_node root = {0};

    CX_TEST_DO {
        CxTreeIterator 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_add(&root, &a, tree_node_layout);
    cx_tree_add(&a, &b, tree_node_layout);
    cx_tree_add(&b, &c, tree_node_layout);

    CX_TEST_DO {
        CxTreeIterator 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_add(&root, &a, tree_node_layout);
    cx_tree_add(&root, &b, tree_node_layout);
    cx_tree_add(&root, &c, tree_node_layout);
    cx_tree_add(&b, &ba, tree_node_layout);
    cx_tree_add(&b, &bb, tree_node_layout);
    cx_tree_add(&b, &bc, tree_node_layout);
    cx_tree_add(&bb, &bba, tree_node_layout);

    CX_TEST_DO {
        CxTreeIterator 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_add(&root, &a, tree_node_layout);
    cx_tree_add(&root, &b, tree_node_layout);
    cx_tree_add(&root, &c, tree_node_layout);
    cx_tree_add(&a, &aa, tree_node_layout);
    cx_tree_add(&a, &ab, tree_node_layout);
    cx_tree_add(&b, &ba, tree_node_layout);
    cx_tree_add(&c, &ca, tree_node_layout);
    cx_tree_add(&c, &cb, tree_node_layout);
    cx_tree_add(&c, &cc, tree_node_layout);
    cx_tree_add(&cb, &cba, tree_node_layout);
    CX_TEST_DO {
        CxTreeIterator 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) {
                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.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_add(&root, &a, tree_node_layout);
    cx_tree_add(&root, &b, tree_node_layout);
    cx_tree_add(&root, &c, tree_node_layout);
    cx_tree_add(&a, &aa, tree_node_layout);
    cx_tree_add(&a, &ab, tree_node_layout);
    cx_tree_add(&b, &ba, tree_node_layout);
    cx_tree_add(&c, &ca, tree_node_layout);
    cx_tree_add(&c, &cb, tree_node_layout);
    cx_tree_add(&c, &cc, tree_node_layout);
    cx_tree_add(&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_add(&root, &a, tree_node_layout);
    cx_tree_add(&root, &b, tree_node_layout);
    cx_tree_add(&root, &c, tree_node_layout);
    cx_tree_add(&a, &aa, tree_node_layout);
    cx_tree_add(&a, &ab, tree_node_layout);
    cx_tree_add(&b, &ba, tree_node_layout);
    cx_tree_add(&c, &ca, tree_node_layout);
    cx_tree_add(&c, &cb, tree_node_layout);
    cx_tree_add(&c, &cc, tree_node_layout);
    cx_tree_add(&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_high_create) {
    CxTestingAllocator talloc;
    cx_testing_allocator_init(&talloc);
    CX_TEST_DO {
        CxTree *tree = cxTreeCreate(
                &talloc.base,
                sizeof(tree_node_file),
                CX_STORE_POINTERS,
                NULL, offsetof(tree_node_file, path),
                cx_tree_node_layout(tree_node_file)
        );
        CX_TEST_ASSERT(tree->collection.allocator == &talloc.base);
        CX_TEST_ASSERT(tree->node_size == sizeof(tree_node_file));
        CX_TEST_ASSERT(tree->collection.elem_size == sizeof(void*));
        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 == true);
        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(tree->loc_data == offsetof(tree_node_file, path));

        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_root) {
    CxTestingAllocator talloc;
    cx_testing_allocator_init(&talloc);
    CX_TEST_DO {
        CxTree *tree = cxTreeCreate(
                &talloc.base,
                sizeof(tree_node_file),
                CX_STORE_POINTERS,
                NULL, -1,
                cx_tree_node_layout(tree_node_file)
        );

        CX_TEST_ASSERT(tree->root == NULL);
        // create root without data
        tree_node_file *root = cxTreeCreateRoot(tree);
        CX_TEST_ASSERT(root != NULL);
        CX_TEST_ASSERT(root == tree->root);
        // re-create same root (does nothing)
        tree_node_file *root2 = cxTreeCreateRoot(tree);
        CX_TEST_ASSERT(root2 == root);

        // next test
        cxTreeClear(tree);

        // try to create with data, but loc_data is not known
        root = cxTreeCreateRootData(tree, "/");
        CX_TEST_ASSERT(root == NULL);

        // set the loc_data
        tree->loc_data = offsetof(tree_node_file, path);
        root = cxTreeCreateRootData(tree, "/");
        CX_TEST_ASSERT(root != NULL);
        CX_TEST_ASSERT(strcmp(root->path, "/") == 0);

        cxTreeFree(tree);
        CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
    }
}

CX_TEST(test_tree_high_set_root) {
    CxTestingAllocator talloc;
    cx_testing_allocator_init(&talloc);
    CX_TEST_DO {
        CxTree *tree = cxTreeCreate(
                &talloc.base,
                sizeof(tree_node_file),
                CX_STORE_POINTERS,
                NULL, -1,
                cx_tree_node_layout(tree_node_file)
        );

        CX_TEST_ASSERT(tree->root == NULL);

        tree_node_file *root = cxTreeCreateRoot(tree);
        CX_TEST_ASSERT(root != NULL);
        CX_TEST_ASSERT(root == tree->root);

        // create a different root externally
        tree_node_file *root2 = cxZalloc(&talloc.base, sizeof(tree_node_file));

        // replace the root
        tree_node_file *old = cxTreeSetRoot(tree, root2);
        CX_TEST_ASSERT(old == root);

        // free the tree, check that there is memory leaking
        cxTreeFree(tree);
        CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));

        // free the old root, check that memory is fine
        cxFree(&talloc.base, old);
        CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
    }
}

CX_TEST(test_tree_high_tree_depth) {
    tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0};
    cx_tree_add(&root, &child1, tree_node_layout);
    cx_tree_add(&root, &child2, tree_node_layout);
    cx_tree_add(&child1, &child3, tree_node_layout);
    CxTree *tree = cxTreeCreate(cxDefaultAllocator, sizeof(tree_node),
        sizeof(int), &root, offsetof(tree_node, data), 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, sizeof(tree_node),
            sizeof(int), NULL, offsetof(tree_node, data), tree_node_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 = cxTreeCreate(cxDefaultAllocator, sizeof(tree_node),
        sizeof(int), &root, offsetof(tree_node, data), 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, sizeof(tree_node),
            sizeof(int), NULL, offsetof(tree_node, data), tree_node_layout);
        CX_TEST_ASSERT(cxTreeDepth(empty) == 0);
        cxTreeFree(empty);
    }
    cxTreeFree(tree);
}

static void test_tree_remove_node_relink_mock(
        void *node,
        CX_UNUSED const void *oldp,
        CX_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/";
    }
}

static CX_TEST_SUBROUTINE(validate_tree_high_add_find_remove_nodes,
            CxAllocator *alloc, bool use_dfs) {
    CxTree *tree = cxTreeCreate(alloc,
        sizeof(tree_node_file),
        CX_STORE_POINTERS,
        NULL, offsetof(tree_node_file, path),
        cx_tree_node_layout(tree_node_file)
    );
    cxSetCompareFunc(tree, strcmp);

    {
        tree_node_file *root = cxTreeCreateRootData(tree, "/");
        tree_node_file *home = cxTreeAddData(tree, root, "/home/");
        tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/");
        cxTreeAddData(tree, foo, "/home/foo/bar/");
        tree_node_file *usr = cxTreeAddData(tree, root, "/usr/");
        cxTreeAddData(tree, usr, "/usr/lib/");
    }

    tree_node_file *foo = cxTreeFind(tree, "/home/foo/", use_dfs);
    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(NULL != cxTreeAddData(tree, foo->parent, "/home/baz/"));
    tree_node_file *baz = cxTreeFind(tree, "/home/baz/", use_dfs);
    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/", use_dfs);
    CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/usr/", foo, 0, use_dfs));
    tree_node_file *bar = cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 0, use_dfs);
    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/", use_dfs);
    cxTreeAddNode(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/", use_dfs));
    CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/bar/", use_dfs));
    CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/bar/", use_dfs));

    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/", use_dfs));
    CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/lib/", use_dfs));
    CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/share/", use_dfs));
    tree_node_file *relinked_share = cxTreeFind(tree, "/share/", use_dfs);
    tree_node_file *relinked_lib = cxTreeFind(tree, "/lib/", use_dfs);
    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/", use_dfs));
    cxTreeFree(tree);

    // we are not done yet, because we need to free the removed stuff
    cxFree(alloc, usr);
    // for the subtree, we use a little trick and wrap it in a new tree
    CxTree *foo_tree = cxTreeCreate(alloc,
            sizeof(tree_node_file),
            CX_STORE_POINTERS,
            foo, offsetof(tree_node_file, path),
            cx_tree_node_layout(tree_node_file)
    );
    cxSetAdvancedDestructor(foo_tree, cxFree, alloc);
    cxTreeFree(foo_tree);
}

CX_TEST(test_tree_high_add_find_remove_nodes) {
    CxTestingAllocator talloc;
    cx_testing_allocator_init(&talloc);
    CxAllocator *alloc = &talloc.base;

    CX_TEST_DO {
        CX_TEST_CALL_SUBROUTINE(validate_tree_high_add_find_remove_nodes, alloc, true);
        CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
        CX_TEST_CALL_SUBROUTINE(validate_tree_high_add_find_remove_nodes, alloc, false);
        CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
    }
    cx_testing_allocator_destroy(&talloc);
}

static CX_TEST_SUBROUTINE(validate_tree_high_add_find_destroy_nodes,
        CxAllocator *alloc, bool use_dfs) {
    CxTree *tree = cxTreeCreate(alloc,
        sizeof(tree_node_file),
        CX_STORE_POINTERS,
        NULL, offsetof(tree_node_file, path),
        cx_tree_node_layout(tree_node_file)
    );
    cxSetCompareFunc(tree, strcmp);

    {
        tree_node_file *root = cxTreeCreateRootData(tree, "/");
        tree_node_file *home = cxTreeAddData(tree, root, "/home/");
        tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/");
        cxTreeAddData(tree, foo, "/home/foo/bar/");
        tree_node_file *usr = cxTreeAddData(tree, root, "/usr/");
        cxTreeAddData(tree, usr, "/usr/lib/");
    }

    tree_node_file *foo = cxTreeFind(tree, "/home/foo/", use_dfs);
    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(NULL != cxTreeAddData(tree, foo->parent, "/home/baz/"));
    tree_node_file *baz = cxTreeFind(tree, "/home/baz/", use_dfs);
    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/", use_dfs);
    CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/usr/", foo, 0, use_dfs));
    tree_node_file *bar = cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 0, use_dfs);
    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/", use_dfs);
    cxTreeAddNode(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/", use_dfs));
    CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/bar/", use_dfs));
    CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/bar/", use_dfs));

    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/", use_dfs));
    CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/lib/", use_dfs));
    CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/share/", use_dfs));
    tree_node_file *relinked_share = cxTreeFind(tree, "/share/", use_dfs);
    tree_node_file *relinked_lib = cxTreeFind(tree, "/lib/", use_dfs);
    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/", use_dfs));

    cxTreeFree(tree);
}

CX_TEST(test_tree_high_add_find_destroy_nodes) {
    CxTestingAllocator talloc;
    cx_testing_allocator_init(&talloc);
    CxAllocator *alloc = &talloc.base;

    CX_TEST_DO {
        CX_TEST_CALL_SUBROUTINE(validate_tree_high_add_find_destroy_nodes, alloc, true);
        CX_TEST_CALL_SUBROUTINE(validate_tree_high_add_find_destroy_nodes, alloc, false);
        CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
    }
    cx_testing_allocator_destroy(&talloc);
}

CX_TEST(test_tree_high_add_find_without_loc_data) {
    CxTestingAllocator talloc;
    cx_testing_allocator_init(&talloc);
    CxAllocator *alloc = &talloc.base;
    CX_TEST_DO {
        CxTree *tree = cxTreeCreate(alloc,
            sizeof(tree_node_file),
            CX_STORE_POINTERS,
            NULL, offsetof(tree_node_file, path),
            cx_tree_node_layout(tree_node_file)
        );
        cxSetCompareFunc(tree, strcmp);
        tree_node_file *root = cxTreeCreateRootData(tree, "/");
        tree_node_file *home = cxTreeAddData(tree, root, "/home/");
        tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/");
        cxTreeAddData(tree, foo, "/home/foo/bar/");
        tree_node_file *usr = cxTreeAddData(tree, root, "/usr/");
        cxTreeAddData(tree, usr, "/usr/lib/");

        void *found = cxTreeFind(tree, "/home/foo/", true);
        CX_TEST_ASSERT(found == foo);

        // now remove the loc_data
        tree->loc_data = -1;
        found = cxTreeFind(tree, "/home/foo/", true);
        CX_TEST_ASSERT(found == NULL);

        CX_TEST_ASSERT(NULL == cxTreeAddData(tree, root, "/usr/local/"));

        cxTreeFree(tree);
        CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
    }
    cx_testing_allocator_destroy(&talloc);
}

CX_TEST(test_tree_high_find_max_depth) {
    CxTree *tree = cxTreeCreate(NULL,
        sizeof(tree_node_file),
        CX_STORE_POINTERS,
        NULL, offsetof(tree_node_file, path),
        cx_tree_node_layout(tree_node_file)
    );
    cxSetCompareFunc(tree, strcmp);
    tree_node_file *root = cxTreeCreateRootData(tree, "/");
    tree_node_file *home = cxTreeAddData(tree, root, "/home/");
    tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/");
    tree_node_file *bar = cxTreeAddData(tree, foo, "/home/foo/bar/");
    tree_node_file *usr = cxTreeAddData(tree, root, "/usr/");
    cxTreeAddData(tree, usr, "/usr/lib/");
    CX_TEST_DO {
        CX_TEST_ASSERT(bar == cxTreeFindInSubtree(tree, "/home/foo/bar/", tree->root, 4, true));
        CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/home/foo/bar/", tree->root, 3, true));
        CX_TEST_ASSERT(bar == cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 3, true));
        CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 2, true));
    }
    cxTreeFree(tree);
}

CX_TEST(test_tree_high_find_fast) {
    CxTree *tree = cxTreeCreate(NULL,
        sizeof(tree_node_file),
        CX_STORE_POINTERS,
        NULL, offsetof(tree_node_file, path),
        cx_tree_node_layout(tree_node_file)
    );
    cxSetCompareFunc(tree, strcmp);
    tree_node_file *root = cxTreeCreateRootData(tree, "/");
    tree_node_file *home = cxTreeAddData(tree, root, "/home/");
    tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/");
    tree_node_file *bar = cxTreeAddData(tree, foo, "/home/foo/bar/");
    tree_node_file *baz = cxTreeAddData(tree, home, "/home/baz/");
    tree_node_file *usr = cxTreeAddData(tree, root, "/usr/");
    tree_node_file *lib = cxTreeAddData(tree, usr, "/usr/lib/");
    CX_TEST_DO {
        // test that loc_data not needed for FindFast!
        tree->loc_data = -1;

        // find from root
        CX_TEST_ASSERT(root == cxTreeFindFast(tree, "/",
            tree_node_file_search_func));
        CX_TEST_ASSERT(home == cxTreeFindFast(tree, "/home/",
            tree_node_file_search_func));
        CX_TEST_ASSERT(foo == cxTreeFindFast(tree, "/home/foo/",
            tree_node_file_search_func));
        CX_TEST_ASSERT(bar == cxTreeFindFast(tree, "/home/foo/bar/",
            tree_node_file_search_func));
        CX_TEST_ASSERT(usr == cxTreeFindFast(tree, "/usr/",
            tree_node_file_search_func));
        CX_TEST_ASSERT(lib == cxTreeFindFast(tree, "/usr/lib/",
            tree_node_file_search_func));

        // find from correct subtree
        CX_TEST_ASSERT(foo == cxTreeFindFastInSubtree(tree, "/home/foo/",
            tree_node_file_search_func, home, 0));
        CX_TEST_ASSERT(bar == cxTreeFindFastInSubtree(tree, "/home/foo/bar/",
            tree_node_file_search_func, home, 0));
        CX_TEST_ASSERT(lib == cxTreeFindFastInSubtree(tree, "/usr/lib/",
            tree_node_file_search_func, usr, 0));

        // find in wrong subtree
        CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/home/foo/",
            tree_node_file_search_func, usr, 0));
        CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/home/foo/bar/",
            tree_node_file_search_func, baz, 0));
        CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/usr/lib/",
            tree_node_file_search_func, home, 0));

        // some tests with max depth
        // -------------------------
        CX_TEST_ASSERT(bar == cxTreeFindFastInSubtree(tree, "/home/foo/bar/", tree_node_file_search_func, tree->root, 4));
        CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/home/foo/bar/", tree_node_file_search_func, tree->root, 3));
        CX_TEST_ASSERT(bar == cxTreeFindFastInSubtree(tree, "/home/foo/bar/", tree_node_file_search_func, home, 3));
        CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/home/foo/bar/", tree_node_file_search_func, home, 2));
    }
    cxTreeFree(tree);
}

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,
                sizeof(tree_node_file),
                CX_STORE_POINTERS,
                NULL, offsetof(tree_node_file, path),
                cx_tree_node_layout(tree_node_file)
        );

        {
            tree_node_file *root = cxTreeCreateRootData(tree, "/");
            tree_node_file *home = cxTreeAddData(tree, root, "/home/");
            tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/");
            cxTreeAddData(tree, foo, "/home/foo/bar/");
            tree_node_file *usr = cxTreeAddData(tree, root, "/usr/");
            cxTreeAddData(tree, usr, "/usr/lib/");
        }
        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 = cxTreeCreate(alloc,
                sizeof(tree_node_file),
                CX_STORE_POINTERS,
                root, offsetof(tree_node_file, path),
                cx_tree_node_layout(tree_node_file)
        );
        cxSetAdvancedDestructor(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_add(&root, &child1, tree_node_layout);
    cx_tree_add(&root, &child2, tree_node_layout);
    cx_tree_add(&child1, &child3, tree_node_layout);
    CX_TEST_DO {
        CxTree *tree = cxTreeCreate(cxDefaultAllocator, sizeof(tree_node),
            sizeof(int), &root, offsetof(tree_node, data), tree_node_layout);
        cxSetDestructor(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,
            sizeof(tree_node_file),
            CX_STORE_POINTERS,
            NULL, offsetof(tree_node_file, path),
            cx_tree_node_layout(tree_node_file)
    );
    {
        tree_node_file *root = cxTreeCreateRootData(tree, "/");
        cxTreeAddData(tree, root, "/etc");
        tree_node_file *home = cxTreeAddData(tree, root, "/home");
        cxTreeAddData(tree, home, "/home/jane");
        tree_node_file *usr = cxTreeAddData(tree, root, "/usr");
        cxTreeAddData(tree, usr, "/usr/local");
        cxTreeAddData(tree, usr, "/usr/local/lib");
        tree_node_file *var = cxTreeAddData(tree, root, "/var");
        cxTreeAddData(tree, var, "/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_iterator_large_depth) {
    CxTree *tree = cxTreeCreate(NULL,
            sizeof(tree_node),
            sizeof(int),
            NULL, offsetof(tree_node, data),
            tree_node_layout
    );
    int c = 0;
    tree_node *root = cxTreeCreateRootData(tree, &c);
    unsigned depths[6] = {10, 20, 15, 30, 25, 5};
    for (unsigned b = 0 ; b < 3 ; b++) {
        c++;
        tree_node *branch = cxTreeAddData(tree, root, &c);
        tree_node *p = branch;
        for (unsigned d = 0; d < depths[b*2+0] ; d++) {
            c++;
            p = cxTreeAddData(tree, p, &c);
        }
        p = branch;
        for (unsigned d = 0; d < depths[b*2+1] ; d++) {
            c++;
            p = cxTreeAddData(tree, p, &c);
        }
    }
    CX_TEST_DO {
        CX_TEST_ASSERT(cxTreeSize(tree) == 109);
        CX_TEST_ASSERT(cxTreeSubtreeSize(tree, root) == 109);
        CX_TEST_ASSERT(cxTreeSubtreeSize(tree, root->children) == 1+depths[0]+depths[1]);
        CX_TEST_ASSERT(cxTreeSubtreeSize(tree, root->children->next) == 1+depths[2]+depths[3]);
        CX_TEST_ASSERT(cxTreeSubtreeSize(tree, root->children->next->next) == 1+depths[4]+depths[5]);
        CxTreeIterator iter = cxTreeIterate(tree, false);
        cx_foreach(tree_node*, n, iter) {
            CX_TEST_ASSERT((size_t)n->data == iter.counter - 1);
        }
    }
    cxTreeFree(tree);
}

CX_TEST(test_tree_high_visitor) {
    CxTree *tree = cxTreeCreate(NULL,
            sizeof(tree_node_file),
            CX_STORE_POINTERS,
            NULL, offsetof(tree_node_file, path),
            cx_tree_node_layout(tree_node_file)
    );
    {
        tree_node_file *root = cxTreeCreateRootData(tree, "/");
        cxTreeAddData(tree, root, "/etc");
        tree_node_file *home = cxTreeAddData(tree, root, "/home");
        cxTreeAddData(tree, home, "/home/jane");
        tree_node_file *usr = cxTreeAddData(tree, root, "/usr");
        tree_node_file *usr_local = cxTreeAddData(tree, usr, "/usr/local");
        cxTreeAddData(tree, usr_local, "/usr/local/lib");
        tree_node_file *var = cxTreeAddData(tree, root, "/var");
        cxTreeAddData(tree, var, "/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];
        CxTreeIterator 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_add);
    cx_test_register(suite, test_tree_add_move_to_other_parent);
    cx_test_register(suite, test_tree_remove);
    cx_test_register(suite, test_tree_remove_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_create_for_empty_tree);
    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);

    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_root);
    cx_test_register(suite, test_tree_high_set_root);
    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_add_find_remove_nodes);
    cx_test_register(suite, test_tree_high_add_find_destroy_nodes);
    cx_test_register(suite, test_tree_high_add_find_without_loc_data);
    cx_test_register(suite, test_tree_high_find_max_depth);
    cx_test_register(suite, test_tree_high_find_fast);
    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_iterator_large_depth);
    cx_test_register(suite, test_tree_high_visitor);

    return suite;
}