EtcPal  0.4.1
ETC Platform Abstraction Layer (EtcPal)
View other versions:
rbtree (Red-Black Trees)

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
}
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);
found = etcpal_rbtree_find(&tree, &struct_2); // found == NULL
EXPECT_EQ(etcpal_rbtree_size(&tree), 0);
etcpal_error_t
A set of error codes that can be returned by library functions.
Definition: error.h:49
etcpal_error_t etcpal_rbtree_clear(EtcPalRbTree *self)
Clear all values from a red-black tree.
Definition: rbtree.c:518
void * etcpal_rbiter_first(EtcPalRbIter *self, EtcPalRbTree *tree)
Point a red-black tree iterator at the first value in the tree.
Definition: rbtree.c:731
etcpal_error_t etcpal_rbtree_remove(EtcPalRbTree *self, const void *value)
Remove a value from a red-black tree.
Definition: rbtree.c:381
void * etcpal_rbtree_find(EtcPalRbTree *self, const void *value)
Find a value in a red-black tree.
Definition: rbtree.c:209
void * etcpal_rbiter_next(EtcPalRbIter *self)
Advance a red-black tree iterator.
Definition: rbtree.c:760
EtcPalRbTree * etcpal_rbtree_init(EtcPalRbTree *self, EtcPalRbTreeNodeCmpFunc node_cmp_cb, EtcPalRbNodeAllocFunc alloc_f, EtcPalRbNodeDeallocFunc dealloc_f)
Initialize a red-black tree node.
Definition: rbtree.c:156
size_t etcpal_rbtree_size(EtcPalRbTree *self)
Get the current number of values in a red-black tree.
Definition: rbtree.c:580
EtcPalRbIter * etcpal_rbiter_init(EtcPalRbIter *self)
Initialize a red-black tree iterator.
Definition: rbtree.c:652
etcpal_error_t etcpal_rbtree_insert(EtcPalRbTree *self, void *value)
Insert a new value into a red-black tree.
Definition: rbtree.c:247
A red-black tree iterator.
Definition: rbtree.h:223
A red-black tree node.
Definition: rbtree.h:196
A red-black tree.
Definition: rbtree.h:208

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...
 
EtcPalRbNodeetcpal_rbnode_init (EtcPalRbNode *self, void *value)
 Initialize a red-black tree node. More...
 
EtcPalRbTreeetcpal_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...
 
EtcPalRbIteretcpal_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]nodePointer 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]selfThe tree in which two values are being compared.
[in]value_aThe first node being compared.
[in]value_bThe 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]selfThe tree in which the node resides.
[in]nodeThe 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]selfIterator to point at the first value.
[in]treeTree 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]selfThe 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]selfIterator to point at the last value.
[in]treeTree 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]selfIterator to modify.
[in]treeTree of which to get the lower bound.
[in]valueThe 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]selfIterator 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]selfIterator 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]selfIterator to modify.
[in]treeTree of which to get the upper bound.
[in]valueThe 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]selfThe node to be initialized.
[in]valuePointer 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]selfTree 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]selfTree to clear.
[in]node_cbCallback 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]selfTree in which to find the value.
[in]valueValue 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]selfThe tree to be initialized.
[in]node_cmp_cbA function to use for comparing values in the tree.
[in]alloc_fA function to use for allocating new node structures.
[in]dealloc_fA 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]selfTree in which to insert the value.
[in]valueValue 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]selfTree in which to insert the value.
[in]nodeNode 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]selfTree from which to remove the value.
[in]valueValue 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]selfTree from which to remove the value.
[in]valueValue to remove.
[in]node_cbCallback 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]selfThe 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]selfTree to test.
[in]rootNode 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.