src/lib/rbtree.c

   1 /*
   2  * rbtree.c     Red-black balanced binary trees.
   3  *
   4  * Version:     $Id$
   5  *
   6  *   This library is free software; you can redistribute it and/or
   7  *   modify it under the terms of the GNU Lesser General Public
   8  *   License as published by the Free Software Foundation; either
   9  *   version 2.1 of the License, or (at your option) any later version.
  10  *
  11  *   This library is distributed in the hope that it will be useful,
  12  *   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  14  *   Lesser General Public License for more details.
  15  *
  16  *   You should have received a copy of the GNU Lesser General Public
  17  *   License along with this library; if not, write to the Free Software
  18  *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  19  *
  20  *  Copyright 2004,2006  The FreeRADIUS server project
  21  */
  22
  23 #include <freeradius-devel/ident.h>
  24 RCSID("$Id$")
  25
  26 #include <freeradius-devel/libradius.h>
  27
  28 /* red-black tree description */
  29 typedef enum { Black, Red } NodeColor;
  30
  31 struct rbnode_t {
  32     rbnode_t    *Left;          /* left child */
  33     rbnode_t    *Right;         /* right child */
  34     rbnode_t    *Parent;        /* parent */
  35     NodeColor   Color;          /* node color (black, red) */
  36     void        *Data;          /* data stored in node */
  37 };
  38
  39 #define NIL &Sentinel           /* all leafs are sentinels */
  40 static rbnode_t Sentinel = { NIL, NIL, NULL, Black, NULL};
  41
  42 struct rbtree_t {
  43 #ifndef NDEBUG
  44         uint32_t magic;
  45 #endif
  46         rbnode_t *Root;
  47         int     num_elements;
  48         int (*Compare)(const void *, const void *);
  49         int replace_flag;
  50         void (*freeNode)(void *);
  51 };
  52 #define RBTREE_MAGIC (0x5ad09c42)
  53
  54 /*
  55  *      Walks the tree to delete all nodes.
  56  *      Does NOT re-balance it!
  57  */
  58 static void FreeWalker(rbtree_t *tree, rbnode_t *X)
  59 {
  60         if (X->Left != NIL) FreeWalker(tree, X->Left);
  61         if (X->Right != NIL) FreeWalker(tree, X->Right);
  62
  63         if (tree->freeNode) tree->freeNode(X->Data);
  64         free(X);
  65 }
  66
  67 void rbtree_free(rbtree_t *tree)
  68 {
  69         if (!tree) return;
  70
  71         /*
  72          *      Walk the tree, deleting the nodes...
  73          */
  74         if (tree->Root != NIL) FreeWalker(tree, tree->Root);
  75
  76 #ifndef NDEBUG
  77         tree->magic = 0;
  78 #endif
  79         tree->Root = NULL;
  80         free(tree);
  81 }
  82
  83 /*
  84  *      Create a new red-black tree.
  85  */
  86 rbtree_t *rbtree_create(int (*Compare)(const void *, const void *),
  87                         void (*freeNode)(void *),
  88                         int replace_flag)
  89 {
  90         rbtree_t        *tree;
  91
  92         if (!Compare) return NULL;
  93
  94         tree = malloc(sizeof(*tree));
  95         if (!tree) return NULL;
  96
  97         memset(tree, 0, sizeof(*tree));
  98 #ifndef NDEBUG
  99         tree->magic = RBTREE_MAGIC;
 100 #endif
 101         tree->Root = NIL;
 102         tree->Compare = Compare;
 103         tree->replace_flag = replace_flag;
 104         tree->freeNode = freeNode;
 105
 106         return tree;
 107 }
 108
 109
 110 static void RotateLeft(rbtree_t *tree, rbnode_t *X)
 111 {
 112         /**************************
 113          *  rotate Node X to left *
 114          **************************/
 115
 116         rbnode_t *Y = X->Right;
 117
 118         /* establish X->Right link */
 119         X->Right = Y->Left;
 120         if (Y->Left != NIL) Y->Left->Parent = X;
 121
 122         /* establish Y->Parent link */
 123         if (Y != NIL) Y->Parent = X->Parent;
 124         if (X->Parent) {
 125                 if (X == X->Parent->Left)
 126                         X->Parent->Left = Y;
 127                 else
 128                         X->Parent->Right = Y;
 129         } else {
 130                 tree->Root = Y;
 131         }
 132
 133         /* link X and Y */
 134         Y->Left = X;
 135         if (X != NIL) X->Parent = Y;
 136 }
 137
 138 static void RotateRight(rbtree_t *tree, rbnode_t *X)
 139 {
 140         /****************************
 141          *  rotate Node X to right  *
 142          ****************************/
 143
 144         rbnode_t *Y = X->Left;
 145
 146         /* establish X->Left link */
 147         X->Left = Y->Right;
 148         if (Y->Right != NIL) Y->Right->Parent = X;
 149
 150         /* establish Y->Parent link */
 151         if (Y != NIL) Y->Parent = X->Parent;
 152         if (X->Parent) {
 153                 if (X == X->Parent->Right)
 154                         X->Parent->Right = Y;
 155                 else
 156                         X->Parent->Left = Y;
 157         } else {
 158                 tree->Root = Y;
 159         }
 160
 161         /* link X and Y */
 162         Y->Right = X;
 163         if (X != NIL) X->Parent = Y;
 164 }
 165
 166 static void InsertFixup(rbtree_t *tree, rbnode_t *X)
 167 {
 168         /*************************************
 169          *  maintain red-black tree balance  *
 170          *  after inserting node X           *
 171          *************************************/
 172
 173         /* check red-black properties */
 174         while (X != tree->Root && X->Parent->Color == Red) {
 175                 /* we have a violation */
 176                 if (X->Parent == X->Parent->Parent->Left) {
 177                         rbnode_t *Y = X->Parent->Parent->Right;
 178                         if (Y->Color == Red) {
 179
 180                                 /* uncle is red */
 181                                 X->Parent->Color = Black;
 182                                 Y->Color = Black;
 183                                 X->Parent->Parent->Color = Red;
 184                                 X = X->Parent->Parent;
 185                         } else {
 186
 187                                 /* uncle is black */
 188                                 if (X == X->Parent->Right) {
 189                                         /* make X a left child */
 190                                         X = X->Parent;
 191                                         RotateLeft(tree, X);
 192                                 }
 193
 194                                 /* recolor and rotate */
 195                                 X->Parent->Color = Black;
 196                                 X->Parent->Parent->Color = Red;
 197                                 RotateRight(tree, X->Parent->Parent);
 198                         }
 199                 } else {
 200
 201                         /* mirror image of above code */
 202                         rbnode_t *Y = X->Parent->Parent->Left;
 203                         if (Y->Color == Red) {
 204
 205                                 /* uncle is red */
 206                                 X->Parent->Color = Black;
 207                                 Y->Color = Black;
 208                                 X->Parent->Parent->Color = Red;
 209                                 X = X->Parent->Parent;
 210                         } else {
 211
 212                                 /* uncle is black */
 213                                 if (X == X->Parent->Left) {
 214                                         X = X->Parent;
 215                                         RotateRight(tree, X);
 216                                 }
 217                                 X->Parent->Color = Black;
 218                                 X->Parent->Parent->Color = Red;
 219                                 RotateLeft(tree, X->Parent->Parent);
 220                         }
 221                 }
 222         }
 223
 224         tree->Root->Color = Black;
 225 }
 226
 227
 228 /*
 229  *      Insert an element into the tree.
 230  */
 231 rbnode_t *rbtree_insertnode(rbtree_t *tree, void *Data)
 232 {
 233         rbnode_t *Current, *Parent, *X;
 234
 235         /***********************************************
 236          *  allocate node for Data and insert in tree  *
 237          ***********************************************/
 238
 239         /* find where node belongs */
 240         Current = tree->Root;
 241         Parent = NULL;
 242         while (Current != NIL) {
 243                 int result;
 244
 245                 /*
 246                  *      See if two entries are identical.
 247                  */
 248                 result = tree->Compare(Data, Current->Data);
 249                 if (result == 0) {
 250                         /*
 251                          *      Don't replace the entry.
 252                          */
 253                         if (tree->replace_flag == 0) {
 254                                 return NULL;
 255                         }
 256
 257                         /*
 258                          *      Do replace the entry.
 259                          */
 260                         if (tree->freeNode) tree->freeNode(Current->Data);
 261                         Current->Data = Data;
 262                         return Current;
 263                 }
 264
 265                 Parent = Current;
 266                 Current = (result < 0) ? Current->Left : Current->Right;
 267         }
 268
 269         /* setup new node */
 270         if ((X = malloc (sizeof(*X))) == NULL) {
 271                 exit(1);        /* FIXME! */
 272         }
 273
 274         X->Data = Data;
 275         X->Parent = Parent;
 276         X->Left = NIL;
 277         X->Right = NIL;
 278         X->Color = Red;
 279
 280         /* insert node in tree */
 281         if (Parent) {
 282                 if (tree->Compare(Data, Parent->Data) <= 0)
 283                         Parent->Left = X;
 284                 else
 285                         Parent->Right = X;
 286         } else {
 287                 tree->Root = X;
 288         }
 289
 290         InsertFixup(tree, X);
 291
 292         tree->num_elements++;
 293
 294         return X;
 295 }
 296
 297 int rbtree_insert(rbtree_t *tree, void *Data)
 298 {
 299         if (rbtree_insertnode(tree, Data)) return 1;
 300         return 0;
 301 }
 302
 303 static void DeleteFixup(rbtree_t *tree, rbnode_t *X, rbnode_t *Parent)
 304 {
 305         /*************************************
 306          *  maintain red-black tree balance  *
 307          *  after deleting node X            *
 308          *************************************/
 309
 310         while (X != tree->Root && X->Color == Black) {
 311                 if (X == Parent->Left) {
 312                         rbnode_t *W = Parent->Right;
 313                         if (W->Color == Red) {
 314                                 W->Color = Black;
 315                                 Parent->Color = Red; /* Parent != NIL? */
 316                                 RotateLeft(tree, Parent);
 317                                 W = Parent->Right;
 318                         }
 319                         if (W->Left->Color == Black && W->Right->Color == Black) {
 320                                 if (W != NIL) W->Color = Red;
 321                                 X = Parent;
 322                                 Parent = X->Parent;
 323                         } else {
 324                                 if (W->Right->Color == Black) {
 325                                         if (W->Left != NIL) W->Left->Color = Black;
 326                                         W->Color = Red;
 327                                         RotateRight(tree, W);
 328                                         W = Parent->Right;
 329                                 }
 330                                 W->Color = Parent->Color;
 331                                 if (Parent != NIL) Parent->Color = Black;
 332                                 if (W->Right->Color != Black) {
 333                                         W->Right->Color = Black;
 334                                 }
 335                                 RotateLeft(tree, Parent);
 336                                 X = tree->Root;
 337                         }
 338                 } else {
 339                         rbnode_t *W = Parent->Left;
 340                         if (W->Color == Red) {
 341                                 W->Color = Black;
 342                                 Parent->Color = Red; /* Parent != NIL? */
 343                                 RotateRight(tree, Parent);
 344                                 W = Parent->Left;
 345                         }
 346                         if (W->Right->Color == Black && W->Left->Color == Black) {
 347                                 if (W != NIL) W->Color = Red;
 348                                 X = Parent;
 349                                 Parent = X->Parent;
 350                         } else {
 351                                 if (W->Left->Color == Black) {
 352                                         if (W->Right != NIL) W->Right->Color = Black;
 353                                         W->Color = Red;
 354                                         RotateLeft(tree, W);
 355                                         W = Parent->Left;
 356                                 }
 357                                 W->Color = Parent->Color;
 358                                 if (Parent != NIL) Parent->Color = Black;
 359                                 if (W->Left->Color != Black) {
 360                                         W->Left->Color = Black;
 361                                 }
 362                                 RotateRight(tree, Parent);
 363                                 X = tree->Root;
 364                         }
 365                 }
 366         }
 367         X->Color = Black;
 368 }
 369
 370 /*
 371  *      Delete an element from the tree.
 372  */
 373 void rbtree_delete(rbtree_t *tree, rbnode_t *Z)
 374 {
 375         rbnode_t *X, *Y;
 376         rbnode_t *Parent;
 377
 378         /*****************************
 379          *  delete node Z from tree  *
 380          *****************************/
 381
 382         if (!Z || Z == NIL) return;
 383
 384         if (Z->Left == NIL || Z->Right == NIL) {
 385                 /* Y has a NIL node as a child */
 386                 Y = Z;
 387         } else {
 388                 /* find tree successor with a NIL node as a child */
 389                 Y = Z->Right;
 390                 while (Y->Left != NIL) Y = Y->Left;
 391         }
 392
 393         /* X is Y's only child */
 394         if (Y->Left != NIL)
 395                 X = Y->Left;
 396         else
 397                 X = Y->Right;   /* may be NIL! */
 398
 399         /* remove Y from the parent chain */
 400         Parent = Y->Parent;
 401         if (X != NIL) X->Parent = Parent;
 402
 403         if (Parent)
 404                 if (Y == Parent->Left)
 405                         Parent->Left = X;
 406                 else
 407                         Parent->Right = X;
 408         else
 409                 tree->Root = X;
 410
 411         if (Y != Z) {
 412                 if (tree->freeNode) tree->freeNode(Z->Data);
 413                 Z->Data = Y->Data;
 414                 Y->Data = NULL;
 415
 416                 if (Y->Color == Black && X != NIL)
 417                         DeleteFixup(tree, X, Parent);
 418
 419                 /*
 420                  *      The user structure in Y->Data MAY include a
 421                  *      pointer to Y.  In that case, we CANNOT delete
 422                  *      Y.  Instead, we copy Z (which is now in the
 423                  *      tree) to Y, and fix up the parent/child
 424                  *      pointers.
 425                  */
 426                 memcpy(Y, Z, sizeof(*Y));
 427
 428                 if (!Y->Parent) {
 429                         tree->Root = Y;
 430                 } else {
 431                         if (Y->Parent->Left == Z) Y->Parent->Left = Y;
 432                         if (Y->Parent->Right == Z) Y->Parent->Right = Y;
 433                 }
 434                 if (Y->Left->Parent == Z) Y->Left->Parent = Y;
 435                 if (Y->Right->Parent == Z) Y->Right->Parent = Y;
 436
 437                 free(Z);
 438
 439         } else {
 440                 if (tree->freeNode) tree->freeNode(Y->Data);
 441
 442                 if (Y->Color == Black && X != NIL)
 443                         DeleteFixup(tree, X, Parent);
 444
 445                 free(Y);
 446         }
 447
 448         tree->num_elements--;
 449 }
 450
 451 /*
 452  *      Delete a node from the tree, based on given data, which MUST
 453  *      have come from rbtree_finddata().
 454  */
 455 int rbtree_deletebydata(rbtree_t *tree, const void *data)
 456 {
 457         rbnode_t *node = rbtree_find(tree, data);
 458
 459         if (!node) return 0;    /* false */
 460
 461         rbtree_delete(tree, node);
 462
 463         return 1;
 464 }
 465
 466
 467 /*
 468  *      Find an element in the tree, returning the data, not the node.
 469  */
 470 rbnode_t *rbtree_find(rbtree_t *tree, const void *Data)
 471 {
 472         /*******************************
 473          *  find node containing Data  *
 474          *******************************/
 475
 476         rbnode_t *Current = tree->Root;
 477
 478         while (Current != NIL) {
 479                 int result = tree->Compare(Data, Current->Data);
 480
 481                 if (result == 0) {
 482                         return Current;
 483                 } else {
 484                         Current = (result < 0) ?
 485                                 Current->Left : Current->Right;
 486                 }
 487         }
 488         return NULL;
 489 }
 490
 491 /*
 492  *      Find the user data.
 493  */
 494 void *rbtree_finddata(rbtree_t *tree, const void *Data)
 495 {
 496         rbnode_t *X;
 497
 498         X = rbtree_find(tree, Data);
 499         if (!X) return NULL;
 500
 501         return X->Data;
 502 }
 503
 504 /*
 505  *      Walk the tree, Pre-order
 506  *
 507  *      We call ourselves recursively for each function, but that's OK,
 508  *      as the stack is only log(N) deep, which is ~12 entries deep.
 509  */
 510 static int WalkNodePreOrder(rbnode_t *X,
 511                             int (*callback)(void *, void *), void *context)
 512 {
 513         int rcode;
 514
 515         rcode = callback(context, X->Data);
 516         if (rcode != 0) return rcode;
 517
 518         if (X->Left != NIL) {
 519                 rcode = WalkNodePreOrder(X->Left, callback, context);
 520                 if (rcode != 0) return rcode;
 521         }
 522
 523         if (X->Right != NIL) {
 524                 rcode = WalkNodePreOrder(X->Right, callback, context);
 525                 if (rcode != 0) return rcode;
 526         }
 527
 528         return 0;               /* we know everything returned zero */
 529 }
 530
 531 /*
 532  *      Inorder
 533  */
 534 static int WalkNodeInOrder(rbnode_t *X,
 535                            int (*callback)(void *, void *), void *context)
 536 {
 537         int rcode;
 538
 539         if (X->Left != NIL) {
 540                 rcode = WalkNodeInOrder(X->Left, callback, context);
 541                 if (rcode != 0) return rcode;
 542         }
 543
 544         rcode = callback(context, X->Data);
 545         if (rcode != 0) return rcode;
 546
 547         if (X->Right != NIL) {
 548                 rcode = WalkNodeInOrder(X->Right, callback, context);
 549                 if (rcode != 0) return rcode;
 550         }
 551
 552         return 0;               /* we know everything returned zero */
 553 }
 554
 555
 556 /*
 557  *      PostOrder
 558  */
 559 static int WalkNodePostOrder(rbnode_t *X,
 560                              int (*callback)(void *, void*), void *context)
 561 {
 562         int rcode;
 563
 564         if (X->Left != NIL) {
 565                 rcode = WalkNodeInOrder(X->Left, callback, context);
 566                 if (rcode != 0) return rcode;
 567         }
 568
 569         if (X->Right != NIL) {
 570                 rcode = WalkNodeInOrder(X->Right, callback, context);
 571                 if (rcode != 0) return rcode;
 572         }
 573
 574         rcode = callback(context, X->Data);
 575         if (rcode != 0) return rcode;
 576
 577         return 0;               /* we know everything returned zero */
 578 }
 579
 580 /*
 581  *      Walk the entire tree.  The callback function CANNOT modify
 582  *      the tree.
 583  *
 584  *      The callback function should return 0 to continue walking.
 585  *      Any other value stops the walk, and is returned.
 586  */
 587 int rbtree_walk(rbtree_t *tree, RBTREE_ORDER order,
 588                 int (*callback)(void *, void *), void *context)
 589 {
 590         if (tree->Root == NIL) return 0;
 591
 592         switch (order) {
 593         case PreOrder:
 594                 return WalkNodePreOrder(tree->Root, callback, context);
 595         case InOrder:
 596                 return WalkNodeInOrder(tree->Root, callback, context);
 597         case PostOrder:
 598                 return WalkNodePostOrder(tree->Root, callback, context);
 599
 600         default:
 601                 break;
 602         }
 603
 604         return -1;
 605 }
 606
 607 int rbtree_num_elements(rbtree_t *tree)
 608 {
 609         if (!tree) return 0;
 610
 611         return tree->num_elements;
 612 }
 613
 614
 615 /*
 616  *      Given a Node, return the data.
 617  */
 618 void *rbtree_node2data(rbtree_t *tree, rbnode_t *node)
 619 {
 620         tree = tree;            /* -Wunused */
 621
 622         if (!node) return NULL;
 623
 624         return node->Data;
 625 }
 626
 627 /*
 628  *      Return left-most child.
 629  */
 630 void *rbtree_min(rbtree_t *tree)
 631 {
 632         rbnode_t *Current;
 633
 634         if (!tree || !tree->Root) return NULL;
 635
 636         Current = tree->Root;
 637         while (Current->Left != NIL) Current = Current->Left;
 638
 639         return Current->Data;
 640 }