#include "class.h"

Include dependency graph for tree.h:

This graph shows which files directly or indirectly include this file:

Macros
#define	TREE_RIGHT(node) (NULL!=(node)?(node)->right:NULL)

#define	TREE_LEFT(node) (NULL!=(node)?(node)->left:NULL)

#define	TREE_PARENT(node) (NULL!=(node)?(node)->parent:NULL)

#define	TREE_CHILD(node) (NULL==TREE_RIGHT((node))?TREE_LEFT((node)):TREE_RIGHT((node)))

#define	TREE_RIGHT_LEFT(node) (NULL!=TREE_RIGHT((node))?TREE_LEFT(TREE_RIGHT((node))):NULL)

#define	TREE_LEFT_RIGHT(node) (NULL!=TREE_LEFT((node))?TREE_RIGHT(TREE_LEFT((node))):NULL)

#define	TREE_SIBLING(node)

#define	TREE_GRANDPARENT(node) (NULL!=TREE_PARENT((node))?TREE_PARENT((node))->parent:NULL)

#define	TREE_UNCLE(node)

#define	TREE_ROTATE_LEFT(root, node)

#define	TREE_ROTATE_RIGHT(root, node)

#define	TREE_REPLACE_NODE(root, node1, node2)

Typedefs
typedef int(*	TreeComp) (const void , const void )

typedef void(*	TreeAction) (const void *, const int)

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

Functions
	CLASS (Tree)

void *	treeFind (Tree, const void *, TreeComp)

void *	treeInsert (Tree , const void , TreeComp)

void *	treeDelete (Tree , const void , TreeComp)

void	treeWalk (Tree, TreeAction)

void	treeDestroy (Tree *, TreeAction)

Detailed Description

Author: Georg Hopp

Copyright: Copyright © 2012 Georg Hopp

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.

Definition in file tree.h.

Macro Definition Documentation

#define TREE_CHILD ( node ) (NULL==TREE_RIGHT((node))?TREE_LEFT((node)):TREE_RIGHT((node)))

Definition at line 32 of file tree.h.

Referenced by treeDelete().

#define TREE_GRANDPARENT ( node ) (NULL!=TREE_PARENT((node))?TREE_PARENT((node))->parent:NULL)

Definition at line 48 of file tree.h.

Referenced by treeInsert().

#define TREE_LEFT ( node ) (NULL!=(node)?(node)->left:NULL)

Definition at line 29 of file tree.h.

Referenced by inOrderSuccessor(), treeDelete(), treeDestroy(), treeFind(), treeInsert(), treeRotateRight(), and treeWalk().

#define TREE_LEFT_RIGHT ( node ) (NULL!=TREE_LEFT((node))?TREE_RIGHT(TREE_LEFT((node))):NULL)

Definition at line 38 of file tree.h.

Referenced by treeRotateRight().

#define TREE_PARENT ( node ) (NULL!=(node)?(node)->parent:NULL)

Definition at line 30 of file tree.h.

Referenced by treeDelete(), treeDestroy(), treeInsert(), treeRotateLeft(), treeRotateRight(), and treeWalk().

#define TREE_REPLACE_NODE	(	root,
		node1,
		node2
	)

Value:

do {                                                 \
        if (NULL != TREE_PARENT((node1))) {              \
            if ((node1) == TREE_PARENT((node1))->left) { \
				TREE_PARENT((node1))->left = (node2);    \
            } else {                                     \
				TREE_PARENT((node1))->right = (node2);   \
            }                                            \
        } else {                                         \
            *(root) = (node2);                           \
        }                                                \
        if (NULL != (node2)) {                           \
            (node2)->parent = (node1)->parent;           \
        }                                                \
    } while(0)

Definition at line 98 of file tree.h.

Referenced by treeDelete().

#define TREE_RIGHT ( node ) (NULL!=(node)?(node)->right:NULL)

Definition at line 28 of file tree.h.

Referenced by inOrderSuccessor(), treeDelete(), treeDestroy(), treeFind(), treeInsert(), treeRotateLeft(), and treeWalk().

#define TREE_RIGHT_LEFT ( node ) (NULL!=TREE_RIGHT((node))?TREE_LEFT(TREE_RIGHT((node))):NULL)

