source/rbTree.c

   1 static const char CVSID[] = "$Id: rbTree.c,v 1.7 2002/07/11 21:18:10 slobasso Exp $";
   2 /*******************************************************************************
   3 *                                                                              *
   4 * rbTree.c -- Nirvana editor red-black balanced binary tree                    *
   5 *                                                                              *
   6 * Copyright (C) 2001 Mark Edel                                                 *
   7 *                                                                              *
   8 * This is free software; you can redistribute it and/or modify it under the    *
   9 * terms of the GNU General Public License as published by the Free Software    *
  10 * Foundation; either version 2 of the License, or (at your option) any later   *
  11 * version.                                                                     *
  12 *                                                                              *
  13 * This software is distributed in the hope that it will be useful, but WITHOUT *
  14 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or        *
  15 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License        *
  16 * for more details.                                                            *
  17 *                                                                              *
  18 * You should have received a copy of the GNU General Public License along with *
  19 * software; if not, write to the Free Software Foundation, Inc., 59 Temple     *
  20 * Place, Suite 330, Boston, MA  02111-1307 USA                                 *
  21 *                                                                              *
  22 * Nirvana Text Editor                                                          *
  23 * July, 1993                                                                   *
  24 *                                                                              *
  25 * Written by Mark Edel                                                         *
  26 *                                                                              *
  27 *******************************************************************************/
  28
  29 /*
  30 ** rbTree is a red-black balanced binary tree
  31 ** the base node holds the leftmost, rightmost and root pointers
  32 ** and a node count
  33 */
  34
  35 #ifdef HAVE_CONFIG_H
  36 #include "../config.h"
  37 #endif
  38
  39 #include "rbTree.h"
  40
  41 #include <stdlib.h>
  42 #include <string.h>
  43 /*#define RBTREE_TEST_CODE*/
  44 #ifdef RBTREE_TEST_CODE
  45 #include <stdio.h>
  46 #endif
  47
  48 #ifdef HAVE_DEBUG_H
  49 #include "../debug.h"
  50 #endif
  51
  52
  53 #define rbTreeNodeRed       0
  54 #define rbTreeNodeBlack     1
  55
  56 /*
  57 ** rotate a node left
  58 */
  59 static void rotateLeft(rbTreeNode *x, rbTreeNode **root)
  60 {
  61     rbTreeNode *y = x->right;
  62     x->right = y->left;
  63     if (y->left != NULL) {
  64         y->left->parent = x;
  65     }
  66     y->parent = x->parent;
  67
  68     if (x == *root) {
  69         *root = y;
  70     }
  71     else if (x == x->parent->left) {
  72         x->parent->left = y;
  73     }
  74     else {
  75         x->parent->right = y;
  76     }
  77     y->left = x;
  78     x->parent = y;
  79 }
  80
  81 /*
  82 ** rotate a node right
  83 */
  84 static void rotateRight(rbTreeNode *x, rbTreeNode **root)
  85 {
  86     rbTreeNode *y = x->left;
  87     x->left = y->right;
  88     if (y->right != NULL) {
  89         y->right->parent = x;
  90     }
  91     y->parent = x->parent;
  92
  93     if (x == *root) {
  94         *root = y;
  95     }
  96     else if (x == x->parent->right) {
  97         x->parent->right = y;
  98     }
  99     else {
 100         x->parent->left = y;
 101     }
 102     y->right = x;
 103     x->parent = y;
 104 }
 105
 106 /*
 107 ** balance tree after an insert of node x
 108 */
 109 static void insertBalance(rbTreeNode *x, rbTreeNode **root)
 110 {
 111   x->color = rbTreeNodeRed;
 112   while (x != *root && x->parent->color == rbTreeNodeRed) {
 113     if (x->parent == x->parent->parent->left) {
 114       rbTreeNode *y = x->parent->parent->right;
 115       if (y && y->color == rbTreeNodeRed) {
 116         x->parent->color = rbTreeNodeBlack;
 117         y->color = rbTreeNodeBlack;
 118         x->parent->parent->color = rbTreeNodeRed;
 119         x = x->parent->parent;
 120       }
 121       else {
 122         if (x == x->parent->right) {
 123           x = x->parent;
 124           rotateLeft(x, root);
 125         }
 126         x->parent->color = rbTreeNodeBlack;
 127         x->parent->parent->color = rbTreeNodeRed;
 128         rotateRight(x->parent->parent, root);
 129       }
 130     }
 131     else {
 132       rbTreeNode *y = x->parent->parent->left;
 133       if (y && y->color == rbTreeNodeRed) {
 134         x->parent->color = rbTreeNodeBlack;
 135         y->color = rbTreeNodeBlack;
 136         x->parent->parent->color = rbTreeNodeRed;
 137         x = x->parent->parent;
 138       }
 139       else {
 140         if (x == x->parent->left) {
 141           x = x->parent;
 142           rotateRight(x, root);
 143         }
 144         x->parent->color = rbTreeNodeBlack;
 145         x->parent->parent->color = rbTreeNodeRed;
 146         rotateLeft(x->parent->parent, root);
 147       }
 148     }
 149   }
 150   (*root)->color = rbTreeNodeBlack;
 151 }
 152
 153 /*
 154 ** returns the leftmost node (the beginning of the sorted list)
 155 */
 156 rbTreeNode *rbTreeBegin(rbTreeNode *base)
 157 {
 158     return(base->left);
 159 }
 160
 161 /*
 162 ** returns the rightmost node (the end of the sorted list)
 163 */
 164 rbTreeNode *rbTreeReverseBegin(rbTreeNode *base)
 165 {
 166     return(base->right);
 167 }
 168
 169 /*
 170 ** search for a node and return it's pointer, NULL if not found
 171 */
 172 rbTreeNode *rbTreeFind(rbTreeNode *base, rbTreeNode *searchNode,
 173                         rbTreeCompareNodeCB compareRecords)
 174 {
 175     rbTreeNode *foundNode = NULL;
 176     rbTreeNode *current = base->parent;
 177     while(current != NULL) {
 178         int compareResult = compareRecords(searchNode, current);
 179
 180         if (compareResult < 0) {
 181             current = current->left;
 182         }
 183         else if (compareResult > 0) {
 184             current = current->right;
 185         }
 186         else {
 187             foundNode = current;
 188             current = NULL;
 189         }
 190     }
 191     return(foundNode);
 192 }
 193
 194 /*
 195 ** insert a node into the tree and rebalance it
 196 ** if a duplicate is found copy the new data over it
 197 ** returns the new node
 198 */
 199 rbTreeNode *rbTreeInsert(rbTreeNode *base, rbTreeNode *searchNode,
 200                             rbTreeCompareNodeCB compareRecords,
 201                             rbTreeAllocateNodeCB allocateNode,
 202                             rbTreeCopyToNodeCB copyToNode)
 203 {
 204     rbTreeNode *current, *parent, *x;
 205     int fromLeft = 0, foundMatch = 0;
 206
 207     current = base->parent;
 208     parent = NULL;
 209     x = NULL;
 210     while(current != NULL) {
 211         int compareResult = compareRecords(searchNode, current);
 212
 213         if (compareResult < 0) {
 214             parent = current;
 215             current = current->left;
 216             fromLeft = 1;
 217         }
 218         else if (compareResult > 0) {
 219             parent = current;
 220             current = current->right;
 221             fromLeft = 0;
 222         }
 223         else {
 224             x = current;
 225             if (!copyToNode(x, searchNode)) {
 226                 x = NULL;
 227             }
 228             current = NULL;
 229             foundMatch = 1;
 230         }
 231     }
 232
 233     if (!foundMatch) {
 234         x = allocateNode(searchNode);
 235         if (x) {
 236             x->parent = parent;
 237             x->left = NULL;
 238             x->right = NULL;
 239             x->color = rbTreeNodeRed;
 240
 241             if (parent) {
 242                 if (fromLeft) {
 243                     parent->left = x;
 244                 }
 245                 else {
 246                     parent->right = x;
 247                 }
 248             }
 249             else {
 250                 base->parent = x;
 251             }
 252             ++(base->color);
 253             if (x->parent == base->left && (x->parent == NULL || x->parent->left == x)) {
 254                 base->left = x;
 255             }
 256             if (x->parent == base->right && (x->parent == NULL || x->parent->right == x)) {
 257                 base->right = x;
 258             }
 259             insertBalance(x, &base->parent);
 260         }
 261     }
 262     return(x);
 263 }
 264
 265 /*
 266 ** unlink a node from the tree and rebalance it.
 267 ** returns the removed node pointer
 268 */
 269 rbTreeNode *rbTreeUnlinkNode(rbTreeNode *base, rbTreeNode *z)
 270 {
 271     int swapColor;
 272     rbTreeNode *x, *y, *x_parent;
 273
 274     y = z;
 275     if (y->left == NULL) {
 276         x = y->right;
 277         if (y == base->left) {
 278             base->left = rbTreeNext(y);
 279         }
 280     }
 281     else {
 282         if (y->right == NULL) {
 283             x = y->left;
 284             if (y == base->right) {
 285                 base->right = rbTreePrevious(y);
 286             }
 287         }
 288         else {
 289             y = y->right;
 290             while (y->left != NULL) {
 291                 y = y->left;
 292             }
 293             x = y->right;
 294         }
 295     }
 296     if (y != z) {
 297         z->left->parent = y;
 298         y->left = z->left;
 299         if (y != z->right) {
 300             x_parent = y->parent;
 301             if (x != NULL) {
 302                 x->parent = y->parent;
 303             }
 304             y->parent->left = x;
 305             y->right = z->right;
 306             z->right->parent = y;
 307         }
 308         else {
 309             x_parent = y;
 310         }
 311         if (base->parent == z) {
 312             base->parent = y;
 313         }
 314         else if (z->parent->left == z) {
 315             z->parent->left = y;
 316         }
 317         else {
 318             z->parent->right = y;
 319         }
 320         y->parent = z->parent;
 321
 322         swapColor = y->color;
 323         y->color = z->color;
 324         z->color = swapColor;
 325
 326         y = z;
 327     }
 328     else {
 329         x_parent = y->parent;
 330         if (x != NULL) {
 331             x->parent = y->parent;
 332         }
 333         if (base->parent == z) {
 334             base->parent = x;
 335         }
 336         else {
 337             if (z->parent->left == z) {
 338                 z->parent->left = x;
 339             }
 340             else {
 341                 z->parent->right = x;
 342             }
 343         }
 344     }
 345
 346     --(base->color);
 347
 348     if (y->color != rbTreeNodeRed) {
 349         while (x != base->parent && (x == NULL || x->color == rbTreeNodeBlack)) {
 350             if (x == x_parent->left) {
 351                 rbTreeNode *w = x_parent->right;
 352                 if (w->color == rbTreeNodeRed) {
 353                     w->color = rbTreeNodeBlack;
 354                     x_parent->color = rbTreeNodeRed;
 355                     rotateLeft(x_parent, &base->parent);
 356                     w = x_parent->right;
 357                 }
 358                 if ((w->left == NULL ||
 359                 w->left->color == rbTreeNodeBlack) &&
 360                 (w->right == NULL ||
 361                 w->right->color == rbTreeNodeBlack)) {
 362
 363                     w->color = rbTreeNodeRed;
 364                     x = x_parent;
 365                     x_parent = x_parent->parent;
 366                 } else {
 367                     if (w->right == NULL ||
 368                     w->right->color == rbTreeNodeBlack) {
 369
 370                         if (w->left) {
 371                             w->left->color = rbTreeNodeBlack;
 372                         }
 373                         w->color = rbTreeNodeRed;
 374                         rotateRight(w, &base->parent);
 375                         w = x_parent->right;
 376                     }
 377                     w->color = x_parent->color;
 378                     x_parent->color = rbTreeNodeBlack;
 379                     if (w->right) {
 380                         w->right->color = rbTreeNodeBlack;
 381                     }
 382                     rotateLeft(x_parent, &base->parent);
 383                     break;
 384                 }
 385             }
 386             else {
 387                 rbTreeNode *w = x_parent->left;
 388                 if (w->color == rbTreeNodeRed) {
 389                     w->color = rbTreeNodeBlack;
 390                     x_parent->color = rbTreeNodeRed;
 391                     rotateRight(x_parent, &base->parent);
 392                     w = x_parent->left;
 393                 }
 394                 if ((w->right == NULL ||
 395                     w->right->color == rbTreeNodeBlack) &&
 396                     (w->left == NULL ||
 397                     w->left->color == rbTreeNodeBlack)) {
 398
 399                     w->color = rbTreeNodeRed;
 400                     x = x_parent;
 401                     x_parent = x_parent->parent;
 402                 }
 403                 else {
 404                     if (w->left == NULL ||
 405                         w->left->color == rbTreeNodeBlack) {
 406
 407                         if (w->right) {
 408                             w->right->color = rbTreeNodeBlack;
 409                         }
 410                         w->color = rbTreeNodeRed;
 411                         rotateLeft(w, &base->parent);
 412                         w = x_parent->left;
 413                     }
 414                     w->color = x_parent->color;
 415                     x_parent->color = rbTreeNodeBlack;
 416                     if (w->left) {
 417                         w->left->color = rbTreeNodeBlack;
 418                     }
 419                     rotateRight(x_parent, &base->parent);
 420                     break;
 421                 }
 422             }
 423         }
 424         if (x) {
 425             x->color = rbTreeNodeBlack;
 426         }
 427     }
 428     return(y);
 429 }
 430
 431 /*
 432 ** delete an already found node and dispose it
 433 */
 434 void rbTreeDeleteNode(rbTreeNode *base, rbTreeNode *foundNode,
 435                     rbTreeDisposeNodeCB disposeNode)
 436 {
 437     disposeNode(rbTreeUnlinkNode(base, foundNode));
 438 }
 439
 440 /*
 441 ** search for a node and remove it from the tree
 442 ** disposing the removed node
 443 ** returns 1 if a node was found, otherwise 0
 444 */
 445 int rbTreeDelete(rbTreeNode *base, rbTreeNode *searchNode,
 446                     rbTreeCompareNodeCB compareRecords,
 447                     rbTreeDisposeNodeCB disposeNode)
 448 {
 449     int foundNode = 0;
 450     rbTreeNode *z;
 451
 452     z = rbTreeFind(base, searchNode, compareRecords);
 453     if (z != NULL) {
 454         rbTreeDeleteNode(base, z, disposeNode);
 455         foundNode = 1;
 456     }
 457     return(foundNode);
 458 }
 459
 460 /*
 461 ** move an iterator foreward one element
 462 ** note that a valid pointer must be passed,
 463 ** passing NULL will result in unpredictable results
 464 */
 465 rbTreeNode *rbTreeNext(rbTreeNode *x)
 466 {
 467     if (x->right != NULL) {
 468         x = x->right;
 469         while (x->left != NULL) {
 470             x = x->left;
 471         }
 472     }
 473     else {
 474         rbTreeNode *fromX;
 475         do {
 476             fromX = x;
 477             x = x->parent;
 478         } while (x && fromX == x->right);
 479     }
 480     return(x);
 481 }
 482
 483 /*
 484 ** move an iterator back one element
 485 ** note that a valid pointer must be passed,
 486 ** passing NULL will result in unpredictable results
 487 */
 488 rbTreeNode *rbTreePrevious(rbTreeNode *x)
 489 {
 490     if (x->left != NULL) {
 491         x = x->left;
 492         while (x->right != NULL) {
 493             x = x->right;
 494         }
 495     }
 496     else {
 497         rbTreeNode *fromX;
 498         do {
 499             fromX = x;
 500             x = x->parent;
 501         } while (x && fromX == x->left);
 502     }
 503     return(x);
 504 }
 505
 506 /*
 507 ** returns the number of real data nodes in the tree, not counting
 508 ** the base node since it contains no data
 509 */
 510 int rbTreeSize(rbTreeNode *base)
 511 {
 512     return(base->color);
 513 }
 514
 515 /*
 516 ** Allocate a new red-black tree using an empty node to hold pointers
 517 */
 518 rbTreeNode *rbTreeNew(rbTreeAllocateEmptyNodeCB allocateEmptyNode)
 519 {
 520     rbTreeNode *rootStorage = allocateEmptyNode();
 521     if (rootStorage) {
 522         rootStorage->left = NULL;   /* leftmost node */
 523         rootStorage->right = NULL;  /* rightmost node */
 524         rootStorage->parent = NULL; /* root node */
 525         rootStorage->color = 0;     /* node count */
 526     }
 527     return(rootStorage);
 528 }
 529
 530 /*
 531 ** iterate through all nodes, unlinking and disposing them
 532 ** extra effort is made to maintain all links, the size, and
 533 ** leftmost/rightmost pointers, so that the tree can be dumped
 534 ** when debugging problems. We could probably ifdef some of this
 535 ** since it goes unused most of the time
 536 ** the tree is not kept balanced since all nodes will be removed
 537 */
 538 void rbTreeDispose(rbTreeNode *base, rbTreeDisposeNodeCB disposeNode)
 539 {
 540     rbTreeNode *iter = rbTreeBegin(base);
 541     while (iter != NULL) {
 542         rbTreeNode *nextIter = rbTreeNext(iter);
 543
 544         if (iter->parent) {
 545             if (iter->parent->left == iter) {
 546                 iter->parent->left = iter->right;
 547             }
 548             else {
 549                 iter->parent->right = iter->right;
 550             }
 551         }
 552         if (iter->right != NULL) {
 553             iter->right->parent = iter->parent;
 554         }
 555         base->left = nextIter;
 556         if (base->right == iter) {
 557             base->right = NULL;
 558         }
 559         --(base->color);
 560         if (base->parent == iter) {
 561             base->parent = nextIter;
 562         }
 563         disposeNode(iter);
 564
 565         iter = nextIter;
 566     }
 567     disposeNode(base);
 568 }
 569
 570 #ifdef RBTREE_TEST_CODE
 571 /* ================================================================== */
 572
 573 /*
 574 ** code to test basic stuff of tree routines
 575 */
 576
 577 typedef struct TestNode {
 578     rbTreeNode      nodePointers; /* MUST BE FIRST MEMBER */
 579     char *str;
 580     char *key;
 581 } TestNode;
 582
 583
 584 static int rbTreeCompareNode_TestNode(rbTreeNode *left, rbTreeNode *right)
 585 {
 586     return(strcmp(((TestNode *)left)->key, ((TestNode *)right)->key));
 587 }
 588
 589 static rbTreeNode *rbTreeAllocateNode_TestNode(rbTreeNode *src)
 590 {
 591     TestNode *newNode = malloc(sizeof(TestNode));
 592     if (newNode) {
 593         newNode->str = malloc(strlen(((TestNode *)src)->str) + 1);
 594         if (newNode->str) {
 595             strcpy(newNode->str, ((TestNode *)src)->str);
 596
 597             newNode->key = malloc(strlen(((TestNode *)src)->key) + 1);
 598             if (newNode->key) {
 599                 strcpy(newNode->key, ((TestNode *)src)->key);
 600             }
 601             else {
 602                 free(newNode->str);
 603                 newNode->str = NULL;
 604
 605                 free(newNode);
 606                 newNode = NULL;
 607             }
 608         }
 609         else {
 610             free(newNode);
 611             newNode = NULL;
 612         }
 613     }
 614     return((rbTreeNode *)newNode);
 615 }
 616
 617 rbTreeNode *rbTreeAllocateEmptyNodeCB_TestNode(void)
 618 {
 619     TestNode *newNode = malloc(sizeof(TestNode));
 620     if (newNode) {
 621         newNode->str = NULL;
 622         newNode->key = NULL;
 623     }
 624     return((rbTreeNode *)newNode);
 625 }
 626
 627 static void rbTreeDisposeNode_TestNode(rbTreeNode *src)
 628 {
 629     if (src) {
 630         if (((TestNode *)src)->str) {
 631             free(((TestNode *)src)->str);
 632             ((TestNode *)src)->str = NULL;
 633         }
 634         if (((TestNode *)src)->key) {
 635             free(((TestNode *)src)->key);
 636             ((TestNode *)src)->key = NULL;
 637         }
 638         src->left = (void *)-1;
 639         src->right = (void *)-1;
 640         src->parent = (void *)-1;
 641         src->color = rbTreeNodeBlack;
 642
 643         free(src);
 644     }
 645 }
 646
 647 static int rbTreeCopyToNode_TestNode(rbTreeNode *dst, rbTreeNode *src)
 648 {
 649     TestNode newValues;
 650     int copiedOK = 0;
 651
 652     newValues.str = malloc(strlen(((TestNode *)src)->str) + 1);
 653     if (newValues.str) {
 654         strcpy(newValues.str, ((TestNode *)src)->str);
 655
 656         newValues.key = malloc(strlen(((TestNode *)src)->key) + 1);
 657         if (newValues.key) {
 658             strcpy(newValues.key, ((TestNode *)src)->key);
 659
 660             ((TestNode *)dst)->str = newValues.str;
 661             ((TestNode *)dst)->key = newValues.key;
 662             copiedOK = 1;
 663         }
 664         else {
 665             free(newValues.str);
 666             newValues.str = NULL;
 667         }
 668     }
 669     return(copiedOK);
 670 }
 671
 672 static void DumpTree(rbTreeNode *base)
 673 {
 674     rbTreeNode *newNode;
 675
 676     newNode = rbTreeBegin(base);
 677     while (newNode != NULL) {
 678         rbTreeNode *nextNode = rbTreeNext(newNode);
 679
 680         printf("[%s] = \"%s\"\n", ((TestNode *)newNode)->key, ((TestNode *)newNode)->str);
 681         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"));
 682
 683         newNode = nextNode;
 684     }
 685 }
 686
 687 int main(int argc, char **argv)
 688 {
 689     rbTreeNode *base, *newNode;
 690     TestNode searchNode;
 691     char tmpkey[20], tmpValue[40];
 692     int i;
 693
 694     searchNode.key = tmpkey;
 695     searchNode.str = tmpValue;
 696
 697     base = rbTreeNew(rbTreeAllocateEmptyNodeCB_TestNode);
 698     if (!base) {
 699         printf("Failed New!!!\n");
 700         exit(1);
 701     }
 702     for (i = 0; i < 100; ++i) {
 703         sprintf(tmpkey, "%d", i);
 704         sprintf(tmpValue, "<%d>", i * i);
 705
 706         newNode = rbTreeInsert(base, (rbTreeNode *)&searchNode,
 707                             rbTreeCompareNode_TestNode,
 708                             rbTreeAllocateNode_TestNode,
 709                             rbTreeCopyToNode_TestNode);
 710         if (!newNode) {
 711             printf("Failed!!!\n");
 712             exit(1);
 713         }
 714     }
 715
 716     newNode = rbTreeBegin(base);
 717     while (newNode != NULL) {
 718         rbTreeNode *nextNode = rbTreeNext(newNode);
 719
 720         printf("[%s] = \"%s\"\n", ((TestNode *)newNode)->key, ((TestNode *)newNode)->str);
 721
 722         if (strlen(((TestNode *)newNode)->str) < 7) {
 723             int didDelete;
 724
 725             printf("Deleting [%s]\n", ((TestNode *)newNode)->key);
 726             didDelete = rbTreeDelete(base, newNode,
 727                     rbTreeCompareNode_TestNode, rbTreeDisposeNode_TestNode);
 728             printf("delete result = %d\n", didDelete);
 729         }
 730
 731         newNode = nextNode;
 732     }
 733
 734     printf("Tree Size = %d\n", rbTreeSize(base));
 735     printf("\n++++++++++++++++\n");
 736     DumpTree(base);
 737     printf("\n++++++++++++++++\n");
 738
 739     rbTreeDispose(base, rbTreeDisposeNode_TestNode);
 740
 741     printf("\nDone.\n");
 742     return(0);
 743 }
 744 #endif