rbtree.c File Reference

Include dependency graph for rbtree.c:

Go to the source code of this file.

Functions
static void	rb_tree_rotate_left (rb_tree_t *rt, rb_node_t *x)
static void	rb_tree_rotate_right (rb_tree_t *rt, rb_node_t *y)
static void	rb_tree_fixup_inline (rb_tree_t *rt, rb_node_t *y, rb_node_t *z)
static void	rb_tree_insert (rb_tree_t *rt, rb_node_t *z)
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)
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_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_successor (rb_tree_t *rt, rb_node_t *x)
rb_node_t *	rb_tree_predecessor (rb_tree_t *rt, rb_node_t *x)
static void	rb_tree_transplant (rb_tree_t *rt, rb_node_t *u, rb_node_t *v)
static void	rb_tree_del_node_internal (rb_tree_t *rt, rb_node_t *z)
void	rb_tree_del_node (rb_tree_t *rt, rb_node_t *z)
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)
u32	rb_tree_n_nodes (rb_tree_t *rt)
void	rb_tree_free_nodes (rb_tree_t *rt)
void	rb_tree_init (rb_tree_t *rt)
int	rb_tree_is_init (rb_tree_t *rt)

Function Documentation

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_del_node_internal()

static void rb_tree_del_node_internal ( rb_tree_t *  rt, rb_node_t *  z  )

static

Definition at line 319 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

rb_tree_fixup_inline()

static void rb_tree_fixup_inline ( rb_tree_t *  rt, rb_node_t *  y, rb_node_t *  z  )

inlinestatic

Definition at line 78 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_insert()

static void rb_tree_insert ( rb_tree_t *  rt, rb_node_t *  z  )

static

Definition at line 141 of file rbtree.c.

Here is the call graph for this function:

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:

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_rotate_left()

static void rb_tree_rotate_left ( rb_tree_t *  rt, rb_node_t *  x  )

inlinestatic

Definition at line 24 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

rb_tree_rotate_right()

static void rb_tree_rotate_right ( rb_tree_t *  rt, rb_node_t *  y  )

inlinestatic

Definition at line 51 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:

rb_tree_transplant()

static void rb_tree_transplant ( rb_tree_t *  rt, rb_node_t *  u, rb_node_t *  v  )

inlinestatic

Definition at line 304 of file rbtree.c.

Here is the call graph for this function:

Here is the caller graph for this function: