DialogF.c- DialogF.h
- Makefile.common
- Makefile.dependencies
- check_lin_tif
- clearcase.c
- clearcase.h
- colorchooser.c
- colorchooser.h
- dragAndDrop.c
- dragAndDrop.h
- ec_glob.c
- ec_glob.h
- fileUtils.c
- fileUtils.h
- filedialog.c
- filedialog.h
- fontsel.c
- fontsel.h
- getfiles.c
- getfiles.h
- libxattr.c
- libxattr.h
- managedList.c
- managedList.h
- misc.c
- misc.h
- motif.c
- motif.h
- nedit_malloc.c
- nedit_malloc.h
- pathutils.c
- pathutils.h
- prefFile.c
- prefFile.h
- printUtils.c
- printUtils.h
- rbTree.c
- rbTree.h
- refString.c
- refString.h
- system.h
- textfield.c
- textfield.h
- textfieldP.h
- utils.c
- utils.h
- xdnd.c
- xdnd.h
/*******************************************************************************
* *
* 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 "../util/nedit_malloc.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;
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 = NEditMalloc(sizeof(TestNode));
if (newNode) {
newNode->str = NEditMalloc(strlen(((TestNode *)src)->str) + 1);
if (newNode->str) {
strcpy(newNode->str, ((TestNode *)src)->str);
newNode->key = NEditMalloc(strlen(((TestNode *)src)->key) + 1);
if (newNode->key) {
strcpy(newNode->key, ((TestNode *)src)->key);
}
else {
NEditFree(newNode->str);
newNode->str = NULL;
NEditFree(newNode);
newNode = NULL;
}
}
else {
NEditFree(newNode);
newNode = NULL;
}
}
return((rbTreeNode *)newNode);
}
rbTreeNode *rbTreeAllocateEmptyNodeCB_TestNode(void)
{
TestNode *newNode = NEditMalloc(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) {
NEditFree(((TestNode *)src)->str);
((TestNode *)src)->str = NULL;
}
if (((TestNode *)src)->key) {
NEditFree(((TestNode *)src)->key);
((TestNode *)src)->key = NULL;
}
src->left = (void *)-1;
src->right = (void *)-1;
src->parent = (void *)-1;
src->color = rbTreeNodeBlack;
NEditFree(src);
}
}
static int rbTreeCopyToNode_TestNode(rbTreeNode *dst, rbTreeNode *src)
{
TestNode newValues;
int copiedOK = 0;
newValues.str = NEditMalloc(strlen(((TestNode *)src)->str) + 1);
if (newValues.str) {
strcpy(newValues.str, ((TestNode *)src)->str);
newValues.key = NEditMalloc(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 {
NEditFree(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