Overview

A red-black tree implementation.

#include "lwpa_rbtree.h"

A red-black tree is a popular design for a self-balancing binary search tree. Based on a public-domain red-black tree implementation; see the header file for details.

Data Structures
struct	LwpaRbNode
	A red-black tree node. More...

struct	LwpaRbTree
	A red-black tree. More...

struct	LwpaRbIter
	A red-black tree iterator. More...

Macros
#define	RB_ITER_MAX_HEIGHT 64
	The tallest allowable tree that can be iterated over.

Typedefs
typedef struct LwpaRbNode	LwpaRbNode

typedef struct LwpaRbTree	LwpaRbTree

typedef struct LwpaRbIter	LwpaRbIter
	A red-black tree iterator. More...

Functions
int	rb_tree_node_cmp_ptr_cb (const LwpaRbTree self, const LwpaRbNode a, const LwpaRbNode *b)
	The default node comparison callback. More...

void	rb_tree_node_dealloc_cb (const LwpaRbTree self, LwpaRbNode node)
	The default node deallocation callback. More...

LwpaRbNode *	rb_node_init (LwpaRbNode self, void value)
	Initialize a red-black tree node. More...

LwpaRbTree *	rb_tree_init (LwpaRbTree *self, rb_tree_node_cmp_f cmp, rb_node_alloc_f alloc_f, rb_node_dealloc_f dealloc_f)
	Initialize a red-black tree node. More...

void *	rb_tree_find (LwpaRbTree self, void value)
	Find a value in a red-black tree. More...

int	rb_tree_insert (LwpaRbTree self, void value)
	Insert a new value into a red-black tree. More...

int	rb_tree_remove (LwpaRbTree self, void value)
	Remove a value from a red-black tree. More...

int	rb_tree_clear (LwpaRbTree *self)
	Clear all values from a red-black tree. More...

size_t	rb_tree_size (LwpaRbTree *self)
	Get the current number of values in a red-black tree. More...

int	rb_tree_insert_node (LwpaRbTree self, LwpaRbNode node)
	Insert a node containing a new value into a red-black tree. More...

int	rb_tree_remove_with_cb (LwpaRbTree self, void value, rb_tree_node_f node_cb)
	Remove a value from a red-black tree, calling back into the application with the node and value being removed. More...

int	rb_tree_clear_with_cb (LwpaRbTree *self, rb_tree_node_f node_cb)
	Clear all values from a red-black tree, calling back into the application for each node and value being removed. More...

int	rb_tree_test (LwpaRbTree self, LwpaRbNode root)
	Test the validity of a red-black tree. More...

LwpaRbIter *	rb_iter_init (LwpaRbIter *self)
	Initialize a red-black tree iterator. More...

void *	rb_iter_first (LwpaRbIter self, LwpaRbTree tree)
	Point a red-black tree iterator at the first value in the tree. More...

void *	rb_iter_last (LwpaRbIter self, LwpaRbTree tree)
	Point a red-black tree iterator at the last value in the tree. More...

void *	rb_iter_next (LwpaRbIter *self)
	Advance a red-black tree iterator. More...

void *	rb_iter_prev (LwpaRbIter *self)
	Reverse-advance a red-black tree iterator. More...

Callback Functions
typedef int(*	rb_tree_node_cmp_f) (const LwpaRbTree self, const LwpaRbNode node_a, const LwpaRbNode *node_b)
	A function type that compares two nodes in a tree. More...

typedef void(*	rb_tree_node_f) (const LwpaRbTree self, LwpaRbNode node)
	A function type to be called for each node in a tree. More...

typedef LwpaRbNode (	rb_node_alloc_f) ()
	A function type to allocate a new node. More...

typedef void(*	rb_node_dealloc_f) (LwpaRbNode *node)
	A function type to deallocate a node. More...

Typedef Documentation

◆ LwpaRbIter

typedef struct LwpaRbIter LwpaRbIter

A red-black tree iterator.

Initialize using rb_iter_init() before carrying out any other operation on the iterator.

◆ rb_node_alloc_f

typedef LwpaRbNode*(* rb_node_alloc_f) ()

A function type to allocate a new node.

The user provides the allocation method for new nodes, whether this be malloc() or some more static method. A function of this type is saved by the tree struct and called on a call to rb_tree_insert().

Returns: Pointer to the newly allocated node.

◆ rb_node_dealloc_f

typedef void(* rb_node_dealloc_f) (LwpaRbNode *node)

A function type to deallocate a node.

The user provides the deallocation method for nodes, whether this be free() or some more static method. A function of this type is saved by the tree struct and called on calls to rb_tree_remove() and rb_tree_clear().

Parameters

[in] node Pointer to node to deallocate.

◆ rb_tree_node_cmp_f

typedef int(* rb_tree_node_cmp_f) (const LwpaRbTree *self, const LwpaRbNode *node_a, const LwpaRbNode *node_b)

A function type that compares two nodes in a tree.

A default, rb_tree_node_cmp_ptr_cb(), is provided which simply compares the pointer (address) of the value member of each node.

Parameters

[in]	self	The tree in which two nodes are being compared.
[in]	node_a	The first node being compared.
[in]	node_b	The second node being compared.

Returns: < 0 (node_a's value is less than node_b's value)
0 (node_a's value is equal to node_b's value)
> 0 (node_a's value is greater than node_b's value)

◆ rb_tree_node_f

typedef void(* rb_tree_node_f) (const LwpaRbTree *self, LwpaRbNode *node)

A function type to be called for each node in a tree.

Usually provided on a tree-wide clear or destroy operation; in this case, it should provide any deallocation necessary for the node structure and its value. A default, rb_tree_node_dealloc_cb(), is provided which simply calls the tree's rb_node_dealloc_f on the node.

Parameters

[in]	self	The tree in which the node resides.
[in]	node	The node for which an action should be performed.

Function Documentation

◆ rb_iter_first()

void* rb_iter_first	(	LwpaRbIter *	self,
		LwpaRbTree *	tree
	)

Point a red-black tree iterator at the first value in the tree.

The first value is the lowest, as determined by the rb_tree_node_cmp_f provided in rb_tree_init(). Use rb_iter_next() to get the next higher value.

Parameters

[in]	self	Iterator to point at the first value.
[in]	tree	Tree of which to get the first value.

Returns: Pointer to the first value or NULL (the tree was empty or invalid).

◆ rb_iter_init()

LwpaRbIter* rb_iter_init ( LwpaRbIter * self )

Initialize a red-black tree iterator.

This function must be called on a new iterator before using any of the other rb_iter_* functions on it.

Parameters

[in] self The iterator to be initialized.

Returns: Pointer to the iterator that was initialized.

◆ rb_iter_last()

void* rb_iter_last	(	LwpaRbIter *	self,
		LwpaRbTree *	tree
	)

Point a red-black tree iterator at the last value in the tree.

The last value is the highest, as determined by the rb_tree_node_cmp_f provided in rb_tree_init(). Use rb_iter_prev() to get the next lower value.

Parameters

[in]	self	Iterator to point at the last value.
[in]	tree	Tree of which to get the last value.

Returns: Pointer to the last value or NULL (the tree was empty or invalid).

◆ rb_iter_next()

void* rb_iter_next ( LwpaRbIter * self )

Advance a red-black tree iterator.

Gets the next higher value in the tree as determined by the rb_tree_node_cmp_f provided in rb_tree_init().

Parameters

[in] self Iterator to advance.

Returns: Pointer to next higher value, or NULL (the end of the tree has been reached).

◆ rb_iter_prev()

void* rb_iter_prev ( LwpaRbIter * self )

Reverse-advance a red-black tree iterator.

Gets the next lower value in the tree as determined by the rb_tree_node_cmp_f provided in rb_tree_init().

Parameters

[in] self Iterator to reverse-advance.

Returns: Pointer to next lower value, or NULL (the beginning of the tree has been reached).

◆ rb_node_init()

LwpaRbNode* rb_node_init	(	LwpaRbNode *	self,
		void *	value
	)

Initialize a red-black tree node.

This function must be called on a new node before inserting it manually using rb_tree_insert_node(). When using rb_tree_insert(), this function is called on the new node automatically.

Parameters

[in]	self	The node to be initialized.
[in]	value	Pointer to the value to assign to the node.

Returns: Pointer to the node that was initialized.

◆ rb_tree_clear()

int rb_tree_clear ( LwpaRbTree * self )

Clear all values from a red-black tree.

The node memory is deallocated using the rb_node_dealloc_f provided in rb_tree_init(); the user is responsible for deallocating the value memory.

Parameters

[in] self Tree to clear.

Returns: 1 (the tree was cleared) or 0 (an error occurred).

◆ rb_tree_clear_with_cb()

int rb_tree_clear_with_cb	(	LwpaRbTree *	self,
		rb_tree_node_f	node_cb
	)

Clear all values from a red-black tree, calling back into the application for each node and value being removed.

The user provides a rb_tree_node_f callback function which is called for each node in the tree. The user is responsible for deallocating both the node and value memory.

Parameters

[in]	self	Tree to clear.
[in]	node_cb	Callback function to call with each node and value being removed.

Returns: 1 (the tree was cleared) or 0 (an error occurred).

◆ rb_tree_find()

void* rb_tree_find	(	LwpaRbTree *	self,
		void *	value
	)

Find a value in a red-black tree.

Uses the rb_tree_node_cmp_f provided in rb_tree_init() to compare values. Lookup guaranteed in log(n) time.

Parameters

[in]	self	Tree in which to find the value.
[in]	value	Value to find.

Returns: Pointer to the value (value found) or NULL (value not found).

◆ rb_tree_init()

LwpaRbTree* rb_tree_init	(	LwpaRbTree *	self,
		rb_tree_node_cmp_f	node_cmp_cb,
		rb_node_alloc_f	alloc_f,
		rb_node_dealloc_f	dealloc_f
	)

Initialize a red-black tree node.

This function must be called on a new red-black tree before performing any other operations on it.

Parameters

[in]	self	The tree to be initialized.
[in]	node_cmp_cb	A function to use for comparing values in the tree.
[in]	alloc_f	A function to use for allocating new node structures.
[in]	dealloc_f	A function to use for deallocating node structures.

Returns: Pointer to the tree that was initialized.

◆ rb_tree_insert()

int rb_tree_insert	(	LwpaRbTree *	self,
		void *	value
	)

Insert a new value into a red-black tree.

If the value did not already exist in the tree, a new node is allocated using the rb_node_alloc_f provided in rb_tree_init(). Uses the rb_tree_node_cmp_f provided in rb_tree_init() to compare values. Insertion guaranteed in log(n) time.

Parameters

[in]	self	Tree in which to insert the value.
[in]	value	Value to insert.

Returns: 1 (the value was inserted or the value already existed in the tree) or 0 (an error occurred).

◆ rb_tree_insert_node()

int rb_tree_insert_node	(	LwpaRbTree *	self,
		LwpaRbNode *	node
	)

Insert a node containing a new value into a red-black tree.

The node is supplied by the caller and its memory must remain valid as long as it remains in the tree. Uses the rb_tree_node_cmp_f provided in rb_tree_init() to compare values. Insertion guaranteed in log(n) time.

Parameters

[in]	self	Tree in which to insert the value.
[in]	node	Node containing value to insert. Must have been previously initialized using rb_node_init().

Returns: 1 (the value was inserted or the value already existed in the tree) or 0 (an error occurred).

◆ rb_tree_node_cmp_ptr_cb()

int rb_tree_node_cmp_ptr_cb	(	const LwpaRbTree *	self,
		const LwpaRbNode *	a,
		const LwpaRbNode *	b
	)

The default node comparison callback.

This function can be supplied as an argument to any function that takes a rb_tree_node_cmp_f. Simply compares the pointer addresses of the two node values.

◆ rb_tree_node_dealloc_cb()

void rb_tree_node_dealloc_cb	(	const LwpaRbTree *	self,
		LwpaRbNode *	node
	)

The default node deallocation callback.

This function can be supplied as an argument to any function that takes a rb_tree_node_f. Simply deallocates the node using the tree's dealloc_f.

◆ rb_tree_remove()

int rb_tree_remove	(	LwpaRbTree *	self,
		void *	value
	)

Remove a value from a red-black tree.

The node memory is deallocated using the rb_node_dealloc_f provided in rb_tree_init(); the user is responsible for deallocating the value memory. Uses the rb_tree_node_cmp_f provided in rb_tree_init() to compare values. Removal guaranteed in log(n) time.

Parameters

[in]	self	Tree from which to remove the value.
[in]	value	Value to remove.

Returns: 1 (the value was removed) or 0 (the value did not exist in the tree or an error occurred).

◆ rb_tree_remove_with_cb()

int rb_tree_remove_with_cb	(	LwpaRbTree *	self,
		void *	value,
		rb_tree_node_f	node_cb
	)

Remove a value from a red-black tree, calling back into the application with the node and value being removed.

The user provides a rb_tree_node_f callback function and is responsible for deallocating both the node and value memory. Uses the rb_tree_node_cmp_f provided in rb_tree_init() to compare values. Removal guaranteed in log(n) time.

Parameters

[in]	self	Tree from which to remove the value.
[in]	value	Value to remove.
[in]	node_cb	Callback function to call with the node and value being removed.

Returns: 1 (the value was removed) or 0 (the value did not exist in the tree or an error occurred).

◆ rb_tree_size()

size_t rb_tree_size ( LwpaRbTree * self )

Get the current number of values in a red-black tree.

Parameters

[in] self The tree of which to get the size.

Returns: The number of values currently in the tree.

◆ rb_tree_test()

int rb_tree_test	(	LwpaRbTree *	self,
		LwpaRbNode *	root
	)

Test the validity of a red-black tree.

A debugging function; tests that both basic binary tree rules and specific red-black rules are not violated.

Parameters

[in]	self	Tree to test.
[in]	root	Node at which to start the test. All nodes beneath this node will be tested.

Returns: 1 (no violations were found) or 0 (a violation was found).

Overview

Data Structures

Macros

Typedefs

Functions

Callback Functions

Typedef Documentation

◆ LwpaRbIter

◆ rb_node_alloc_f

◆ rb_node_dealloc_f

◆ rb_tree_node_cmp_f

◆ rb_tree_node_f

Function Documentation

◆ rb_iter_first()

◆ rb_iter_init()

◆ rb_iter_last()

◆ rb_iter_next()

◆ rb_iter_prev()

◆ rb_node_init()

◆ rb_tree_clear()

◆ rb_tree_clear_with_cb()

◆ rb_tree_find()

◆ rb_tree_init()

◆ rb_tree_insert()

◆ rb_tree_insert_node()

◆ rb_tree_node_cmp_ptr_cb()

◆ rb_tree_node_dealloc_cb()

◆ rb_tree_remove()

◆ rb_tree_remove_with_cb()

◆ rb_tree_size()

◆ rb_tree_test()