rbtree.h File Reference

#include <kernel/defs.h>
#include <stdint.h>
#include <sys/list.h>

Include dependency graph for rbtree.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

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 struct rbnode	rbnode_t
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.

Typedef Documentation

rbnode_t

typedef struct rbnode rbnode_t

Definition at line 8 of file rbtree.h.