tree_macros.h

Go to the documentation of this file.

/**
 * \file
 *
 * \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/>.
 */

#ifndef __TR_TREE_MACROS_H__
#define __TR_TREE_MACROS_H__

#include "trbase.h"

#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)       \
    (NULL!=(node)->parent?          \
     ((node)==(node)->parent->left? \
      (node)->parent->right:        \
      (node)->parent->left):        \
     NULL)

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

#define TR_TREE_REPLACE_NODE(root, node1, node2) \
    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;       \
    }

#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)                      \
    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;                         \
    }

typedef enum {rbBlack=1, rbRed=2} TR_rbColor;

#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) \
    succ = (node)->right;                \
    while (NULL != succ->left) {         \
        succ = succ->left;               \
    }

/*
 * Find data in a tree. 
 * Attention: This will change node, so normally you need to copy
 * it before using this macro.
 * Also be aware that found needs to be a valid lvalue and an integer.
 */
#define TR_TREE_FIND(node, search, found, comp)       \
    (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;                                \
            }                                         \
        }                                             \
    }

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

#define TR_TREE_BALANCE_DELETE_CASE2(root, node, sibling)   \
    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));                \
    }

#define TR_TREE_BALANCE_DELETE_CASE34(root, node, sibling) \
    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;                                           \
        }                                                    \
    }

/*
 * 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.
 */
#define TR_TREE_BALANCE_DELETE_CASE5(root, node, sibling)     \
    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));                    \
    }

#define TR_TREE_BALANCE_DELETE_CASE6(root, node, sibling) \
    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);  \
        }                                                   \
    }

#define TR_TREE_BALANCE_DELETE(root, node, sibling)              \
    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;                                                   \
    }

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

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

#define TR_TREE_BALANCE_INSERT_CASE3(node)            \
    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;                                     \
    }

#define TR_TREE_BALANCE_INSERT_CASE4(root, node)                  \
    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;                                   \
    }

#define TR_TREE_BALANCE_INSERT_CASE5(root, node)                   \
        (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);  \
        }

#define TR_TREE_BALANCE_INSERT(root, node)               \
    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;                                           \
    }

#endif // __TR_TREE_MACROS_H__

// vim: set ts=4 sw=4: