FD.io VPP  v20.01-48-g3e0dafb74
Vector Packet Processing
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_trb_tree_min_subtree (rb_tree_t *rt, rb_node_t *x)
 
rb_node_trb_tree_max_subtree (rb_tree_t *rt, rb_node_t *x)
 
rb_node_trb_tree_search_subtree (rb_tree_t *rt, rb_node_t *x, u32 key)
 
rb_node_trb_tree_search_subtree_custom (rb_tree_t *rt, rb_node_t *x, u32 key, rb_tree_lt_fn ltfn)
 
rb_node_trb_tree_successor (rb_tree_t *rt, rb_node_t *x)
 
rb_node_trb_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_trb_node (rb_tree_t *rt, rb_node_index_t ri)
 
static rb_node_trb_node_right (rb_tree_t *rt, rb_node_t *n)
 
static rb_node_trb_node_left (rb_tree_t *rt, rb_node_t *n)
 
static rb_node_trb_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

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

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 80 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 68 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 74 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 92 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 98 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 86 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:
+ Here is the caller 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 444 of file rbtree.c.

+ Here is the call graph for this function:
+ Here is the caller 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 456 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 474 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 481 of file rbtree.c.

+ 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 261 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 253 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 468 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 286 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 230 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 241 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 269 of file rbtree.c.

+ Here is the call graph for this function: