rbtree.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

Include dependency graph for rbtree.c:

Go to the source code of this file.

Data Structures
struct	element

Macros
#define	NVALUES   10

Enumerations
enum	rbColor { rbBlack =1, rbRed =2, rbBlack =1, rbRed =2 }

Functions
struct element *	newElement (size_t size)
struct element *	findElement (struct element *tree, size_t size)
struct element *	grandparent (struct element *node)
struct element *	uncle (struct element *node)
struct element *	sibling (struct element *node)
void	rotateLeft (struct element **tree, struct element *node)
void	rotateRight (struct element **tree, struct element *node)
void	replaceNode (struct element **tree, struct element *node1, struct element *node2)
struct element *	insertElement (struct element **tree, struct element *element)
struct element *	findInOrderSuccessor (struct element *tree)
struct element *	deleteOneChild (struct element **, struct element *)
struct element *	deleteElement (struct element **tree, struct element *element)
void	traverse (struct element *tree, void(*cb)(struct element *, int))
void	post (struct element *tree, void(*cb)(struct element *, int))
void	printElement (struct element *node, int depth)
void	cleanup (struct element *node, int depth)
int	main (int argc, char *argv[])

---

Data Structure Documentation

struct element

Definition at line 5 of file binarytree.c.

Collaboration diagram for element:

Data Fields
enum rbColor	color
int	data
struct element *	last
struct element *	left
struct element *	next
struct element *	parent
void *	ptr
struct element *	right
size_t	size

Macro Definition Documentation

#define NVALUES   10

Definition at line 5 of file rbtree.c.

Enumeration Type Documentation

enum rbColor

Enumerator
rbBlack
rbRed
rbBlack
rbRed

Definition at line 7 of file rbtree.c.

{rbBlack=1, rbRed=2};

Function Documentation

void cleanup	(	struct element *	node,
		int	depth
	)

Definition at line 697 of file rbtree.c.

References element::next, and printElement().

{
    while (NULL != node) {
        printf("free node: ");
        printElement(node, 0);
        struct element * next = node->next;
        free(node);
        node = next;
    }
}

Here is the call graph for this function:

struct element* deleteElement	(	struct element **	tree,
		struct element *	element
	)

Definition at line 339 of file rbtree.c.

References element::color, findInOrderSuccessor(), element::last, element::left, element::next, element::parent, rbBlack, rbRed, replaceNode(), element::right, rotateLeft(), rotateRight(), sibling(), and element::size.

Referenced by main().

