rbtree.c

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

                        rotateRight(w, &base->parent);
                        w = x_parent->right;
                    }
                    w->color = x_parent->color;
                    x_parent->color = rbTreeNodeBlack;
                    if (w->right) {
                        w->right->color = rbTreeNodeBlack;
                    }
                    rotateLeft(x_parent, &base->parent);
                    break;
                }
            }
            else {
                rbTreeNode *w = x_parent->left;
                if (w->color == rbTreeNodeRed) {
                    w->color = rbTreeNodeBlack;
                    x_parent->color = rbTreeNodeRed;
                    rotateRight(x_parent, &base->parent);
                    w = x_parent->left;
                }
                if ((w->right == NULL || 
                    w->right->color == rbTreeNodeBlack) &&
                    (w->left == NULL || 
                    w->left->color == rbTreeNodeBlack)) {

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

                        if (w->right) {
                            w->right->color = rbTreeNodeBlack;
                        }
                        w->color = rbTreeNodeRed;
                        rotateLeft(w, &base->parent);
                        w = x_parent->left;
                    }
                    w->color = x_parent->color;
                    x_parent->color = rbTreeNodeBlack;
                    if (w->left) {
                        w->left->color = rbTreeNodeBlack;
                    }
                    rotateRight(x_parent, &base->parent);
                    break;
                }
            }
        }
        if (x) {
            x->color = rbTreeNodeBlack;
        }
    }
    return(y);
}

/*
** delete an already found node and dispose it
*/
void rbTreeDeleteNode(rbTreeNode *base, rbTreeNode *foundNode,
                    rbTreeDisposeNodeCB disposeNode)
{
    disposeNode(rbTreeUnlinkNode(base, foundNode));
}

/*
** search for a node and remove it from the tree
** disposing the removed node
** returns 1 if a node was found, otherwise 0
*/
int rbTreeDelete(rbTreeNode *base, rbTreeNode *searchNode,
                    rbTreeCompareNodeCB compareRecords,
                    rbTreeDisposeNodeCB disposeNode)
{
    int foundNode = 0;
    rbTreeNode *z;

    z = rbTreeFind(base, searchNode, compareRecords);
    if (z != NULL) {
        rbTreeDeleteNode(base, z, disposeNode);
        foundNode = 1;
    }
    return(foundNode);
}

/*
** move an iterator foreward one element
** note that a valid pointer must be passed,
** passing NULL will result in unpredictable results
*/
rbTreeNode *rbTreeNext(rbTreeNode *x)
{
    if (x->right != NULL) {
        x = x->right;
        while (x->left != NULL) {
            x = x->left;
        }
    }
    else {
        rbTreeNode *fromX;
        do {
            fromX = x;
            x = x->parent;
        } while (x && fromX == x->right);
    }
    return(x);
}

/*
** move an iterator back one element
** note that a valid pointer must be passed,
** passing NULL will result in unpredictable results
*/
rbTreeNode *rbTreePrevious(rbTreeNode *x)
{
    if (x->left != NULL) {
        x = x->left;
        while (x->right != NULL) {
            x = x->right;
        }
    }
    else {
        rbTreeNode *fromX;
        do {
            fromX = x;
            x = x->parent;
        } while (x && fromX == x->left);
    }
    return(x);
}

/*
** returns the number of real data nodes in the tree, not counting
** the base node since it contains no data
*/
int rbTreeSize(rbTreeNode *base)
{
    return(base->color);
}

/*
** Allocate a new red-black tree using an empty node to hold pointers
*/
rbTreeNode *rbTreeNew(rbTreeAllocateEmptyNodeCB allocateEmptyNode)
{
    rbTreeNode *rootStorage = allocateEmptyNode();
    if (rootStorage) {
        rootStorage->left = NULL;   /* leftmost node */
        rootStorage->right = NULL;  /* rightmost node */
        rootStorage->parent = NULL; /* root node */
        rootStorage->color = 0;     /* node count */
    }
    return(rootStorage);
}

/*
** iterate through all nodes, unlinking and disposing them
** extra effort is made to maintain all links, the size, and
** leftmost/rightmost pointers, so that the tree can be dumped
** when debugging problems. We could probably ifdef some of this
** since it goes unused most of the time
** the tree is not kept balanced since all nodes will be removed
*/
void rbTreeDispose(rbTreeNode *base, rbTreeDisposeNodeCB disposeNode)
{
    rbTreeNode *iter = rbTreeBegin(base);
    while (iter != NULL) {
        rbTreeNode *nextIter = rbTreeNext(iter);

        if (iter->parent) {
            if (iter->parent->left == iter) {
                iter->parent->left = iter->right;
            }
            else {
                iter->parent->right = iter->right;
            }
        }
        if (iter->right != NULL) {
            iter->right->parent = iter->parent;
        }
        base->left = nextIter;
        if (base->right == iter) {
            base->right = NULL;
        }
        --(base->color);
        if (base->parent == iter) {
            base->parent = nextIter;
        }
        disposeNode(iter);

        iter = nextIter;
    }
    disposeNode(base);
}

#ifdef RBTREE_TEST_CODE
/* ================================================================== */

/*
** code to test basic stuff of tree routines
*/

typedef struct TestNode {
    rbTreeNode      nodePointers; /* MUST BE FIRST MEMBER */
    char *str;
    char *key;
} TestNode;


static int rbTreeCompareNode_TestNode(rbTreeNode *left, rbTreeNode *right)
{
    return(strcmp(((TestNode *)left)->key, ((TestNode *)right)->key));
}

static rbTreeNode *rbTreeAllocateNode_TestNode(rbTreeNode *src)
{
    TestNode *newNode = malloc(sizeof(TestNode));
    if (newNode) {
        newNode->str = malloc(strlen(((TestNode *)src)->str) + 1);
        if (newNode->str) {
            strcpy(newNode->str, ((TestNode *)src)->str);
            
            newNode->key = malloc(strlen(((TestNode *)src)->key) + 1);
            if (newNode->key) {
                strcpy(newNode->key, ((TestNode *)src)->key);
            }
            else {
                free(newNode->str);
                newNode->str = NULL;

                free(newNode);
                newNode = NULL;
            }
        }
        else {
            free(newNode);
            newNode = NULL;
        }
    }
    return((rbTreeNode *)newNode);
}

rbTreeNode *rbTreeAllocateEmptyNodeCB_TestNode(void)
{
    TestNode *newNode = malloc(sizeof(TestNode));
    if (newNode) {
        newNode->str = NULL;
        newNode->key = NULL;
    }
    return((rbTreeNode *)newNode);
}

static void rbTreeDisposeNode_TestNode(rbTreeNode *src)
{
    if (src) {
        if (((TestNode *)src)->str) {
            free(((TestNode *)src)->str);
            ((TestNode *)src)->str = NULL;
        }
        if (((TestNode *)src)->key) {
            free(((TestNode *)src)->key);
            ((TestNode *)src)->key = NULL;
        }
        src->left = (void *)-1;
        src->right = (void *)-1;
        src->parent = (void *)-1;
        src->color = rbTreeNodeBlack;

        free(src);
    }
}

static int rbTreeCopyToNode_TestNode(rbTreeNode *dst, rbTreeNode *src)
{
    TestNode newValues;
    int copiedOK = 0;
    
    newValues.str = malloc(strlen(((TestNode *)src)->str) + 1);
    if (newValues.str) {
        strcpy(newValues.str, ((TestNode *)src)->str);
        
        newValues.key = malloc(strlen(((TestNode *)src)->key) + 1);
        if (newValues.key) {
            strcpy(newValues.key, ((TestNode *)src)->key);
            
            ((TestNode *)dst)->str = newValues.str;
            ((TestNode *)dst)->key = newValues.key;
            copiedOK = 1;
        }
        else {
            free(newValues.str);
            newValues.str = NULL;
        }
    }
    return(copiedOK);
}

static void DumpTree(rbTreeNode *base)
{
    rbTreeNode *newNode;
    
    newNode = rbTreeBegin(base);
    while (newNode != NULL) {
        rbTreeNode *nextNode = rbTreeNext(newNode);
        
        printf("[%s] = \"%s\"\n", ((TestNode *)newNode)->key, ((TestNode *)newNode)->str);
        printf("[%x] l[%x] r[%x] p[%x] <%s>\n", (int)newNode, (int)newNode->left, (int)newNode->right, (int)newNode->parent, ((newNode->color == rbTreeNodeBlack)?"Black":"Red"));
        
        newNode = nextNode;
    }
}

int main(int argc, char **argv)
{
    rbTreeNode *base, *newNode;
    TestNode searchNode;
    char tmpkey[20], tmpValue[40];
    int i;
    
    searchNode.key = tmpkey;
    searchNode.str = tmpValue;

    base = rbTreeNew(rbTreeAllocateEmptyNodeCB_TestNode);
    if (!base) {
        printf("Failed New!!!\n");
        exit(1);
    }
    for (i = 0; i < 100; ++i) {
        sprintf(tmpkey, "%d", i);
        sprintf(tmpValue, "<%d>", i * i);
        
        newNode = rbTreeInsert(base, (rbTreeNode *)&searchNode,
                            rbTreeCompareNode_TestNode,
                            rbTreeAllocateNode_TestNode,
                            rbTreeCopyToNode_TestNode);
        if (!newNode) {
            printf("Failed!!!\n");
            exit(1);
        }
    }
    
    newNode = rbTreeBegin(base);
    while (newNode != NULL) {
        rbTreeNode *nextNode = rbTreeNext(newNode);
        
        printf("[%s] = \"%s\"\n", ((TestNode *)newNode)->key, ((TestNode *)newNode)->str);
        
        if (strlen(((TestNode *)newNode)->str) < 7) {
            int didDelete;
            
            printf("Deleting [%s]\n", ((TestNode *)newNode)->key);
            didDelete = rbTreeDelete(base, newNode,
                    rbTreeCompareNode_TestNode, rbTreeDisposeNode_TestNode);
            printf("delete result = %d\n", didDelete);
        }

        newNode = nextNode;
    }

    printf("Tree Size = %d\n", rbTreeSize(base));
    printf("\n++++++++++++++++\n");
    DumpTree(base);
    printf("\n++++++++++++++++\n");

    rbTreeDispose(base, rbTreeDisposeNode_TestNode);

    printf("\nDone.\n");
    return(0);
}
#endif