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 cmp, 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.

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.

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.

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.

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.

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.

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