vppinfra: fix rbtree node delete

Type:fix

Make sure tnil color is black and that the right node colors are
updated.

Change-Id: Ibd9d7ea9438df4dab977202955957824723a865d
Signed-off-by: Florin Coras <fcoras@cisco.com>

diff --git a/src/plugins/unittest/rbtree_test.c b/src/plugins/unittest/rbtree_test.c
index 490be9c..bfab98c 100644 (file)
--- 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 df759cb..ff86b0f 100644 (file)
--- 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;