Interface for tree implementations. More...

#include "common.h"
#include "collection.h"

Data Structures
struct	cx_tree_iterator_s
	A depth-first tree iterator. More...

struct	cx_tree_visitor_queue_s
	An element in a visitor queue. More...

struct	cx_tree_visitor_s
	A breadth-first tree iterator. More...

struct	cx_tree_node_base_s
	Base structure that can be used for tree nodes in a CxTree. More...

struct	cx_tree_s
	Structure for holding the base data of a tree. More...

struct	cx_tree_class_s
	The class definition for arbitrary trees. More...

Macros
#define	cxTreeIteratorContinue(iterator) (iterator).skip = true; continue
	Advises the iterator to skip the subtree below the current node and also continues the current loop.

#define	cxTreeVisitorContinue(visitor) cxTreeIteratorContinue(visitor)
	Advises the visitor to skip the subtree below the current node and also continues the current loop.

#define	CX_TREE_SEARCH_INFINITE_DEPTH 0
	Macro that can be used instead of the magic value for infinite search depth.

#define	CX_TREE_NODE_BASE(type)
	Macro to roll out the cx_tree_node_base_s structure with a custom node type.

#define	cx_tree_node_base_layout
	Macro for specifying the layout of a base node tree.

#define	cxTreeClear(tree) cxTreeDestroySubtree(tree, tree->root)
	Destroys the tree contents.

#define	cxTreeCreateSimple(allocator, create_func, search_func, search_data_func)
	Creates a new tree structure based on a default layout.

Typedefs
typedef struct cx_tree_iterator_s	CxTreeIterator
	A depth-first tree iterator.

typedef struct cx_tree_visitor_s	CxTreeVisitor
	A breadth-first tree iterator.

typedef int(*	cx_tree_search_data_func) (const void node, const void data)
	Function pointer for a search function.

typedef int(*	cx_tree_search_func) (const void node, const void new_node)
	Function pointer for a search function.

typedef void (	cx_tree_node_create_func) (const void , void )
	Describes a function that creates a tree node from the specified data.

typedef struct cx_tree_class_s	cx_tree_class
	Tree class type.

typedef struct cx_tree_s	CxTree
	Common type for all tree implementations.

typedef void(*	cx_tree_relink_func) (void node, const void old_parent, const void *new_parent)
	A function that is invoked when a node needs to be re-linked to a new parent.

Functions
static void	cxTreeIteratorDispose (CxTreeIterator *iter)
	Releases internal memory of the given tree iterator.

static void	cxTreeVisitorDispose (CxTreeVisitor *visitor)
	Releases internal memory of the given tree visitor.

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)
	Links a node to a (new) parent.

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)
	Unlinks a node from its parent.

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)
	Searches for data in a tree.

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)
	Searches for a node in a tree.

CxTreeIterator	cx_tree_iterator (void *root, bool visit_on_exit, ptrdiff_t loc_children, ptrdiff_t loc_next)
	Creates a depth-first iterator for a tree with the specified root node.

CxTreeVisitor	cx_tree_visitor (void *root, ptrdiff_t loc_children, ptrdiff_t loc_next)
	Creates a breadth-first iterator for a tree with the specified root node.

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)
	Adds multiple elements efficiently to a tree.

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)
	Adds multiple elements efficiently to a tree.

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)
	Adds data to a tree.

void	cxTreeDestroySubtree (CxTree tree, void node)
	Destroys a node and it's subtree.

void	cxTreeFree (CxTree *tree)
	Deallocates the tree structure.

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)
	Creates a new tree structure based on the specified layout.

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)
	Creates a new tree structure based on an existing tree.

static int	cxTreeInsert (CxTree tree, const void data)
	Inserts data into the tree.

static size_t	cxTreeInsertIter (CxTree tree, struct cx_iterator_base_s iter, size_t n)
	Inserts elements provided by an iterator efficiently into the tree.

static size_t	cxTreeInsertArray (CxTree tree, const void data, size_t elem_size, size_t n)
	Inserts an array of data efficiently into the tree.

static void *	cxTreeFind (CxTree tree, const void data)
	Searches the data in the specified tree.

static void *	cxTreeFindInSubtree (CxTree tree, const void data, void *subtree_root, size_t max_depth)
	Searches the data in the specified subtree.

size_t	cxTreeSubtreeSize (CxTree tree, void subtree_root)
	Determines the size of the specified subtree.

size_t	cxTreeSubtreeDepth (CxTree tree, void subtree_root)
	Determines the depth of the specified subtree.

size_t	cxTreeDepth (CxTree *tree)
	Determines the depth of the entire tree.

static CxTreeIterator	cxTreeIterateSubtree (CxTree tree, void node, bool visit_on_exit)
	Creates a depth-first iterator for the specified tree starting in `node`.

static CxTreeVisitor	cxTreeVisitSubtree (CxTree tree, void node)
	Creates a breadth-first iterator for the specified tree starting in `node`.

static CxTreeIterator	cxTreeIterate (CxTree *tree, bool visit_on_exit)
	Creates a depth-first iterator for the specified tree.

static CxTreeVisitor	cxTreeVisit (CxTree *tree)
	Creates a breadth-first iterator for the specified tree.

void	cxTreeSetParent (CxTree tree, void parent, void *child)
	Sets the (new) parent of the specified child.

void	cxTreeAddChildNode (CxTree tree, void parent, void *child)
	Adds a new node to the tree.

int	cxTreeAddChild (CxTree tree, void parent, const void *data)
	Creates a new node and adds it to the tree.

int	cxTreeRemoveNode (CxTree tree, void node, cx_tree_relink_func relink_func)
	Removes a node and re-links its children to its former parent.

void	cxTreeRemoveSubtree (CxTree tree, void node)
	Removes a node and it's subtree from the tree.

int	cxTreeDestroyNode (CxTree tree, void node, cx_tree_relink_func relink_func)
	Destroys a node and re-links its children to its former parent.

Variables
unsigned int	cx_tree_add_look_around_depth
	The local search depth for a new subtree when adding multiple elements.

Detailed Description

Interface for tree implementations.

Author: Mike Becker; Olaf Wintermann

Copyright: 2-Clause BSD License

Macro Definition Documentation

◆ CX_TREE_NODE_BASE

#define CX_TREE_NODE_BASE ( type )

Value:

    type *parent; \
    type *children;\
    type *last_child;\
    type *prev;\
    type *next

Macro to roll out the cx_tree_node_base_s structure with a custom node type.

Must be used as first member in your custom tree struct.

Parameters

type	the data type for the nodes

◆ cx_tree_node_base_layout

#define cx_tree_node_base_layout

Value:

    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)

Macro for specifying the layout of a base node tree.

When your tree uses CX_TREE_NODE_BASE, you can use this macro in all tree functions that expect the layout parameters loc_parent, loc_children, loc_last_child, loc_prev, and loc_next.

◆ cxTreeClear

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

Destroys the tree contents.

It is guaranteed that the simple destructor is invoked before the advanced destructor, starting with the leaf nodes of the subtree.

This is a convenience macro for invoking cxTreeDestroySubtree() on the root node of the tree.

Attention: Be careful when calling this function when no destructor function is registered that actually frees the memory of nodes. In that case you will need a reference to the (former) root node of the tree somewhere or otherwise you will be leaking memory.

Parameters

tree the tree

See also: cxTreeDestroySubtree()

◆ cxTreeCreateSimple

#define cxTreeCreateSimple	(	allocator,
		create_func,
		search_func,
		search_data_func )

Value:

cxTreeCreate(allocator, create_func, search_func, search_data_func, \

cx_tree_node_base_layout)

cx_tree_node_base_layout

#define cx_tree_node_base_layout

Macro for specifying the layout of a base node tree.

Definition tree.h:834

cxTreeCreate

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)

Creates a new tree structure based on the specified layout.

Creates a new tree structure based on a default layout.

Nodes created by create_func MUST contain cx_tree_node_base_s as first member (or at least respect the default offsets specified in the tree struct) and they MUST be allocated with the specified allocator.

Note: This function will also register an advanced destructor which will free the nodes with the allocator's free() method.

Parameters

allocator	(`CxAllocator*`) the allocator that shall be used
create_func	(`cx_tree_node_create_func`) a function that creates new nodes
search_func	(`cx_tree_search_func`) a function that compares two nodes
search_data_func	(`cx_tree_search_data_func`) a function that compares a node with data

Returns: (CxTree*) the new tree

See also: cxTreeCreate()

◆ cxTreeIteratorContinue

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

Advises the iterator to skip the subtree below the current node and also continues the current loop.

Parameters

iterator (CxTreeIterator) the iterator

◆ cxTreeVisitorContinue

#define cxTreeVisitorContinue ( visitor ) cxTreeIteratorContinue(visitor)

Advises the visitor to skip the subtree below the current node and also continues the current loop.

Parameters

visitor (CxTreeVisitor) the visitor

Typedef Documentation

◆ cx_tree_node_create_func

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

Describes a function that creates a tree node from the specified data.

The first argument points to the data the node shall contain and the second argument may be used for additional data (e.g. an allocator). Functions of this type shall either return a new pointer to a newly created node or NULL when allocation fails.

Note: the function may leave the node pointers in the struct uninitialized. The caller is responsible to set them according to the intended use case.

◆ cx_tree_relink_func

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

A function that is invoked when a node needs to be re-linked to a new parent.

When a node is re-linked, sometimes the contents need to be updated. This callback is invoked by cxTreeRemoveNode() and cxTreeDestroyNode() so that those updates can be applied when re-linking the children of the removed node.

Parameters

node	the affected node
old_parent	the old parent of the node
new_parent	the new parent of the node

◆ cx_tree_search_data_func

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

Function pointer for a search function.

A function of this kind shall check if the specified node contains the given 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. Zero means exact match and a positive number is an implementation defined measure for the distance to an exact match.

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.

Parameters

node	the node that is currently investigated
data	the data that is searched for

Returns: 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

◆ cx_tree_search_func

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

Function pointer for a search function.

A function of this kind shall check if the specified node contains the same data as new_node 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. Zero means exact match and a positive number is an implementation defined measure for the distance to an exact match.

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.

Parameters

node	the node that is currently investigated
new_node	a new node with the information which is searched

Returns: 0 if node contains the same data as new_node, positive if one of the children might contain the data, negative if neither the node, nor the children contains the data

◆ CxTreeIterator

typedef struct cx_tree_iterator_s CxTreeIterator

A depth-first 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 underlying data structure is mutated by other means than this iterator (e.g. elements added or removed), the iterator becomes invalid (regardless of what cxIteratorValid() returns).

See also: CxIterator

◆ CxTreeVisitor

typedef struct cx_tree_visitor_s CxTreeVisitor

A breadth-first tree iterator.

This iterator needs to maintain a visitor queue that will be automatically freed once the iterator becomes invalid. If you want to discard the iterator before, you MUST manually call cxTreeVisitorDispose().

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 underlying data structure is mutated by other means than this iterator (e.g. elements added or removed), the iterator becomes invalid (regardless of what cxIteratorValid() returns).

See also: CxIterator

Function Documentation

◆ cx_tree_add()

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 )

Adds data to a tree.

An adequate location where to add the new tree node is searched with the specified sfunc.

When a location is found, the cfunc will be invoked with cdata.

The node returned by cfunc will be linked into the tree. When sfunc returned a positive integer, the new node will be linked as a child. The other children (now siblings of the new node) are then checked with sfunc, whether they could be children of the new node and re-linked accordingly.

When sfunc returned zero and the found node has a parent, the new node will be added as sibling - otherwise, the new node will be added as a child.

When sfunc returned a negative value, the new node will not be added to the tree and this function returns a non-zero value. The caller should check if cnode contains a node pointer and deal with the node that could not be added.

This function also returns a non-zero value when cfunc tries to allocate a new node but fails to do so. In that case, the pointer stored to cnode will be NULL.

Multiple elements can be added more efficiently with cx_tree_add_array() or cx_tree_add_iter().

Parameters

src	a pointer to the data
sfunc	a search function
cfunc	a node creation function
cdata	optional additional data
cnode	the location where a pointer to the new node is stored
root	the root node of the tree
loc_parent	offset in the node struct for the parent pointer
loc_children	offset in the node struct for the children linked list
loc_last_child	optional offset in the node struct for the pointer to the last child in the linked list (negative if there is no such pointer)
loc_prev	optional offset in the node struct for the prev pointer
loc_next	offset in the node struct for the next pointer

Returns: zero when a new node was created and added to the tree, non-zero otherwise

◆ cx_tree_add_array()

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 )

Adds multiple elements efficiently to a tree.

Once an element cannot be added to the tree, this function returns, storing the pointer of the created node to failed. The integer returned by this function denotes the number of elements from the src array that have been successfully processed. When all elements could be processed, a NULL pointer will be written to failed.

The advantage of this function compared to multiple invocations of cx_tree_add() is that the search for the insert locations is not always started from the root node. Instead, the function checks cx_tree_add_look_around_depth many parent nodes of the current insert location before starting from the root node again. When the variable is set to zero, only the last found location is checked again.

Refer to the documentation of cx_tree_add() for more details.

Parameters

src	a pointer to the source data array
num	the number of elements in the `src` array
elem_size	the size of each element in the `src` array
sfunc	a search function
cfunc	a node creation function
cdata	optional additional data
failed	location where the pointer to a failed node shall be stored
root	the root node of the tree
loc_parent	offset in the node struct for the parent pointer
loc_children	offset in the node struct for the children linked list
loc_last_child	optional offset in the node struct for the pointer to the last child in the linked list (negative if there is no such pointer)
loc_prev	optional offset in the node struct for the prev pointer
loc_next	offset in the node struct for the next pointer

Returns: the number of array elements successfully processed

See also: cx_tree_add()

◆ cx_tree_add_iter()

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 )

Adds multiple elements efficiently to a tree.

Once an element cannot be added to the tree, this function returns, leaving the iterator in a valid state pointing to the element that could not be added. Also, the pointer of the created node will be stored to failed. The integer returned by this function denotes the number of elements obtained from the iter that have been successfully processed. When all elements could be processed, a NULL pointer will be written to failed.

The advantage of this function compared to multiple invocations of cx_tree_add() is that the search for the insert locations is not always started from the root node. Instead, the function checks cx_tree_add_look_around_depth many parent nodes of the current insert location before starting from the root node again. When the variable is set to zero, only the last found location is checked again.

Refer to the documentation of cx_tree_add() for more details.

Parameters

iter	a pointer to an arbitrary iterator
num	the maximum number of elements to obtain from the iterator
sfunc	a search function
cfunc	a node creation function
cdata	optional additional data
root	the root node of the tree
failed	location where the pointer to a failed node shall be stored
loc_parent	offset in the node struct for the parent pointer
loc_children	offset in the node struct for the children linked list
loc_last_child	optional offset in the node struct for the pointer to the last child in the linked list (negative if there is no such pointer)
loc_prev	optional offset in the node struct for the prev pointer
loc_next	offset in the node struct for the next pointer

Returns: the number of nodes created and added

See also: cx_tree_add()

◆ cx_tree_iterator()

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

Creates a depth-first iterator for a tree with the specified root node.

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.

Remarks: The returned iterator does not support cxIteratorFlagRemoval().

Parameters

root	the root node
visit_on_exit	set to true, when the iterator shall visit a node again after processing all children
loc_children	offset in the node struct for the children linked list
loc_next	offset in the node struct for the next pointer

Returns: the new tree iterator

See also: cxTreeIteratorDispose()

◆ cx_tree_link()

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 )

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 appended to the list of all currently existing children.

Parameters

parent	the parent node
node	the node that shall be linked
loc_parent	offset in the node struct for the parent pointer
loc_children	offset in the node struct for the children linked list
loc_last_child	optional offset in the node struct for the pointer to the last child in the linked list (negative if there is no such pointer)
loc_prev	optional offset in the node struct for the prev pointer
loc_next	offset in the node struct for the next pointer

See also: cx_tree_unlink()

◆ cx_tree_search()

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 )

Searches for a node in a tree.

When no node with the same data can be found, the search function might return a closest result which might be a good starting point for adding the new node to the tree (see also cx_tree_add()).

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 sfunc (meaning: the return value of sfunc which is closest to zero). If that is also ambiguous, an arbitrary node matching the criteria is returned.

Parameters

root	the root node
depth	the maximum depth (zero=indefinite, one=just root)
node	the node to search for
sfunc	the search function
result	where the result shall be stored
loc_children	offset in the node struct for the children linked list
loc_next	offset in the node struct for the next pointer

Returns: 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

◆ cx_tree_search_data()

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 )

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 (see also cx_tree_add()).

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 sfunc (meaning: the return value of sfunc which is closest to zero). If that is also ambiguous, an arbitrary node matching the criteria is returned.

Parameters

root	the root node
depth	the maximum depth (zero=indefinite, one=just root)
data	the data to search for
sfunc	the search function
result	where the result shall be stored
loc_children	offset in the node struct for the children linked list
loc_next	offset in the node struct for the next pointer

Returns: 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

◆ cx_tree_unlink()

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 )

Unlinks a node from its parent.

If the node has no parent, this function does nothing.

Parameters

node	the node that shall be unlinked from its parent
loc_parent	offset in the node struct for the parent pointer
loc_children	offset in the node struct for the children linked list
loc_last_child	optional offset in the node struct for the pointer to the last child in the linked list (negative if there is no such pointer)
loc_prev	optional offset in the node struct for the prev pointer
loc_next	offset in the node struct for the next pointer

See also: cx_tree_link()

◆ cx_tree_visitor()

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

Creates a breadth-first iterator for a tree with the specified root node.

Note: A tree visitor needs to maintain a queue of to be visited nodes, which is allocated using stdlib malloc(). When the visitor becomes invalid, this memory is automatically released. However, if you wish to cancel the iteration before the visitor becomes invalid by itself, you MUST call cxTreeVisitorDispose() manually to release the memory.

Remarks: The returned iterator does not support cxIteratorFlagRemoval().

Parameters

root	the root node
loc_children	offset in the node struct for the children linked list
loc_next	offset in the node struct for the next pointer

Returns: the new tree visitor

See also: cxTreeVisitorDispose()

◆ cxTreeAddChild()

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

Creates a new node and adds it to the tree.

With this function you can decide where exactly the new node shall be added. If you specified an appropriate search function, you may want to consider leaving this task to the tree by using cxTreeInsert().

Be aware that adding nodes at arbitrary locations in the tree might cause wrong or undesired results when subsequently invoking cxTreeInsert() and the invariant imposed by the search function does not hold any longer.

Parameters

tree	the tree
parent	the parent node of the new node
data	the data that will be submitted to the create function

Returns: zero when the new node was created, non-zero on allocation failure

See also: cxTreeInsert()

◆ cxTreeAddChildNode()

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

Adds a new node to the tree.

If the child is already member of the tree, the behavior is undefined. Use cxTreeSetParent() if you want to move a subtree to another location.

Attention: The node may be externally created, but MUST obey the same rules as if it was created by the tree itself with cxTreeAddChild() (e.g. use the same allocator).

Parameters

tree	the tree
parent	the parent of the node to add
child	the node to add

See also: cxTreeSetParent()

◆ cxTreeCreate()

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 )

Creates a new tree structure based on the specified layout.

The specified allocator will be used for creating the tree struct and SHALL be used by create_func to allocate memory for the nodes.

Note: This function will also register an advanced destructor which will free the nodes with the allocator's free() method.

Parameters

allocator	the allocator that shall be used (if `NULL`, a default stdlib allocator will be used)
create_func	a function that creates new nodes
search_func	a function that compares two nodes
search_data_func	a function that compares a node with data
loc_parent	offset in the node struct for the parent pointer
loc_children	offset in the node struct for the children linked list
loc_last_child	optional offset in the node struct for the pointer to the last child in the linked list (negative if there is no such pointer)
loc_prev	optional offset in the node struct for the prev pointer
loc_next	offset in the node struct for the next pointer

Returns: the new tree

See also: cxTreeCreateSimple(); cxTreeCreateWrapped()

◆ cxTreeCreateWrapped()

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 )

Creates a new tree structure based on an existing tree.

The specified allocator will be used for creating the tree struct.

Attention: This function will create an incompletely defined tree structure where neither the create function, the search function, nor a destructor will be set. If you wish to use any of this functionality for the wrapped tree, you need to specify those functions afterwards.

Parameters

allocator	the allocator that was used for nodes of the wrapped tree (if `NULL`, a default stdlib allocator is assumed)
root	the root node of the tree that shall be wrapped
loc_parent	offset in the node struct for the parent pointer
loc_children	offset in the node struct for the children linked list
loc_last_child	optional offset in the node struct for the pointer to the last child in the linked list (negative if there is no such pointer)
loc_prev	optional offset in the node struct for the prev pointer
loc_next	offset in the node struct for the next pointer

Returns: the new tree

See also: cxTreeCreate()

◆ cxTreeDepth()

size_t cxTreeDepth ( CxTree * tree )

Determines the depth of the entire tree.

Parameters

tree the tree

Returns: the tree depth, counting the root as one

◆ cxTreeDestroyNode()

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

Destroys a node and re-links its children to its former parent.

If the node is not part of the tree, the behavior is undefined.

It is guaranteed that the simple destructor is invoked before the advanced destructor.

Attention: This function will not free the memory of the node with the tree's allocator, because that is usually done by the advanced destructor and would therefore result in a double-free.

Parameters

tree	the tree
node	the node to destroy (must not be the root node)
relink_func	optional callback to update the content of each re-linked node

Returns: zero on success, non-zero if node is the root node of the tree

◆ cxTreeDestroySubtree()

void cxTreeDestroySubtree	(	CxTree *	tree,
		void *	node )

Destroys a node and it's subtree.

It is guaranteed that the simple destructor is invoked before the advanced destructor, starting with the leaf nodes of the subtree.

When this function is invoked on the root node of the tree, it destroys the tree contents, but - in contrast to cxTreeFree() - not the tree structure, leaving an empty tree behind.

Note: The destructor function, if any, will not be invoked. That means you will need to free the removed subtree by yourself, eventually.

Attention: This function will not free the memory of the nodes with the tree's allocator, because that is usually done by the advanced destructor and would therefore result in a double-free.

Parameters

tree	the tree
node	the node to remove

See also: cxTreeFree()

◆ cxTreeFind()

static void * cxTreeFind	(	CxTree *	tree,
		const void *	data )

inlinestatic

Searches the data in the specified tree.

Remarks: For this function to work, the tree needs a specified search_data function, which might not be available wrapped trees (see cxTreeCreateWrapped()).

Parameters

tree	the tree
data	the data to search for

Returns: the first matching node, or NULL when the data cannot be found

◆ cxTreeFindInSubtree()

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

inlinestatic

Searches the data in the specified subtree.

When max_depth is zero, the depth is not limited. The subtree_root itself is on depth 1 and its children have depth 2.

Note: When subtree_root is not part of the tree, the behavior is undefined.

Remarks: For this function to work, the tree needs a specified search_data function, which might not be the case for wrapped trees (see cxTreeCreateWrapped()).

Parameters

tree	the tree
data	the data to search for
subtree_root	the node where to start
max_depth	the maximum search depth

Returns: the first matching node, or NULL when the data cannot be found

◆ cxTreeFree()

void cxTreeFree ( CxTree * tree )

Deallocates the tree structure.

The destructor functions are invoked for each node, starting with the leaf nodes. It is guaranteed that for each node the simple destructor is invoked before the advanced destructor.

Attention: This function will only invoke the destructor functions on the nodes. It will NOT additionally free the nodes with the tree's allocator, because that would cause a double-free in most scenarios where the advanced destructor is already freeing the memory.

Parameters

tree	the tree to free

◆ cxTreeInsert()

static int cxTreeInsert	(	CxTree *	tree,
		const void *	data )

inlinestatic

Inserts data into the tree.

Remarks: For this function to work, the tree needs specified search and create functions, which might not be available for wrapped trees (see cxTreeCreateWrapped()).

Parameters

tree	the tree
data	the data to insert

Return values

zero	success
non-zero	failure

◆ cxTreeInsertArray()

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

inlinestatic

Inserts an array of data efficiently into the tree.

Remarks: For this function to work, the tree needs specified search and create functions, which might not be available for wrapped trees (see cxTreeCreateWrapped()).

Parameters

tree	the tree
data	the array of data to insert
elem_size	the size of each element in the array
n	the number of elements in the array

Returns: the number of elements that could be successfully inserted

◆ cxTreeInsertIter()

static size_t cxTreeInsertIter	(	CxTree *	tree,
		struct cx_iterator_base_s *	iter,
		size_t	n )

inlinestatic

Inserts elements provided by an iterator efficiently into the tree.

Remarks: For this function to work, the tree needs specified search and create functions, which might not be available for wrapped trees (see cxTreeCreateWrapped()).

Parameters

tree	the tree
iter	the iterator providing the elements
n	the maximum number of elements to insert

Returns: the number of elements that could be successfully inserted

◆ cxTreeIterate()

static CxTreeIterator cxTreeIterate	(	CxTree *	tree,
		bool	visit_on_exit )

inlinestatic

Creates a depth-first iterator for the specified tree.

Parameters

tree	the tree to iterate
visit_on_exit	true, if the iterator shall visit a node again when leaving the subtree

Returns: a tree iterator (depth-first)

See also: cxTreeVisit()

◆ cxTreeIterateSubtree()

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

inlinestatic

Creates a depth-first iterator for the specified tree starting in node.

If the node is not part of the tree, the behavior is undefined.

Parameters

tree	the tree to iterate
node	the node where to start
visit_on_exit	true, if the iterator shall visit a node again when leaving the subtree

Returns: a tree iterator (depth-first)

See also: cxTreeVisit()

◆ cxTreeIteratorDispose()

static void cxTreeIteratorDispose ( CxTreeIterator * iter )

inlinestatic

Releases internal memory of the given tree iterator.

Parameters

iter	the iterator

◆ cxTreeRemoveNode()

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

Removes a node and re-links its children to its former parent.

If the node is not part of the tree, the behavior is undefined.

Note: The destructor function, if any, will not be invoked. That means you will need to free the removed node by yourself, eventually.

Parameters

tree	the tree
node	the node to remove (must not be the root node)
relink_func	optional callback to update the content of each re-linked node

Returns: zero on success, non-zero if node is the root node of the tree

◆ cxTreeRemoveSubtree()

void cxTreeRemoveSubtree	(	CxTree *	tree,
		void *	node )

Removes a node and it's subtree from the tree.

If the node is not part of the tree, the behavior is undefined.

Note: The destructor function, if any, will not be invoked. That means you will need to free the removed subtree by yourself, eventually.

Parameters

tree	the tree
node	the node to remove

◆ cxTreeSetParent()

void cxTreeSetParent	(	CxTree *	tree,
		void *	parent,
		void *	child )

Sets the (new) parent of the specified child.

If the child is not already member of the tree, this function behaves as cxTreeAddChildNode().

Parameters

tree	the tree
parent	the (new) parent of the child
child	the node to add

See also: cxTreeAddChildNode()

◆ cxTreeSubtreeDepth()

size_t cxTreeSubtreeDepth	(	CxTree *	tree,
		void *	subtree_root )

Determines the depth of the specified subtree.

Parameters

tree	the tree
subtree_root	the root node of the subtree

Returns: the tree depth including the subtree_root

◆ cxTreeSubtreeSize()

size_t cxTreeSubtreeSize	(	CxTree *	tree,
		void *	subtree_root )

Determines the size of the specified subtree.

Parameters

tree	the tree
subtree_root	the root node of the subtree

Returns: the number of nodes in the specified subtree

◆ cxTreeVisit()

static CxTreeVisitor cxTreeVisit ( CxTree * tree )

inlinestatic

Creates a breadth-first iterator for the specified tree.

Parameters

tree	the tree to iterate

Returns: a tree visitor (a.k.a. breadth-first iterator)

See also: cxTreeIterate()

◆ cxTreeVisitorDispose()

static void cxTreeVisitorDispose ( CxTreeVisitor * visitor )

inlinestatic

Releases internal memory of the given tree visitor.

Parameters

visitor the visitor

◆ cxTreeVisitSubtree()

static CxTreeVisitor cxTreeVisitSubtree	(	CxTree *	tree,
		void *	node )

inlinestatic

Creates a breadth-first iterator for the specified tree starting in node.

If the node is not part of the tree, the behavior is undefined.

Parameters

tree	the tree to iterate
node	the node where to start

Returns: a tree visitor (a.k.a. breadth-first iterator)

See also: cxTreeIterate()

Variable Documentation

◆ cx_tree_add_look_around_depth

unsigned int cx_tree_add_look_around_depth

extern

The local search depth for a new subtree when adding multiple elements.

The default value is 3. This variable is used by cx_tree_add_array() and cx_tree_add_iter() to implement optimized insertion of multiple elements into a tree.

Data Structures

Macros

Typedefs

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ CX_TREE_NODE_BASE

◆ cx_tree_node_base_layout

◆ cxTreeClear

◆ cxTreeCreateSimple

◆ cxTreeIteratorContinue

◆ cxTreeVisitorContinue

Typedef Documentation

◆ cx_tree_node_create_func

◆ cx_tree_relink_func

◆ cx_tree_search_data_func

◆ cx_tree_search_func

◆ CxTreeIterator

◆ CxTreeVisitor

Function Documentation

◆ cx_tree_add()

◆ cx_tree_add_array()

◆ cx_tree_add_iter()

◆ cx_tree_iterator()

◆ cx_tree_link()

◆ cx_tree_search()

◆ cx_tree_search_data()

◆ cx_tree_unlink()

◆ cx_tree_visitor()

◆ cxTreeAddChild()

◆ cxTreeAddChildNode()

◆ cxTreeCreate()

◆ cxTreeCreateWrapped()

◆ cxTreeDepth()

◆ cxTreeDestroyNode()

◆ cxTreeDestroySubtree()

◆ cxTreeFind()

◆ cxTreeFindInSubtree()

◆ cxTreeFree()

◆ cxTreeInsert()

◆ cxTreeInsertArray()

◆ cxTreeInsertIter()

◆ cxTreeIterate()

◆ cxTreeIterateSubtree()

◆ cxTreeIteratorDispose()

◆ cxTreeRemoveNode()

◆ cxTreeRemoveSubtree()

◆ cxTreeSetParent()

◆ cxTreeSubtreeDepth()

◆ cxTreeSubtreeSize()

◆ cxTreeVisit()

◆ cxTreeVisitorDispose()

◆ cxTreeVisitSubtree()

Variable Documentation

◆ cx_tree_add_look_around_depth