Always fixup after deleting a black child node in rbtree

	This prevents rbtree_delete from creating unbalanced/illegal rbtrees.

diff --git a/src/lib/rbtree.c b/src/lib/rbtree.c
index 2f452e6..056e905 100644 (file)
--- a/src/lib/rbtree.c
+++ b/src/lib/rbtree.c
@@ -364,7 +364,7 @@ static void DeleteFixup(rbtree_t *tree, rbnode_t *X, rbnode_t *Parent)
                        }
                }
        }
-       X->Color = Black;
+       if (X != NIL) X->Color = Black; /* Avoid cache-dirty on NIL */
 }
 
 /*
@@ -413,7 +413,7 @@ void rbtree_delete(rbtree_t *tree, rbnode_t *Z)
                Z->Data = Y->Data;
                Y->Data = NULL;
 
-               if (Y->Color == Black && X != NIL)
+               if (Y->Color == Black)
                        DeleteFixup(tree, X, Parent);
 
                /*
@@ -439,7 +439,7 @@ void rbtree_delete(rbtree_t *tree, rbnode_t *Z)
        } else {
                if (tree->freeNode) tree->freeNode(Y->Data);
 
-               if (Y->Color == Black && X != NIL)
+               if (Y->Color == Black)
                        DeleteFixup(tree, X, Parent);
 
                free(Y);