{
    struct element * node = *tree;
    struct element * del_node;
    struct element * child;
    struct element * s;

    // find the relevant node and it's parent
    while (NULL != node) {

        if (element->size < node->size) {
            node = node->left;
        } else if (element->size > node->size) {
            node = node->right;
        } else {
            if (NULL != node->next) {
                if (NULL != node->parent) {
                    if (node == node->parent->left) {
                        node->parent->left = node->next;
                    } else {
                        node->parent->right = node->next;
                    }
                } else {
                    *tree = node->next;
                }

                if (NULL != node->left) {
                    node->left->parent = node->next;
                }

                if (NULL != node->right) {
                    node->right->parent = node->next;
                }
                
                node->next->last   = node->last;
                node->next->color  = node->color;
                node->next->parent = node->parent;
                node->next->left   = node->left;
                node->next->right  = node->right;

                return node;
            }
            break;
        }
    }

    // element not found
    if (NULL == node) {
        return node;
    }

    del_node = node;

    // now our cases follows...the first one is the same as with
    // simple binary search trees. Two non null children.

    // case 1: two children
    if (NULL != node->left && NULL != node->right) {
        struct element * successor = findInOrderSuccessor(node);

        enum rbColor tmpcolor      = successor->color;
        struct element * tmpparent = successor->parent;
        struct element * tmpleft   = successor->left;
        struct element * tmpright  = successor->right;

        replaceNode(tree, node, successor);

        successor->color        = node->color;
        successor->left         = node->left;
        successor->left->parent = successor;
        // the right one might be successor...
        if (node->right == successor) {
            successor->right = node;
            node->parent     = successor;
        } else {
            successor->right    = node->right;
            node->right->parent = successor;
            node->parent        = tmpparent;
            tmpparent->left     = node;
        }

        node->color  = tmpcolor;
        node->left   = tmpleft;
        node->right  = tmpright;
    }

    // Precondition: n has at most one non-null child.
    child = (NULL == node->right) ? node->left : node->right;
    replaceNode(tree, node, child);

    // delete one child case
    // TODO this is overly complex as simply derived from the function...
    // maybe this can be simplified. Maybe not...check.
    if (node->color == rbBlack) {
        if (NULL != child && child->color == rbRed) {
            child->color = rbBlack;
            // done despite modifying tree itself if neccessary..
            return del_node;
        } else {
            if (NULL != child) {
                node = child;
            } else {
                node->color = rbBlack;
                node->left  = NULL;
                node->right = NULL;
            }
        }
    } else {
        return del_node;
    }

    // delete and rb rebalance...
    while(1) {
        // case 1
        if (NULL == node->parent) {
            // done again
            break;
        }

        // case 2
        s = sibling(node);

        if (NULL != s && s->color == rbRed) {
            node->parent->color = rbRed;
            s->color            = rbBlack;

            /*
             * detect which child we are...assumption
             * if we are not parent->right and parent->right is not
             * null we must be left, even if its set to NULL previously
             */
            if (NULL != node->parent->right && node != node->parent->right) {
                rotateLeft(tree, node->parent);
            } else {
                rotateRight(tree, node->parent);
            }
        }

        s = sibling(node);
        // case 3 / 4
        if (NULL == s || ((s->color == rbBlack) &&
                    (NULL == s->left || s->left->color == rbBlack) &&
                    (NULL == s->right || s->right->color == rbBlack))) {

            if (NULL != s) {
                s->color = rbRed;
            }

            if (node->parent->color == rbBlack) {
                // case 3
                node = node->parent;
                continue;
            } else {
                // case 4
                node->parent->color = rbBlack;
                // and done again...
                break;
            }
        }

        // case 5
        if  (NULL != s && s->color == rbBlack) {
            // this if statement is trivial,
            // due to case 2 (even though case 2 changed the sibling to a
            // sibling's child,
            // the sibling's child can't be red, since no red parent can
            // have a red child).
            //
            // the following statements just force the red to be on the
            // left of the left of the parent,
            // or right of the right, so case 6 will rotate correctly.
            if ((node == node->parent->left) &&
                    (NULL == s->right || s->right->color == rbBlack) &&
                    (NULL != s->left && s->left->color == rbRed)) {

                // this last test is trivial too due to cases 2-4.
                s->color       = rbRed;
                s->left->color = rbBlack;

                rotateRight(tree, s);
            } else if ((node == node->parent->right) &&
                    (NULL == s->left || s->left->color == rbBlack) &&
                    (NULL != s->right && s->right->color == rbRed)) {
                // this last test is trivial too due to cases 2-4.
                s->color        = rbRed;
                s->right->color = rbBlack;

                rotateLeft(tree, s);
            }
        }

        s = sibling(node);
        // case 6
        if (NULL != s) {
            s->color = node->parent->color;
        }

        if (NULL != node && NULL != node->parent) {
            node->parent->color = rbBlack;

            /*
             * detect which child we are...assumption
             * if we are not parent->right and parent->right is not
             * null we must be left, even if its set to NULL previously
             */
            if (NULL != node->parent->right && node != node->parent->right) {
                if (NULL != s->right) {
                    s->right->color = rbBlack;
                }
                rotateLeft(tree, node->parent);
            } else {
                if (NULL != s->left) {
                    s->left->color = rbBlack;
                }
                rotateRight(tree, node->parent);
            }
        }

        // done...
        break;
    }
 
    //deleteOneChild(tree, node);

    return del_node;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct element* deleteOneChild	(	struct element **	,
		struct element *
	)

struct element* findElement	(	struct element *	tree,
		size_t	size
	)

find element in tree

Definition at line 48 of file rbtree.c.

References element::left, element::right, and element::size.

Referenced by main().

{
    struct element * fitting = NULL;

    while (NULL != tree) {
        if (tree->size == size) {
            fitting = tree;
            break;
        }

        if (size > tree->size) {
            tree = tree->right;
        } else {
            fitting = tree;
            tree    = tree->left;
        }
    }

    return fitting;
}

Here is the caller graph for this function:

struct element* findInOrderSuccessor

(

struct element *

tree

)

delete element from tree

here multiple functions are involved....

find minimum of the right subtree aka leftmost leaf of right subtree aka left in-order successor. We return the parent of the element in the out argument parent. This can be NULL wenn calling.

2: *successor = {size = 80, ptr = 0x603ae0, color = rbRed, parent = 0x603160, left = 0x0, right = 0x0} 1: *node = {size = 70, ptr = 0x603a60, color = rbBlack, parent = 0x603070, left = 0x6030e0, right = 0x6031e0}

Definition at line 325 of file rbtree.c.

References element::left, and element::right.

Referenced by deleteElement().

{
    struct element * node = tree->right;

    while (NULL != node->left) {
        node = node->left;
    }

    return node;
}

Here is the caller graph for this function:

struct element* grandparent

(

struct element *

node

)

Definition at line 74 of file rbtree.c.

References element::parent.

Referenced by insertElement(), and uncle().

{
    if (NULL != node && NULL != node->parent) {
        return node->parent->parent;
    }

    return NULL;
}

Here is the caller graph for this function:

struct element* insertElement	(	struct element **	tree,
		struct element *	element
	)

insert element in tree

Definition at line 194 of file rbtree.c.

References element::color, grandparent(), element::last, element::left, element::next, element::parent, rbBlack, rbRed, element::right, rotateLeft(), rotateRight(), element::size, and uncle().

Referenced by main().

{
    struct element * node     = *tree;
    struct element * new_node = NULL;
    struct element * u;
    struct element * g;

    element->next   = NULL;
    element->last   = NULL;

    element->color  = rbRed;
    element->parent = NULL;
    element->left   = NULL;
    element->right  = NULL;

    // if tree is empty it's simple... :)
    if (NULL == node) {
        *tree = node = new_node = element;
    } else {
        // normal binary tree add....
        while (NULL != node) {
            if (element->size < node->size) {
                if (NULL == node->left) {
                    node->left         = element;
                    node->left->parent = node;
                    new_node = node = node->left;
                    break;
                } else {
                    node = node->left;
                }
            } else if (element->size > node->size) {
                if (NULL == node->right) {
                    node->right         = element;
                    node->right->parent = node;
                    new_node = node = node->right;
                    break;
                } else {
                    node = node->right;
                }
            } else {
                if (NULL == node->next) {
                    node->next = element;
                    node->last = element;
                } else {
                    node->last->next = element;
                    node->last       = element;
                }
                return node;
            }
        }
    }

    if (NULL != new_node) {
        /* 
         * handle reballancing rb style
         */
        while (1) {
            // case 1
            if (node->parent == NULL) {
                node->color = rbBlack;
                // we're done.... :)
                break;
            }

            // case 2
            if (node->parent->color == rbBlack) {
                // Tree is still valid ... wow, again we're done... :)
                break;
            }

            // case 3
            u = uncle(node);
            g = grandparent(node);

            if (u != NULL && u->color == rbRed) {
                node->parent->color = rbBlack;
                u->color            = rbBlack;
                g->color            = rbRed;

                node = g;
                continue;
            }

            // case 4
            if (node == node->parent->right && node->parent == g->left) {
                rotateLeft(tree, node->parent);
                node = node->left; 
            } else if (node == node->parent->left && node->parent == g->right) {

                rotateRight(tree, node->parent);
                node = node->right; 
            }

            // case 5
            g = grandparent(node);

            node->parent->color = rbBlack;
            g->color            = rbRed;

            if (node == node->parent->left) {
                rotateRight(tree, g);
            } else {
                rotateLeft(tree, g);
            }

            // we're done..
            break;
        }
    }

    return new_node;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int main	(	int	argc,
		char *	argv[]
	)

=======================================================================

Definition at line 712 of file rbtree.c.

References deleteElement(), findElement(), insertElement(), newElement(), printElement(), and traverse().

{
    struct element * root  = NULL;
    struct element * found = NULL;

    insertElement(&root, newElement(40));
    insertElement(&root, newElement(50));
    insertElement(&root, newElement(60));
    insertElement(&root, newElement(70));
    insertElement(&root, newElement(80));
    insertElement(&root, newElement(45));
    insertElement(&root, newElement(75));
    insertElement(&root, newElement(85));
    puts("traverse");
    traverse(root, printElement);
    puts("");

    insertElement(&root, newElement(70));
    puts("traverse");
    traverse(root, printElement);
    puts("");

    found = findElement(root, 10);
    if (NULL == found) {
        printf("can't find segmenet of minimum size: %d\n", 10);
    } else {
        printElement(found, 0);
    }
    puts("");

    found = findElement(root, 64);
    if (NULL == found) {
        printf("can't find segmenet of minimum size: %d\n", 64);
    } else {
        printElement(found, 0);
    }
    puts("");

    found = findElement(root, 90);
    if (NULL == found) {
        printf("can't find segmenet of minimum size: %d\n", 90);
    } else {
        printElement(found, 0);
    }
    puts("");

    free(deleteElement(&root, findElement(root, 70)));
    puts("traverse");
    traverse(root, printElement);
    puts("");

    insertElement(&root, newElement(80));
    insertElement(&root, newElement(50));
    insertElement(&root, newElement(80));

    puts("traverse");
    traverse(root, printElement);
    puts("");

    found = deleteElement(&root, findElement(root, 80));
    printf("up to free: %p\n", found);
    free(found);
    puts("traverse");
    traverse(root, printElement);
    puts("");

    found = deleteElement(&root, findElement(root, 50));
    printf("up to free: %p\n", found);
    free(found);
    puts("traverse");
    traverse(root, printElement);
    puts("");

    found = deleteElement(&root, findElement(root, 70));
    printf("up to free: %p\n", found);
    free(found);
    puts("traverse");
    traverse(root, printElement);
    puts("");

//    post(root, cleanup);
//
    return 0;
}

Here is the call graph for this function:

struct element* newElement

(

size_t

size

)

Definition at line 26 of file rbtree.c.

References element::color, element::last, element::left, element::next, element::parent, element::ptr, rbRed, element::right, element::size, and size.

Referenced by main().

{
    struct element * element = malloc(size + sizeof(struct element));

    element->size   = size;
    element->ptr    = element + sizeof(struct element);

    element->next   = NULL;
    element->last   = NULL;

    element->color  = rbRed;
    element->parent = NULL;
    element->left   = NULL;
    element->right  = NULL;

    return element;
}

Here is the caller graph for this function:

void post	(	struct element *	tree,
		void(*)(struct element *, int)	cb
	)

Definition at line 618 of file rbtree.c.

References cb, element::left, element::parent, and element::right.

Referenced by CLASS(), httpRequestCtor(), and httpRequestDtor().

{
    struct element * previous = tree;
    struct element * node     = tree;
    int              depth    = 1;

    /*
     * I think this has something like O(n+log(n)) on a ballanced
     * tree because I have to traverse back the rightmost leaf to
     * the root to get a break condition.
     */
    while (node) {
        /*
         * If we come from the right so nothing and go to our
         * next parent.
         */
        if ((NULL == node->left && NULL == node->right)
                || previous == node->right) {

            struct element * parent = node->parent;

            cb(node, depth);

            previous = node;
            node     = parent;
            depth--;
            continue;
        }

        if ((NULL == node->left || previous == node->left)) {
            /*
             * If there are no more elements to the left or we
             * came from the left, process data.
             */
            previous = node;

            if (NULL != node->right) {
                node = node->right;
                depth++;
            } else {
                node = node->parent;
                depth--;
            }
        } else {
            /*
             * if there are more elements to the left go there.
             */
            previous = node;
            node     = node->left;
            depth++;
        }
    }
}

Here is the caller graph for this function:

void printElement	(	struct element *	node,
		int	depth
	)

Definition at line 672 of file rbtree.c.

References element::color, element::next, element::ptr, rbRed, and element::size.

Referenced by cleanup(), and main().

{
    int  i;

    printf("%s %010zu:%p(%02d)",
            (node->color==rbRed)?"R":"B",
            node->size,
            node->ptr,
            depth);
    for (i=0; i<depth; i++) printf("-");
    puts("");

    node = node->next;
    while (NULL != node) {
        printf("  %s %010zu:%p(%02d)",
                (node->color==rbRed)?"R":"B",
                node->size,
                node->ptr,
                depth);
        for (i=0; i<depth; i++) printf("-");
        puts("");
        node = node->next;
    }
}

Here is the caller graph for this function:

void replaceNode	(	struct element **	tree,
		struct element *	node1,
		struct element *	node2
	)

Definition at line 169 of file rbtree.c.

References element::left, element::parent, and element::right.

Referenced by deleteElement().

{
    if (NULL != node1->parent) {
        if (node1 == node1->parent->left) {
            node1->parent->left = node2;
        } else {
            node1->parent->right = node2;
        }
    } else {
        *tree = node2;
    }

    if (NULL != node2) {
        node2->parent = node1->parent;
    }
}

Here is the caller graph for this function:

void rotateLeft	(	struct element **	tree,
		struct element *	node
	)

Definition at line 117 of file rbtree.c.

References element::left, element::parent, and element::right.

Referenced by deleteElement(), and insertElement().

{
    struct element * rightChild = node->right;
    struct element * rcLeftSub  = node->right->left;

    rightChild->left   = node;
    rightChild->parent = node->parent;
    node->right        = rcLeftSub;
    if (NULL != rcLeftSub) {
        rcLeftSub->parent  = node;
    }

    if (node->parent) {
        if (node->parent->left == node) {
            node->parent->left = rightChild;
        } else {
            node->parent->right = rightChild;
        }
    } else {
        *tree = rightChild;
    }

    node->parent = rightChild;
}

Here is the caller graph for this function:

void rotateRight	(	struct element **	tree,
		struct element *	node
	)

Definition at line 143 of file rbtree.c.

References element::left, element::parent, and element::right.

Referenced by deleteElement(), and insertElement().

{
    struct element * leftChild  = node->left;
    struct element * lcRightSub = node->left->right;

    leftChild->right   = node;
    leftChild->parent  = node->parent;
    node->left         = lcRightSub;
    if (NULL != lcRightSub) {
        lcRightSub->parent = node;
    }

    if (node->parent) {
        if (node->parent->left == node) {
            node->parent->left = leftChild;
        } else {
            node->parent->right = leftChild;
        }
    } else {
        *tree = leftChild;
    }

    node->parent = leftChild;
}

Here is the caller graph for this function:

struct element* sibling

(

struct element *

node

)

Definition at line 100 of file rbtree.c.

References element::left, element::parent, and element::right.

Referenced by deleteElement().

{
    if (NULL == node) {
        return NULL;
    }

    if (NULL == node->parent->left || node == node->parent->left) {
        return node->parent->right;
    } else {
        return node->parent->left;
    }
}

Here is the caller graph for this function:

void traverse	(	struct element *	tree,
		void(*)(struct element *, int)	cb
	)

Definition at line 568 of file rbtree.c.

References cb, element::left, element::parent, and element::right.

Referenced by main().

{
    struct element * previous = tree;
    struct element * node     = tree;
    int              depth    = 1;

    /*
     * I think this has something like O(n+log(n)) on a ballanced
     * tree because I have to traverse back the rightmost leaf to
     * the root to get a break condition.
     */
    while (node) {
        /*
         * If we come from the right so nothing and go to our
         * next parent.
         */
        if (previous == node->right) {
            previous = node;
            node     = node->parent;
            depth--;
            continue;
        }

        if ((NULL == node->left || previous == node->left)) {
            /*
             * If there are no more elements to the left or we
             * came from the left, process data.
             */
            cb(node, depth);
            previous = node;

            if (NULL != node->right) {
                node = node->right;
                depth++;
            } else {
                node = node->parent;
                depth--;
            }
        } else {
            /*
             * if there are more elements to the left go there.
             */
            previous = node;
            node     = node->left;
            depth++;
        }
    }
}

Here is the caller graph for this function:

struct element* uncle

(

struct element *

node

)

Definition at line 84 of file rbtree.c.

References grandparent(), element::left, element::parent, and element::right.

Referenced by insertElement().

{
    struct element * gp = grandparent(node);

    if (NULL == gp) {
        return NULL;
    }

    if (node->parent == gp->left) {
        return gp->right;
    }

    return gp->left;
}

Here is the call graph for this function:

Here is the caller graph for this function: