#include "trbase.h"

Include dependency graph for tree_macros.h:

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

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

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

#define	TR_TREE_CHILD(node) (NULL==TR_TREE_RIGHT((node))?TR_TREE_LEFT((node)):TR_TREE_RIGHT((node)))

#define	TR_TREE_SIBLING(node)

#define	TR_TREE_UNCLE(node)

#define	TR_TREE_REPLACE_NODE(root, node1, node2)

#define	TR_TREE_ROT_RCLD_right(node) ((node)->left)

#define	TR_TREE_ROT_RCLD_left(node) ((node)->right)

#define	TR_TREE_ROTATE(lr, root, node)

#define	TR_TREE_NODE_BLACK(node) (NULL == (node) \|\| rbBlack == (node)->color)

#define	TR_TREE_NODE_RED(node) (NULL == (node) \|\| rbRed == (node)->color)

#define	TR_TREE_NODE_STRICT_BLACK(node) (NULL != (node) && rbBlack == (node)->color)

#define	TR_TREE_NODE_STRICT_RED(node) (NULL != (node) && rbRed == (node)->color)

#define	TR_TREE_INORDER_SUCC(node, succ)

#define	TR_TREE_FIND(node, search, found, comp)

#define	TR_TREE_BALANCE_DELETE_CASE1(node)

#define	TR_TREE_BALANCE_DELETE_CASE2(root, node, sibling)

#define	TR_TREE_BALANCE_DELETE_CASE34(root, node, sibling)

#define	TR_TREE_BALANCE_DELETE_CASE5(root, node, sibling)

#define	TR_TREE_BALANCE_DELETE_CASE6(root, node, sibling)

#define	TR_TREE_BALANCE_DELETE(root, node, sibling)

#define	TR_TREE_BALANCE_INSERT_CASE1(node)

#define	TR_TREE_BALANCE_INSERT_CASE2(node)

#define	TR_TREE_BALANCE_INSERT_CASE3(node)

#define	TR_TREE_BALANCE_INSERT_CASE4(root, node)

#define	TR_TREE_BALANCE_INSERT_CASE5(root, node)

#define	TR_TREE_BALANCE_INSERT(root, node)

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

Detailed Description

Author: Georg Hopp

Copyright: Copyright © 2014 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_macros.h.

Macro Definition Documentation

#define TR_TREE_BALANCE_DELETE	(	root,
		node,
		sibling
	)

Value:

while(1) {                                                   \
		TR_TREE_BALANCE_DELETE_CASE1((node))                     \
        sibling = TR_TREE_SIBLING(node);                         \
		TR_TREE_BALANCE_DELETE_CASE2((root), (node), (sibling))  \
		TR_TREE_BALANCE_DELETE_CASE34((root), (node), (sibling)) \
		TR_TREE_BALANCE_DELETE_CASE5((root), (node), (sibling))  \
		TR_TREE_BALANCE_DELETE_CASE6((root), (node), (sibling))  \
        break;                                                   \
    }

Definition at line 214 of file tree_macros.h.

#define TR_TREE_BALANCE_DELETE_CASE1 ( node )

Value:

if (NULL == (node)->parent) {          \
        break;                             \
    }

Definition at line 130 of file tree_macros.h.

#define TR_TREE_BALANCE_DELETE_CASE2	(	root,
		node,
		sibling
	)

Value:

if (NULL != (sibling) && rbRed == (sibling)->color) {   \
        (node)->parent->color = rbRed;                      \
        (sibling)->color      = rbBlack;                    \
        if (NULL != (node)->parent->right                   \
                && (node) != (node)->parent->right) {       \
			TR_TREE_ROTATE(left, (root), (node)->parent);   \
        } else {                                            \
			TR_TREE_ROTATE(right, (root), (node)->parent);  \
        }                                                   \
        (sibling) = TR_TREE_SIBLING((node));                \
    }

Definition at line 135 of file tree_macros.h.

#define TR_TREE_BALANCE_DELETE_CASE34	(	root,
		node,
		sibling
	)

Value:

if (NULL == (sibling)                                    \
            || (rbBlack == (sibling)->color                  \
                && TR_TREE_NODE_BLACK((sibling)->left)       \
                && TR_TREE_NODE_BLACK((sibling)->right))) {  \
        if (NULL != (sibling)) {                             \
            (sibling)->color = rbRed;                        \
        }                                                    \
        if (rbBlack == (node)->parent->color) {              \
            (node) = (node)->parent;                         \
            continue;                                        \
        } else {                                             \
            (node)->parent->color = rbBlack;                 \
            break;                                           \
        }                                                    \
    }

