#include <vppinfra/rbtree.h>
-static inline rb_node_t *
-rb_node_right (rb_tree_t * rt, rb_node_t * n)
-{
- return pool_elt_at_index (rt->nodes, n->right);
-}
-
-static inline rb_node_t *
-rb_node_left (rb_tree_t * rt, rb_node_t * n)
-{
- return pool_elt_at_index (rt->nodes, n->left);
-}
-
-static inline rb_node_t *
-rb_node_parent (rb_tree_t * rt, rb_node_t * n)
-{
- return pool_elt_at_index (rt->nodes, n->parent);
-}
-
static inline void
rb_tree_rotate_left (rb_tree_t * rt, rb_node_t * x)
{
y->parent = xi;
}
-static void
-rb_tree_insert (rb_tree_t * rt, rb_node_t * z)
+static inline void
+rb_tree_fixup_inline (rb_tree_t * rt, rb_node_t * y, rb_node_t * z)
{
- rb_node_index_t yi = 0, xi = rt->root, zi;
- rb_node_t *y, *zpp, *x, *zp;
-
- y = rb_node (rt, RBTREE_TNIL_INDEX);
- while (xi != RBTREE_TNIL_INDEX)
- {
- x = rb_node (rt, xi);
- y = x;
- if (z->key < x->key)
- xi = x->left;
- else
- xi = x->right;
- }
- yi = rb_node_index (rt, y);
- z->parent = yi;
- if (yi == RBTREE_TNIL_INDEX)
- rt->root = rb_node_index (rt, z);
- else if (z->key < y->key)
- y->left = rb_node_index (rt, z);
- else
- y->right = rb_node_index (rt, z);
+ rb_node_t *zpp, *zp;
+ rb_node_index_t zi;
- /* Tree fixup stage */
while (y->color == RBTREE_RED)
{
zi = rb_node_index (rt, z);
rb_node (rt, rt->root)->color = RBTREE_BLACK;
}
+static void
+rb_tree_insert (rb_tree_t * rt, rb_node_t * z)
+{
+ rb_node_index_t yi = 0, xi = rt->root;
+ rb_node_t *y, *x;
+
+ y = rb_node (rt, RBTREE_TNIL_INDEX);
+ while (xi != RBTREE_TNIL_INDEX)
+ {
+ x = rb_node (rt, xi);
+ y = x;
+ if (z->key < x->key)
+ xi = x->left;
+ else
+ xi = x->right;
+ }
+ yi = rb_node_index (rt, y);
+ z->parent = yi;
+ if (yi == RBTREE_TNIL_INDEX)
+ rt->root = rb_node_index (rt, z);
+ else if (z->key < y->key)
+ y->left = rb_node_index (rt, z);
+ else
+ y->right = rb_node_index (rt, z);
+
+ /* Tree fixup stage */
+ rb_tree_fixup_inline (rt, y, 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, u32 opaque)
+rb_tree_add2 (rb_tree_t * rt, u32 key, uword opaque)
{
rb_node_t *n;
return rb_node_index (rt, n);
}
+rb_node_index_t
+rb_tree_add_custom (rb_tree_t * rt, u32 key, uword opaque, rb_tree_lt_fn ltfn)
+{
+ rb_node_index_t yi = 0, xi = rt->root;
+ rb_node_t *z, *y, *x;
+
+ pool_get_zero (rt->nodes, z);
+ z->key = key;
+ z->color = RBTREE_RED;
+ z->opaque = opaque;
+
+ y = rb_node (rt, RBTREE_TNIL_INDEX);
+ while (xi != RBTREE_TNIL_INDEX)
+ {
+ x = rb_node (rt, xi);
+ y = x;
+ ASSERT (z->key != x->key);
+ if (ltfn (z->key, x->key))
+ xi = x->left;
+ else
+ xi = x->right;
+ }
+ yi = rb_node_index (rt, y);
+ z->parent = yi;
+ if (yi == RBTREE_TNIL_INDEX)
+ rt->root = rb_node_index (rt, z);
+ else if (ltfn (z->key, y->key))
+ y->left = rb_node_index (rt, z);
+ else
+ y->right = rb_node_index (rt, z);
+
+ rb_tree_fixup_inline (rt, y, z);
+
+ return rb_node_index (rt, z);
+}
+
rb_node_t *
rb_tree_search_subtree (rb_tree_t * rt, rb_node_t * x, u32 key)
{
return x;
}
+rb_node_t *
+rb_tree_search_subtree_custom (rb_tree_t * rt, rb_node_t * x, u32 key,
+ rb_tree_lt_fn ltfn)
+{
+ while (rb_node_index (rt, x) != RBTREE_TNIL_INDEX && key != x->key)
+ if (ltfn (key, x->key))
+ x = rb_node_left (rt, x);
+ else
+ x = rb_node_right (rt, x);
+ return x;
+}
+
rb_node_t *
rb_tree_min_subtree (rb_tree_t * rt, rb_node_t * x)
{
v->parent = u->parent;
}
-void
-rb_tree_del_node (rb_tree_t * rt, rb_node_t * z)
+static void
+rb_tree_del_node_internal (rb_tree_t * rt, rb_node_t * z)
{
rb_node_color_t y_original_color;
rb_node_t *x, *y, *yr, *yl, *xp, *w, *wl, *wr;
x->parent = yi;
else
{
- rb_tree_transplant (rt, y, rb_node_right (rt, y));
+ rb_tree_transplant (rt, y, x);
y->right = z->right;
yr = rb_node_right (rt, y);
yr->parent = yi;
wr = rb_node_right (rt, w);
if (wl->color == RBTREE_BLACK && wr->color == RBTREE_BLACK)
{
- w->color = RBTREE_RED;
+ if (!rb_node_is_tnil (rt, w))
+ w->color = RBTREE_RED;
x = xp;
}
else
w->color = RBTREE_RED;
rb_tree_rotate_right (rt, w);
w = rb_node_right (rt, xp);
+ wr = rb_node_right (rt, w);
}
w->color = xp->color;
xp->color = RBTREE_BLACK;
wr = rb_node_right (rt, w);
if (wl->color == RBTREE_BLACK && wr->color == RBTREE_BLACK)
{
- w->color = RBTREE_RED;
+ if (!rb_node_is_tnil (rt, w))
+ w->color = RBTREE_RED;
x = xp;
}
else
w->color = RBTREE_RED;
rb_tree_rotate_left (rt, w);
w = rb_node_left (rt, xp);
+ wl = rb_node_left (rt, w);
}
w->color = xp->color;
xp->color = RBTREE_BLACK;
x->color = RBTREE_BLACK;
}
+void
+rb_tree_del_node (rb_tree_t * rt, rb_node_t * z)
+{
+ rb_tree_del_node_internal (rt, z);
+ pool_put (rt->nodes, z);
+}
+
void
rb_tree_del (rb_tree_t * rt, u32 key)
{
rb_node_t *n;
n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), key);
if (rb_node_index (rt, n) != RBTREE_TNIL_INDEX)
- {
- rb_tree_del_node (rt, n);
- pool_put (rt->nodes, n);
- }
+ rb_tree_del_node (rt, n);
+}
+
+void
+rb_tree_del_custom (rb_tree_t * rt, u32 key, rb_tree_lt_fn ltfn)
+{
+ rb_node_t *n;
+ n = rb_tree_search_subtree_custom (rt, rb_node (rt, rt->root), key, ltfn);
+ if (rb_node_index (rt, n) != RBTREE_TNIL_INDEX)
+ rb_tree_del_node (rt, n);
}
u32
void
rb_tree_free_nodes (rb_tree_t * rt)
{
- rb_node_t *n;
- pool_flush (n, rt->nodes,;);
+ pool_free (rt->nodes);
+ rt->root = RBTREE_TNIL_INDEX;
}
void
tnil->color = RBTREE_BLACK;
}
+int
+rb_tree_is_init (rb_tree_t * rt)
+{
+ if (pool_elts (rt->nodes) == 0)
+ return 0;
+ return 1;
+}
+
/*
* fd.io coding-style-patch-verification: ON
*