rbtree.c

nedit 是一款linux下的开发源码的功能强大的编辑器

static const char CVSID[] = "$Id: rbTree.c,v 1.7 2002/07/11 21:18:10 slobasso Exp $";
/*******************************************************************************
*                                                                              *
* rbTree.c -- Nirvana editor red-black balanced binary tree                    *
*                                                                              *
* Copyright (C) 2001 Mark Edel                                                 *
*                                                                              *
* This 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 2 of the License, or (at your option) any later   *
* version.                                                                     *
*                                                                              *
* This software 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 *
* software; if not, write to the Free Software Foundation, Inc., 59 Temple     *
* Place, Suite 330, Boston, MA  02111-1307 USA                                 *
*                                                                              *
* Nirvana Text Editor                                                          *
* July, 1993                                                                   *
*                                                                              *
* Written by Mark Edel                                                         *
*                                                                              *
*******************************************************************************/

/*
** rbTree is a red-black balanced binary tree
** the base node holds the leftmost, rightmost and root pointers
** and a node count
*/

#ifdef HAVE_CONFIG_H
#include "../config.h"
#endif

#include "rbTree.h"

#include <stdlib.h>
#include <string.h>
/*#define RBTREE_TEST_CODE*/
#ifdef RBTREE_TEST_CODE
#include <stdio.h>
#endif

#ifdef HAVE_DEBUG_H
#include "../debug.h"
#endif


#define rbTreeNodeRed       0
#define rbTreeNodeBlack     1

/*
** rotate a node left
*/
static void rotateLeft(rbTreeNode *x, rbTreeNode **root)
{
    rbTreeNode *y = x->right;
    x->right = y->left;
    if (y->left != NULL) {
        y->left->parent = x;
    }
    y->parent = x->parent;

    if (x == *root) {
        *root = y;
    }
    else if (x == x->parent->left) {
        x->parent->left = y;
    }
    else {
        x->parent->right = y;
    }
    y->left = x;
    x->parent = y;
}

/*
** rotate a node right
*/
static void rotateRight(rbTreeNode *x, rbTreeNode **root)
{
    rbTreeNode *y = x->left;
    x->left = y->right;
    if (y->right != NULL) {
        y->right->parent = x;
    }
    y->parent = x->parent;

    if (x == *root) {
        *root = y;
    }
    else if (x == x->parent->right) {
        x->parent->right = y;
    }
    else {
        x->parent->left = y;
    }
    y->right = x;
    x->parent = y;
}

/*
** balance tree after an insert of node x
*/
static void insertBalance(rbTreeNode *x, rbTreeNode **root)
{
  x->color = rbTreeNodeRed;
  while (x != *root && x->parent->color == rbTreeNodeRed) {
    if (x->parent == x->parent->parent->left) {
      rbTreeNode *y = x->parent->parent->right;
      if (y && y->color == rbTreeNodeRed) {
        x->parent->color = rbTreeNodeBlack;
        y->color = rbTreeNodeBlack;
        x->parent->parent->color = rbTreeNodeRed;
        x = x->parent->parent;
      }
      else {
        if (x == x->parent->right) {
          x = x->parent;
          rotateLeft(x, root);
        }
        x->parent->color = rbTreeNodeBlack;
        x->parent->parent->color = rbTreeNodeRed;
        rotateRight(x->parent->parent, root);
      }
    }
    else {
      rbTreeNode *y = x->parent->parent->left;
      if (y && y->color == rbTreeNodeRed) {
        x->parent->color = rbTreeNodeBlack;
        y->color = rbTreeNodeBlack;
        x->parent->parent->color = rbTreeNodeRed;
        x = x->parent->parent;
      }
      else {
        if (x == x->parent->left) {
          x = x->parent;
          rotateRight(x, root);
        }
        x->parent->color = rbTreeNodeBlack;
        x->parent->parent->color = rbTreeNodeRed;
        rotateLeft(x->parent->parent, root);
      }
    }
  }
  (*root)->color = rbTreeNodeBlack;
}

/*
** returns the leftmost node (the beginning of the sorted list)
*/
rbTreeNode *rbTreeBegin(rbTreeNode *base)
{
    return(base->left);
}

/*
** returns the rightmost node (the end of the sorted list)
*/
rbTreeNode *rbTreeReverseBegin(rbTreeNode *base)
{
    return(base->right);
}

/*
** search for a node and return it's pointer, NULL if not found
*/
rbTreeNode *rbTreeFind(rbTreeNode *base, rbTreeNode *searchNode,
                        rbTreeCompareNodeCB compareRecords)
{
    rbTreeNode *foundNode = NULL;
    rbTreeNode *current = base->parent;
    while(current != NULL) {
        int compareResult = compareRecords(searchNode, current);

        if (compareResult < 0) {
            current = current->left;
        }
        else if (compareResult > 0) {
            current = current->right;
        }
        else {
            foundNode = current;
            current = NULL;
        }
    }
    return(foundNode);
}

