rom/filesys/SFS/FS/redblacktree.c

   1
   2 #include "redblacktree.h"
   3
   4 /* The constants below must be defined in the file which includes
   5    the redblacktree.c code. */
   6
   7 #if 0
   8
   9 #define ROOT     Root                /* The name of the root variable */
  10 #define RBNODE   struct RBTreeNode   /* The name of the structure containing the left,
  11                                         right, parent, nodecolor & data fields. */
  12 #define SENTINEL Sentinel            /* The name of the sentinel node variable (must be a RBNODE) */
  13 #define DATA     data                /* The name of the data field (example: data, sub.mydata) */
  14
  15 #define CompLT(a,b) (a < b)      /* modify these lines to establish data type */
  16 #define CompEQ(a,b) (a == b)
  17
  18 #endif
  19
  20
  21 /* Example RBTreeNode structure:
  22
  23 struct RBTreeNode {
  24   struct RBTreeNode *left;
  25   struct RBTreeNode *right;
  26   struct RBTreeNode *parent;
  27   UWORD magicvalue;
  28   NodeColor color;
  29   unsigned long data;
  30 };
  31
  32 */
  33
  34 /* prototypes */
  35
  36 void InsertNode(RBNODE *X);
  37 static void DeleteNode(RBNODE *X);
  38 void InsertFixup(RBNODE *X);
  39 static void DeleteFixup(RBNODE *X);
  40 void RotateLeft(RBNODE *X);
  41 void RotateRight(RBNODE *X);
  42 RBNODE *FindNode(unsigned long data);
  43
  44 #if 0
  45 #define NIL &SENTINEL           /* all leafs are sentinels */
  46 RBNODE Sentinel = { NULL, NULL, 0, BLACK, 0};
  47
  48 RBNODE *Root = NULL;               /* root of red-black tree */
  49 #endif
  50
  51
  52
  53 void InitRedBlackTree(void) {
  54   ROOT=&SENTINEL;
  55   SENTINEL.left=&SENTINEL;
  56   SENTINEL.right=&SENTINEL;
  57   SENTINEL.parent=0;
  58   SENTINEL.color=BLACK;
  59 //  SENTINEL.magicvalue=0x4a4f;
  60   SENTINEL.DATA=0;
  61 }
  62
  63
  64
  65 void InsertNode(RBNODE *X) {
  66   RBNODE *current, *parent;
  67
  68  /***********************************************
  69   *  allocate node for Data and insert in tree  *
  70   ***********************************************/
  71
  72   /* find where node belongs */
  73   current = ROOT;
  74   parent = 0;
  75   while (current != &SENTINEL) {
  76     // if(CompEQ(X->DATA, current->DATA)) return (current);
  77     parent = current;
  78     current = CompLT(X->DATA, current->DATA) ? current->left : current->right;
  79   }
  80
  81   X->parent = parent;
  82   X->left = &SENTINEL;
  83   X->right = &SENTINEL;
  84   X->color = RED;
  85
  86   /* insert node in tree */
  87   if(parent) {
  88     if(CompLT(X->DATA, parent->DATA)) {
  89       parent->left = X;
  90     }
  91     else {
  92       parent->right = X;
  93     }
  94   }
  95   else {
  96     ROOT = X;
  97   }
  98
  99   InsertFixup(X);
 100 }
 101
 102
 103
 104 void InsertFixup(RBNODE *X) {
 105
 106  /*************************************
 107   *  maintain red-black tree balance  *
 108   *  after inserting node X           *
 109   *************************************/
 110
 111   /* check red-black properties */
 112   while (X != ROOT && X->parent->color == RED) {
 113     /* we have a violation */
 114     if(X->parent == X->parent->parent->left) {
 115       RBNODE *Y = X->parent->parent->right;
 116       if(Y->color == RED) {
 117         /* uncle is red */
 118         X->parent->color = BLACK;
 119         Y->color = BLACK;
 120         X->parent->parent->color = RED;
 121         X = X->parent->parent;
 122       }
 123       else {
 124         /* uncle is black */
 125         if(X == X->parent->right) {
 126             /* make X a left child */
 127             X = X->parent;
 128             RotateLeft(X);
 129         }
 130
 131         /* recolor and rotate */
 132         X->parent->color = BLACK;
 133         X->parent->parent->color = RED;
 134         RotateRight(X->parent->parent);
 135       }
 136     }
 137     else {
 138       /* mirror image of above code */
 139       RBNODE *Y = X->parent->parent->left;
 140       if(Y->color == RED) {
 141
 142         /* uncle is red */
 143         X->parent->color = BLACK;
 144         Y->color = BLACK;
 145         X->parent->parent->color = RED;
 146         X = X->parent->parent;
 147       }
 148       else {
 149         /* uncle is black */
 150         if(X == X->parent->left) {
 151             X = X->parent;
 152             RotateRight(X);
 153         }
 154         X->parent->color = BLACK;
 155         X->parent->parent->color = RED;
 156         RotateLeft(X->parent->parent);
 157       }
 158     }
 159   }
 160   ROOT->color = BLACK;
 161 }
 162
 163 void RotateLeft(RBNODE *X) {
 164
 165  /**************************
 166   *  rotate Node X to left *
 167   **************************/
 168
 169   RBNODE *Y = X->right;
 170
 171   /* establish X->right link */
 172   X->right = Y->left;
 173   if(Y->left != &SENTINEL) {
 174     Y->left->parent = X;
 175   }
 176
 177   /* establish Y->parent link */
 178   if(Y != &SENTINEL) {
 179     Y->parent = X->parent;
 180   }
 181   if(X->parent) {
 182     if(X == X->parent->left) {
 183       X->parent->left = Y;
 184     }
 185     else {
 186       X->parent->right = Y;
 187     }
 188   }
 189   else {
 190     ROOT = Y;
 191   }
 192
 193   /* link X and Y */
 194   Y->left = X;
 195   if(X != &SENTINEL) {
 196     X->parent = Y;
 197   }
 198 }
 199
 200 void RotateRight(RBNODE *X) {
 201
 202  /****************************
 203   *  rotate Node X to right  *
 204   ****************************/
 205
 206   RBNODE *Y = X->left;
 207
 208   /* establish X->left link */
 209   X->left = Y->right;
 210   if(Y->right != &SENTINEL) {
 211     Y->right->parent = X;
 212   }
 213
 214   /* establish Y->parent link */
 215   if(Y != &SENTINEL) {
 216     Y->parent = X->parent;
 217   }
 218   if(X->parent) {
 219     if(X == X->parent->right) {
 220       X->parent->right = Y;
 221     }
 222     else {
 223       X->parent->left = Y;
 224     }
 225   }
 226   else {
 227     ROOT = Y;
 228   }
 229
 230   /* link X and Y */
 231   Y->right = X;
 232   if(X != &SENTINEL) {
 233     X->parent = Y;
 234   }
 235 }
 236
 237 static void DeleteNode(RBNODE *Z) {
 238   RBNODE *X, *Y;
 239   NodeColor c;
 240
 241  /*****************************
 242   *  delete node Z from tree  *
 243   *****************************/
 244
 245   if(!Z || Z == &SENTINEL) {
 246     return;
 247   }
 248
 249   if(Z->left == &SENTINEL || Z->right == &SENTINEL) {
 250     /* Y has a &SENTINEL node as a child */
 251     Y = Z;
 252   }
 253   else {
 254     /* find tree successor with a &SENTINEL node as a child */
 255     Y = Z->right;
 256     while(Y->left != &SENTINEL) {
 257       Y = Y->left;
 258     }
 259   }
 260
 261   /* X is Y's only child */
 262   if(Y->left != &SENTINEL) {
 263     X = Y->left;
 264   }
 265   else {
 266     X = Y->right;
 267   }
 268
 269   /* remove Y from the parent chain */
 270   X->parent = Y->parent;
 271   if(Y->parent) {
 272     if(Y == Y->parent->left) {
 273       Y->parent->left = X;
 274     }
 275     else {
 276       Y->parent->right = X;
 277     }
 278   }
 279   else {
 280     ROOT = X;
 281   }
 282
 283   c=Y->color;
 284
 285   if(Y != Z) {
 286     Y->parent=Z->parent;
 287     if(Z->parent!=0) {
 288       if(Z == Z->parent->left) {
 289         Z->parent->left=Y;
 290       }
 291       else {
 292         Z->parent->right=Y;
 293       }
 294     }
 295     else {
 296       ROOT=Y;
 297     }
 298
 299     Y->left=Z->left;
 300     Y->right=Z->right;
 301     Y->left->parent=Y;
 302     Y->right->parent=Y;
 303     Y->color=Z->color;
 304   }
 305   if(c == BLACK) {
 306     DeleteFixup(X);
 307   }
 308 }
 309
 310 void DeleteFixup(RBNODE *X) {
 311
 312    /*************************************
 313     *  maintain red-black tree balance  *
 314     *  after deleting node X            *
 315     *************************************/
 316
 317   while (X != ROOT && X->color == BLACK) {
 318     if(X == X->parent->left) {
 319       RBNODE *W = X->parent->right;
 320       if(W->color == RED) {
 321         W->color = BLACK;
 322         X->parent->color = RED;
 323         RotateLeft (X->parent);
 324         W = X->parent->right;
 325       }
 326       if(W->left->color == BLACK && W->right->color == BLACK) {
 327         W->color = RED;
 328         X = X->parent;
 329       }
 330       else {
 331         if(W->right->color == BLACK) {
 332           W->left->color = BLACK;
 333           W->color = RED;
 334           RotateRight (W);
 335           W = X->parent->right;
 336         }
 337         W->color = X->parent->color;
 338         X->parent->color = BLACK;
 339         W->right->color = BLACK;
 340         RotateLeft (X->parent);
 341         X = ROOT;
 342       }
 343     }
 344     else {
 345       RBNODE *W = X->parent->left;
 346       if(W->color == RED) {
 347         W->color = BLACK;
 348         X->parent->color = RED;
 349         RotateRight (X->parent);
 350         W = X->parent->left;
 351       }
 352       if(W->right->color == BLACK && W->left->color == BLACK) {
 353         W->color = RED;
 354         X = X->parent;
 355       }
 356       else {
 357         if(W->left->color == BLACK) {
 358           W->right->color = BLACK;
 359           W->color = RED;
 360           RotateLeft (W);
 361           W = X->parent->left;
 362         }
 363         W->color = X->parent->color;
 364         X->parent->color = BLACK;
 365         W->left->color = BLACK;
 366         RotateRight (X->parent);
 367         X = ROOT;
 368       }
 369     }
 370   }
 371   X->color = BLACK;
 372 }
 373
 374 #ifdef DEBUGCODE
 375 static RBNODE *FindClosestNode(unsigned long data) {
 376   RBNODE *closest=0;
 377   RBNODE *current = ROOT;
 378
 379   /* Finds the node containing data, or the next higher one.  Always
 380      check the resulting node.  It can be a Sentinel node, or if there
 381      is no node higher than or equal to data then the previous node
 382      will be returned. */
 383
 384   while(current != &SENTINEL) {
 385     closest=current;
 386     if(CompEQ(data, current->DATA)) {
 387       return (current);
 388     }
 389     else {
 390       current = CompLT(data, current->DATA) ? current->left : current->right;
 391     }
 392   }
 393   return(closest);
 394 }
 395 #endif
 396
 397 RBNODE *FindNode(unsigned long data) {
 398   RBNODE *current = ROOT;
 399
 400  /*******************************
 401   *  find node containing data  *
 402   *******************************/
 403
 404   while(current != &SENTINEL) {
 405     if(CompEQ(data, current->DATA)) {
 406       return (current);
 407     }
 408     else {
 409       current = CompLT(data, current->DATA) ? current->left : current->right;
 410     }
 411   }
 412   return(0);
 413 }
 414
 415
 416
 417 RBNODE *FindNodeFrom(RBNODE *current,unsigned long data) {
 418
 419  /*******************************
 420   *  find node containing data  *
 421   *******************************/
 422
 423   while(current != &SENTINEL) {
 424     if(CompEQ(data, current->DATA)) {
 425       return (current);
 426     }
 427     else {
 428       current = CompLT(data, current->DATA) ? current->left : current->right;
 429     }
 430   }
 431   return(0);
 432 }
 433
 434
 435
 436
 437 #ifdef DEBUGCODE
 438 /* Call with FindAllNodes(ROOT,...); */
 439
 440 static void FindAllNodes(RBNODE *current,unsigned long data) {
 441
 442  /************************************
 443   *  find all nodes containing Data  *
 444   ************************************/
 445
 446   if(current != &SENTINEL) {
 447     if(CompEQ(data, current->DATA)) {
 448
 449       // do something with Current here.
 450
 451       FindAllNodes(current->left,data);
 452       FindAllNodes(current->right,data);
 453     }
 454     else {
 455       CompLT(data, current->DATA) ? FindAllNodes(current->left,data) : FindAllNodes(current->right,data);
 456     }
 457   }
 458 }
 459 #endif
 460
 461
 462 void WalkTree(RBNODE *current) {
 463   if(current!=&SENTINEL) {
 464     WalkTree(current->left);
 465     WalkTree(current->right);
 466   }
 467 }
 468
 469
 470
 471 RBNODE *FirstNode(void) {
 472   RBNODE *n=ROOT;
 473
 474   /* This function returns the first node, or 0 if there are no nodes at all. */
 475
 476   if(n==&SENTINEL) {
 477     return(0);
 478   }
 479
 480   while(n->left != &SENTINEL) {
 481     n=n->left;
 482   }
 483
 484   return(n);
 485 }
 486
 487
 488 RBNODE *NextNode(RBNODE *n) {
 489 //  cop(n, "nextnode 1");
 490
 491   if(n->right != &SENTINEL) {
 492     n=n->right;
 493     while(n->left != &SENTINEL) {
 494       n=n->left;
 495 //      cop(n, "nextnode 2");
 496     }
 497     return(n);
 498   }
 499
 500   while(n->parent!=0) {
 501     if(n->parent->left == n) {
 502       break;
 503     }
 504
 505     n=n->parent;
 506 //    cop(n, "nextnode 3");
 507   }
 508
 509   return(n->parent);
 510 }