FD.io VPP  v21.01.1
Vector Packet Processing
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)
 
__clib_export rb_node_index_t rb_tree_add (rb_tree_t *rt, u32 key)
 
__clib_export rb_node_index_t rb_tree_add2 (rb_tree_t *rt, u32 key, uword opaque)
 
__clib_export rb_node_index_t rb_tree_add_custom (rb_tree_t *rt, u32 key, uword opaque, rb_tree_lt_fn ltfn)
 
__clib_export rb_node_trb_tree_search_subtree (rb_tree_t *rt, rb_node_t *x, u32 key)
 
__clib_export rb_node_trb_tree_search_subtree_custom (rb_tree_t *rt, rb_node_t *x, u32 key, rb_tree_lt_fn ltfn)
 
__clib_export rb_node_trb_tree_min_subtree (rb_tree_t *rt, rb_node_t *x)
 
__clib_export rb_node_trb_tree_max_subtree (rb_tree_t *rt, rb_node_t *x)
 
__clib_export rb_node_trb_tree_successor (rb_tree_t *rt, rb_node_t *x)
 
__clib_export rb_node_trb_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)
 
__clib_export void rb_tree_del_node (rb_tree_t *rt, rb_node_t *z)
 
__clib_export void rb_tree_del (rb_tree_t *rt, u32 key)
 
__clib_export void rb_tree_del_custom (rb_tree_t *rt, u32 key, rb_tree_lt_fn ltfn)
 
__clib_export u32 rb_tree_n_nodes (rb_tree_t *rt)
 
__clib_export void rb_tree_free_nodes (rb_tree_t *rt)
 
__clib_export void rb_tree_init (rb_tree_t *rt)
 
__clib_export int rb_tree_is_init (rb_tree_t *rt)
 

Function Documentation

◆ rb_tree_add()

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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