/*
** insert a node into the tree and rebalance it
** if a duplicate is found copy the new data over it
** returns the new node
*/
rbTreeNode *rbTreeInsert(rbTreeNode *base, rbTreeNode *searchNode,
                            rbTreeCompareNodeCB compareRecords,
                            rbTreeAllocateNodeCB allocateNode,
                            rbTreeCopyToNodeCB copyToNode)
{
    rbTreeNode *current, *parent, *x;
    int fromLeft = 0, foundMatch = 0;

    current = base->parent;
    parent = NULL;
    x = NULL;
    while(current != NULL) {
        int compareResult = compareRecords(searchNode, current);

        if (compareResult < 0) {
            parent = current;
            current = current->left;
            fromLeft = 1;
        }
        else if (compareResult > 0) {
            parent = current;
            current = current->right;
            fromLeft = 0;
        }
        else {
            x = current;
            if (!copyToNode(x, searchNode)) {
                x = NULL;
            }
            current = NULL;
            foundMatch = 1;
        }
    }

    if (!foundMatch) {
        x = allocateNode(searchNode);
        if (x) {
            x->parent = parent;
            x->left = NULL;
            x->right = NULL;
            x->color = rbTreeNodeRed;

            if (parent) {
                if (fromLeft) {
                    parent->left = x;
                }
                else {
                    parent->right = x;
                }
            }
            else {
                base->parent = x;
            }
            ++(base->color);
            if (x->parent == base->left && (x->parent == NULL || x->parent->left == x)) {
                base->left = x;
            }
            if (x->parent == base->right && (x->parent == NULL || x->parent->right == x)) {
                base->right = x;
            }
            insertBalance(x, &base->parent);
        }
    }
    return(x);
}

/*
** unlink a node from the tree and rebalance it.
** returns the removed node pointer
*/
rbTreeNode *rbTreeUnlinkNode(rbTreeNode *base, rbTreeNode *z)
{
    int swapColor;
    rbTreeNode *x, *y, *x_parent;

    y = z;
    if (y->left == NULL) {
        x = y->right;
        if (y == base->left) {
            base->left = rbTreeNext(y);
        }
    }
    else {
        if (y->right == NULL) {
            x = y->left;
            if (y == base->right) {
                base->right = rbTreePrevious(y);
            }
        }
        else {
            y = y->right;
            while (y->left != NULL) {
                y = y->left;
            }
            x = y->right;
        }
    }
    if (y != z) {
        z->left->parent = y;
        y->left = z->left;
        if (y != z->right) {
            x_parent = y->parent;
            if (x != NULL) {
                x->parent = y->parent;
            }
            y->parent->left = x;
            y->right = z->right;
            z->right->parent = y;
        }
        else {
            x_parent = y;
        }
        if (base->parent == z) {
            base->parent = y;
        }
        else if (z->parent->left == z) {
            z->parent->left = y;
        }
        else {
            z->parent->right = y;
        }
        y->parent = z->parent;

        swapColor = y->color;
        y->color = z->color;
        z->color = swapColor;

        y = z;
    }
    else {
        x_parent = y->parent;
        if (x != NULL) {
            x->parent = y->parent;
        }
        if (base->parent == z) {
            base->parent = x;
        }
        else {
            if (z->parent->left == z) {
                z->parent->left = x;
            }
            else {
                z->parent->right = x;
            }
        }
    }

    --(base->color);

    if (y->color != rbTreeNodeRed) { 
        while (x != base->parent && (x == NULL || x->color == rbTreeNodeBlack)) {
            if (x == x_parent->left) {
                rbTreeNode *w = x_parent->right;
                if (w->color == rbTreeNodeRed) {
                    w->color = rbTreeNodeBlack;
                    x_parent->color = rbTreeNodeRed;
                    rotateLeft(x_parent, &base->parent);
                    w = x_parent->right;
                }
                if ((w->left == NULL || 
                w->left->color == rbTreeNodeBlack) &&
                (w->right == NULL || 
                w->right->color == rbTreeNodeBlack)) {

                    w->color = rbTreeNodeRed;
                    x = x_parent;
                    x_parent = x_parent->parent;
                } else {
                    if (w->right == NULL || 
                    w->right->color == rbTreeNodeBlack) {

                        if (w->left) {
                            w->left->color = rbTreeNodeBlack;
                        }
                        w->color = rbTreeNodeRed;