An unbalanced binary tree. More...

Data Structures
struct	cstl_bintree_node
	Node to anchor an element within a binary tree. More...

struct	cstl_bintree
	Binary tree object. More...

Macros
#define	CSTL_BINTREE_INITIALIZER(TYPE, MEMB, CMP, PRIV)
	Constant initialization of a cstl_bintree object.

#define	DECLARE_CSTL_BINTREE(NAME, TYPE, MEMB, CMP, PRIV)
	(Statically) declare and initialize a binary tree

Typedefs
typedef int	cstl_bintree_const_visit_func_t(const void e, cstl_bintree_visit_order_t ord, void p)
	The type of visit function associated with cstl_bintree_foreach()

Enumerations
enum	cstl_bintree_visit_order_t { CSTL_BINTREE_VISIT_ORDER_PRE , CSTL_BINTREE_VISIT_ORDER_MID , CSTL_BINTREE_VISIT_ORDER_POST , CSTL_BINTREE_VISIT_ORDER_LEAF }
	Enumeration indicating the order in which a tree element is being visited during `cstl_bintree_foreach()` More...

enum	cstl_bintree_foreach_dir_t { CSTL_BINTREE_FOREACH_DIR_FWD , CSTL_BINTREE_FOREACH_DIR_REV }
	Enumeration indicating the order in which elements in a tree are visited during `cstl_bintree_foreach()` More...

Functions
static void	cstl_bintree_init (struct cstl_bintree const bt, cstl_compare_func_t const cmp, void *const priv, const size_t off)
	Initialize a binary tree object.

static size_t	cstl_bintree_size (const struct cstl_bintree *const bt)
	Get the number of objects in the tree.

void	cstl_bintree_insert (struct cstl_bintree bt, void e, void *p)
	Insert a new object into the tree.

const void *	cstl_bintree_find (const struct cstl_bintree bt, const void e, const void **p)
	Find an element within a tree.

void *	cstl_bintree_erase (struct cstl_bintree bt, const void e)
	Remove an element from the tree.

void	cstl_bintree_clear (struct cstl_bintree bt, cstl_xtor_func_t clr, void *priv)
	Remove all elements from the tree.

void	cstl_bintree_swap (struct cstl_bintree a, struct cstl_bintree b)
	Swap the tree objects at the two given locations.

int	cstl_bintree_foreach (const struct cstl_bintree bt, cstl_bintree_const_visit_func_t visit, void *priv, cstl_bintree_foreach_dir_t dir)
	Visit each element in a tree, calling a user-defined function for each visit.

void	cstl_bintree_height (const struct cstl_bintree bt, size_t min, size_t *max)
	Determine the maximum and minimum heights of a tree.

Detailed Description

An unbalanced binary tree.

Macro Definition Documentation

◆ CSTL_BINTREE_INITIALIZER

#define CSTL_BINTREE_INITIALIZER	(	TYPE,
		MEMB,
		CMP,
		PRIV
	)

Value:

    {                                                   \
        .root = NULL,                                   \
        .size = 0,                                      \
        .off = offsetof(TYPE, MEMB),                    \
        .cmp = {                                        \
            .func = CMP,                                \
            .priv = PRIV                                \
        }                                               \
    }

Constant initialization of a cstl_bintree object.

Parameters

TYPE	The type of object that the tree will hold
MEMB	The name of the `cstl_bintree_node` member within `TYPE`.
CMP	A pointer to a function of type `cstl_compare_func_t` that will be used to compare elements in the tree
PRIV	A pointer to a private data structure that will be passed to calls to the `CMP` function

See also: cstl_bintree_node for a description of the relationship between TYPE and MEMB

Definition at line 90 of file bintree.h.

◆ DECLARE_CSTL_BINTREE

#define DECLARE_CSTL_BINTREE	(	NAME,
		TYPE,
		MEMB,
		CMP,
		PRIV
	)

Value:

struct cstl_bintree NAME = \

CSTL_BINTREE_INITIALIZER(TYPE, MEMB, CMP, PRIV)

cstl_bintree

Binary tree object.

Definition bintree.h:63

(Statically) declare and initialize a binary tree

Parameters

