16 #ifndef SRC_VPPINFRA_RBTREE_H_ 17 #define SRC_VPPINFRA_RBTREE_H_ 22 #define RBTREE_TNIL_INDEX 0
rb_node_t * rb_tree_min_subtree(rb_tree_t *rt, rb_node_t *x)
static rb_node_t * rb_node_left(rb_tree_t *rt, rb_node_t *n)
rb_node_t * rb_tree_search_subtree(rb_tree_t *rt, rb_node_t *x, u32 key)
Fixed length block allocator.
static rb_node_t * rb_node(rb_tree_t *rt, rb_node_index_t ri)
struct rb_tree_ rb_tree_t
#define RBTREE_TNIL_INDEX
static rb_node_t * rb_node_right(rb_tree_t *rt, rb_node_t *n)
rb_node_t * rb_tree_successor(rb_tree_t *rt, rb_node_t *x)
rb_node_t * rb_tree_search_subtree_custom(rb_tree_t *rt, rb_node_t *x, u32 key, rb_tree_lt_fn ltfn)
enum rb_tree_color_ rb_node_color_t
rb_node_index_t left
left child index
rb_node_index_t parent
parent index
static rb_node_index_t rb_node_index(rb_tree_t *rt, rb_node_t *n)
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
uword opaque
value stored by node
rb_node_t * rb_tree_predecessor(rb_tree_t *rt, rb_node_t *x)
void rb_tree_del_custom(rb_tree_t *rt, u32 key, rb_tree_lt_fn ltfn)
static rb_node_t * rb_node_parent(rb_tree_t *rt, rb_node_t *n)
rb_node_index_t rb_tree_add(rb_tree_t *rt, u32 key)
rb_node_t * rb_tree_max_subtree(rb_tree_t *rt, rb_node_t *x)
rb_node_index_t right
right child index
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)
static u8 rb_node_is_tnil(rb_tree_t *rt, rb_node_t *n)
void rb_tree_free_nodes(rb_tree_t *rt)
void rb_tree_init(rb_tree_t *rt)
rb_node_t * nodes
pool of nodes
int(* rb_tree_lt_fn)(u32 a, u32 b)
struct rb_node_ rb_node_t
rb_node_index_t root
root index
u32 rb_tree_n_nodes(rb_tree_t *rt)
void rb_tree_del(rb_tree_t *rt, u32 key)