Definition at line 35 of file tree.h.

Referenced by treeRotateLeft().

#define TREE_ROTATE_LEFT	(	root,
		node
	)

Value:

do {                                                    \
        if (NULL != TREE_RIGHT_LEFT((node))) {              \
			TREE_RIGHT_LEFT((node))->parent = (node);       \
        }                                                   \
		TREE_RIGHT((node))->left = (node);                  \
        if (NULL != TREE_PARENT((node))) {                  \
            if (TREE_PARENT((node))->left==(node)) {        \
				TREE_PARENT((node))->left = (node)->right;  \
            } else {                                        \
				TREE_PARENT((node))->right = (node)->right; \
            }                                               \
        } else {                                            \
            *(root) = (node)->right;                        \
        }                                                   \
        (node)->right  = TREE_RIGHT_LEFT((node));           \
        (node)->parent = (node)->right;                     \
		TREE_RIGHT((node))->parent = (node)->parent;        \
    } while(0)

Definition at line 58 of file tree.h.

#define TREE_ROTATE_RIGHT	(	root,
		node
	)

Value:

do {                                                    \
        if (NULL != TREE_LEFT_RIGHT((node))) {              \
			TREE_LEFT_RIGHT((node))->parent = (node);       \
        }                                                   \
		TREE_LEFT((node))->right = (node);                  \
        if (NULL != TREE_PARENT((node))) {                  \
            if (TREE_PARENT((node))->left==(node)) {        \
				TREE_PARENT((node))->left = (node)->left;   \
            } else {                                        \
				TREE_PARENT((node))->right = (node)->left;  \
            }                                               \
        } else {                                            \
            *(root) = (node)->left;                         \
        }                                                   \
		TREE_LEFT((node))->parent = (node)->parent;         \
        (node)->left   = TREE_LEFT_RIGHT((node));           \
        (node)->parent = (node)->right;                     \
    } while(0)

Definition at line 78 of file tree.h.

#define TREE_SIBLING ( node )

Value:

(NULL!=TREE_PARENT((node))?          \
     ((node)==TREE_PARENT((node))->left? \
      TREE_PARENT((node))->right:        \
      TREE_PARENT((node))->left):        \
     NULL)

Definition at line 41 of file tree.h.

Referenced by treeDelete().

#define TREE_UNCLE ( node )

Value:

(NULL!=TREE_GRANDPARENT((node))?                       \
     (TREE_PARENT((node))==TREE_GRANDPARENT((node))->left? \
	  TREE_GRANDPARENT((node))->right:                     \
	  TREE_GRANDPARENT((node))->left):                     \
     NULL)

Definition at line 51 of file tree.h.

Referenced by treeInsert().

Typedef Documentation

typedef void(* TreeAction) (const void *, const int)

Definition at line 128 of file tree.h.

typedef int(* TreeComp) (const void *, const void *)

Definition at line 127 of file tree.h.

Enumeration Type Documentation

enum rbColor

Enumerator
rbBlack
rbRed
rbBlack
rbRed

Definition at line 115 of file tree.h.

115 {rbBlack=1, rbRed=2};

rbBlack

Definition: tree.h:115

rbRed

Definition: tree.h:115

Function Documentation

CLASS ( Tree )

Definition at line 117 of file tree.h.

             {
     void * data;
 
     enum rbColor color;
 
     Tree parent;
     Tree left;
     Tree right;
 };

void* treeDelete	(	Tree *	,
		const void *	,
		TreeComp
	)

Definition at line 31 of file tree/delete.c.

References comp(), inOrderSuccessor(), rbBlack, rbRed, TREE_CHILD, TREE_LEFT, TREE_PARENT, TREE_REPLACE_NODE, TREE_RIGHT, TREE_SIBLING, treeRotateLeft(), and treeRotateRight().

