From 1aecbf40567f0f1943285c774b4d6369e1a90ceb Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Sun, 26 Jul 2020 10:50:06 +0200
Subject: Code Cleanup für Red-Black-Trees
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 rb.c | 1088 +++++++++++++++++++++++++++++++-----------------------------------
 1 file changed, 518 insertions(+), 570 deletions(-)

(limited to 'rb.c')

diff --git a/rb.c b/rb.c
index c95ab83..2a8bff2 100644
--- a/rb.c
+++ b/rb.c
@@ -1,158 +1,8 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include <time.h>
-#include "util.h"
-
-typedef int T;
-
-#if 0
-struct rbtree {
-	T data;
-	enum { RED, BLACK } color;
-	struct rbtree *left, *right, *p;
-};
-
-struct rbtree *
-rb_alloc(T data)
-{
-	struct rbtree *node = malloc(sizeof *node);
-	if ( node )
-	{
-		node->data = data;
-		node->left = NULL;
-		node->right = NULL;
-		node->p = NULL;
-	}
-	return node;
-}
-
-void
-rb_left_rotate(struct rbtree **root, struct rbtree *x)
-{
-	struct rbtree *y = x->right;
-	x->right = y->left;
-	if ( y->left )
-		y->left->p = x;
-
-	y->p = x->p;
-	if ( x->p == NULL )
-		*root = y;
-	else if ( x == x->p->left )
-		x->p->left = y;
-	else
-		x->p->right = y;
-
-	y->left = x;
-	x->p = y;
-}
-
-void
-rb_right_rotate(struct rbtree **root, struct rbtree *y)
-{
-	struct rbtree *x = y->left;
-	y->left = x->right;
-	if ( x->right )
-		x->right->p = y;
-
-	x->p = y->p;
-	if ( y->p == NULL )
-		*root = x;
-	else if ( y == y->p->left )
-		y->p->left = x;
-	else
-		y->p->right = x;
-
-	x->right = y;
-	y->p = x;
-}
-
-void
-rb_insert_fixup(struct rbtree **root, struct rbtree **z)
-{
-	struct rbtree *y;
-
-	while ( z->p->color == RED ) {
-		if ( z->p == z->p->p->left ) {
-			y = z->p->p->right;
-			if ( y->color == RED ) {
-				z->p->color = BLACK;
-				y->color = BLACK;
-				z->p->p->color = RED;
-				z = z->p->p;
-			}
-			else {
-				if ( z == z->p->right ) {
-					z = z->p;
-					rb_left_rotate(root, z);
-				}
-				z->p->color = BLACK;
-				z->p->p->color = RED;
-				rb_right_rotate(root, z->p->p);
-			}
-		}
-		else {
-			y = z->p->p->left;
-			if ( y->color == RED ) {
-				z->p->color = BLACK;
-				y->color = BLACK;
-				z->p->p->color = RED;
-				z = z->p->p;
-			}
-			else {
-				if ( z == z->p->left ) {
-					z = z->p;
-					rb_right_rotate(root, z);
-				}
-				z->p->color = BLACK;
-				z->p->p->color = RED;
-				rb_left_rotate(root, z->p->p);
-			}
-		}
-	}
-	
-	(*root)->color = BLACK;
-}
-
-void
-rb_insert_node(struct rbtree **root, T data)
-{
-	struct rbtree *z = rb_alloc(data);
-
-	if ( *root == NULL ) {
-		z->color = BLACK;
-		*root = z;
-	}
-	else {
-		struct rbtree *y = NULL;
-		struct rbtree *x = *root;
-
-		while ( x ) {
-			y = x;
-			if ( z->data < x->data )
-				x = x->left;
-			else
-				x = x->right;
-		}
-		z->p = y;
-
-		if ( y == NULL )		// kann entfallen!
-			*root = z;
-		else if ( z->data < y->data )
-			y->left = z;
-		else
-			y->right = z;
-
-		z->left = NULL;			// kann entfallen!
-		z->right = NULL;		// kann entfallen!
-		z->color = RED;
-
-		rb_insert_fixup(root, &z);
-	}
-}
-
-#endif
-
 
+#include "util.h"
 
 /* The authors of this work have released all rights to it and placed it
 in the public domain under the Creative Commons CC0 1.0 waiver
@@ -169,48 +19,48 @@ SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 Retrieved from: http://en.literateprograms.org/Red-black_tree_(C)?oldid=19567
 */
 
-enum rbtree_node_color { RED, BLACK };
+enum rbtree_node_color { RED,
+	                     BLACK };
 
 typedef struct rbtree_node_t {
-void* key;
-void* value;
-struct rbtree_node_t* left;
-struct rbtree_node_t* right;
-struct rbtree_node_t* parent;
-enum rbtree_node_color color;
-} *rbtree_node;
+	void *                 key;
+	void *                 value;
+	struct rbtree_node_t * left;
+	struct rbtree_node_t * right;
+	struct rbtree_node_t * parent;
+	enum rbtree_node_color color;
+} * rbtree_node;
 
 typedef struct rbtree_t {
-rbtree_node root;
-} *rbtree;
+	rbtree_node root;
+} * rbtree;
 
-typedef int (*compare_func)(void* left, void* right);
+typedef int (*compare_func)(void *left, void *right);
 
 rbtree rbtree_create();
-void* rbtree_lookup(rbtree t, void* key, compare_func compare);
-void rbtree_insert(rbtree t, void* key, void* value, compare_func compare);
-void rbtree_delete(rbtree t, void* key, compare_func compare);
-
+void * rbtree_lookup(rbtree t, void *key, compare_func compare);
+void   rbtree_insert(rbtree t, void *key, void *value, compare_func compare);
+void   rbtree_delete(rbtree t, void *key, compare_func compare);
 
 #include <assert.h>
 #include <stdlib.h>
 
-typedef rbtree_node node;
+typedef rbtree_node            node;
 typedef enum rbtree_node_color color;
 
-static node grandparent(node n);
-static node sibling(node n);
-static node uncle(node n);
-static void verify_properties(rbtree t);
-static void verify_property_1(node root);
-static void verify_property_2(node root);
+static node  grandparent(node n);
+static node  sibling(node n);
+static node  uncle(node n);
+static void  verify_properties(rbtree t);
+static void  verify_property_1(node root);
+static void  verify_property_2(node root);
 static color node_color(node n);
-static void verify_property_4(node root);
-static void verify_property_5(node root);
-static void verify_property_5_helper(node n, int black_count, int* black_count_path);
+static void  verify_property_4(node root);
+static void  verify_property_5(node root);
+static void  verify_property_5_helper(node n, int black_count, int *black_count_path);
 
-static node new_node(void* key, void* value, color node_color, node left, node right);
-static node lookup_node(rbtree t, void* key, compare_func compare);
+static node new_node(void *key, void *value, color node_color, node left, node right);
+static node lookup_node(rbtree t, void *key, compare_func compare);
 static void rotate_left(rbtree t, node n);
 static void rotate_right(rbtree t, node n);
 
@@ -228,334 +78,434 @@ static void delete_case4(rbtree t, node n);
 static void delete_case5(rbtree t, node n);
 static void delete_case6(rbtree t, node n);
 
