Code Cleanup für Red-Black-Trees

1 files changed, 483 insertions, 535 deletions

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
+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
+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);
+
+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) {
+
+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_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);
+
+void
+verify_property_2(node root)
+{
+        assert(node_color(root) == BLACK);
 }
-color node_color(node n) {
-    return n == NULL ? BLACK : n->color;
+
+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_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(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);
+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;
+
+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
+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;
+
+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 *
+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_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
+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
+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
+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_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_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_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_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
+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);
+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;
+        }
 
-    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);
+        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);
 }
-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);
+
+static node
+maximum_node(node n)
+{
+        assert(n != NULL);
+        while ( n->right != NULL ) {
+                n = n->right;
+        }
+        return 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_case1(rbtree t, node n)
+{
+        if ( n->parent == NULL )
+                return;
+        else
+                delete_case2(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_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_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_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_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
+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(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);
-    }
+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);
+int
+main()
+{
+        int    i;
+        rbtree t = rbtree_create();
 
-    for(i=0; i<5000; i++) {
-        long x = rand() % 10000;
-        long y = rand() % 10000;
+        for ( i = 0; i < 50; i++ ) {
+                long x = rand() % 10000;
+                long y = rand() % 10000;
 #ifdef TRACE
-        print_tree(t);
-        printf("Inserting %d -> %d\n\n", x, y);
+                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);
-    }
-    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;
-}
-
-#if 0
-int main__(void)
-{
-        struct rbtree *tree = NULL;
+                rbtree_insert(t, (void *) x, (void *) y, compare_int);
+                assert(rbtree_lookup(t, (void *) x, compare_int) == (void *) y);
+        }
 
-        srand(time(NULL));
-        for ( int i = 0; i != 10; ++i )
-                rb_insert_node(&tree, rand());
+        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;
+}