/*
* 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.
*/
/**
* \file tree.h
* \brief Interface for tree implementations.
* \author Mike Becker
* \author Olaf Wintermann
* \copyright 2-Clause BSD License
*/
#ifndef UCX_TREE_H
#define UCX_TREE_H
#include "common.h"
#include "iterator.h"
#ifdef __cplusplus
extern "C" {
#endif
/**
* A depth-first tree iterator.
*
* This iterator is not position-aware in a strict sense, as it does not assume a particular order of elements in the
* tree. However, the iterator keeps track of the number of nodes it has passed in a counter variable.
* Each node, regardless of the number of passes, is counted only once.
*
* @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the
* underlying data structure is mutated by other means than this iterator (e.g. elements added or removed),
* the iterator becomes invalid (regardless of what cxIteratorValid() returns).
*
* @see CxIterator
*/
typedef struct cx_tree_iterator_s {
/**
* Base members.
*/
CX_ITERATOR_BASE;
/**
* Indicates whether the subtree below the current node shall be skipped.
*/
bool skip;
/**
* Set to true, when the iterator shall visit a node again
* when all it's children have been processed.
*/
bool visit_on_exit;
/**
* True, if this iterator is currently leaving the node.
*/
bool exiting;
/**
* Offset in the node struct for the children linked list.
*/
ptrdiff_t loc_children;
/**
* Offset in the node struct for the next pointer.
*/
ptrdiff_t loc_next;
/**
* The total number of distinct nodes that have been passed so far.
*/
size_t counter;
/**
* The currently observed node.
*
* This is the same what cxIteratorCurrent() would return.
*/
void *node;
/**
* Stores a copy of the next pointer of the visited node.
* Allows freeing a node on exit without corrupting the iteration.
*/
void *node_next;
/**
* Internal stack.
* Will be automatically freed once the iterator becomes invalid.
*
* If you want to discard the iterator before, you need to manually
* call cxTreeIteratorDispose().
*/
void **stack;
/**
* Internal capacity of the stack.
*/
size_t stack_capacity;
union {
/**
* Internal stack size.
*/
size_t stack_size;
/**
* The current depth in the tree.
*/
size_t depth;
};
} CxTreeIterator;
/**
* An element in a visitor queue.
*/
struct cx_tree_visitor_queue_s {
/**
* The tree node to visit.
*/
void *node;
/**
* The depth of the node.
*/
size_t depth;
/**
* The next element in the queue or \c NULL.
*/
struct cx_tree_visitor_queue_s *next;
};
/**
* A breadth-first tree iterator.
*
* This iterator needs to maintain a visitor queue that will be automatically freed once the iterator becomes invalid.
* If you want to discard the iterator before, you MUST manually call cxTreeVisitorDispose().
*
* This iterator is not position-aware in a strict sense, as it does not assume a particular order of elements in the
* tree. However, the iterator keeps track of the number of nodes it has passed in a counter variable.
* Each node, regardless of the number of passes, is counted only once.
*
* @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the
* underlying data structure is mutated by other means than this iterator (e.g. elements added or removed),
* the iterator becomes invalid (regardless of what cxIteratorValid() returns).
*
* @see CxIterator
*/
typedef struct cx_tree_visitor_s {
/**
* Base members.
*/
CX_ITERATOR_BASE;
/**
* Indicates whether the subtree below the current node shall be skipped.
*/
bool skip;
/**
* Offset in the node struct for the children linked list.
*/
ptrdiff_t loc_children;
/**
* Offset in the node struct for the next pointer.
*/
ptrdiff_t loc_next;
/**
* The total number of distinct nodes that have been passed so far.
*/
size_t counter;
/**
* The currently observed node.
*
* This is the same what cxIteratorCurrent() would return.
*/
void *node;
/**
* The current depth in the tree.
*/
size_t depth;
/**
* The next element in the visitor queue.
*/
struct cx_tree_visitor_queue_s *queue_next;
/**
* The last element in the visitor queue.
*/
struct cx_tree_visitor_queue_s *queue_last;
} CxTreeVisitor;
/**
* Releases internal memory of the given tree iterator.
* @param iter the iterator
*/
__attribute__((__nonnull__))
static inline void cxTreeIteratorDispose(CxTreeIterator *iter) {
free(iter->stack);
iter->stack = NULL;
}
/**
* Releases internal memory of the given tree visitor.
* @param visitor the visitor
*/
__attribute__((__nonnull__))
static inline void cxTreeVisitorDispose(CxTreeVisitor *visitor) {
struct cx_tree_visitor_queue_s *q = visitor->queue_next;
while (q != NULL) {
struct cx_tree_visitor_queue_s *next = q->next;
free(q);
q = next;
}
}
/**
* Advises the iterator to skip the subtree below the current node and
* also continues the current loop.
*
* @param iterator the iterator
*/
#define cxTreeIteratorContinue(iterator) (iterator).skip = true; continue
/**
* Advises the visitor to skip the subtree below the current node and
* also continues the current loop.
*
* @param visitor the visitor
*/
#define cxTreeVisitorContinue(visitor) cxTreeIteratorContinue(visitor)
/**
* Links a node to a (new) parent.
*
* If the node has already a parent, it is unlinked, first.
* If the parent has children already, the node is \em prepended to the list
* of all currently existing children.
*
* @param parent the parent node
* @param node the node that shall be linked
* @param loc_parent offset in the node struct for the parent pointer
* @param loc_children offset in the node struct for the children linked list
* @param loc_prev offset in the node struct for the prev pointer
* @param loc_next offset in the node struct for the next pointer
* @see cx_tree_unlink()
*/
__attribute__((__nonnull__))
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
);
/**
* Unlinks a node from its parent.
*
* If the node has no parent, this function does nothing.
*
* @param node the node that shall be unlinked from its parent
* @param loc_parent offset in the node struct for the parent pointer
* @param loc_children offset in the node struct for the children linked list
* @param loc_prev offset in the node struct for the prev pointer
* @param loc_next offset in the node struct for the next pointer
* @see cx_tree_link()
*/
__attribute__((__nonnull__))
void cx_tree_unlink(
void *node,
ptrdiff_t loc_parent,
ptrdiff_t loc_children,
ptrdiff_t loc_prev,
ptrdiff_t loc_next
);
/**
* Function pointer for a search function.
*
* A function of this kind shall check if the specified \p node
* contains the given \p data or if one of the children might contain
* the data.
*
* The function should use the returned integer to indicate how close the
* match is, where a negative number means that it does not match at all.
*
* For example if a tree stores file path information, a node that is
* describing a parent directory of a filename that is searched, shall
* return a positive number to indicate that a child node might contain the
* searched item. On the other hand, if the node denotes a path that is not a
* prefix of the searched filename, the function would return -1 to indicate
* that * the search does not need to be continued in that branch.
*
* @param node the node that is currently investigated
* @param data the data that is searched for
*
* @return 0 if the node contains the data,
* positive if one of the children might contain the data,
* negative if neither the node, nor the children contains the data
*/
typedef int (*cx_tree_search_func)(void const *node, void const* data);
/**
* Searches for data in a tree.
*
* When the data cannot be found exactly, the search function might return a
* closest result which might be a good starting point for adding a new node
* to the tree.
*
* Depending on the tree structure it is not necessarily guaranteed that the
* "closest" match is uniquely defined. This function will search for a node
* with the best match according to the \p sfunc (meaning: the return value of
* \p sfunc which is closest to zero). If that is also ambiguous, an arbitrary
* node matching the criteria is returned.
*
* @param root the root node
* @param data the data to search for
* @param sfunc the search function
* @param result where the result shall be stored
* @param loc_children offset in the node struct for the children linked list
* @param loc_next offset in the node struct for the next pointer
* @return zero if the node was found exactly, positive if a node was found that
* could contain the node (but doesn't right now), negative if the tree does not
* contain any node that might be related to the searched data
*/
__attribute__((__nonnull__))
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
);
/**
* Creates a depth-first iterator for a tree with the specified root node.
*
* @note A tree iterator needs to maintain a stack of visited nodes, which is allocated using stdlib malloc().
* When the iterator becomes invalid, this memory is automatically released. However, if you wish to cancel the
* iteration before the iterator becomes invalid by itself, you MUST call cxTreeIteratorDispose() manually to release
* the memory.
*
* @remark The returned iterator does not support cxIteratorFlagRemoval().
*
* @param root the root node
* @param visit_on_exit set to true, when the iterator shall visit a node again after processing all children
* @param loc_children offset in the node struct for the children linked list
* @param loc_next offset in the node struct for the next pointer
* @return the new tree iterator
* @see cxTreeIteratorDispose()
*/
__attribute__((__nonnull__))
CxTreeIterator cx_tree_iterator(
void *root,
bool visit_on_exit,
ptrdiff_t loc_children,
ptrdiff_t loc_next
);
/**
* Creates a breadth-first iterator for a tree with the specified root node.
*
* @note A tree visitor needs to maintain a queue of to be visited nodes, which is allocated using stdlib malloc().
* When the visitor becomes invalid, this memory is automatically released. However, if you wish to cancel the
* iteration before the visitor becomes invalid by itself, you MUST call cxTreeVisitorDispose() manually to release
* the memory.
*
* @remark The returned iterator does not support cxIteratorFlagRemoval().
*
* @param root the root node
* @param loc_children offset in the node struct for the children linked list
* @param loc_next offset in the node struct for the next pointer
* @return the new tree visitor
* @see cxTreeVisitorDispose()
*/
__attribute__((__nonnull__))
CxTreeVisitor cx_tree_visitor(
void *root,
ptrdiff_t loc_children,
ptrdiff_t loc_next
);
#ifdef __cplusplus
} // extern "C"
#endif
#endif //UCX_TREE_H