-node grandparent(node n) {
-    assert (n != NULL);
-    assert (n->parent != NULL); /* Not the root node */
-    assert (n->parent->parent != NULL); /* Not child of root */
-    return n->parent->parent;
-}
-node sibling(node n) {
-    assert (n != NULL);
-    assert (n->parent != NULL); /* Root node has no sibling */
-    if (n == n->parent->left)
-        return n->parent->right;
-    else
-        return n->parent->left;
-}
-node uncle(node n) {
-    assert (n != NULL);
-    assert (n->parent != NULL); /* Root node has no uncle */
-    assert (n->parent->parent != NULL); /* Children of root have no uncle */
-    return sibling(n->parent);
-}
-void verify_properties(rbtree t) {
+node
+grandparent(node n)
+{
+	assert(n != NULL);
+	assert(n->parent != NULL);         /* Not the root node */
+	assert(n->parent->parent != NULL); /* Not child of root */
+	return n->parent->parent;
+}
+
+node
+sibling(node n)
+{
+	assert(n != NULL);
+	assert(n->parent != NULL); /* Root node has no sibling */
+	if ( n == n->parent->left )
+		return n->parent->right;
+	else
+		return n->parent->left;
+}
+
+node
+uncle(node n)
+{
+	assert(n != NULL);
+	assert(n->parent != NULL);         /* Root node has no uncle */
+	assert(n->parent->parent != NULL); /* Children of root have no uncle */
+	return sibling(n->parent);
+}
+
+void
+verify_properties(rbtree t)
+{
 #ifdef VERIFY_RBTREE
-    verify_property_1(t->root);
-    verify_property_2(t->root);
-    /* Property 3 is implicit */
-    verify_property_4(t->root);
-    verify_property_5(t->root);
+	verify_property_1(t->root);
+	verify_property_2(t->root);
+	/* Property 3 is implicit */
+	verify_property_4(t->root);
+	verify_property_5(t->root);
 #endif
 }
-void verify_property_1(node n) {
-    assert(node_color(n) == RED || node_color(n) == BLACK);
-    if (n == NULL) return;
-    verify_property_1(n->left);
-    verify_property_1(n->right);
-}
-void verify_property_2(node root) {
-    assert(node_color(root) == BLACK);
-}
-color node_color(node n) {
-    return n == NULL ? BLACK : n->color;
-}
-void verify_property_4(node n) {
-    if (node_color(n) == RED) {
-        assert (node_color(n->left)   == BLACK);
-        assert (node_color(n->right)  == BLACK);
-        assert (node_color(n->parent) == BLACK);
-    }
-    if (n == NULL) return;
-    verify_property_4(n->left);
-    verify_property_4(n->right);
-}
-void verify_property_5(node root) {
-    int black_count_path = -1;
-    verify_property_5_helper(root, 0, &black_count_path);
-}
-
-void verify_property_5_helper(node n, int black_count, int* path_black_count) {
-    if (node_color(n) == BLACK) {
-        black_count++;
-    }
-    if (n == NULL) {
-        if (*path_black_count == -1) {
-            *path_black_count = black_count;
-        } else {
-            assert (black_count == *path_black_count);
-        }
-        return;
-    }
-    verify_property_5_helper(n->left,  black_count, path_black_count);
-    verify_property_5_helper(n->right, black_count, path_black_count);
-}
-rbtree rbtree_create() {
-    rbtree t = malloc(sizeof(struct rbtree_t));
-    t->root = NULL;
-    verify_properties(t);
-    return t;
-}
-node new_node(void* key, void* value, color node_color, node left, node right) {
-    node result = malloc(sizeof(struct rbtree_node_t));
-    result->key = key;
-    result->value = value;
-    result->color = node_color;
-    result->left = left;
-    result->right = right;
-    if (left  != NULL)  left->parent = result;
-    if (right != NULL) right->parent = result;
-    result->parent = NULL;
-    return result;
-}
-node lookup_node(rbtree t, void* key, compare_func compare) {
-    node n = t->root;
-    while (n != NULL) {
-        int comp_result = compare(key, n->key);
-        if (comp_result == 0) {
-            return n;
-        } else if (comp_result < 0) {
-            n = n->left;
-        } else {
-            assert(comp_result > 0);
-            n = n->right;
-        }
-    }
-    return n;
-}
-void* rbtree_lookup(rbtree t, void* key, compare_func compare) {
-    node n = lookup_node(t, key, compare);
-    return n == NULL ? NULL : n->value;
-}
-void rotate_left(rbtree t, node n) {
-    node r = n->right;
-    replace_node(t, n, r);
-    n->right = r->left;
-    if (r->left != NULL) {
-        r->left->parent = n;
-    }
-    r->left = n;
-    n->parent = r;
-}
-
-void rotate_right(rbtree t, node n) {
-    node L = n->left;
-    replace_node(t, n, L);
-    n->left = L->right;
-    if (L->right != NULL) {
-        L->right->parent = n;
-    }
-    L->right = n;
-    n->parent = L;
-}
-void replace_node(rbtree t, node oldn, node newn) {
-    if (oldn->parent == NULL) {
-        t->root = newn;
-    } else {
-        if (oldn == oldn->parent->left)
-            oldn->parent->left = newn;
-        else
-            oldn->parent->right = newn;
-    }
-    if (newn != NULL) {
-        newn->parent = oldn->parent;
-    }
-}
-void rbtree_insert(rbtree t, void* key, void* value, compare_func compare) {
-    node inserted_node = new_node(key, value, RED, NULL, NULL);
-    if (t->root == NULL) {
-        t->root = inserted_node;
-    } else {
-        node n = t->root;
-        while (1) {
-            int comp_result = compare(key, n->key);
-            if (comp_result == 0) {
-                n->value = value;
-                return;
-            } else if (comp_result < 0) {
-                if (n->left == NULL) {
-                    n->left = inserted_node;
-                    break;
-                } else {
-                    n = n->left;
-                }
-            } else {
-                assert (comp_result > 0);
-                if (n->right == NULL) {
-                    n->right = inserted_node;
-                    break;
-                } else {
-                    n = n->right;
-                }
-            }
-        }
-        inserted_node->parent = n;
-    }
-    insert_case1(t, inserted_node);
-    verify_properties(t);
-}
-void insert_case1(rbtree t, node n) {
-    if (n->parent == NULL)
-        n->color = BLACK;
-    else
-        insert_case2(t, n);
-}
-void insert_case2(rbtree t, node n) {
-    if (node_color(n->parent) == BLACK)
-        return; /* Tree is still valid */
-    else
-        insert_case3(t, n);
-}
-void insert_case3(rbtree t, node n) {
-    if (node_color(uncle(n)) == RED) {
-        n->parent->color = BLACK;
-        uncle(n)->color = BLACK;
-        grandparent(n)->color = RED;
-        insert_case1(t, grandparent(n));
-    } else {
-        insert_case4(t, n);
-    }
-}
-void insert_case4(rbtree t, node n) {
-    if (n == n->parent->right && n->parent == grandparent(n)->left) {
-        rotate_left(t, n->parent);
-        n = n->left;
-    } else if (n == n->parent->left && n->parent == grandparent(n)->right) {
-        rotate_right(t, n->parent);
-        n = n->right;
-    }
-    insert_case5(t, n);
-}
-void insert_case5(rbtree t, node n) {
-    n->parent->color = BLACK;
-    grandparent(n)->color = RED;
-    if (n == n->parent->left && n->parent == grandparent(n)->left) {
-        rotate_right(t, grandparent(n));
-    } else {
-        assert (n == n->parent->right && n->parent == grandparent(n)->right);
-        rotate_left(t, grandparent(n));
-    }
-}
-void rbtree_delete(rbtree t, void* key, compare_func compare) {
-    node child;
-    node n = lookup_node(t, key, compare);
-    if (n == NULL) return;  /* Key not found, do nothing */
-    if (n->left != NULL && n->right != NULL) {
-        /* Copy key/value from predecessor and then delete it instead */
-        node pred = maximum_node(n->left);
-        n->key   = pred->key;
-        n->value = pred->value;
-        n = pred;
-    }
-
-    assert(n->left == NULL || n->right == NULL);
-    child = n->right == NULL ? n->left  : n->right;
-    if (node_color(n) == BLACK) {
-        n->color = node_color(child);
-        delete_case1(t, n);
-    }
-    replace_node(t, n, child);
-    if (n->parent == NULL && child != NULL) // root should be black
-        child->color = BLACK;
-    free(n);
-
-    verify_properties(t);
-}
-static node maximum_node(node n) {
-    assert (n != NULL);
-    while (n->right != NULL) {
-        n = n->right;
-    }
-    return n;
-}
-void delete_case1(rbtree t, node n) {
-    if (n->parent == NULL)
-        return;
-    else
-        delete_case2(t, n);
-}
-void delete_case2(rbtree t, node n) {
-    if (node_color(sibling(n)) == RED) {
-        n->parent->color = RED;
-        sibling(n)->color = BLACK;
-        if (n == n->parent->left)
-            rotate_left(t, n->parent);
-        else
-            rotate_right(t, n->parent);
-    }
-    delete_case3(t, n);
-}
-void delete_case3(rbtree t, node n) {
-    if (node_color(n->parent) == BLACK &&
-        node_color(sibling(n)) == BLACK &&
-        node_color(sibling(n)->left) == BLACK &&
-        node_color(sibling(n)->right) == BLACK)
-    {
-        sibling(n)->color = RED;
-        delete_case1(t, n->parent);
-    }
-    else
-        delete_case4(t, n);
-}
-void delete_case4(rbtree t, node n) {
-    if (node_color(n->parent) == RED &&
-        node_color(sibling(n)) == BLACK &&
-        node_color(sibling(n)->left) == BLACK &&
-        node_color(sibling(n)->right) == BLACK)
-    {
-        sibling(n)->color = RED;
-        n->parent->color = BLACK;
-    }
-    else
-        delete_case5(t, n);
-}
-void delete_case5(rbtree t, node n) {
-    if (n == n->parent->left &&
-        node_color(sibling(n)) == BLACK &&
-        node_color(sibling(n)->left) == RED &&
-        node_color(sibling(n)->right) == BLACK)
-    {
-        sibling(n)->color = RED;
-        sibling(n)->left->color = BLACK;
-        rotate_right(t, sibling(n));
-    }
-    else if (n == n->parent->right &&
-             node_color(sibling(n)) == BLACK &&
-             node_color(sibling(n)->right) == RED &&
-             node_color(sibling(n)->left) == BLACK)
-    {
-        sibling(n)->color = RED;
-        sibling(n)->right->color = BLACK;
-        rotate_left(t, sibling(n));
-    }
-    delete_case6(t, n);
-}
-void delete_case6(rbtree t, node n) {
-    sibling(n)->color = node_color(n->parent);
-    n->parent->color = BLACK;
-    if (n == n->parent->left) {
-        assert (node_color(sibling(n)->right) == RED);
-        sibling(n)->right->color = BLACK;
-        rotate_left(t, n->parent);
-    }
-    else
-    {
-        assert (node_color(sibling(n)->left) == RED);
-        sibling(n)->left->color = BLACK;
-        rotate_right(t, n->parent);
-    }
+
+void
+verify_property_1(node n)
+{
+	assert(node_color(n) == RED || node_color(n) == BLACK);
+	if ( n == NULL )
+		return;
+	verify_property_1(n->left);
+	verify_property_1(n->right);
+}
+
+void
+verify_property_2(node root)
+{
+	assert(node_color(root) == BLACK);
+}
+
+color
+node_color(node n)
+{
+	return n == NULL ? BLACK : n->color;
+}
+
+void
+verify_property_4(node n)
+{
+	if ( node_color(n) == RED ) {
+		assert(node_color(n->left) == BLACK);
+		assert(node_color(n->right) == BLACK);
+		assert(node_color(n->parent) == BLACK);
+	}
+	if ( n == NULL )
+		return;
+	verify_property_4(n->left);
+	verify_property_4(n->right);
 }
 
+void
+verify_property_5(node root)
+{
+	int black_count_path = -1;
+	verify_property_5_helper(root, 0, &black_count_path);
+}
+
+void
+verify_property_5_helper(node n, int black_count, int *path_black_count)
+{
+	if ( node_color(n) == BLACK ) {
+		black_count++;
+	}
+	if ( n == NULL ) {
+		if ( *path_black_count == -1 ) {
+			*path_black_count = black_count;
+		}
+		else {
+			assert(black_count == *path_black_count);
+		}
+		return;
+	}
+	verify_property_5_helper(n->left, black_count, path_black_count);
+	verify_property_5_helper(n->right, black_count, path_black_count);
+}
+
+rbtree
+rbtree_create()
+{
+	rbtree t = malloc(sizeof(struct rbtree_t));
+	t->root  = NULL;
+	verify_properties(t);
+	return t;
+}
 
+node
+new_node(void *key, void *value, color node_color, node left, node right)
+{
+	node result   = malloc(sizeof(struct rbtree_node_t));
+	result->key   = key;
+	result->value = value;
+	result->color = node_color;
+	result->left  = left;
+	result->right = right;
+	if ( left != NULL )
+		left->parent = result;
+	if ( right != NULL )
+		right->parent = result;
+	result->parent = NULL;
+	return result;
+}
+
+node
+lookup_node(rbtree t, void *key, compare_func compare)
+{
+	node n = t->root;
+	while ( n != NULL ) {
+		int comp_result = compare(key, n->key);
+		if ( comp_result == 0 ) {
+			return n;
+		}
+		else if ( comp_result < 0 ) {
+			n = n->left;
+		}
+		else {
+			assert(comp_result > 0);
+			n = n->right;
+		}
+	}
+	return n;
+}
+
+void *
+rbtree_lookup(rbtree t, void *key, compare_func compare)
+{
+	node n = lookup_node(t, key, compare);
+	return n == NULL ? NULL : n->value;
+}
+
+void
+rotate_left(rbtree t, node n)
+{
+	node r = n->right;
+	replace_node(t, n, r);
+	n->right = r->left;
+	if ( r->left != NULL ) {
+		r->left->parent = n;
+	}
+	r->left   = n;
+	n->parent = r;
+}
+
+void
+rotate_right(rbtree t, node n)
+{
+	node L = n->left;
+	replace_node(t, n, L);
+	n->left = L->right;
+	if ( L->right != NULL ) {
+		L->right->parent = n;
+	}
+	L->right  = n;
+	n->parent = L;
+}
+
+void
+replace_node(rbtree t, node oldn, node newn)
+{
+	if ( oldn->parent == NULL ) {
+		t->root = newn;
+	}
+	else {
+		if ( oldn == oldn->parent->left )
+			oldn->parent->left = newn;
+		else
+			oldn->parent->right = newn;
+	}
+	if ( newn != NULL ) {
+		newn->parent = oldn->parent;
+	}
+}
+
+void
+rbtree_insert(rbtree t, void *key, void *value, compare_func compare)
+{
+	node inserted_node = new_node(key, value, RED, NULL, NULL);
+	if ( t->root == NULL ) {
+		t->root = inserted_node;
+	}
+	else {
+		node n = t->root;
+		while ( 1 ) {
+			int comp_result = compare(key, n->key);
+			if ( comp_result == 0 ) {
+				n->value = value;
+				return;
+			}
+			else if ( comp_result < 0 ) {
+				if ( n->left == NULL ) {
+					n->left = inserted_node;
+					break;
+				}
+				else {
+					n = n->left;
+				}
+			}
+			else {
+				assert(comp_result > 0);
+				if ( n->right == NULL ) {
+					n->right = inserted_node;
+					break;
+				}
+				else {
+					n = n->right;
+				}
+			}
+		}
+		inserted_node->parent = n;
+	}
+	insert_case1(t, inserted_node);
+	verify_properties(t);
+}
+
+void
+insert_case1(rbtree t, node n)
+{
+	if ( n->parent == NULL )
+		n->color = BLACK;
+	else
+		insert_case2(t, n);
+}
+
+void
+insert_case2(rbtree t, node n)
+{
+	if ( node_color(n->parent) == BLACK )
+		return; /* Tree is still valid */
+	else
+		insert_case3(t, n);
+}
+
+void
+insert_case3(rbtree t, node n)
+{
+	if ( node_color(uncle(n)) == RED ) {
+		n->parent->color      = BLACK;
+		uncle(n)->color       = BLACK;
+		grandparent(n)->color = RED;
+		insert_case1(t, grandparent(n));
+	}
+	else {
+		insert_case4(t, n);
+	}
+}
+
+void
+insert_case4(rbtree t, node n)
+{
+	if ( n == n->parent->right && n->parent == grandparent(n)->left ) {
+		rotate_left(t, n->parent);
+		n = n->left;
+	}
+	else if ( n == n->parent->left && n->parent == grandparent(n)->right ) {
+		rotate_right(t, n->parent);
+		n = n->right;
+	}
+	insert_case5(t, n);
+}
+
+void
+insert_case5(rbtree t, node n)
+{
+	n->parent->color      = BLACK;
+	grandparent(n)->color = RED;
+	if ( n == n->parent->left && n->parent == grandparent(n)->left ) {
+		rotate_right(t, grandparent(n));
+	}
+	else {
+		assert(n == n->parent->right && n->parent == grandparent(n)->right);
+		rotate_left(t, grandparent(n));
+	}
+}
+
+void
+rbtree_delete(rbtree t, void *key, compare_func compare)
+{
+	node child;
+	node n = lookup_node(t, key, compare);
+	if ( n == NULL )
+		return; /* Key not found, do nothing */
+	if ( n->left != NULL && n->right != NULL ) {
+		/* Copy key/value from predecessor and then delete it instead */
+		node pred = maximum_node(n->left);
+		n->key    = pred->key;
+		n->value  = pred->value;
+		n         = pred;
+	}
+
+	assert(n->left == NULL || n->right == NULL);
+	child = n->right == NULL ? n->left : n->right;
+	if ( node_color(n) == BLACK ) {
+		n->color = node_color(child);
+		delete_case1(t, n);
+	}
+	replace_node(t, n, child);
+	if ( n->parent == NULL && child != NULL ) // root should be black
+		child->color = BLACK;
+	free(n);
+
+	verify_properties(t);
+}
+
+static node
+maximum_node(node n)
+{
+	assert(n != NULL);
+	while ( n->right != NULL ) {
+		n = n->right;
+	}
+	return n;
+}
+
+void
+delete_case1(rbtree t, node n)
+{
+	if ( n->parent == NULL )
+		return;
+	else
+		delete_case2(t, n);
+}
+
+void
+delete_case2(rbtree t, node n)
+{
+	if ( node_color(sibling(n)) == RED ) {
+		n->parent->color  = RED;
+		sibling(n)->color = BLACK;
+		if ( n == n->parent->left )
+			rotate_left(t, n->parent);
+		else
+			rotate_right(t, n->parent);
+	}
+	delete_case3(t, n);
+}
+
+void
+delete_case3(rbtree t, node n)
+{
+	if ( node_color(n->parent) == BLACK &&
+	     node_color(sibling(n)) == BLACK &&
+	     node_color(sibling(n)->left) == BLACK &&
+	     node_color(sibling(n)->right) == BLACK ) {
+		sibling(n)->color = RED;
+		delete_case1(t, n->parent);
+	}
+	else
+		delete_case4(t, n);
+}
+
+void
+delete_case4(rbtree t, node n)
+{
+	if ( node_color(n->parent) == RED &&
+	     node_color(sibling(n)) == BLACK &&
+	     node_color(sibling(n)->left) == BLACK &&
+	     node_color(sibling(n)->right) == BLACK ) {
+		sibling(n)->color = RED;
+		n->parent->color  = BLACK;
+	}
+	else
+		delete_case5(t, n);
+}
+
+void
+delete_case5(rbtree t, node n)
+{
+	if ( n == n->parent->left &&
+	     node_color(sibling(n)) == BLACK &&
+	     node_color(sibling(n)->left) == RED &&
+	     node_color(sibling(n)->right) == BLACK ) {
+		sibling(n)->color       = RED;
+		sibling(n)->left->color = BLACK;
+		rotate_right(t, sibling(n));
+	}
+	else if ( n == n->parent->right &&
+	          node_color(sibling(n)) == BLACK &&
+	          node_color(sibling(n)->right) == RED &&
+	          node_color(sibling(n)->left) == BLACK ) {
+		sibling(n)->color        = RED;
+		sibling(n)->right->color = BLACK;
+		rotate_left(t, sibling(n));
+	}
+	delete_case6(t, n);
+}
+
+void
+delete_case6(rbtree t, node n)
+{
+	sibling(n)->color = node_color(n->parent);
+	n->parent->color  = BLACK;
+	if ( n == n->parent->left ) {
+		assert(node_color(sibling(n)->right) == RED);
+		sibling(n)->right->color = BLACK;
+		rotate_left(t, n->parent);
+	}
+	else {
+		assert(node_color(sibling(n)->left) == RED);
+		sibling(n)->left->color = BLACK;
+		rotate_right(t, n->parent);
+	}
+}
 
 /* The authors of this work have released all rights to it and placed it
 in the public domain under the Creative Commons CC0 1.0 waiver
@@ -572,90 +522,88 @@ SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 Retrieved from: http://en.literateprograms.org/Red-black_tree_(C)?oldid=19567
 */
 
-#include <stdio.h>
 #include <assert.h>
+#include <stdio.h>
 #include <stdlib.h> /* rand() */
 
-static int compare_int(void* left, void* right);
+static int  compare_int(void *left, void *right);
 static void print_tree(rbtree t);
 static void print_tree_helper(rbtree_node n, int indent);
 
-int compare_int(void* leftp, void* rightp) {
-    int left = (int)leftp;
-    int right = (int)rightp;
-    if (left < right) 
-        return -1;
-    else if (left > right)
-        return 1;
-    else {
-        assert (left == right);
-        return 0;
-    }
+int
+compare_int(void *leftp, void *rightp)
+{
+	int left  = (int) leftp;
+	int right = (int) rightp;
+	if ( left < right )
+		return -1;
+	else if ( left > right )
+		return 1;
+	else {
+		assert(left == right);
+		return 0;
+	}
 }
 
-#define INDENT_STEP  4
+#define INDENT_STEP 4
 
 void print_tree_helper(rbtree_node n, int indent);
 
-void print_tree(rbtree t) {
-    print_tree_helper(t->root, 0);
-    puts("");
-}
-
-void print_tree_helper(rbtree_node n, int indent) {
-    int i;
-    if (n == NULL) {
-        fputs("<empty tree>", stdout);
-        return;
-    }
-    if (n->right != NULL) {
-        print_tree_helper(n->right, indent + INDENT_STEP);
-    }
-    for(i=0; i<indent; i++)
-        fputs(" ", stdout);
-    if (n->color == BLACK)
-        printf("%d\n", (int)n->key);
-    else
-        printf("<%d>\n", (int)n->key);
-    if (n->left != NULL) {
-        print_tree_helper(n->left, indent + INDENT_STEP);
-    }
-}
-
-int main() {
-    int i;
-    rbtree t = rbtree_create();
-    print_tree(t);
-
-    for(i=0; i<5000; i++) {
-        long x = rand() % 10000;
-        long y = rand() % 10000;
-#ifdef TRACE
-        print_tree(t);
-        printf("Inserting %d -> %d\n\n", x, y);
-#endif
-        rbtree_insert(t, (void*)x, (void*)y, compare_int);
-        assert(rbtree_lookup(t, (void*)x, compare_int) == (void*)y);
-    }
-    for(i=0; i<60000; i++) {
-        long x = rand() % 10000;
-#ifdef TRACE
-        print_tree(t);
-        printf("Deleting key %d\n\n", x);
-#endif
-        rbtree_delete(t, (void*)x, compare_int);
-    }
-    return 0;
+void
+print_tree(rbtree t)
+{
+	print_tree_helper(t->root, 0);
+	puts("");
+}
+
+void
+print_tree_helper(rbtree_node n, int indent)
+{
+	int i;
+	if ( n == NULL ) {
+		fputs("<empty tree>", stdout);
+		return;
+	}
+	if ( n->right != NULL ) {
+		print_tree_helper(n->right, indent + INDENT_STEP);
+	}
+	for ( i = 0; i < indent; i++ )
+		fputs(" ", stdout);
+	if ( n->color == BLACK )
+		printf("%d\n", (int) n->key);
+	else
+		printf("<%d>\n", (int) n->key);
+	if ( n->left != NULL ) {
+		print_tree_helper(n->left, indent + INDENT_STEP);
+	}
 }
 
-#if 0
-int main__(void)
+int
+main()
 {
-	struct rbtree *tree = NULL;
+	int    i;
+	rbtree t = rbtree_create();
 
-	srand(time(NULL));
-	for ( int i = 0; i != 10; ++i )
-		rb_insert_node(&tree, rand());
+	for ( i = 0; i < 50; i++ ) {
+		long x = rand() % 10000;
+		long y = rand() % 10000;
+#ifdef TRACE
+		print_tree(t);
+		printf("Inserting %ld -> %ld\n\n", x, y);
+#endif
+		rbtree_insert(t, (void *) x, (void *) y, compare_int);
+		assert(rbtree_lookup(t, (void *) x, compare_int) == (void *) y);
+	}
 
-}
+	print_tree(t);
+
+	for ( i = 0; i < 60000; i++ ) {
+		long x = rand() % 10000;
+#ifdef TRACE
+		print_tree(t);
+		printf("Deleting key %ld\n\n", x);
 #endif
+		rbtree_delete(t, (void *) x, compare_int);
+	}
+	return 0;
+}
-- 
cgit v1.3