rbtree.h File Reference

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	rb_node_
struct	rb_tree_

Macros
#define	RBTREE_TNIL_INDEX   0

Typedefs
typedef u32	rb_node_index_t
typedef enum rb_tree_color_	rb_node_color_t
typedef struct rb_node_	rb_node_t
typedef struct rb_tree_	rb_tree_t
typedef int(*	rb_tree_lt_fn) (u32 a, u32 b)

Enumerations
enum	rb_tree_color_ { RBTREE_RED, RBTREE_BLACK }

Functions
void	rb_tree_init (rb_tree_t *rt)
rb_node_index_t	rb_tree_add (rb_tree_t *rt, u32 key)
rb_node_index_t	rb_tree_add2 (rb_tree_t *rt, u32 key, uword opaque)
rb_node_index_t	rb_tree_add_custom (rb_tree_t *rt, u32 key, uword opaque, rb_tree_lt_fn ltfn)
void	rb_tree_del (rb_tree_t *rt, u32 key)
void	rb_tree_del_node (rb_tree_t *rt, rb_node_t *z)
void	rb_tree_del_custom (rb_tree_t *rt, u32 key, rb_tree_lt_fn ltfn)
void	rb_tree_free_nodes (rb_tree_t *rt)
u32	rb_tree_n_nodes (rb_tree_t *rt)
rb_node_t *	rb_tree_min_subtree (rb_tree_t *rt, rb_node_t *x)
rb_node_t *	rb_tree_max_subtree (rb_tree_t *rt, rb_node_t *x)
rb_node_t *	rb_tree_search_subtree (rb_tree_t *rt, rb_node_t *x, u32 key)
rb_node_t *	rb_tree_search_subtree_custom (rb_tree_t *rt, rb_node_t *x, u32 key, rb_tree_lt_fn ltfn)
rb_node_t *	rb_tree_successor (rb_tree_t *rt, rb_node_t *x)
rb_node_t *	rb_tree_predecessor (rb_tree_t *rt, rb_node_t *x)
int	rb_tree_is_init (rb_tree_t *rt)
static rb_node_index_t	rb_node_index (rb_tree_t *rt, rb_node_t *n)
static u8	rb_node_is_tnil (rb_tree_t *rt, rb_node_t *n)
static rb_node_t *	rb_node (rb_tree_t *rt, rb_node_index_t ri)
static rb_node_t *	rb_node_right (rb_tree_t *rt, rb_node_t *n)
static rb_node_t *	rb_node_left (rb_tree_t *rt, rb_node_t *n)
static rb_node_t *	rb_node_parent (rb_tree_t *rt, rb_node_t *n)

Macro Definition Documentation

RBTREE_TNIL_INDEX

#define RBTREE_TNIL_INDEX   0

Definition at line 22 of file rbtree.h.

Typedef Documentation

rb_node_color_t

typedef enum rb_tree_color_ rb_node_color_t

rb_node_index_t

typedef u32 rb_node_index_t

Definition at line 24 of file rbtree.h.

rb_node_t

typedef struct rb_node_ rb_node_t

rb_tree_lt_fn

typedef int(* rb_tree_lt_fn) (u32 a, u32 b)

Definition at line 48 of file rbtree.h.

rb_tree_t

typedef struct rb_tree_ rb_tree_t

Enumeration Type Documentation

rb_tree_color_

enum rb_tree_color_

Enumerator
RBTREE_RED
RBTREE_BLACK

Definition at line 26 of file rbtree.h.

Function Documentation

rb_node()

static rb_node_t* rb_node ( rb_tree_t *  rt, rb_node_index_t  ri  )

inlinestatic

Definition at line 82 of file rbtree.h.

Here is the caller graph for this function:

rb_node_index()

static rb_node_index_t rb_node_index ( rb_tree_t *  rt, rb_node_t *  n  )

inlinestatic

Definition at line 70 of file rbtree.h.

Here is the caller graph for this function:

rb_node_is_tnil()

static u8 rb_node_is_tnil ( rb_tree_t *  rt, rb_node_t *  n  )

inlinestatic

Definition at line 76 of file rbtree.h.

Here is the call graph for this function:

Here is the caller graph for this function:

rb_node_left()

static rb_node_t* rb_node_left ( rb_tree_t *  rt, rb_node_t *  n  )

inlinestatic

Definition at line 94 of file rbtree.h.

Here is the caller graph for this function:

rb_node_parent()

static rb_node_t* rb_node_parent ( rb_tree_t *  rt, rb_node_t *  n  )

inlinestatic

Definition at line 100 of file rbtree.h.

Here is the caller graph for this function:

rb_node_right()

static rb_node_t* rb_node_right ( rb_tree_t *  rt, rb_node_t *  n  )

inlinestatic

Definition at line 88 of file rbtree.h.

Here is the caller graph for this function:

rb_tree_add()

rb_node_index_t rb_tree_add	(	rb_tree_t *	rt,
		u32	key
	)

Definition at line 170 of file rbtree.c.

Here is the call graph for this function:

rb_tree_add2()

rb_node_index_t rb_tree_add2	(	rb_tree_t *	rt,
		u32	key,
		uword	opaque
	)

Definition at line 182 of file rbtree.c.

Here is the call graph for this function:

rb_tree_add_custom()

rb_node_index_t rb_tree_add_custom	(	rb_tree_t *	rt,
		u32	key,
		uword	opaque,
		rb_tree_lt_fn	ltfn
	)

Definition at line 195 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

rb_tree_del()

void rb_tree_del	(	rb_tree_t *	rt,
		u32	key
	)

Definition at line 452 of file rbtree.c.

Here is the call graph for this function:

rb_tree_del_custom()

void rb_tree_del_custom	(	rb_tree_t *	rt,
		u32	key,
		rb_tree_lt_fn	ltfn
	)

Definition at line 461 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

rb_tree_del_node()

void rb_tree_del_node	(	rb_tree_t *	rt,
		rb_node_t *	z
	)

Definition at line 445 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

rb_tree_free_nodes()

void rb_tree_free_nodes

(

rb_tree_t *

rt

)

Definition at line 476 of file rbtree.c.

Here is the caller graph for this function:

rb_tree_init()

void rb_tree_init

(

rb_tree_t *

rt

)

Definition at line 483 of file rbtree.c.

Here is the caller graph for this function:

rb_tree_is_init()

int rb_tree_is_init

(

rb_tree_t *

rt

)

Definition at line 496 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

rb_tree_max_subtree()

rb_node_t* rb_tree_max_subtree	(	rb_tree_t *	rt,
		rb_node_t *	x
	)

Definition at line 262 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

rb_tree_min_subtree()

rb_node_t* rb_tree_min_subtree	(	rb_tree_t *	rt,
		rb_node_t *	x
	)

Definition at line 254 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

rb_tree_n_nodes()

u32 rb_tree_n_nodes

(

rb_tree_t *

rt

)

Definition at line 470 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

rb_tree_predecessor()

rb_node_t* rb_tree_predecessor	(	rb_tree_t *	rt,
		rb_node_t *	x
	)

Definition at line 287 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

rb_tree_search_subtree()

rb_node_t* rb_tree_search_subtree	(	rb_tree_t *	rt,
		rb_node_t *	x,
		u32	key
	)

Definition at line 231 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

rb_tree_search_subtree_custom()

rb_node_t* rb_tree_search_subtree_custom	(	rb_tree_t *	rt,
		rb_node_t *	x,
		u32	key,
		rb_tree_lt_fn	ltfn
	)

Definition at line 242 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

rb_tree_successor()

rb_node_t* rb_tree_successor	(	rb_tree_t *	rt,
		rb_node_t *	x
	)

Definition at line 270 of file rbtree.c.

Here is the call graph for this function: