Overview

A red-black tree implementation.

#include "etcpal/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.

If you have access to C++, just use std::map or std::set. They're much nicer than this module.

Red-black tree nodes store arbitrary data as a void* pointer, which are compared with a user-provided EtcPalRbTreeNodeCmpFunc. The module user must also manage memory allocation for each node of the red-black tree by providing an EtcPalRbNodeAllocFunc and EtcPalRbNodeDeallocFunc, which must allocate and deallocate EtcPalRbNode instances. Note: if you don't have access to a malloc() implementation, mempool (Memory Pools) is a convenient way to allocate nodes.

typedef struct MyStruct
{
  int key;
} MyStruct;
 
int compare_func(const EtcPalRbTree* self, const void* value_a, const void* value_b)
{
  const MyStruct* a = (const MyStruct*)value_a;
  const MyStruct* b = (const MyStruct*)value_b;
  return (a->key > b->key) - (a->key < b->key);
}
 
EtcPalRbNode* node_alloc_func()
{
  return (EtcPalRbNode*)malloc(sizeof(EtcPalRbNode)); // Or some other method you define
}
 
void node_dealloc_func(EtcPalRbNode* node)
{
  free(node); // Or some other method you define
}
 
EtcPalRbTree tree;
etcpal_rbtree_init(&tree, compare_func, node_alloc_func, node_dealloc_func);
 
MyStruct struct_1;
struct_1.key = 20;
etcpal_rbtree_insert(&tree, &struct_1);
 
MyStruct struct_2;
struct_2.key = 30;
etcpal_rbtree_insert(&tree, &struct_2);
 
EXPECT_EQ(etcpal_rbtree_size(&tree), 2);
 
MyStruct* found = etcpal_rbtree_find(&struct_1); // found == &struct_1
found = etcpal_rbtree_find(&struct_2); // found == &struct_2
 
etcpal_error_t insert_res = etcpal_rbtree_insert(&tree, &struct_1); // insert_res == kEtcPalErrExists
 
EtcPalRbIter tree_iter;
etcpal_rbiter_init(&tree_iter);
MyStruct* iter_val = etcpal_rbiter_first(&iter, &tree); // iter_val == &struct_1
iter_val = etcpal_rbiter_next(&tree_iter); // iter_val == &struct_2
iter_val = etcpal_rbiter_next(&tree_iter); // iter_val == NULL
 
etcpal_rbtree_remove(&tree, &struct_1);
found = etcpal_rbtree_find(&tree, &struct_1); // found == NULL
EXPECT_EQ(etcpal_rbtree_size(&tree), 1);
 
etcpal_rbtree_clear(&tree);
found = etcpal_rbtree_find(&tree, &struct_2); // found == NULL
EXPECT_EQ(etcpal_rbtree_size(&tree), 0);

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

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

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

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

Typedefs
typedef struct EtcPalRbIter	EtcPalRbIter
	A red-black tree iterator. More...

Functions
int	etcpal_rbtree_node_cmp_ptr_cb (const EtcPalRbTree self, const void a, const void *b)
	The default node comparison callback. More...

void	etcpal_rbtree_node_dealloc_cb (const EtcPalRbTree self, EtcPalRbNode node)
	The default node deallocation callback. More...

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

EtcPalRbTree *	etcpal_rbtree_init (EtcPalRbTree *self, EtcPalRbTreeNodeCmpFunc node_cmp_cb, EtcPalRbNodeAllocFunc alloc_f, EtcPalRbNodeDeallocFunc dealloc_f)
	Initialize a red-black tree node. More...

void *	etcpal_rbtree_find (EtcPalRbTree self, const void value)
	Find a value in a red-black tree. More...

etcpal_error_t	etcpal_rbtree_insert (EtcPalRbTree self, void value)
	Insert a new value into a red-black tree. More...

etcpal_error_t	etcpal_rbtree_remove (EtcPalRbTree self, const void value)
	Remove a value from a red-black tree. More...

etcpal_error_t	etcpal_rbtree_clear (EtcPalRbTree *self)
	Clear all values from a red-black tree. More...

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

etcpal_error_t	etcpal_rbtree_insert_node (EtcPalRbTree self, EtcPalRbNode node)
	Insert a node containing a new value into a red-black tree. More...

etcpal_error_t	etcpal_rbtree_remove_with_cb (EtcPalRbTree self, const void value, EtcPalRbTreeNodeFunc node_cb)
	Remove a value from a red-black tree, calling back into the application with the node and value being removed. More...

etcpal_error_t	etcpal_rbtree_clear_with_cb (EtcPalRbTree *self, EtcPalRbTreeNodeFunc node_cb)
	Clear all values from a red-black tree, calling back into the application for each node and value being removed. More...

int	etcpal_rbtree_test (EtcPalRbTree self, EtcPalRbNode root)
	Test the validity of a red-black tree. More...

EtcPalRbIter *	etcpal_rbiter_init (EtcPalRbIter *self)
	Initialize a red-black tree iterator. More...

void *	etcpal_rbiter_first (EtcPalRbIter self, EtcPalRbTree tree)
	Point a red-black tree iterator at the first value in the tree. More...

void *	etcpal_rbiter_last (EtcPalRbIter self, EtcPalRbTree tree)
	Point a red-black tree iterator at the last value in the tree. More...

void *	etcpal_rbiter_next (EtcPalRbIter *self)
	Advance a red-black tree iterator. More...

void *	etcpal_rbiter_prev (EtcPalRbIter *self)
	Reverse-advance a red-black tree iterator. More...

void *	etcpal_rbiter_lower_bound (EtcPalRbIter self, EtcPalRbTree tree, const void *value)
	Point a red-black tree iterator to the lower-bound of a value. More...

void *	etcpal_rbiter_upper_bound (EtcPalRbIter self, EtcPalRbTree tree, const void *value)
	Point a red-black tree iterator to the upper-bound of a value. More...

Callback Functions
typedef int(*	EtcPalRbTreeNodeCmpFunc) (const EtcPalRbTree self, const void value_a, const void *value_b)
	A function type that compares two value instances contained in a tree. More...

typedef void(*	EtcPalRbTreeNodeFunc) (const EtcPalRbTree self, EtcPalRbNode node)
	A function type to be called for each node in a tree. More...

typedef EtcPalRbNode (	EtcPalRbNodeAllocFunc) (void)
	A function type to allocate a new node. More...

typedef void(*	EtcPalRbNodeDeallocFunc) (EtcPalRbNode *node)
	A function type to deallocate a node. More...

Typedef Documentation

◆ EtcPalRbIter

typedef struct EtcPalRbIter EtcPalRbIter

A red-black tree iterator.

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

◆ EtcPalRbNodeAllocFunc

typedef EtcPalRbNode*(* EtcPalRbNodeAllocFunc) (void)

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 etcpal_rbtree_insert().

Returns: Pointer to the newly allocated node.

◆ EtcPalRbNodeDeallocFunc

typedef void(* EtcPalRbNodeDeallocFunc) (EtcPalRbNode *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 etcpal_rbtree_remove() and etcpal_rbtree_clear().

Parameters

[in] node Pointer to node to deallocate.

◆ EtcPalRbTreeNodeCmpFunc

typedef int(* EtcPalRbTreeNodeCmpFunc) (const EtcPalRbTree *self, const void *value_a, const void *value_b)

A function type that compares two value instances contained in a tree.

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

Parameters

[in]	self	The tree in which two values are being compared.
[in]	value_a	The first node being compared.
[in]	value_b	The second node being compared.

Returns: < 0: value_a is less than value_b; 0: value_a is equal to value_b; > 0: value_a is greater than value_b

◆ EtcPalRbTreeNodeFunc

typedef void(* EtcPalRbTreeNodeFunc) (const EtcPalRbTree *self, EtcPalRbNode *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, etcpal_rbtree_node_dealloc_cb(), is provided which simply calls the tree's EtcPalRbNodeDeallocFunc 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

◆ etcpal_rbiter_first()

void* etcpal_rbiter_first	(	EtcPalRbIter *	self,
		EtcPalRbTree *	tree
	)

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

The first value is the lowest, as determined by the EtcPalRbTreeNodeCmpFunc provided in etcpal_rbtree_init(). Use etcpal_rbiter_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).

◆ etcpal_rbiter_init()

EtcPalRbIter* etcpal_rbiter_init ( EtcPalRbIter * self )

Initialize a red-black tree iterator.

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

Parameters

[in] self The iterator to be initialized.

Returns: Pointer to the iterator that was initialized.

◆ etcpal_rbiter_last()

void* etcpal_rbiter_last	(	EtcPalRbIter *	self,
		EtcPalRbTree *	tree
	)

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

The last value is the highest, as determined by the EtcPalRbTreeNodeCmpFunc provided in etcpal_rbtree_init(). Use etcpal_rbiter_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).

◆ etcpal_rbiter_lower_bound()

void* etcpal_rbiter_lower_bound	(	EtcPalRbIter *	self,
		EtcPalRbTree *	tree,
		const void *	value
	)

Point a red-black tree iterator to the lower-bound of a value.

Gets the first value in the tree that is not considered to go before the given value.

Parameters

[in]	self	Iterator to modify.
[in]	tree	Tree of which to get the lower bound.
[in]	value	The value to compare against to determine the lower bound.

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

◆ etcpal_rbiter_next()

void* etcpal_rbiter_next ( EtcPalRbIter * self )

Advance a red-black tree iterator.

Gets the next higher value in the tree as determined by the EtcPalRbTreeNodeCmpFunc provided in etcpal_rbtree_init().

Parameters

[in] self Iterator to advance.

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

◆ etcpal_rbiter_prev()

void* etcpal_rbiter_prev ( EtcPalRbIter * self )

Reverse-advance a red-black tree iterator.

Gets the next lower value in the tree as determined by the EtcPalRbTreeNodeCmpFunc provided in etcpal_rbtree_init().

Parameters

[in] self Iterator to reverse-advance.

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

◆ etcpal_rbiter_upper_bound()

void* etcpal_rbiter_upper_bound	(	EtcPalRbIter *	self,
		EtcPalRbTree *	tree,
		const void *	value
	)

Point a red-black tree iterator to the upper-bound of a value.

Gets the first value in the tree that is considered to go after the given value.

Parameters

[in]	self	Iterator to modify.
[in]	tree	Tree of which to get the upper bound.
[in]	value	The value to compare against to determine the upper bound.

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

◆ etcpal_rbnode_init()

EtcPalRbNode* etcpal_rbnode_init	(	EtcPalRbNode *	self,
		void *	value
	)

Initialize a red-black tree node.

This function must be called on a new node before inserting it manually using etcpal_rbtree_insert_node(). When using etcpal_rbtree_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.

◆ etcpal_rbtree_clear()

etcpal_error_t etcpal_rbtree_clear ( EtcPalRbTree * self )

Clear all values from a red-black tree.

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

If this function returns kEtcPalErrOk, all iterators created using the etcpal_rbiter_*() functions are invalidated.

Parameters

[in] self Tree to clear.

Returns: kEtcPalErrOk: The tree was cleared.; kEtcPalErrInvalid: Invalid argument provided.

◆ etcpal_rbtree_clear_with_cb()

etcpal_error_t etcpal_rbtree_clear_with_cb	(	EtcPalRbTree *	self,
		EtcPalRbTreeNodeFunc	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 EtcPalRbTreeNodeFunc callback function which is called for each node in the tree. The user is responsible for deallocating both the node and value memory.

If this function returns kEtcPalErrOk, all iterators created using the etcpal_rbiter_*() functions are invalidated.

Parameters

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

Returns: kEtcPalErrOk: The tree was cleared.; kEtcPalErrInvalid: Invalid argument provided.

◆ etcpal_rbtree_find()

void* etcpal_rbtree_find	(	EtcPalRbTree *	self,
		const void *	value
	)

Find a value in a red-black tree.

Uses the EtcPalRbTreeNodeCmpFunc provided in etcpal_rbtree_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).

◆ etcpal_rbtree_init()

EtcPalRbTree* etcpal_rbtree_init	(	EtcPalRbTree *	self,
		EtcPalRbTreeNodeCmpFunc	node_cmp_cb,
		EtcPalRbNodeAllocFunc	alloc_f,
		EtcPalRbNodeDeallocFunc	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.

◆ etcpal_rbtree_insert()

etcpal_error_t etcpal_rbtree_insert	(	EtcPalRbTree *	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 EtcPalRbNodeAllocFunc provided in etcpal_rbtree_init(). Uses the EtcPalRbTreeNodeCmpFunc provided in etcpal_rbtree_init() to compare values. Insertion guaranteed in log(n) time.

If this function returns kEtcPalErrOk, all iterators created using the etcpal_rbiter_*() functions are invalidated.

Parameters

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

Returns: kEtcPalErrOk: the value was inserted.; kEtcPalErrExists: the value already existed in the tree.; kEtcPalErrNoMem: Couldn't allocate new node.; kEtcPalErrInvalid: Invalid argument provided.

◆ etcpal_rbtree_insert_node()

etcpal_error_t etcpal_rbtree_insert_node	(	EtcPalRbTree *	self,
		EtcPalRbNode *	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 EtcPalRbTreeNodeCmpFunc provided in etcpal_rbtree_init() to compare values. Insertion guaranteed in log(n) time.

If this function returns kEtcPalErrOk, all iterators created using the etcpal_rbiter_*() functions are invalidated.

Parameters

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

Returns: kEtcPalErrOk: The value was inserted.; kEtcPalErrExists: The value already existed in the tree.; kEtcPalErrInvalid: Invalid argument provided.

◆ etcpal_rbtree_node_cmp_ptr_cb()

int etcpal_rbtree_node_cmp_ptr_cb	(	const EtcPalRbTree *	self,
		const void *	a,
		const void *	b
	)

The default node comparison callback.

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

◆ etcpal_rbtree_node_dealloc_cb()

void etcpal_rbtree_node_dealloc_cb	(	const EtcPalRbTree *	self,
		EtcPalRbNode *	node
	)

The default node deallocation callback.

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

◆ etcpal_rbtree_remove()

etcpal_error_t etcpal_rbtree_remove	(	EtcPalRbTree *	self,
		const void *	value
	)

Remove a value from a red-black tree.

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

If this function returns kEtcPalErrOk, all iterators created using the etcpal_rbiter_*() functions are invalidated.

Parameters

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

Returns: kEtcPalErrOk: The value was removed.; kEtcPalErrInvalid: Invalid argument provided.; kEtcPalErrNotFound: The value did not exist in the tree.

◆ etcpal_rbtree_remove_with_cb()

etcpal_error_t etcpal_rbtree_remove_with_cb	(	EtcPalRbTree *	self,
		const void *	value,
		EtcPalRbTreeNodeFunc	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 EtcPalRbTreeNodeFunc callback function and is responsible for deallocating both the node and value memory. Uses the EtcPalRbTreeNodeCmpFunc provided in etcpal_rbtree_init() to compare values. Removal guaranteed in log(n) time.

If this function returns kEtcPalErrOk, all iterators created using the etcpal_rbiter_*() functions are invalidated.

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: kEtcPalErrOk: The value was removed.; kEtcPalErrInvalid: Invalid argument provided.; kEtcPalErrNotFound: The value did not exist in the tree.

◆ etcpal_rbtree_size()

size_t etcpal_rbtree_size ( EtcPalRbTree * 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.

◆ etcpal_rbtree_test()

int etcpal_rbtree_test	(	EtcPalRbTree *	self,
		EtcPalRbNode *	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: The "black height" of the tree; the number of black nodes present in the traversal from the root to each leaf. A valid red-black tree requires this number to be the same for every possible traversal.; 0: Invalid tree.

Overview

Data Structures

Macros

Typedefs

Functions

Callback Functions

Typedef Documentation

◆ EtcPalRbIter

◆ EtcPalRbNodeAllocFunc

◆ EtcPalRbNodeDeallocFunc

◆ EtcPalRbTreeNodeCmpFunc

◆ EtcPalRbTreeNodeFunc

Function Documentation

◆ etcpal_rbiter_first()

◆ etcpal_rbiter_init()

◆ etcpal_rbiter_last()

◆ etcpal_rbiter_lower_bound()

◆ etcpal_rbiter_next()

◆ etcpal_rbiter_prev()

◆ etcpal_rbiter_upper_bound()

◆ etcpal_rbnode_init()

◆ etcpal_rbtree_clear()

◆ etcpal_rbtree_clear_with_cb()

◆ etcpal_rbtree_find()

◆ etcpal_rbtree_init()

◆ etcpal_rbtree_insert()

◆ etcpal_rbtree_insert_node()

◆ etcpal_rbtree_node_cmp_ptr_cb()

◆ etcpal_rbtree_node_dealloc_cb()

◆ etcpal_rbtree_remove()

◆ etcpal_rbtree_remove_with_cb()

◆ etcpal_rbtree_size()

◆ etcpal_rbtree_test()