A self-balancing binary tree. More...

Data Structures
struct	cstl_rbtree_node
	Node to anchor an element within a red-black tree. More...

struct	cstl_rbtree
	Red-black tree object. More...

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

#define	DECLARE_CSTL_RBTREE(NAME, TYPE, MEMB, CMP, PRIV)
	(Statically) declare and initialize a red-black tree

Functions
static void	cstl_rbtree_init (struct cstl_rbtree const t, cstl_compare_func_t const cmp, void *const priv, const size_t off)
	Initialize a red-black tree object.

static size_t	cstl_rbtree_size (const struct cstl_rbtree *const t)
	Get the number of objects in the tree.

void	cstl_rbtree_insert (struct cstl_rbtree t, void e, void *p)
	Insert a new object into the tree.

static const void *	cstl_rbtree_find (const struct cstl_rbtree const t, const void const e, const void **const p)
	Find an element within a tree.

void *	cstl_rbtree_erase (struct cstl_rbtree t, const void e)
	Remove an element from the tree.

static void	cstl_rbtree_clear (struct cstl_rbtree const t, cstl_xtor_func_t const clr, void *const priv)
	Remove all elements from the tree.

static void	cstl_rbtree_swap (struct cstl_rbtree const a, struct cstl_rbtree const b)
	Swap the tree objects at the two given locations.

static int	cstl_rbtree_foreach (const struct cstl_rbtree const t, cstl_bintree_const_visit_func_t const visit, void *const priv, const cstl_bintree_foreach_dir_t dir)
	Visit each element in a tree, calling a user-defined function for each visit.

static void	cstl_rbtree_height (const struct cstl_rbtree const t, size_t const min, size_t *const max)
	Determine the maximum and minimum heights of a tree.

Detailed Description

A self-balancing binary tree.

Macro Definition Documentation

◆ CSTL_RBTREE_INITIALIZER

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

Value:

    {                                                           \
        .t = CSTL_BINTREE_INITIALIZER(TYPE, MEMB.n, CMP, PRIV), \
        .off = offsetof(TYPE, MEMB),                            \
    }

Constant initialization of a cstl_rbtree object.

Parameters

TYPE	The type of object that the tree will hold
MEMB	The name of the `cstl_rbtree_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_rbtree_node for a description of the relationship between TYPE and MEMB

Definition at line 95 of file rbtree.h.

◆ DECLARE_CSTL_RBTREE

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

Value:

struct cstl_rbtree NAME = \

CSTL_RBTREE_INITIALIZER(TYPE, MEMB, CMP, PRIV)

cstl_rbtree

Red-black tree object.

Definition rbtree.h:75

(Statically) declare and initialize a red-black 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_rbtree_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_rbtree_node for a description of the relationship between TYPE and MEMB

Definition at line 114 of file rbtree.h.

Function Documentation

◆ cstl_rbtree_clear()

static void cstl_rbtree_clear	(	struct cstl_rbtree *const	t,
		cstl_xtor_func_t *const	clr,
		void *const	priv
	)

inlinestatic

Remove all elements from the tree.

Parameters

[in]	t	A pointer to the red-black 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 233 of file rbtree.h.

◆ cstl_rbtree_erase()

void * cstl_rbtree_erase	(	struct cstl_rbtree *	t,
		const void *	e
	)

Remove an element from the tree.

Parameters

[in]	t	A pointer to the red-black 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 327 of file rbtree.c.

◆ cstl_rbtree_find()

static const void * cstl_rbtree_find	(	const struct cstl_rbtree *const	t,
		const void *const	e,
		const void **const	p
	)

inlinestatic

Find an element within a tree.

Parameters

[in]	t	A pointer to the red-black 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 187 of file rbtree.h.

◆ cstl_rbtree_foreach()

static int cstl_rbtree_foreach	(	const struct cstl_rbtree *const	t,
		cstl_bintree_const_visit_func_t *const	visit,
		void *const	priv,
		const cstl_bintree_foreach_dir_t	dir
	)

inlinestatic

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

Parameters

[in]	t	A pointer to the red-black 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 275 of file rbtree.h.

◆ cstl_rbtree_height()

static void cstl_rbtree_height	(	const struct cstl_rbtree *const	t,
		size_t *const	min,
		size_t *const	max
	)

inlinestatic

Determine the maximum and minimum heights of a tree.

Parameters

[in]	t	A pointer to the red-black 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 291 of file rbtree.h.

◆ cstl_rbtree_init()

static void cstl_rbtree_init	(	struct cstl_rbtree *const	t,
		cstl_compare_func_t *const	cmp,
		void *const	priv,
		const size_t	off
	)

inlinestatic

Initialize a red-black tree object.

Parameters

[in,out]	t	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_rbtree_node` object within the object(s) that will be stored in the tree

Definition at line 128 of file rbtree.h.

◆ cstl_rbtree_insert()

void cstl_rbtree_insert	(	struct cstl_rbtree *	t,
		void *	e,
		void *	p
	)

Insert a new object into the tree.

Parameters

[in]	t	A pointer to the red-black 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 98 of file rbtree.c.

◆ cstl_rbtree_size()

static size_t cstl_rbtree_size ( const struct cstl_rbtree *const t )

inlinestatic

Get the number of objects in the tree.

Parameters

[in] t A pointer to the red-black tree

Returns: The number of objects in the tree

Definition at line 145 of file rbtree.h.

◆ cstl_rbtree_swap()

static void cstl_rbtree_swap	(	struct cstl_rbtree *const	a,
		struct cstl_rbtree *const	b
	)

inlinestatic

Swap the tree objects at the two given locations.

Parameters

[in,out]	a	A pointer to a red-black tree
[in,out]	b	A pointer to a(nother) red-black 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 249 of file rbtree.h.

Data Structures

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ CSTL_RBTREE_INITIALIZER

◆ DECLARE_CSTL_RBTREE

Function Documentation

◆ cstl_rbtree_clear()

◆ cstl_rbtree_erase()

◆ cstl_rbtree_find()

◆ cstl_rbtree_foreach()

◆ cstl_rbtree_height()

◆ cstl_rbtree_init()

◆ cstl_rbtree_insert()

◆ cstl_rbtree_size()

◆ cstl_rbtree_swap()