summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--src/plugins/unittest/rbtree_test.c6
-rw-r--r--src/vppinfra/rbtree.c10
2 files changed, 12 insertions, 4 deletions
diff --git a/src/plugins/unittest/rbtree_test.c b/src/plugins/unittest/rbtree_test.c
index 490be9c156e..bfab98c3cd7 100644
--- a/src/plugins/unittest/rbtree_test.c
+++ b/src/plugins/unittest/rbtree_test.c
@@ -160,7 +160,11 @@ rbtree_test_basic (vlib_main_t * vm, unformat_input_t * input)
* Delete all keys
*/
for (i = 0; i < n_keys; i++)
- rb_tree_del (rt, i);
+ {
+ rb_tree_del (rt, i);
+ if (rt->nodes[RBTREE_TNIL_INDEX].color != RBTREE_BLACK)
+ RBTREE_TEST (0, "tnil should be black");
+ }
RBTREE_TEST (rb_tree_n_nodes (rt) == 1, "number nodes %u is %u",
1, rb_tree_n_nodes (rt));
diff --git a/src/vppinfra/rbtree.c b/src/vppinfra/rbtree.c
index df759cb2344..ff86b0f1b5b 100644
--- a/src/vppinfra/rbtree.c
+++ b/src/vppinfra/rbtree.c
@@ -344,7 +344,7 @@ rb_tree_del_node (rb_tree_t * rt, rb_node_t * z)
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;
@@ -379,7 +379,8 @@ rb_tree_del_node (rb_tree_t * rt, rb_node_t * z)
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
@@ -390,6 +391,7 @@ rb_tree_del_node (rb_tree_t * rt, rb_node_t * z)
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;
@@ -412,7 +414,8 @@ rb_tree_del_node (rb_tree_t * rt, rb_node_t * z)
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
@@ -423,6 +426,7 @@ rb_tree_del_node (rb_tree_t * rt, rb_node_t * z)
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;