Mercurial > hg > ucx / file revision

# Tree

UCX provides several low-level function for working with arbitrary tree structures,
as well as some high-level functions for trees that induce a certain order on the data they store. 

The following convenience macros allow you to declare and use simple tree structures.

```C
#define CX_TREE_NODE_BASE(Type)

#define cx_tree_node_base_layout
```

The `CX_TREE_NODE_BASE` macro declares four pointers of type `Type*`:
`parent`, `children`, `last_child`, `prev`, and `next`,
which must be placed as first member into your struct.

You can use it for example like this:
```C
typedef struct my_tree_node_s {
    CX_TREE_NODE_BASE(struct my_tree_node_s);
    int value;
    char *desc;
} MyTreeNode;
```

The macro `cx_tree_node_base_layout` expands to the offsets of the above-mentioned pointers.
It will become handy when calling the low-level tree functions which expect all offsets to be passed as arguments. 

Before diving into the function definitions, there are four function pointer declarations you should know.

```C
#include <cx/tree.h>

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

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);

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

A `cx_tree_node_create_func` takes a pointer to the `data` the new node shall contain, and a `context` (which might be an allocator, for example).
It shall allocate and return the created node, or `NULL` when node creation is not possible.

A `cx_tree_search_data_func` shall check if the `node` contains the `data`, or if a child node might contain the data.
It shall return zero, when `node` contains the `data`.
When a child node _might_ contain the data, the returned positive number shall indicate how close the match is.
It is _not_ relevant if the data can actually be found in the subtree - the positive number also indicates that the data could be inserted in that subtree.
Only when the entire subtree starting with `node` cannot contain the `data`, a negative number is supposed to be returned.

A `cx_tree_search_func` behaves exactly the same, except that it does expect a pointer to the `data` but a pointer to a node structure.
In combination with the `cx_tree_node_create_func`, when inserting nodes with the high-level functions, a `new_node` is created first,
and then an appropriate insertion point is searched with the `cx_tree_search_func`.

A `cx_tree_relink_func` is used when an intermediate node is removed from the tree and it's children need to be detached from
the removed `old_parent` and attached to a `new_parent`.

## Create

```C
#include <cx/tree.h>

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);

CxTree *cxTreeCreateSimple(const CxAllocator *allocator,
        cx_tree_node_create_func create_func,
        cx_tree_search_func search_func,
        cx_tree_search_data_func search_data_func);

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);
```

<warning>
TODO: document
</warning>

## Add Nodes

```C
#include <cx/tree.h>

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);

extern unsigned int cx_tree_add_look_around_depth;

size_t cx_tree_add_iter(struct cx_iterator_base_s *iter, size_t n,
        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);
        
size_t cx_tree_add_array(const void *src, size_t n, 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);
        
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);


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

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

void cxTreeSetParent(CxTree *tree, void *parent, void *child);
        
int cxTreeInsert(CxTree *tree, const void *data);

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

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

<warning>
TODO: document
</warning>

## Size and Depth

```C
#include <cx/tree.h>

size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);

size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root);

size_t cxTreeDepth(CxTree *tree);
```

<warning>
TODO: document
</warning>

## Search

```C
#include <cx/tree.h>

#define CX_TREE_SEARCH_INFINITE_DEPTH

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);

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);
        
void *cxTreeFind(CxTree *tree, const void *data);

void *cxTreeFindInSubtree(CxTree *tree, const void *data,
        void *subtree_root, size_t max_depth);
```

<warning>
TODO: document
</warning>

## Iterator and Visitor

```C
#include <cx/tree.h>

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

CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit);

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

#define cxTreeIteratorContinue(iter)

void cxTreeIteratorDispose(CxTreeIterator *iter);


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

CxTreeVisitor cxTreeVisit(CxTree *tree);

CxTreeVisitor cxTreeVisitSubtree(CxTree *tree, void *node)

#define cxTreeVisitorContinue(visitor)

void cxTreeVisitorDispose(CxTreeVisitor *visitor);
```

<warning>
TODO: document
</warning>

## Remove

```C
#include <cx/tree.h>

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);

int cxTreeRemoveNode(CxTree *tree, void *node,
        cx_tree_relink_func relink_func);

void cxTreeRemoveSubtree(CxTree *tree, void *node);
```

<warning>
TODO: document
</warning>

## Dispose

```C
#include <cx/tree.h>

int cxTreeDestroyNode(CxTree *tree, void *node,
        cx_tree_relink_func relink_func);

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

void cxTreeClear(CxTree *tree);

void cxTreeFree(CxTree *tree);
```

<warning>
TODO: document and mention the destructor support
</warning>

<seealso>
<category ref="apidoc">
<a href="https://ucx.sourceforge.io/api/tree_8h.html">tree.h</a>
</category>
</seealso>