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
static inline void cxTreeIteratorDispose(CxTreeIterator *iter) {
    free(iter->stack);
    iter->stack = NULL;
}
 
cx_attr_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;
    }
}
 
#define cxTreeIteratorContinue(iterator) (iterator).skip = true; continue
 
#define cxTreeVisitorContinue(visitor) cxTreeIteratorContinue(visitor)
 
cx_attr_nonnull
cx_attr_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_attr_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
 
cx_attr_nonnull
typedef int (*cx_tree_search_data_func)(const void *node, const void *data);
 
 
cx_attr_nonnull
typedef int (*cx_tree_search_func)(const void *node, const void *new_node);
 
cx_attr_nonnull
cx_attr_access_w(5)
cx_attr_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_attr_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_attr_export
CxTreeIterator cx_tree_iterator(
        void *root,
        bool visit_on_exit,
        ptrdiff_t loc_children,
        ptrdiff_t loc_next
);
 
cx_attr_nodiscard
cx_attr_export
CxTreeVisitor cx_tree_visitor(
        void *root,
        ptrdiff_t loc_children,
        ptrdiff_t loc_next
);
 
cx_attr_nonnull_arg(1)
typedef void *(*cx_tree_node_create_func)(const void *, void *);
 
cx_attr_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_attr_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_attr_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_attr_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_attr_export
void cxTreeDestroySubtree(CxTree *tree, void *node);
 
 
#define cxTreeClear(tree) cxTreeDestroySubtree(tree, tree->root)
 
cx_attr_export
void cxTreeFree(CxTree *tree);
 
cx_attr_nonnull_arg(2, 3, 4)
cx_attr_nodiscard
cx_attr_malloc
cx_attr_dealloc(cxTreeFree, 1)
cx_attr_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_attr_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
static inline int cxTreeInsert(
        CxTree *tree,
        const void *data
) {
    return tree->cl->insert_element(tree, data);
}
 
cx_attr_nonnull
static inline size_t cxTreeInsertIter(
        CxTree *tree,
        CxIteratorBase *iter,
        size_t n
) {
    return tree->cl->insert_many(tree, iter, n);
}
 
cx_attr_nonnull
static inline size_t cxTreeInsertArray(
        CxTree *tree,
        const void *data,
        size_t elem_size,
        size_t n
) {
    if (n == 0) return 0;
    if (n == 1) return 0 == cxTreeInsert(tree, data) ? 1 : 0;
    CxIterator iter = cxIterator(data, elem_size, n);
    return cxTreeInsertIter(tree, cxIteratorRef(iter), n);
}
 
cx_attr_nonnull
cx_attr_nodiscard
static inline void *cxTreeFind(
        CxTree *tree,
        const void *data
) {
    return tree->cl->find(tree, tree->root, data, 0);
}
 
cx_attr_nonnull
cx_attr_nodiscard
static inline void *cxTreeFindInSubtree(
        CxTree *tree,
        const void *data,
        void *subtree_root,
        size_t max_depth
) {
    return tree->cl->find(tree, subtree_root, data, max_depth);
}
 
cx_attr_nonnull
cx_attr_nodiscard
cx_attr_export
size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);
 
cx_attr_nonnull
cx_attr_nodiscard
cx_attr_export
size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root);
 
cx_attr_nonnull
cx_attr_nodiscard
cx_attr_export
size_t cxTreeDepth(CxTree *tree);
 
cx_attr_nonnull
cx_attr_nodiscard
static inline CxTreeIterator cxTreeIterateSubtree(
        CxTree *tree,
        void *node,
        bool visit_on_exit
) {
    return cx_tree_iterator(
            node, visit_on_exit,
            tree->loc_children, tree->loc_next
    );
}
 
cx_attr_nonnull
cx_attr_nodiscard
static inline CxTreeVisitor cxTreeVisitSubtree(CxTree *tree, void *node) {
    return cx_tree_visitor(
            node, tree->loc_children, tree->loc_next
    );
}
 
cx_attr_nonnull
cx_attr_nodiscard
static inline CxTreeIterator cxTreeIterate(
        CxTree *tree,
        bool visit_on_exit
) {
    return cxTreeIterateSubtree(tree, tree->root, visit_on_exit);
}
 
cx_attr_nonnull
cx_attr_nodiscard
static inline CxTreeVisitor cxTreeVisit(CxTree *tree) {
    return cxTreeVisitSubtree(tree, tree->root);
}
 
cx_attr_nonnull
cx_attr_export
void cxTreeSetParent(
        CxTree *tree,
        void *parent,
        void *child
);
 
cx_attr_nonnull
cx_attr_export
void cxTreeAddChildNode(
        CxTree *tree,
        void *parent,
        void *child
);
 
cx_attr_nonnull
cx_attr_export
int cxTreeAddChild(
        CxTree *tree,
        void *parent,
        const void *data
);
 
cx_attr_nonnull
typedef void (*cx_tree_relink_func)(
        void *node,
        const void *old_parent,
        const void *new_parent
);
 
cx_attr_nonnull_arg(1, 2)
cx_attr_export
int cxTreeRemoveNode(
        CxTree *tree,
        void *node,
        cx_tree_relink_func relink_func
);
 
cx_attr_nonnull
cx_attr_export
void cxTreeRemoveSubtree(CxTree *tree, void *node);
 
cx_attr_nonnull_arg(1, 2)
cx_attr_export
int cxTreeDestroyNode(
        CxTree *tree,
        void *node,
        cx_tree_relink_func relink_func
);
 
#ifdef __cplusplus
} // extern "C"
#endif
 
#endif //UCX_TREE_H