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_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)
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

#define RBTREE_TNIL_INDEX   0

Definition at line 22 of file rbtree.h.

Typedef Documentation

typedef enum rb_tree_color_ rb_node_color_t

typedef u32 rb_node_index_t

Definition at line 24 of file rbtree.h.

typedef struct rb_node_ rb_node_t

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

Definition at line 48 of file rbtree.h.

typedef struct rb_tree_ rb_tree_t

Enumeration Type Documentation

enum rb_tree_color_

Enumerator
RBTREE_RED
RBTREE_BLACK

Definition at line 26 of file rbtree.h.

Function Documentation

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

inlinestatic

Definition at line 80 of file rbtree.h.

Here is the caller graph for this function:

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

inlinestatic

Definition at line 68 of file rbtree.h.

Here is the caller graph for this function:

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

inlinestatic

Definition at line 74 of file rbtree.h.

Here is the call graph for this function:

Here is the caller graph for this function:

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

inlinestatic

Definition at line 92 of file rbtree.h.

Here is the caller graph for this function:

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

inlinestatic

Definition at line 98 of file rbtree.h.

Here is the caller graph for this function:

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

inlinestatic

Definition at line 86 of file rbtree.h.

Here is the caller graph for this function:

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_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:

Here is the caller graph for this function:

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:

void rb_tree_del	(	rb_tree_t *	rt,
		u32	key
	)

Definition at line 444 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 456 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

void rb_tree_free_nodes

(

rb_tree_t *

rt

)

Definition at line 474 of file rbtree.c.

Here is the caller graph for this function:

void rb_tree_init

(

rb_tree_t *

rt

)

Definition at line 481 of file rbtree.c.

Here is the caller graph for this function:

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

Definition at line 261 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 253 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

u32 rb_tree_n_nodes

(

rb_tree_t *

rt

)

Definition at line 468 of file rbtree.c.

Here is the call graph for this function:

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

Definition at line 286 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 230 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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 241 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 269 of file rbtree.c.

Here is the call graph for this function: