/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
*
* Copyright 2024 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/array_list.h"
#include <assert.h>
#define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
#define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
#define tree_parent(node) CX_TREE_PTR(node, loc_parent)
#define tree_children(node) CX_TREE_PTR(node, loc_children)
#define tree_prev(node) CX_TREE_PTR(node, loc_prev)
#define tree_next(node) CX_TREE_PTR(node, loc_next)
void cx_tree_link(
void *restrict parent,
void *restrict node,
ptrdiff_t loc_parent,
ptrdiff_t loc_children,
ptrdiff_t loc_prev,
ptrdiff_t loc_next
) {
void *current_parent = tree_parent(node);
if (current_parent == parent) return;
if (current_parent != NULL) {
cx_tree_unlink(node, loc_parent, loc_children,
loc_prev, loc_next);
}
if (tree_children(parent) == NULL) {
tree_children(parent) = node;
} else {
void *children = tree_children(parent);
tree_prev(children) = node;
tree_next(node) = children;
tree_children(parent) = node;
}
tree_parent(node) = parent;
}
void cx_tree_unlink(
void *node,
ptrdiff_t loc_parent,
ptrdiff_t loc_children,
ptrdiff_t loc_prev,
ptrdiff_t loc_next
) {
if (tree_parent(node) == NULL) return;
void *left = tree_prev(node);
void *right = tree_next(node);
assert(left == NULL || tree_children(tree_parent(node)) != node);
if (left == NULL) {
tree_children(tree_parent(node)) = right;
} else {
tree_next(left) = right;
}
if (right != NULL) tree_prev(right) = left;
tree_parent(node) = NULL;
tree_prev(node) = NULL;
tree_next(node) = NULL;
}
int cx_tree_search(
void const *root,
void const *data,
cx_tree_search_func sfunc,
void **result,
ptrdiff_t loc_children,
ptrdiff_t loc_next
) {
int ret;
*result = NULL;
// shortcut: compare root before doing anything else
ret = sfunc(root, data);
if (ret < 0) {
return ret;
} else if (ret == 0 || tree_children(root) == NULL) {
*result = (void*)root;
return ret;
}
// create a working stack
CX_ARRAY_DECLARE(void const*, work);
cx_array_initialize(work, 32);
// add the children of root to the working stack
{
void *c = tree_children(root);
while (c != NULL) {
cx_array_simple_add(work, c);
c = tree_next(c);
}
}
// remember a candidate for adding the data
// also remember the exact return code from sfunc
void *candidate = NULL;
int ret_candidate = -1;
// process the working stack
while (work_size > 0) {
// pop element
void const *node = work[--work_size];
// apply the search function
ret = sfunc(node, data);
if (ret == 0) {
// if found, exit the search
*result = (void*) node;
work_size = 0;
break;
} else if (ret > 0) {
// if children might contain the data, add them to the stack
void *c = tree_children(node);
while (c != NULL) {
cx_array_simple_add(work, c);
c = tree_next(c);
}
// remember this node in case no child is suitable
if (ret_candidate < 0 || ret < ret_candidate) {
candidate = (void *) node;
ret_candidate = ret;
}
}
}
// not found, but was there a candidate?
if (ret != 0 && candidate != NULL) {
ret = ret_candidate;
*result = candidate;
}
// free the working queue and return
free(work);
return ret;
}
static bool cx_tree_iter_valid(void const *it) {
struct cx_tree_iterator_s const *iter = it;
return iter->node != NULL;
}
static void *cx_tree_iter_current(void const *it) {
struct cx_tree_iterator_s const *iter = it;
return iter->node;
}
static void cx_tree_iter_next(void *it) {
struct cx_tree_iterator_s *iter = it;
ptrdiff_t const loc_next = iter->loc_next;
ptrdiff_t const loc_children = iter->loc_children;
void *children;
// check if we are currently exiting or entering nodes
if (iter->exiting) {
children = NULL;
// skipping on exit is pointless, just clear the flag
iter->skip = false;
} else {
if (iter->skip) {
// skip flag is set, pretend that there are no children
iter->skip = false;
children = NULL;
} else {
// try to enter the children (if any)
children = tree_children(iter->node);
}
}
if (children == NULL) {
// search for the next node
void *next;
cx_tree_iter_search_next:
// check if there is a sibling
if (iter->exiting) {
next = iter->node_next;
} else {
next = tree_next(iter->node);
iter->node_next = next;
}
if (next == NULL) {
// no sibling, we are done with this node and exit
if (iter->visit_on_exit && !iter->exiting) {
// iter is supposed to visit the node again
iter->exiting = true;
} else {
iter->exiting = false;
if (iter->depth == 1) {
// there is no parent - we have iterated the entire tree
// invalidate the iterator and free the node stack
iter->node = iter->node_next = NULL;
iter->stack_capacity = iter->depth = 0;
free(iter->stack);
iter->stack = NULL;
} else {
// the parent node can be obtained from the top of stack
// this way we can avoid the loc_parent in the iterator
iter->depth--;
iter->node = iter->stack[iter->depth - 1];
// retry with the parent node to find a sibling
goto cx_tree_iter_search_next;
}
}
} else {
if (iter->visit_on_exit && !iter->exiting) {
// iter is supposed to visit the node again
iter->exiting = true;
} else {
iter->exiting = false;
// move to the sibling
iter->counter++;
iter->node = next;
// new top of stack is the sibling
iter->stack[iter->depth - 1] = next;
}
}
} else {
// node has children, push the first child onto the stack and enter it
cx_array_simple_add(iter->stack, children);
iter->node = children;
iter->counter++;
}
}
CxTreeIterator cx_tree_iterator(
void *root,
bool visit_on_exit,
ptrdiff_t loc_children,
ptrdiff_t loc_next
) {
CxTreeIterator iter;
iter.loc_children = loc_children;
iter.loc_next = loc_next;
iter.visit_on_exit = visit_on_exit;
// allocate stack
iter.stack_capacity = 16;
iter.stack = malloc(sizeof(void *) * 16);
iter.depth = 0;
// visit the root node
iter.node = root;
iter.node_next = NULL;
iter.counter = 1;
iter.depth = 1;
iter.stack[0] = root;
iter.exiting = false;
iter.skip = false;
// assign base iterator functions
iter.base.mutating = false;
iter.base.remove = false;
iter.base.current_impl = NULL;
iter.base.valid = cx_tree_iter_valid;
iter.base.next = cx_tree_iter_next;
iter.base.current = cx_tree_iter_current;
return iter;
}
static bool cx_tree_visitor_valid(void const *it) {
struct cx_tree_visitor_s const *iter = it;
return iter->node != NULL;
}
static void *cx_tree_visitor_current(void const *it) {
struct cx_tree_visitor_s const *iter = it;
return iter->node;
}
__attribute__((__nonnull__))
static void cx_tree_visitor_enqueue_siblings(
struct cx_tree_visitor_s *iter, void *node, ptrdiff_t loc_next) {
node = tree_next(node);
while (node != NULL) {
struct cx_tree_visitor_queue_s *q;
q = malloc(sizeof(struct cx_tree_visitor_queue_s));
q->depth = iter->queue_last->depth;
q->node = node;
iter->queue_last->next = q;
iter->queue_last = q;
node = tree_next(node);
}
iter->queue_last->next = NULL;
}
static void cx_tree_visitor_next(void *it) {
struct cx_tree_visitor_s *iter = it;
ptrdiff_t const loc_next = iter->loc_next;
ptrdiff_t const loc_children = iter->loc_children;
// add the children of the current node to the queue
// unless the skip flag is set
void *children;
if (iter->skip) {
iter->skip = false;
children = NULL;
} else {
children = tree_children(iter->node);
}
if (children != NULL) {
struct cx_tree_visitor_queue_s *q;
q = malloc(sizeof(struct cx_tree_visitor_queue_s));
q->depth = iter->depth + 1;
q->node = children;
if (iter->queue_last == NULL) {
assert(iter->queue_next == NULL);
iter->queue_next = q;
} else {
iter->queue_last->next = q;
}
iter->queue_last = q;
cx_tree_visitor_enqueue_siblings(iter, children, loc_next);
}
// check if there is a next node
if (iter->queue_next == NULL) {
iter->node = NULL;
return;
}
// dequeue the next node
iter->node = iter->queue_next->node;
iter->depth = iter->queue_next->depth;
{
struct cx_tree_visitor_queue_s *q = iter->queue_next;
iter->queue_next = q->next;
if (iter->queue_next == NULL) {
assert(iter->queue_last == q);
iter->queue_last = NULL;
}
free(q);
}
// increment the node counter
iter->counter++;
}
CxTreeVisitor cx_tree_visitor(
void *root,
ptrdiff_t loc_children,
ptrdiff_t loc_next
) {
CxTreeVisitor iter;
iter.loc_children = loc_children;
iter.loc_next = loc_next;
// allocate stack
iter.depth = 0;
// visit the root node
iter.node = root;
iter.counter = 1;
iter.depth = 1;
iter.skip = false;
iter.queue_next = NULL;
iter.queue_last = NULL;
// assign base iterator functions
iter.base.mutating = false;
iter.base.remove = false;
iter.base.current_impl = NULL;
iter.base.valid = cx_tree_visitor_valid;
iter.base.next = cx_tree_visitor_next;
iter.base.current = cx_tree_visitor_current;
return iter;
}