/*
- * Copyright (c) 2004-2005, 2007 Todd C. Miller <Todd.Miller@courtesan.com>
+ * Copyright (c) 2004-2005, 2007,2009 Todd C. Miller <Todd.Miller@courtesan.com>
*
* Permission to use, copy, modify, and distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
#include "sudo.h"
#include "redblack.h"
-#ifndef lint
-__unused static const char rcsid[] = "$Sudo: redblack.c,v 1.10 2008/11/22 15:01:25 millert Exp $";
-#endif /* lint */
-
static void rbrepair __P((struct rbtree *, struct rbnode *));
static void rotate_left __P((struct rbtree *, struct rbnode *));
static void rotate_right __P((struct rbtree *, struct rbnode *));
* In addition to the ordinary requirements imposed on binary search
* trees, we make the following additional requirements of any valid
* red-black tree:
- * 1) The root is black.
- * 2) All leaves are black.
- * 3) Both children of each red node are black.
- * 4) The paths from each leaf up to the root each contain the same
+ * 1) Every node is either red or black.
+ * 2) The root is black.
+ * 3) All leaves are black.
+ * 4) Both children of each red node are black.
+ * 5) The paths from each leaf up to the root each contain the same
* number of black nodes.
*/
* Delete node 'z' from the tree and return its data pointer.
*/
void *rbdelete(tree, z)
- struct rbtree* tree;
- struct rbnode* z;
+ struct rbtree *tree;
+ struct rbnode *z;
{
struct rbnode *x, *y;
void *data = z->data;
{
struct rbnode *sibling;
- while (node->color == black) {
+ while (node->color == black && node != rbroot(tree)) {
if (node == node->parent->left) {
sibling = node->parent->right;
if (sibling->color == red) {
node->parent->color = black;
sibling->right->color = black;
rotate_left(tree, node->parent);
- break;
+ node = rbroot(tree); /* exit loop */
}
} else { /* if (node == node->parent->right) */
sibling = node->parent->left;
node->parent->color = black;
sibling->left->color = black;
rotate_right(tree, node->parent);
- break;
+ node = rbroot(tree); /* exit loop */
}
}
}
+ node->color = black;
}