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