src/cx/tree.h

/*
 * 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

/**
 * When entering a node.
 *
 * When this is the first sibling, source is the parent, otherwise it is the previous child.
 */
#define CX_TREE_ITERATOR_ENTER      0x1
/**
 * When advancing to the next child.
 *
 * The visited node is the next child and the source is the previous child.
 * This pass is triggered after exiting the previous child and before entering the next child.
 */
#define CX_TREE_ITERATOR_NEXT_CHILD 0x2
/**
 * When exiting the node.
 *
 * The visited node is the node being exited and source is the previously entered node
 * (usually the last child of the exited node, unless it has no children, in which case it is the node itself).
 * When advancing to the next child in a list of siblings, the previous child is exited, first.
 */
#define CX_TREE_ITERATOR_EXIT       0x4

/**
 * 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
 * iterator is based on a collection and the underlying collection is mutated by other means than this iterator
 * (e.g. elements added or removed), the iterator becomes invalid (regardless of what cxIteratorValid() returns)
 * and MUST be re-obtained from the collection.
 *
 * @see CxIterator
 */
typedef struct cx_tree_iterator_s {
    /**
     * The base properties of this iterator.
     */
    struct cx_iterator_base_s base;
    /**
     * The passes that are requested by this iterator.
     * A combination of the flags #CX_TREE_ITERATOR_ENTER, #CX_TREE_ITERATOR_NEXT_CHILD, #CX_TREE_ITERATOR_EXIT.
     *
     * Changing the value after beginning the iteration is unspecified.
     */
    uint8_t requested_passes;
    /**
     * The current pass.
     *
     * @see CX_TREE_ITERATOR_ENTER
     * @see CX_TREE_ITERATOR_NEXT_CHILD
     * @see CX_TREE_ITERATOR_EXIT
     */
    uint8_t current_pass;
    /**
     * Offset in the node struct for the children linked list.
     */
    off_t loc_children;
    /**
     * Offset in the node struct for the next pointer.
     */
    off_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 node where we came from.
     *
     * - When entering the root node, this is \c NULL.
     * - When entering another node, this is the node's parent.
     * - When advancing to the next child, this is the previous child.
     */
    void *source;
    /**
     * 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;
    /**
     * Current depth.
     */
    size_t depth;
} CxTreeIterator;

/**
 * Releases internal memory of the given tree iterator.
 * @param iter the iterator
 */
static inline void cxTreeIteratorDispose(CxTreeIterator *iter) {
    free(iter->stack);
}

/**
 * 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 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 an iterator for a tree with the specified root node.
 *
 * The \p passes argument is supposed to be a combination of the flags
 * #CX_TREE_ITERATOR_ENTER, #CX_TREE_ITERATOR_NEXT_CHILD, and #CX_TREE_ITERATOR_EXIT.
 * Alternatively, the integer 1 is equivalent to just specifying #CX_TREE_ITERATOR_ENTER
 * which will cause the iterator to pass every node only once (when entering the node).
 *
 * When #CX_TREE_ITERATOR_EXIT is set, the iterator will visit a parent node again,
 * when \em every of it's children has been visited (including the case when the node does not have any children).
 *
 * When #CX_TREE_ITERATOR_NEXT_CHILD is set, the iterator will visit a parent node again,
 * when advancing from one child to the next.
 *
 * @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 At the moment, the returned iterator does not support cxIteratorFlagRemoval().
 *
 * @param root the root node
 * @param passes the passes this iterator shall perform
 * @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,
        int passes,
        ptrdiff_t loc_children,
        ptrdiff_t loc_next
);

#ifdef __cplusplus
} // extern "C"
#endif

#endif //UCX_TREE_H