diff options
| author |   Florin Coras <fcoras@cisco.com> | 2019-06-19 16:45:09 -0700 |
|---|---|---|
| committer | Florin Coras <fcoras@cisco.com> | 2019-06-19 16:50:30 -0700 |
| commit | d314963d0f1d12c45c55c7fd210f93c5cac3a8fc (patch) | |
| tree | 70e630d04046e8a4c5e1fe261bdae402ce4f6798 | |
| parent | 6ac96762dc2631bb1c720057f2b9dd854c69b767 (diff) | |
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>
| -rw-r--r-- | src/plugins/unittest/rbtree_test.c | 6 | ||||
| -rw-r--r-- | src/vppinfra/rbtree.c | 10 |
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; |