Augmented Red-Black Tree. More...

Collaboration diagram for Red-Black Tree:

Detailed Description

Augmented Red-Black Tree.

A Red-Black Tree (RBT) is a tree structure that maintains sorted data to allow for efficient insertion, deletion, and lookup operations with a worst case time complexity of O(log n).

Used As A Sorted Linked List

The name "Red-Black Tree" can be a bit confusing. To the user of the tree, it simply acts as a highly optimized sorted linked list.

The tree structure allows for more efficient operations compared to a standard linked list (O(log n) vs O(n)), and the red-black properties ensure that the tree remains balanced, preventing it from degenerating into a linear structure. However, the user of the tree does not need to be concerned with these implementation details.

Todo:: Cache minimum and maximum nodes for O(1) access.

Update Callbacks

The tree supports an optional update callback that is called whenever a node is inserted, removed or swapped. This allows for the tree to be "augmented" with additional data. For example, if you wanted to track the global minimum of some value in each node, you could do so by updating the minimum value in the update callback, such that you no longer need to traverse the tree to find the minimum. Very useful for the scheduler.

See also: Wikipedia Red-Black Tree for more information on Red-Black Trees.; Earliest Eligible Virtual Deadline First for the original paper describing EEVDF, contains some usefull information on balanced trees.

Data Structures
struct	rbnode_t
	Red-Black Tree Node. More...

struct	rbtree_t
	Red-Black Tree. More...

Macros
#define	RBNODE_OPPOSITE(direction) ((rbnode_direction_t)(1 - (direction)))
	Get the opposite direction (left <-> right).

#define	RBNODE_FROM_PARENT(node) ((rbnode_direction_t)((node)->parent->children[RBNODE_RIGHT] == (node) ? RBNODE_RIGHT : RBNODE_LEFT))
	Get the direction of a node from its parent.

#define	RBNODE_CREATE
	Create a Red-Black Tree Node initializer.

#define	RBTREE_FOR_EACH(elem, tree, member)
	Iterates over a Red-Black Tree in ascending order.

#define	RBTREE_FOR_EACH_REVERSE(elem, tree, member)
	Iterates over a Red-Black Tree in descending order.

Typedefs
typedef int64_t(*	rbnode_compare_t) (const rbnode_t a, const rbnode_t b)
	Comparison function for Red-Black Tree nodes.

typedef void(*	rbnode_update_t) (rbnode_t *node)
	Update function for Red-Black Tree nodes.

Enumerations
enum	rbnode_color_t { RBNODE_RED = 0 , RBNODE_BLACK = 1 }
	Red-Black Tree Node Colors. More...

enum	rbnode_direction_t { RBNODE_LEFT = 0 , RBNODE_RIGHT = 1 , RBNODE_AMOUNT = 2 }
	Red-Black Tree Node Directions. More...

Functions
void	rbtree_init (rbtree_t *tree, rbnode_compare_t compare, rbnode_update_t update)
	Initialize a Red-Black Tree.

rbnode_t *	rbtree_rotate (rbtree_t tree, rbnode_t node, rbnode_direction_t direction)
	Rotate a node in the Red-Black Tree.

rbnode_t *	rbtree_find_min (rbnode_t *node)
	Find the minimum node in a subtree.

rbnode_t *	rbtree_find_max (rbnode_t *node)
	Find the maximum node in a subtree.

void	rbtree_swap (rbtree_t tree, rbnode_t a, rbnode_t *b)
	Swap two nodes in the Red-Black Tree.

void	rbtree_insert (rbtree_t tree, rbnode_t node)
	Insert a node into the Red-Black Tree.

void	rbtree_remove (rbtree_t tree, rbnode_t node)
	Remove a node from the Red-Black Tree.

void	rbtree_fix (rbtree_t tree, rbnode_t node)
	Move the node to its correct position in the Red-Black Tree.

bool	rbtree_is_empty (const rbtree_t *tree)
	Check if the Red-Black Tree is empty.

rbnode_t *	rbtree_next (const rbnode_t *node)
	Get the next node in the tree, in predecessor order.

rbnode_t *	rbtree_prev (const rbnode_t *node)
	Get the previous node in the tree, in predecessor order.

Macro Definition Documentation

◆ RBNODE_OPPOSITE

#define RBNODE_OPPOSITE ( direction ) ((rbnode_direction_t)(1 - (direction)))

Get the opposite direction (left <-> right).

Parameters

direction The direction to get the opposite of.

Returns: The opposite direction.

Definition at line 74 of file rbtree.h.

◆ RBNODE_FROM_PARENT

#define RBNODE_FROM_PARENT ( node ) ((rbnode_direction_t)((node)->parent->children[RBNODE_RIGHT] == (node) ? RBNODE_RIGHT : RBNODE_LEFT))

Get the direction of a node from its parent.

Parameters

node	The node to get the direction of.

Returns: The direction of the node from its parent.

Definition at line 82 of file rbtree.h.

◆ RBNODE_CREATE

#define RBNODE_CREATE

Value:

    (rbnode_t) \
    { \
        .parent = NULL, .children = {NULL, NULL}, .color = RBNODE_RED \
    }

Create a Red-Black Tree Node initializer.

Returns: A Red-Black Tree Node initializer.

Definition at line 104 of file rbtree.h.

◆ RBTREE_FOR_EACH

#define RBTREE_FOR_EACH	(	elem,
		tree,
		member
	)

Value:

    for ((elem) = \
             ((tree)->root != NULL ? CONTAINER_OF(rbtree_find_min((tree)->root), typeof(*(elem)), member) : NULL); \
        (elem) != NULL; (elem) = (rbtree_next(&(elem)->member) != NULL \
                                ? CONTAINER_OF(rbtree_next(&(elem)->member), typeof(*(elem)), member) \
                                : NULL))

Iterates over a Red-Black Tree in ascending order.

Parameters

elem	The loop variable, a pointer to the structure containing the tree node.
tree	A pointer to the `rbtree_t` structure to iterate over.
member	The name of the `rbnode_t` member within the structure `elem`.

Definition at line 259 of file rbtree.h.

◆ RBTREE_FOR_EACH_REVERSE

#define RBTREE_FOR_EACH_REVERSE	(	elem,
		tree,
		member
	)

Value:

    for ((elem) = \
             ((tree)->root != NULL ? CONTAINER_OF(rbtree_find_max((tree)->root), typeof(*(elem)), member) : NULL); \
        (elem) != NULL; (elem) = (rbtree_prev(&(elem)->member) != NULL \
                                ? CONTAINER_OF(rbtree_prev(&(elem)->member), typeof(*(elem)), member) \
                                : NULL))

Iterates over a Red-Black Tree in descending order.

Parameters

elem	The loop variable, a pointer to the structure containing the tree node.
tree	A pointer to the `rbtree_t` structure to iterate over.
member	The name of the `rbnode_t` member within the structure `elem`.

Definition at line 272 of file rbtree.h.

Typedef Documentation

◆ rbnode_compare_t

typedef int64_t(* rbnode_compare_t) (const rbnode_t *a, const rbnode_t *b)

Comparison function for Red-Black Tree nodes.

Should return:

A negative value if a is less than b.
Zero if a is equal to b.
A positive value if a is greater than b.

Parameters

a	The first node to compare.
b	The second node to compare.

Returns: The comparison result.

Definition at line 122 of file rbtree.h.

◆ rbnode_update_t

typedef void(* rbnode_update_t) (rbnode_t *node)

Update function for Red-Black Tree nodes.

Called whenever a node is inserted, removed or swapped.

Parameters

node	The node to update.

Definition at line 131 of file rbtree.h.

Enumeration Type Documentation

◆ rbnode_color_t

enum rbnode_color_t

Red-Black Tree Node Colors.

Enumerator
RBNODE_RED
RBNODE_BLACK

Definition at line 49 of file rbtree.h.

◆ rbnode_direction_t

enum rbnode_direction_t

Red-Black Tree Node Directions.

Used to index into the children array of a rbnode_t.

Enumerator
RBNODE_LEFT
RBNODE_RIGHT
RBNODE_AMOUNT

Definition at line 61 of file rbtree.h.

Function Documentation

◆ rbtree_init()

void rbtree_init	(	rbtree_t *	tree,
		rbnode_compare_t	compare,
		rbnode_update_t	update
	)

Initialize a Red-Black Tree.

Will not allocate any memory.

Parameters

tree	The tree to initialize.
compare	The comparison function to use.
update	The update function to use, or `NULL`.

Definition at line 30 of file rbtree.c.

