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_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 = 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)->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_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};
    cx_tree_link(&parent, &child1, tree_node_layout);
    cx_tree_link(&parent, &child3, 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 == 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 last 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 == NULL);
        CX_TEST_ASSERT(child1.parent == 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, &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, &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, &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, &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, &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, &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_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.mutating);
        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_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);
    }
}

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;
    tree_node child;
    cx_tree_link(&root, &child, 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.mutating);
        CX_TEST_ASSERT(!iter.base.remove);
        CX_TEST_ASSERT(iter.queue_next != NULL);
        CX_TEST_ASSERT(iter.queue_last != NULL);
        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));
        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_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);
        free(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);
        free(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);
    }
}

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);
        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);
        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->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->size == 0);
        CX_TEST_ASSERT(tree->simple_destructor == NULL);
        CX_TEST_ASSERT(tree->advanced_destructor == (cx_destructor_func2) cxFree);
        CX_TEST_ASSERT(tree->destructor_data == &talloc.base);
        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);

        cxTreeDestroy(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(
                cxDefaultAllocator,
                tree_node_file_create_hl,
                tree_node_file_search,
                tree_node_file_search_data
        );
        CX_TEST_ASSERT(tree->cl != NULL);
        CX_TEST_ASSERT(tree->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->size == 0);
        CX_TEST_ASSERT(tree->simple_destructor == NULL);
        CX_TEST_ASSERT(tree->advanced_destructor == (cx_destructor_func2) cxFree);
        CX_TEST_ASSERT(tree->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));
        cxTreeDestroy(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(cxDefaultAllocator, &root, tree_node_layout);
        CX_TEST_ASSERT(tree->cl != NULL);
        CX_TEST_ASSERT(tree->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->size == 4);
        CX_TEST_ASSERT(tree->simple_destructor == NULL);
        CX_TEST_ASSERT(tree->advanced_destructor == NULL);
        CX_TEST_ASSERT(tree->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));
        cxTreeDestroy(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);
        cxTreeDestroy(empty);
    }
    cxTreeDestroy(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(tree->size == 6);
        CX_TEST_ASSERT(0 != cxTreeInsert(tree, "newroot"));
        CX_TEST_ASSERT(tree->size == 6);

        CX_TEST_ASSERT(talloc.alloc_total == 8);
        CX_TEST_ASSERT(talloc.free_total == 1); // the one that could not be added

        cxTreeDestroy(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(tree->size == 6);

        CX_TEST_ASSERT(talloc.alloc_total == 8);
        CX_TEST_ASSERT(talloc.free_total == 1); // the one that could not be added

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

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(tree->size == 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(tree->size == 7);

        tree_node_file *home = cxTreeFind(tree, "/home/");
        CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/usr/", foo));
        tree_node_file *bar = cxTreeFindInSubtree(tree, "/home/foo/bar/", home);
        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/";
        cxTreeAddChildNode(tree, cxTreeFind(tree, "/usr/"), share);
        CX_TEST_ASSERT(tree->size == 8);

        cxTreeRemove(tree, foo);
        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(tree->size == 6);

        cxTreeDestroy(tree);
        // we are not done yet, because we need to free the removed subtree
        CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));

        // for this, we use a little trick and wrap the removed subtree
        CxTree *foo_tree = cxTreeCreateWrapped(alloc, foo, tree_node_file_layout);
        foo_tree->allocator = alloc;
        foo_tree->advanced_destructor = (cx_destructor_func2 ) cxFree;
        foo_tree->destructor_data = alloc;
        cxTreeDestroy(foo_tree);
        CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
    }
    cx_testing_allocator_destroy(&talloc);
}

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_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_iterator_create_and_dispose);
    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_xml);
    cx_test_register(suite, test_tree_iterator_free_nodes);
    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_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_insert_one);
    cx_test_register(suite, test_tree_high_insert_many);
    cx_test_register(suite, test_tree_high_add_find_remove_nodes);

    return suite;
}