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