Here is the caller graph for this function:

◆ rbtree_rotate()

rbnode_t * rbtree_rotate	(	rbtree_t *	tree,
		rbnode_t *	node,
		rbnode_direction_t	direction
	)

Rotate a node in the Red-Black Tree.

See also: https://upload.wikimedia.org/wikipedia/commons/f/f2/Binary_Tree_Rotation_%28animated%29.gif for a animation of tree rotations.

Parameters

tree	The tree containing the node to rotate.
node	The node to rotate.
direction	The direction to rotate.

Returns: The new root of the rotated subtree.

Definition at line 41 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rbtree_find_min()

rbnode_t * rbtree_find_min ( rbnode_t * node )

Find the minimum node in a subtree.

This is the same as just going as far left as possible.

Parameters

node	The root of the subtree.

Returns: The minimum node in the subtree.

Definition at line 186 of file rbtree.c.

Here is the caller graph for this function:

◆ rbtree_find_max()

rbnode_t * rbtree_find_max ( rbnode_t * node )

Find the maximum node in a subtree.

This is the same as just going as far right as possible.

Parameters

node	The root of the subtree.

Returns: The maximum node in the subtree.

Definition at line 201 of file rbtree.c.

Here is the caller graph for this function:

◆ rbtree_swap()

void rbtree_swap	(	rbtree_t *	tree,
		rbnode_t *	a,
		rbnode_t *	b
	)

Swap two nodes in the Red-Black Tree.

Needed as the structure is intrusive, so we can't just swap the data.

Parameters

tree	The tree containing the nodes to swap.
a	The first node to swap.
b	The second node to swap.

Definition at line 216 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rbtree_insert()

void rbtree_insert	(	rbtree_t *	tree,
		rbnode_t *	node
	)

Insert a node into the Red-Black Tree.

Parameters

tree	The tree to insert into.
node	The node to insert.

Definition at line 150 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rbtree_remove()

void rbtree_remove	(	rbtree_t *	tree,
		rbnode_t *	node
	)

Remove a node from the Red-Black Tree.

Parameters

tree	The tree to remove from.
node	The node to remove.

Definition at line 374 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rbtree_fix()

void rbtree_fix	(	rbtree_t *	tree,
		rbnode_t *	node
	)

Move the node to its correct position in the Red-Black Tree.

Should be called whenever the metric used for comparison changes.

Todo:: Currently just calls rbtree_remove() followed by rbtree_insert(), could be optimized?

Parameters

tree	The tree containing the node to update.
node	The node to update.

Definition at line 530 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rbtree_is_empty()

bool rbtree_is_empty ( const rbtree_t * tree )

Check if the Red-Black Tree is empty.

Parameters

tree	The tree to check.

Returns: true if the tree is empty, false otherwise.

Definition at line 539 of file rbtree.c.

Here is the caller graph for this function:

◆ rbtree_next()

rbnode_t * rbtree_next ( const rbnode_t * node )

Get the next node in the tree, in predecessor order.

Parameters

node	The current node.

Returns: The next node in the tree, or NULL if node is the last node.

Definition at line 546 of file rbtree.c.

Here is the call graph for this function:

◆ rbtree_prev()

rbnode_t * rbtree_prev ( const rbnode_t * node )

Get the previous node in the tree, in predecessor order.

Parameters

node	The current node.

Returns: The previous node in the tree, or NULL if node is the first node.

Definition at line 568 of file rbtree.c.

Here is the call graph for this function:

Detailed Description

Used As A Sorted Linked List

Update Callbacks

Data Structures

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ RBNODE_OPPOSITE

◆ RBNODE_FROM_PARENT

◆ RBNODE_CREATE

◆ RBTREE_FOR_EACH

◆ RBTREE_FOR_EACH_REVERSE

Typedef Documentation

◆ rbnode_compare_t

◆ rbnode_update_t

Enumeration Type Documentation

◆ rbnode_color_t

◆ rbnode_direction_t

Function Documentation

◆ rbtree_init()

◆ rbtree_rotate()

◆ rbtree_find_min()

◆ rbtree_find_max()

◆ rbtree_swap()

◆ rbtree_insert()

◆ rbtree_remove()

◆ rbtree_fix()

◆ rbtree_is_empty()

◆ rbtree_next()

◆ rbtree_prev()