Definition at line 148 of file tree_macros.h.

#define TR_TREE_BALANCE_DELETE_CASE5	(	root,
		node,
		sibling
	)

Value:

if (NULL != (sibling) && rbBlack == (sibling)->color) {     \
        if ((node) == (node)->parent->left                      \
                && TR_TREE_NODE_BLACK((sibling)->right)         \
                && TR_TREE_NODE_STRICT_RED((sibling)->left)) {  \
            (sibling)->color       = rbRed;                     \
            (sibling)->left->color = rbBlack;                   \
            TR_TREE_ROTATE(right, (root), (sibling));           \
        } else if ((node) == (node)->parent->right              \
                && TR_TREE_NODE_BLACK((sibling)->left)          \
                && TR_TREE_NODE_STRICT_RED((sibling)->right)) { \
            (sibling)->color        = rbRed;                    \
            (sibling)->right->color = rbBlack;                  \
            TR_TREE_ROTATE(left, (root), (sibling));            \
        }                                                       \
        (sibling) = TR_TREE_SIBLING((node));                    \
    }

Definition at line 176 of file tree_macros.h.

#define TR_TREE_BALANCE_DELETE_CASE6	(	root,
		node,
		sibling
	)

Value:

if (NULL != (sibling)) {                                \
        (sibling)->color = (node)->parent->color;           \
    }                                                       \
    if (NULL != (node) && NULL != (node)->parent) {         \
        (node)->parent->color = rbBlack;                    \
        if (NULL != (node)->parent->right                   \
                && (node) != (node)->parent->right) {       \
            if (NULL != (sibling)->right) {                 \
                (sibling)->right->color = rbBlack;          \
            }                                               \
			TR_TREE_ROTATE(left, (root), (node)->parent);   \
        } else {                                            \
            if (NULL != (sibling)->left) {                  \
                (sibling)->left->color = rbBlack;           \
            }                                               \
			TR_TREE_ROTATE(right, (root), (node)->parent);  \
        }                                                   \
    }

Definition at line 194 of file tree_macros.h.

#define TR_TREE_BALANCE_INSERT	(	root,
		node
	)

Value:

while (1) {                                          \
		TR_TREE_BALANCE_INSERT_CASE1((node))             \
		TR_TREE_BALANCE_INSERT_CASE2((node))             \
        if (NULL != (node)->parent->parent) {            \
			TR_TREE_BALANCE_INSERT_CASE3((node))         \
			TR_TREE_BALANCE_INSERT_CASE4((root), (node)) \
			TR_TREE_BALANCE_INSERT_CASE5((root), (node)) \
        }                                                \
        break;                                           \
    }

Definition at line 266 of file tree_macros.h.

#define TR_TREE_BALANCE_INSERT_CASE1 ( node )

Value:

if (NULL == (node)->parent) {          \
        (node)->color = rbBlack;           \
        break;                             \
    }

Definition at line 225 of file tree_macros.h.

#define TR_TREE_BALANCE_INSERT_CASE2 ( node )

Value:

if (rbBlack == (node)->parent->color) { \
        break;                              \
    }

Definition at line 231 of file tree_macros.h.

#define TR_TREE_BALANCE_INSERT_CASE3 ( node )

Value:

if (NULL != TR_TREE_UNCLE(node)                   \
            && rbRed == TR_TREE_UNCLE(node)->color) { \
        (node)->parent->color         = rbBlack;      \
        TR_TREE_UNCLE(node)->color    = rbBlack;      \
        (node)->parent->parent->color = rbRed;        \
        (node) = (node)->parent->parent;              \
        continue;                                     \
    }

Definition at line 236 of file tree_macros.h.

#define TR_TREE_BALANCE_INSERT_CASE4	(	root,
		node
	)

Value:

if ((node) == (node)->parent->right                           \
            && (node)->parent == (node)->parent->parent->left) {  \
		TR_TREE_ROTATE(left, (root), (node)->parent);             \
        (node) = (node)->left;                                    \
    } else if ((node) == (node)->parent->left                     \
            && (node)->parent == (node)->parent->parent->right) { \
		TR_TREE_ROTATE(right, (root), (node)->parent);            \
        (node) = (node)->right;                                   \
    }

Definition at line 246 of file tree_macros.h.

#define TR_TREE_BALANCE_INSERT_CASE5	(	root,
		node
	)

Value:

