42 else if (xp->
left == xi)
69 else if (yp->
right == yi)
210 if (ltfn (z->
key, x->
key))
219 else if (ltfn (z->
key, y->
key))
245 if (ltfn (key, x->
key))
321 rb_node_t *x, *y, *yr, *yl, *xp, *w, *wl, *wr;
325 y_original_color = y->
color;
340 y_original_color = y->
color;
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_predecessor(rb_tree_t *rt, rb_node_t *x)
static void rb_tree_rotate_left(rb_tree_t *rt, rb_node_t *x)
static rb_node_t * rb_node_left(rb_tree_t *rt, rb_node_t *n)
#define pool_get_zero(P, E)
Allocate an object E from a pool P and zero it.
static rb_node_t * rb_node(rb_tree_t *rt, rb_node_index_t ri)
#define RBTREE_TNIL_INDEX
static rb_node_t * rb_node_right(rb_tree_t *rt, rb_node_t *n)
u32 rb_tree_n_nodes(rb_tree_t *rt)
void rb_tree_free_nodes(rb_tree_t *rt)
enum rb_tree_color_ rb_node_color_t
rb_node_index_t rb_tree_add2(rb_tree_t *rt, u32 key, uword opaque)
rb_node_index_t left
left child index
static void rb_tree_transplant(rb_tree_t *rt, rb_node_t *u, rb_node_t *v)
rb_node_index_t parent
parent index
static rb_node_index_t rb_node_index(rb_tree_t *rt, rb_node_t *n)
void rb_tree_del(rb_tree_t *rt, u32 key)
uword opaque
value stored by node
rb_node_t * rb_tree_successor(rb_tree_t *rt, rb_node_t *x)
#define pool_put(P, E)
Free an object E in pool P.
static void rb_tree_rotate_right(rb_tree_t *rt, rb_node_t *y)
void rb_tree_init(rb_tree_t *rt)
rb_node_t * rb_tree_min_subtree(rb_tree_t *rt, rb_node_t *x)
#define pool_free(p)
Free a pool.
static rb_node_t * rb_node_parent(rb_tree_t *rt, rb_node_t *n)
rb_node_index_t right
right child index
rb_node_t * rb_tree_search_subtree(rb_tree_t *rt, rb_node_t *x, u32 key)
void rb_tree_del_custom(rb_tree_t *rt, u32 key, rb_tree_lt_fn ltfn)
static void rb_tree_fixup_inline(rb_tree_t *rt, rb_node_t *y, rb_node_t *z)
static u8 rb_node_is_tnil(rb_tree_t *rt, rb_node_t *n)
rb_node_index_t rb_tree_add(rb_tree_t *rt, u32 key)
rb_node_t * nodes
pool of nodes
int(* rb_tree_lt_fn)(u32 a, u32 b)
void rb_tree_del_node(rb_tree_t *rt, rb_node_t *z)
rb_node_index_t rb_tree_add_custom(rb_tree_t *rt, u32 key, uword opaque, rb_tree_lt_fn ltfn)
static void rb_tree_insert(rb_tree_t *rt, rb_node_t *z)
rb_node_index_t root
root index
rb_node_t * rb_tree_max_subtree(rb_tree_t *rt, rb_node_t *x)
static uword pool_elts(void *v)
Number of active elements in a pool.