NAME	The name of the variable being declared
TYPE	The type of object that the tree will hold
MEMB	The name of the `cstl_bintree_node` member within `TYPE`.
CMP	A pointer to a function of type `cstl_compare_func_t` that will be used to compare elements in the tree
PRIV	A pointer to a private data structure that will be passed to calls to the `CMP` function

See also: cstl_bintree_node for a description of the relationship between TYPE and MEMB

Definition at line 114 of file bintree.h.

Typedef Documentation

◆ cstl_bintree_const_visit_func_t

typedef int cstl_bintree_const_visit_func_t(const void *e, cstl_bintree_visit_order_t ord, void *p)

The type of visit function associated with cstl_bintree_foreach()

The cstl_bintree_foreach() function requires that visited elements are presented as const because modifying the element could cause the previously determined (in)equality relationships between elements to be modified and for future operations on the tree to result in undefined behavior

Parameters

[in]	e	A pointer to the element being visited
[in]	ord	An enumeration indicating which visit to this element is being performed
[in]	p	A pointer to a private data object belonging to the callee

Return values

0	Continue visiting elements in the tree
Nonzero	Stop visiting elements in the tree

Definition at line 299 of file bintree.h.

Enumeration Type Documentation

◆ cstl_bintree_foreach_dir_t

enum cstl_bintree_foreach_dir_t

Enumeration indicating the order in which elements in a tree are visited during cstl_bintree_foreach()

Note: The enumerations and their descriptions assume that the tree's associated cmp function compares elements in the "normal/expected" fashion

Enumerator
CSTL_BINTREE_FOREACH_DIR_FWD	Each element in the tree is visited from left-to-right.
CSTL_BINTREE_FOREACH_DIR_REV	Each element in the tree is visited from right-to-left.

Definition at line 274 of file bintree.h.

◆ cstl_bintree_visit_order_t

enum cstl_bintree_visit_order_t

Enumeration indicating the order in which a tree element is being visited during cstl_bintree_foreach()

Enumerator
CSTL_BINTREE_VISIT_ORDER_PRE	The first visit to an element that has at least one child.
CSTL_BINTREE_VISIT_ORDER_MID	The second visit to an element, after its first child has/would have been visited.
CSTL_BINTREE_VISIT_ORDER_POST	The last visit to an element, after both children have/would have been visited.
CSTL_BINTREE_VISIT_ORDER_LEAF	The only visit to an element that has no children.

Definition at line 248 of file bintree.h.

Function Documentation

◆ cstl_bintree_clear()

void cstl_bintree_clear	(	struct cstl_bintree *	bt,
		cstl_xtor_func_t *	clr,
		void *	priv
	)

Remove all elements from the tree.

Parameters

[in]	bt	A pointer to the binary tree
[in]	clr	A pointer to a function to be called for each element in the tree
[in]	priv	A pointer to be passed to each invocation of `clr`

All elements are removed from the tree and the clr function is called for each element that was in the tree. The order in which the elements are removed and clr is called is not specified, but the callee may take ownership of an element at the time that clr is called for that element and not before.

Upon return from this function, the tree contains no elements, and is as it was immediately after being initialized. No further operations on the tree are necessary to make it ready to go out of scope or be destroyed.

Definition at line 552 of file bintree.c.

◆ cstl_bintree_erase()

void * cstl_bintree_erase	(	struct cstl_bintree *	bt,
		const void *	e
	)

Remove an element from the tree.

Parameters

[in]	bt	A pointer to the binary tree
[in]	e	A pointer to an object to compare to those in the tree

The tree will be searched for an element that compares as equal to the e parameter as defined by the cmp function provided when the tree was initialized. The first element found that matches will be removed from the tree, and a pointer to that element will be returned.

Returns: A pointer to the removed element

Return values

NULL	No element was found/removed

Definition at line 342 of file bintree.c.

◆ cstl_bintree_find()

const void * cstl_bintree_find	(	const struct cstl_bintree *	bt,
		const void *	e,
		const void **	p
	)

Find an element within a tree.

Parameters

[in]	bt	A pointer to the binary tree
[in]	e	A pointer to an object to compare to those in the tree
[out]	p	The location in which to return a pointer to the parent of the found element (or where it would be located). This pointer may be NULL

The tree will be searched for an element that compares as equal to the e parameter as defined by the cmp function provided when the tree was initialized.

Returns: A pointer to the (first) object in the tree that matches

Return values

NULL	No matching object was found

Definition at line 93 of file bintree.c.

◆ cstl_bintree_foreach()

int cstl_bintree_foreach	(	const struct cstl_bintree *	bt,
		cstl_bintree_const_visit_func_t *	visit,
		void *	priv,
		cstl_bintree_foreach_dir_t	dir
	)

Visit each element in a tree, calling a user-defined function for each visit.

Parameters

[in]	bt	A pointer to the binary tree
[in]	visit	A pointer to a function to be called for each visit
[in]	priv	A pointer to a private data structure that will be passed to each call to `visit`
[in]	dir	The direction in which to traverse the tree

The function continues visiting elements in the tree so long as the given visit function returns 0. If the visit function returns a non-zero value, no more elements are visited, and the function returns the non-zero value that halted visitations.

See also: cstl_bintree_visit_order_t

Definition at line 475 of file bintree.c.

◆ cstl_bintree_height()

void cstl_bintree_height	(	const struct cstl_bintree *	bt,
		size_t *	min,
		size_t *	max
	)

Determine the maximum and minimum heights of a tree.

Parameters

[in]	bt	A pointer to the binary tree
[out]	min	The length of the shortest path from a root to a leaf
[out]	max	The length of the longest path from the root to a leaf

Definition at line 608 of file bintree.c.

◆ cstl_bintree_init()

static void cstl_bintree_init	(	struct cstl_bintree *const	bt,
		cstl_compare_func_t *const	cmp,
		void *const	priv,
		const size_t	off
	)

inlinestatic

Initialize a binary tree object.

Parameters

[in,out]	bt	A pointer to the object to be initialized
[in]	cmp	A function that can compare objects in the tree
[in]	priv	A pointer to private data that will be passed to the `cmp` function
[in]	off	The offset of the `cstl_bintree_node` object within the object(s) that will be stored in the tree

Definition at line 128 of file bintree.h.

◆ cstl_bintree_insert()

void cstl_bintree_insert	(	struct cstl_bintree *	bt,
		void *	e,
		void *	p
	)

Insert a new object into the tree.

Parameters

[in]	bt	A pointer to the binary tree
[in]	e	A pointer to the object to be inserted
[in]	p	A pointer to the parent of the object to be inserted. This pointer may be NULL or can be found via cstl_bintree_find()

The inserted object does not need to compare as unequal to any/all other objects already in the tree. If the object is equal to one or more objects already in the tree, it is up to the caller to distinguish between them during a find or erase operation.

The inserted object must not be modified (in such a way as to affect its comparison with other objects in the tree) as that modification can cause the assumptions about the ordering of elements within the tree to become invalid and lead to undefined behavior.

Definition at line 63 of file bintree.c.

◆ cstl_bintree_size()

static size_t cstl_bintree_size ( const struct cstl_bintree *const bt )

inlinestatic

Get the number of objects in the tree.

Parameters

[in] bt A pointer to the binary tree

Returns: The number of objects in the tree

Definition at line 149 of file bintree.h.

◆ cstl_bintree_swap()

void cstl_bintree_swap	(	struct cstl_bintree *	a,
		struct cstl_bintree *	b
	)

Swap the tree objects at the two given locations.

Parameters

[in,out]	a	A pointer to a binary tree
[in,out]	b	A pointer to a(nother) binary tree

The trees at the given locations will be swapped such that upon return, a will contain the tree previously pointed to by b and vice versa.

Definition at line 506 of file bintree.c.

Data Structures

Macros

Typedefs

Enumerations

Functions

Detailed Description

Macro Definition Documentation

◆ CSTL_BINTREE_INITIALIZER

◆ DECLARE_CSTL_BINTREE

Typedef Documentation

◆ cstl_bintree_const_visit_func_t

Enumeration Type Documentation

◆ cstl_bintree_foreach_dir_t

◆ cstl_bintree_visit_order_t

Function Documentation

◆ cstl_bintree_clear()

◆ cstl_bintree_erase()

◆ cstl_bintree_find()

◆ cstl_bintree_foreach()

◆ cstl_bintree_height()

◆ cstl_bintree_init()

◆ cstl_bintree_insert()

◆ cstl_bintree_size()

◆ cstl_bintree_swap()