tree.h

Go to the documentation of this file.

/*
 * 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.
 */
 
#ifndef UCX_TREE_H
#define UCX_TREE_H
 
#include "common.h"
 
#include "collection.h"
 
#ifdef __cplusplus
extern "C" {
#endif

typedef struct cx_tree_iterator_s {
    CX_ITERATOR_BASE;
    bool skip;
    bool visit_on_exit;
    bool exiting;
    ptrdiff_t loc_children;
    ptrdiff_t loc_next;
    size_t counter;
    void *node;
    void *node_next;
    void **stack;
    size_t stack_capacity;
    union {
        size_t stack_size;
        size_t depth;
    };
} CxTreeIterator;

struct cx_tree_visitor_queue_s {
    void *node;
    size_t depth;
    struct cx_tree_visitor_queue_s *next;
};

typedef struct cx_tree_visitor_s {
    CX_ITERATOR_BASE;
    bool skip;
    ptrdiff_t loc_children;
    ptrdiff_t loc_next;
    size_t counter;
    void *node;
    size_t depth;
    struct cx_tree_visitor_queue_s *queue_next;
    struct cx_tree_visitor_queue_s *queue_last;
} CxTreeVisitor;

cx_attr_nonnull
CX_EXPORT void cxTreeIteratorDispose(CxTreeIterator *iter);

cx_attr_nonnull
CX_EXPORT void cxTreeVisitorDispose(CxTreeVisitor *visitor);

#define cxTreeIteratorContinue(iterator) (iterator).skip = true; continue

#define cxTreeVisitorContinue(visitor) cxTreeIteratorContinue(visitor)

cx_attr_nonnull
CX_EXPORT void cx_tree_link(void *parent, void *node,
        ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
        ptrdiff_t loc_prev, ptrdiff_t loc_next);

cx_attr_nonnull
CX_EXPORT void cx_tree_unlink(void *node,
        ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
        ptrdiff_t loc_prev, ptrdiff_t loc_next);

#define CX_TREE_SEARCH_INFINITE_DEPTH 0

typedef int (*cx_tree_search_data_func)(const void *node, const void *data);
 

typedef int (*cx_tree_search_func)(const void *node, const void *new_node);

cx_attr_nonnull cx_attr_access_w(5)
CX_EXPORT int cx_tree_search_data(const void *root, size_t depth,
        const void *data, cx_tree_search_data_func sfunc,
        void **result, ptrdiff_t loc_children, ptrdiff_t loc_next);

cx_attr_nonnull cx_attr_access_w(5)
CX_EXPORT int cx_tree_search(const void *root, size_t depth,
        const void *node, cx_tree_search_func sfunc,
        void **result, ptrdiff_t loc_children, ptrdiff_t loc_next);

cx_attr_nodiscard
CX_EXPORT CxTreeIterator cx_tree_iterator(void *root, bool visit_on_exit,
        ptrdiff_t loc_children, ptrdiff_t loc_next);

cx_attr_nodiscard
CX_EXPORT CxTreeVisitor cx_tree_visitor(void *root,
        ptrdiff_t loc_children, ptrdiff_t loc_next);

typedef void *(*cx_tree_node_create_func)(const void *, void *);

CX_EXPORT extern unsigned int cx_tree_add_look_around_depth;

cx_attr_nonnull_arg(1, 3, 4, 6, 7) cx_attr_access_w(6)
CX_EXPORT size_t cx_tree_add_iter(struct cx_iterator_base_s *iter, size_t num,
        cx_tree_search_func sfunc, cx_tree_node_create_func cfunc,
        void *cdata, void **failed, void *root,
        ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
        ptrdiff_t loc_prev, ptrdiff_t loc_next);

cx_attr_nonnull_arg(1, 4, 5, 7, 8) cx_attr_access_w(7)
CX_EXPORT size_t cx_tree_add_array(const void *src, size_t num, size_t elem_size,
        cx_tree_search_func sfunc, cx_tree_node_create_func cfunc,
        void *cdata, void **failed, void *root,
        ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
        ptrdiff_t loc_prev, ptrdiff_t loc_next);

cx_attr_nonnull_arg(1, 2, 3, 5, 6) cx_attr_access_w(5)
CX_EXPORT int cx_tree_add(const void *src,
        cx_tree_search_func sfunc, cx_tree_node_create_func cfunc,
        void *cdata, void **cnode, void *root,
        ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
        ptrdiff_t loc_prev, ptrdiff_t loc_next);
 

typedef struct cx_tree_class_s cx_tree_class;

struct cx_tree_node_base_s {
    struct cx_tree_node_base_s *parent;
    struct cx_tree_node_base_s *children;
    struct cx_tree_node_base_s *last_child;
    struct cx_tree_node_base_s *prev;
    struct cx_tree_node_base_s *next;
};

struct cx_tree_s {
    const cx_tree_class *cl;

    const CxAllocator *allocator;

    void *root;

    cx_tree_node_create_func node_create;

    cx_destructor_func simple_destructor;

    cx_destructor_func2 advanced_destructor;

    void *destructor_data;

    cx_tree_search_func search;

    cx_tree_search_data_func search_data;

    size_t size;

    ptrdiff_t loc_parent;

    ptrdiff_t loc_children;

    ptrdiff_t loc_last_child;

    ptrdiff_t loc_prev;

    ptrdiff_t loc_next;
};

#define CX_TREE_NODE_BASE(type) \
    type *parent; \
    type *children;\
    type *last_child;\
    type *prev;\
    type *next

#define cx_tree_node_base_layout \
    offsetof(struct cx_tree_node_base_s, parent),\
    offsetof(struct cx_tree_node_base_s, children),\
    offsetof(struct cx_tree_node_base_s, last_child),\
    offsetof(struct cx_tree_node_base_s, prev),  \
    offsetof(struct cx_tree_node_base_s, next)

struct cx_tree_class_s {
    int (*insert_element)(struct cx_tree_s *tree, const void *data);

    size_t (*insert_many)(struct cx_tree_s *tree, struct cx_iterator_base_s *iter, size_t n);

    void *(*find)(struct cx_tree_s *tree, const void *subtree, const void *data, size_t depth);
};

typedef struct cx_tree_s CxTree;
 

cx_attr_nonnull
CX_EXPORT void cxTreeDestroySubtree(CxTree *tree, void *node);
 

#define cxTreeClear(tree) cxTreeDestroySubtree(tree, tree->root)

CX_EXPORT void cxTreeFree(CxTree *tree);

cx_attr_nonnull_arg(2, 3, 4) cx_attr_nodiscard  cx_attr_malloc cx_attr_dealloc(cxTreeFree, 1)
CX_EXPORT CxTree *cxTreeCreate(const CxAllocator *allocator, cx_tree_node_create_func create_func,
        cx_tree_search_func search_func, cx_tree_search_data_func search_data_func,
        ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
        ptrdiff_t loc_prev, ptrdiff_t loc_next);

#define cxTreeCreateSimple(allocator, create_func, search_func, search_data_func) \
        cxTreeCreate(allocator, create_func, search_func, search_data_func, cx_tree_node_base_layout)

cx_attr_nonnull_arg(2) cx_attr_nodiscard  cx_attr_malloc  cx_attr_dealloc(cxTreeFree, 1)
CX_EXPORT CxTree *cxTreeCreateWrapped(const CxAllocator *allocator, void *root,
        ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
        ptrdiff_t loc_prev, ptrdiff_t loc_next);

cx_attr_nonnull
CX_EXPORT int cxTreeInsert(CxTree *tree, const void *data);

cx_attr_nonnull
CX_EXPORT size_t cxTreeInsertIter(CxTree *tree, CxIteratorBase *iter, size_t n);

cx_attr_nonnull
CX_EXPORT size_t cxTreeInsertArray(CxTree *tree, const void *data, size_t elem_size, size_t n);

cx_attr_nonnull cx_attr_nodiscard
CX_EXPORT void *cxTreeFind(CxTree *tree, const void *data);

cx_attr_nonnull cx_attr_nodiscard
CX_EXPORT void *cxTreeFindInSubtree(CxTree *tree, const void *data, void *subtree_root, size_t max_depth);

cx_attr_nonnull cx_attr_nodiscard
CX_EXPORT size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);

cx_attr_nonnull  cx_attr_nodiscard
CX_EXPORT size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root);

cx_attr_nonnull cx_attr_nodiscard
CX_EXPORT size_t cxTreeSize(CxTree *tree);

cx_attr_nonnull cx_attr_nodiscard
CX_EXPORT size_t cxTreeDepth(CxTree *tree);

cx_attr_nonnull cx_attr_nodiscard
CX_EXPORT CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit);

cx_attr_nonnull cx_attr_nodiscard
CX_EXPORT CxTreeVisitor cxTreeVisitSubtree(CxTree *tree, void *node);

cx_attr_nonnull cx_attr_nodiscard
CX_EXPORT CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit);

cx_attr_nonnull cx_attr_nodiscard
CX_EXPORT CxTreeVisitor cxTreeVisit(CxTree *tree);

cx_attr_nonnull
CX_EXPORT void cxTreeSetParent(CxTree *tree, void *parent, void *child);

cx_attr_nonnull
CX_EXPORT void cxTreeAddChildNode(CxTree *tree, void *parent, void *child);

cx_attr_nonnull
CX_EXPORT int cxTreeAddChild(CxTree *tree, void *parent, const void *data);

typedef void (*cx_tree_relink_func)(
        void *node,
        const void *old_parent,
        const void *new_parent
);

cx_attr_nonnull_arg(1, 2)
CX_EXPORT int cxTreeRemoveNode(CxTree *tree, void *node, cx_tree_relink_func relink_func);

cx_attr_nonnull
CX_EXPORT void cxTreeRemoveSubtree(CxTree *tree, void *node);

cx_attr_nonnull_arg(1, 2)
CX_EXPORT int cxTreeDestroyNode(CxTree *tree, void *node, cx_tree_relink_func relink_func);
 
#ifdef __cplusplus
} // extern "C"
#endif
 
#endif //UCX_TREE_H