Referenced by hashDelete(), hashDeleteByVal(), and main().

 {
     Tree   node = *this;
     Tree   del_node;
 
     void * data;
 
     /*
      * first search for it and if its found return the data
      * and we are done...
      */
     while (NULL != node) {
         int comparison = comp(node->data, search);
 
         if (0 < comparison) {
             node = TREE_LEFT(node);
             continue;
         }
 
         if (0 > comparison) {
             node = TREE_RIGHT(node);
             continue;
         }
 
         if (0 == comparison) {
             break;
         }
     }   
 
     /*
      * nothing was found...return NULL to indicate this.
      */
     if (NULL == node) {
         return NULL;
     }
 
     /*
      * we found an element, store its data pointer as we are
      * up to delete it.
      */
     data = node->data;
 
     /*
      * now remove the element.
      */
     
     /*
      * if we have two children replace data with the one from 
      * out inOrderSuccessor and remove the inOrderSuccessor.
      */
     if (NULL != TREE_LEFT(node) && NULL != TREE_RIGHT(node)) {
         Tree successor = inOrderSuccessor(node);
 
         node->data = successor->data;
         node       = successor;
     }
 
     {
         Tree child = TREE_CHILD(node);
 
         /*
          * if we still have one child replace ourself with it.
          */
         TREE_REPLACE_NODE(this, node, child);
 
         /*
          * and finally delete the node...and prepare ourselfs
          * for rebalancing.
          */
         if (rbBlack == node->color) {
             if (NULL != child && rbRed == child->color) {
                 child->color = rbBlack;
                 delete(node);
                 return data;
             } else {
                 del_node = node;
                 if (NULL != child) {
                     node = child;
                 } else {
                     node->color = rbBlack;
                     node->left  = NULL;
                     node->right = NULL;
                 }
             }
         } else {
             delete(node);
             return data;
         }
     }
 
     /*
      * now comes rebalancing...note that if we came to this point
      * the node is still not deleted.
      * This is because I am not sure if it is needed during the
      * rebalancing process...(this does not make much sense, but
      * to be honest I don't know now.)
      */
     while(1) {
         // case 1
         if (NULL == TREE_PARENT(node)) {
             break;
         }
 
         // case 2
         if (NULL != TREE_SIBLING(node)
                 && rbRed == TREE_SIBLING(node)->color) {
 
             TREE_PARENT(node)->color  = rbRed;
             TREE_SIBLING(node)->color = rbBlack;
 
             if (NULL != TREE_PARENT(node)->right &&
                     node != TREE_PARENT(node)->right) {
 
                 //TREE_ROTATE_LEFT(this, TREE_PARENT(node));
                 treeRotateLeft(this, TREE_PARENT(node));
 
             } else {
 
                 //TREE_ROTATE_RIGHT(this, TREE_PARENT(node));
                 treeRotateRight(this, TREE_PARENT(node));
 
             }
         }
 
         // case 3 / 4
         if (NULL == TREE_SIBLING(node)
                 || (rbBlack == TREE_SIBLING(node)->color
                     && (NULL == TREE_SIBLING(node)->left
                         || rbBlack == TREE_SIBLING(node)->left->color)
                     && (NULL == TREE_SIBLING(node)->right
                         || rbBlack == TREE_SIBLING(node)->right->color))) {
 
             if (NULL != TREE_SIBLING(node)) {
                 TREE_SIBLING(node)->color = rbRed;
             }
 
 
             /*
              * this is the point where during the balancing our tree
              * node can be finally deleted.
              */
             if (rbBlack == TREE_PARENT(node)->color) {
                 // case 3
                 Tree parent = node->parent;
                 node = parent;
                 continue;
             } else {
                 // case 4
                 TREE_PARENT(node)->color = rbBlack;
                 break;
             }
         }
 
         // case 5
         if (NULL != TREE_SIBLING(node)
                 && rbBlack == TREE_SIBLING(node)->color) {
 
             if (node == TREE_PARENT(node)->left
                     && (NULL == TREE_SIBLING(node)->right
                         || rbBlack == TREE_SIBLING(node)->right->color)
                     && (NULL != TREE_SIBLING(node)->left
                         && rbRed == TREE_SIBLING(node)->left->color)) {
 
                 TREE_SIBLING(node)->color       = rbRed;
                 TREE_SIBLING(node)->left->color = rbBlack;
 
                 //TREE_ROTATE_RIGHT(this, TREE_SIBLING(node));
                 treeRotateRight(this, TREE_SIBLING(node));
 
             } else if (node == TREE_PARENT(node)->right
                     && (NULL == TREE_SIBLING(node)->left
                         || rbBlack == TREE_SIBLING(node)->left->color)
                     && (NULL != TREE_SIBLING(node)->right
                         && rbRed == TREE_SIBLING(node)->right->color)) {
 
                 TREE_SIBLING(node)->color        = rbRed;
                 TREE_SIBLING(node)->right->color = rbBlack;
 
                 //TREE_ROTATE_LEFT(this, TREE_SIBLING(node));
                 treeRotateLeft(this, TREE_SIBLING(node));
             }
         }
         
         // case 6
         if (NULL != TREE_SIBLING(node)) {
             TREE_SIBLING(node)->color = TREE_PARENT(node)->color;
         }
 
         if (NULL != node && NULL != TREE_PARENT(node)) {
             TREE_PARENT(node)->color = rbBlack;
 
             if (NULL != TREE_PARENT(node)->right
                     && node != TREE_PARENT(node)->right) {
 
                 if (NULL != TREE_SIBLING(node)->right) {
                     TREE_SIBLING(node)->right->color = rbBlack;
                 }
                 //TREE_ROTATE_LEFT(this, TREE_PARENT(node));
                 treeRotateLeft(this, TREE_PARENT(node));
             } else {
                 if (NULL != TREE_SIBLING(node)->left) {
                     TREE_SIBLING(node)->left->color = rbBlack;
                 }
                 //TREE_ROTATE_RIGHT(this, TREE_PARENT(node));
                 treeRotateRight(this, TREE_PARENT(node));
             }
         }
 
         break;
     }
 
     delete(del_node);
     /*
      * not sure if deleting here is correct.
      */
     return data;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void treeDestroy	(	Tree *	,
		TreeAction
	)

Definition at line 26 of file destroy.c.

References TREE_LEFT, TREE_PARENT, and TREE_RIGHT.

Referenced by hashCleanup(), and main().

 {
     Tree previous = * this;
     Tree node     = * this;
     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 (NULL != node) {
         /*
          * If we come from the right so nothing and go to our
          * next parent.
          */
         if (((NULL == TREE_LEFT(node)
                 || previous == TREE_LEFT(node)) && NULL == TREE_RIGHT(node))
                 || previous == TREE_RIGHT(node)) {
             
             Tree parent = TREE_PARENT(node);
             
             action(node->data, depth);
             
             previous = node;
             delete(node);
             node = parent;
             depth--;
 
             continue;
         }
         
         if ((NULL == TREE_LEFT(node) || previous == TREE_LEFT(node))) {
             /*
              * If there are no more elements to the left or we
              * came from the left, process data.
              */
             previous = node;
             
             if (NULL != TREE_RIGHT(node)) {
                 node = TREE_RIGHT(node);
                 depth++;
             } else { 
                 node = TREE_PARENT(node);
                 depth--;
             }
         } else {
             /*
              * if there are more elements to the left go there.
              */
             previous = node;
             node     = TREE_LEFT(node);
             depth++;
         }
     }
     
     *this = NULL;
 }

Here is the caller graph for this function:

void* treeFind	(	Tree	,
		const void *	,
		TreeComp
	)

Definition at line 26 of file find.c.

References comp(), TREE_LEFT, and TREE_RIGHT.

Referenced by hashGet(), hashGetByVal(), and main().

 {
     while (NULL != this) {
         int comparison = comp(this->data, search);
 
         if (0 < comparison) {
             this = TREE_LEFT(this);
             continue;
         }
 
         if (0 > comparison) {
             this = TREE_RIGHT(this);
             continue;
         }
 
         if (0 == comparison) {
             break;
         }
     }   
 
     return NULL != this ? this->data : NULL;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void* treeInsert	(	Tree *	,
		const void *	,
		TreeComp
	)

Definition at line 29 of file insert.c.

References comp(), rbBlack, rbRed, TREE_GRANDPARENT, TREE_LEFT, TREE_PARENT, TREE_RIGHT, TREE_UNCLE, treeRotateLeft(), and treeRotateRight().

Referenced by hashAdd(), and main().

 {
     Tree node     = *this;
     Tree new_node = NULL;
 
     /*
      * insert the node or return the one in tree if comparison
      * succeeds.
      */
     if (NULL == node) {
         /*
          * if the root is NULL we simple add the element and set
          * node to it.
          */
         *this = node = new_node = new(Tree, search);
     } else {
         /*
          * first search for it and if its found return the data
          * and we are done...
          */
         int  comparison;
 
         while (NULL != node) {
             comparison = comp(node->data, search);
 
             if (0 < comparison) {
                 if (NULL != TREE_LEFT(node)) {
                     node = TREE_LEFT(node);
                     continue;
                 } else {
                     break;
                 }
             }
 
             if (0 > comparison) {
                 if (NULL != TREE_RIGHT(node)) {
                     node = TREE_RIGHT(node);
                     continue;
                 } else {
                     break;
                 }
             }
 
             if (0 == comparison) {
                 return node->data;
             }
         }   
 
         /*
          * as we have not found it now add a new element.
          */
         if (0 < comparison) {
             node->left = new(Tree, search);
             TREE_LEFT(node)->parent = node;
             node = new_node = TREE_LEFT(node);
         } else {
             node->right = new(Tree, search);
             TREE_RIGHT(node)->parent = node;
             node = new_node = TREE_RIGHT(node);
         }
     }
 
     /*
      * we expect node not to be NULL and pointing to our
      * new node at this point...now rabalance the tree
      */
     while (1) {
         // case 1
         if (NULL == TREE_PARENT(node)) {
             node->color = rbBlack;
             break;
         }
 
         // case 2
         if (rbBlack == TREE_PARENT(node)->color) {
             break;
         }
 
         // case 3
         if (NULL != TREE_UNCLE(node) && rbRed == TREE_UNCLE(node)->color) {
             TREE_PARENT(node)->color      = rbBlack;
             TREE_UNCLE(node)->color       = rbBlack;
             TREE_GRANDPARENT(node)->color = rbRed;
 
             node = TREE_GRANDPARENT(node);
             continue;
         }
 
         // case 4
         if (node == TREE_PARENT(node)->right
                 && TREE_PARENT(node) == TREE_GRANDPARENT(node)->left) {
 
             //TREE_ROTATE_LEFT(this, TREE_PARENT(node));
             treeRotateLeft(this, TREE_PARENT(node));
             node = TREE_LEFT(node);
 
         } else if (node == TREE_PARENT(node)->left
                 && TREE_PARENT(node) == TREE_GRANDPARENT(node)->right) {
 
             //TREE_ROTATE_RIGHT(this, TREE_PARENT(node));
             treeRotateRight(this, TREE_PARENT(node));
             node = TREE_RIGHT(node);
 
         }
 
         // case 5
         TREE_PARENT(node)->color      = rbBlack;
         TREE_GRANDPARENT(node)->color = rbRed;
 
         if (node == TREE_PARENT(node)->left) {
             //TREE_ROTATE_RIGHT(this, TREE_GRANDPARENT(node));
             treeRotateRight(this, TREE_GRANDPARENT(node));
         } else {
             //TREE_ROTATE_LEFT(this, TREE_GRANDPARENT(node));
             treeRotateLeft(this, TREE_GRANDPARENT(node));
         }
 
         break;
     }
 
     return new_node->data;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void treeWalk	(	Tree	,
		TreeAction
	)

Definition at line 26 of file walk.c.

References TREE_LEFT, TREE_PARENT, and TREE_RIGHT.

Referenced by hashEach(), and main().

 {
     Tree previous = this;
     Tree node     = this;
     int  depth    = 1;
 
     while (NULL != node) {
         if (previous == TREE_RIGHT(node)) {
             previous = node;
             node     = node->parent;
             depth--;
             continue;
         }
 
         if (NULL == TREE_LEFT(node) || previous == TREE_LEFT(node)) {
             action(node->data, depth);
             previous = node;
 
             if (NULL != TREE_RIGHT(node)) {
                 node = TREE_RIGHT(node);
                 depth++;
             } else {
                 node = TREE_PARENT(node);
                 depth--;
             }
         } else {
             previous = node;
             node     = TREE_LEFT(node);
             depth++;
         }
     }
 }

Here is the caller graph for this function:

Macros

Typedefs

Enumerations

Functions

Detailed Description

Macro Definition Documentation

Typedef Documentation

Enumeration Type Documentation

Function Documentation