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

The function `cxTreeCreate()` creates a `CxTree` structure
where each node created by the `create_func` has the layout specified by the offset arguments.
The function `cxTreeCreateSimple()` is exactly the same, except that it assumes the `cx_tree_node_base_layout`.

In both cases the tree will be created empty, that is with no nodes, not even a root node.
On the other hand, `cxTreeCreateWrapped()` creates a `CxTree` structure with the specified layout and `root` node
where `root` may already be the root of a larger tree.

Note, that a wrapped tree by default has no create or search functions assigned.
Therefore, if you wish to use one of the functions below that needs those function pointers set,
you will have to set them manually by assigning to the respective fields in the `CxTree` structure.

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

The function `cxTreeSubtreeSize()` counts all nodes belonging to the subtree starting with `subtree_root`.

The function `cxTreeSubtreeDepth()` reports the maximum depth of the subtree starting with `subtree_root`.
If the `subtree_root` does not have any children, this results in a depth of one.

The function `cxTreeDepth()` is equivalent to `cxTreeSubtreeDepth()` where `subtree_root` is the root node of the entire tree.

> Passing a `NULL` pointer as `subtree_root` makes those functions return zero.

> In the current UCX version there is no separate function `cxTreeSize()`, because
> the size attribute can be directly accessed in the `CxTree` structure.
> The next UCX version is planned to have also a function for accessing that attribute.
>{style="note"}

## 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 low level functions
</warning>

The function `cxTreeFind()` uses the `search_data_func` of the `CxTree`
to find the `data` in the tree, and returns a pointer to the node when the data was found (or `NULL`, otherwise).

The function `cxTreeFindInSubtree()` is equivalent, except that it restricts the search to nodes
in the subtree starting with (and including) `subtree_root`, and skipping all nodes below the `max_depth`.
Note, that the `max_depth` is specified in relation to the `subtree_root` and not in relation to the entire tree. 

## 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>