(node)->parent->color         = rbBlack;                   \
        (node)->parent->parent->color = rbRed;                     \
        if ((node) == (node)->parent->left) {                      \
			TR_TREE_ROTATE(right, (root), (node)->parent->parent); \
        } else {                                                   \
			TR_TREE_ROTATE(left, (root), (node)->parent->parent);  \
        }

Definition at line 257 of file tree_macros.h.

#define TR_TREE_CHILD ( node ) (NULL==TR_TREE_RIGHT((node))?TR_TREE_LEFT((node)):TR_TREE_RIGHT((node)))

Definition at line 32 of file tree_macros.h.

#define TR_TREE_FIND	(	node,
		search,
		found,
		comp
	)

Value:

(found) = -1;                                     \
    if ((node)) {                                     \
        while (1) {                                   \
            (found) = (comp)((node)->data, (search)); \
            if (0 != (found)) {                       \
                if (0 < (found)) {                    \
                    if (! (node)->left) break;        \
                    (node) = (node)->left;            \
                } else {                              \
                    if (! (node)->right) break;       \
                    (node) = (node)->right;           \
                }                                     \
            } else {                                  \
                break;                                \
            }                                         \
        }                                             \
    }

Definition at line 111 of file tree_macros.h.

#define TR_TREE_INORDER_SUCC	(	node,
		succ
	)

Value:

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

Definition at line 99 of file tree_macros.h.

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

Definition at line 29 of file tree_macros.h.

#define TR_TREE_NODE_BLACK ( node ) (NULL == (node) || rbBlack == (node)->color)

Definition at line 90 of file tree_macros.h.

#define TR_TREE_NODE_RED ( node ) (NULL == (node) || rbRed == (node)->color)

Definition at line 92 of file tree_macros.h.

#define TR_TREE_NODE_STRICT_BLACK ( node ) (NULL != (node) && rbBlack == (node)->color)

Definition at line 94 of file tree_macros.h.

#define TR_TREE_NODE_STRICT_RED ( node ) (NULL != (node) && rbRed == (node)->color)

Definition at line 96 of file tree_macros.h.

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

Definition at line 30 of file tree_macros.h.

#define TR_TREE_REPLACE_NODE	(	root,
		node1,
		node2
	)

Value:

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

Definition at line 47 of file tree_macros.h.

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

Definition at line 28 of file tree_macros.h.

#define TR_TREE_ROT_RCLD_left ( node ) ((node)->right)

Definition at line 62 of file tree_macros.h.

#define TR_TREE_ROT_RCLD_right ( node ) ((node)->left)

Definition at line 61 of file tree_macros.h.

#define TR_TREE_ROTATE	(	lr,
		root,
		node
	)

Value:

if (NULL != (node)) {                                   \
        void * stPar   = node->parent;                      \
        void * relCld  = TR_TREE_ROT_RCLD_##lr(node);       \
        void * relCCld = TR_TREE_ROT_RCLD_##lr(node)->lr;   \
        void * nLeft_p = &TR_TREE_ROT_RCLD_##lr(node);      \
        if (NULL != relCCld) {                              \
            TR_TREE_ROT_RCLD_##lr(node)->lr->parent = node; \
        }                                                   \
        TR_TREE_ROT_RCLD_##lr(node)->lr = node;             \
        if (NULL != node->parent) {                         \
            if (node->parent->left == node) {               \
                node->parent->left = relCld;                \
            } else {                                        \
                node->parent->right = relCld;               \
            }                                               \
        } else {                                            \
            *(root) = relCld;                               \
        }                                                   \
        node->parent = relCld;                              \
        TR_TREE_ROT_RCLD_##lr(node)->parent = stPar;        \
        *(void**)nLeft_p = relCCld;                         \
    }

Definition at line 64 of file tree_macros.h.

#define TR_TREE_SIBLING ( node )

Value:

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

Definition at line 35 of file tree_macros.h.

#define TR_TREE_UNCLE ( node )

Value:

((node)->parent == (node)->parent->parent->left   \
     ? (node)->parent->parent->right                  \
     : (node)->parent->parent->left)

Definition at line 42 of file tree_macros.h.

Enumeration Type Documentation

enum TR_rbColor

Enumerator
rbBlack
rbRed

Definition at line 88 of file tree_macros.h.

88 {rbBlack=1, rbRed=2} TR_rbColor;

TR_rbColor

Definition: tree_macros.h:88

rbRed

Definition: tree_macros.h:88

rbBlack

Definition: tree_macros.h:88

Macros

Enumerations

Detailed Description

Macro Definition Documentation

Enumeration Type Documentation