rbtree.c File Reference

#include <kernel/utils/rbtree.h>
#include <assert.h>

Include dependency graph for rbtree.c:

Go to the source code of this file.

Functions
static void	rbtree_update (rbtree_t *tree, rbnode_t *node)
static void	rbtree_update_to_root (rbtree_t *tree, rbnode_t *node)
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.
static void	rbtree_insert_at (rbtree_t *tree, rbnode_t *parent, rbnode_t *node, rbnode_direction_t direction)
void	rbtree_insert (rbtree_t *tree, rbnode_t *node)
	Insert a node into 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.
static void	rbtree_remove_sanitize (rbtree_t *tree, rbnode_t *node)
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.

Function Documentation

rbtree_update()

static void rbtree_update ( rbtree_t *  tree, rbnode_t *  node  )

inlinestatic

Definition at line 5 of file rbtree.c.

Here is the caller graph for this function:

rbtree_update_to_root()

static void rbtree_update_to_root ( rbtree_t *  tree, rbnode_t *  node  )

inlinestatic

Todo:

This could be optimized to avoid updating nodes multiple times for overlapping paths.

Definition at line 16 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

rbtree_insert_at()

static void rbtree_insert_at ( rbtree_t *  tree, rbnode_t *  parent, rbnode_t *  node, rbnode_direction_t  direction  )

static

Definition at line 86 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

rbtree_remove_sanitize()

static void rbtree_remove_sanitize ( rbtree_t *  tree, rbnode_t *  node  )

static

Definition at line 357 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function: