reactos/drivers/filesystems/ext2_new/src/rbtree.c

   1 /*
   2   Red Black Trees
   3   (C) 1999  Andrea Arcangeli <andrea@suse.de>
   4   (C) 2002  David Woodhouse <dwmw2@infradead.org>
   5
   6   This program is free software; you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License as published by
   8   the Free Software Foundation; either version 2 of the License, or
   9   (at your option) any later version.
  10
  11   This program 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
  14   GNU General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with this program; if not, write to the Free Software
  18   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19
  20   linux/lib/rbtree.c
  21 */
  22
  23 #include <linux/module.h>
  24
  25 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
  26 {
  27     struct rb_node *right = node->rb_right;
  28     struct rb_node *parent = rb_parent(node);
  29
  30     if ((node->rb_right = right->rb_left))
  31         rb_set_parent(right->rb_left, node);
  32     right->rb_left = node;
  33
  34     rb_set_parent(right, parent);
  35
  36     if (parent)
  37     {
  38         if (node == parent->rb_left)
  39             parent->rb_left = right;
  40         else
  41             parent->rb_right = right;
  42     }
  43     else
  44         root->rb_node = right;
  45     rb_set_parent(node, right);
  46 }
  47
  48 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
  49 {
  50     struct rb_node *left = node->rb_left;
  51     struct rb_node *parent = rb_parent(node);
  52
  53     if ((node->rb_left = left->rb_right))
  54         rb_set_parent(left->rb_right, node);
  55     left->rb_right = node;
  56
  57     rb_set_parent(left, parent);
  58
  59     if (parent)
  60     {
  61         if (node == parent->rb_right)
  62             parent->rb_right = left;
  63         else
  64             parent->rb_left = left;
  65     }
  66     else
  67         root->rb_node = left;
  68     rb_set_parent(node, left);
  69 }
  70
  71 void rb_insert_color(struct rb_node *node, struct rb_root *root)
  72 {
  73     struct rb_node *parent, *gparent;
  74
  75     while ((parent = rb_parent(node)) && rb_is_red(parent))
  76     {
  77         gparent = rb_parent(parent);
  78
  79         if (parent == gparent->rb_left)
  80         {
  81             {
  82                 register struct rb_node *uncle = gparent->rb_right;
  83                 if (uncle && rb_is_red(uncle))
  84                 {
  85                     rb_set_black(uncle);
  86                     rb_set_black(parent);
  87                     rb_set_red(gparent);
  88                     node = gparent;
  89                     continue;
  90                 }
  91             }
  92
  93             if (parent->rb_right == node)
  94             {
  95                 register struct rb_node *tmp;
  96                 __rb_rotate_left(parent, root);
  97                 tmp = parent;
  98                 parent = node;
  99                 node = tmp;
 100             }
 101
 102             rb_set_black(parent);
 103             rb_set_red(gparent);
 104             __rb_rotate_right(gparent, root);
 105         } else {
 106             {
 107                 register struct rb_node *uncle = gparent->rb_left;
 108                 if (uncle && rb_is_red(uncle))
 109                 {
 110                     rb_set_black(uncle);
 111                     rb_set_black(parent);
 112                     rb_set_red(gparent);
 113                     node = gparent;
 114                     continue;
 115                 }
 116             }
 117
 118             if (parent->rb_left == node)
 119             {
 120                 register struct rb_node *tmp;
 121                 __rb_rotate_right(parent, root);
 122                 tmp = parent;
 123                 parent = node;
 124                 node = tmp;
 125             }
 126
 127             rb_set_black(parent);
 128             rb_set_red(gparent);
 129             __rb_rotate_left(gparent, root);
 130         }
 131     }
 132
 133     rb_set_black(root->rb_node);
 134 }
 135 EXPORT_SYMBOL(rb_insert_color);
 136
 137 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 138                              struct rb_root *root)
 139 {
 140     struct rb_node *other;
 141
 142     while ((!node || rb_is_black(node)) && node != root->rb_node)
 143     {
 144         if (parent->rb_left == node)
 145         {
 146             other = parent->rb_right;
 147             if (rb_is_red(other))
 148             {
 149                 rb_set_black(other);
 150                 rb_set_red(parent);
 151                 __rb_rotate_left(parent, root);
 152                 other = parent->rb_right;
 153             }
 154             if ((!other->rb_left || rb_is_black(other->rb_left)) &&
 155                     (!other->rb_right || rb_is_black(other->rb_right)))
 156             {
 157                 rb_set_red(other);
 158                 node = parent;
 159                 parent = rb_parent(node);
 160             }
 161             else
 162             {
 163                 if (!other->rb_right || rb_is_black(other->rb_right))
 164                 {
 165                     struct rb_node *o_left;
 166                     if ((o_left = other->rb_left))
 167                         rb_set_black(o_left);
 168                     rb_set_red(other);
 169                     __rb_rotate_right(other, root);
 170                     other = parent->rb_right;
 171                 }
 172                 rb_set_color(other, rb_color(parent));
 173                 rb_set_black(parent);
 174                 if (other->rb_right)
 175                     rb_set_black(other->rb_right);
 176                 __rb_rotate_left(parent, root);
 177                 node = root->rb_node;
 178                 break;
 179             }
 180         }
 181         else
 182         {
 183             other = parent->rb_left;
 184             if (rb_is_red(other))
 185             {
 186                 rb_set_black(other);
 187                 rb_set_red(parent);
 188                 __rb_rotate_right(parent, root);
 189                 other = parent->rb_left;
 190             }
 191             if ((!other->rb_left || rb_is_black(other->rb_left)) &&
 192                     (!other->rb_right || rb_is_black(other->rb_right)))
 193             {
 194                 rb_set_red(other);
 195                 node = parent;
 196                 parent = rb_parent(node);
 197             }
 198             else
 199             {
 200                 if (!other->rb_left || rb_is_black(other->rb_left))
 201                 {
 202                     register struct rb_node *o_right;
 203                     if ((o_right = other->rb_right))
 204                         rb_set_black(o_right);
 205                     rb_set_red(other);
 206                     __rb_rotate_left(other, root);
 207                     other = parent->rb_left;
 208                 }
 209                 rb_set_color(other, rb_color(parent));
 210                 rb_set_black(parent);
 211                 if (other->rb_left)
 212                     rb_set_black(other->rb_left);
 213                 __rb_rotate_right(parent, root);
 214                 node = root->rb_node;
 215                 break;
 216             }
 217         }
 218     }
 219     if (node)
 220         rb_set_black(node);
 221 }
 222
 223 void rb_erase(struct rb_node *node, struct rb_root *root)
 224 {
 225     struct rb_node *child, *parent;
 226     ULONG_PTR color;
 227
 228     if (!node->rb_left)
 229         child = node->rb_right;
 230     else if (!node->rb_right)
 231         child = node->rb_left;
 232     else
 233     {
 234         struct rb_node *old = node, *left;
 235
 236         node = node->rb_right;
 237         while ((left = node->rb_left) != NULL)
 238             node = left;
 239         child = node->rb_right;
 240         parent = rb_parent(node);
 241         color = rb_color(node);
 242
 243         if (child)
 244             rb_set_parent(child, parent);
 245         if (parent == old) {
 246             parent->rb_right = child;
 247             parent = node;
 248         } else
 249             parent->rb_left = child;
 250
 251         node->rb_parent_color = old->rb_parent_color;
 252         node->rb_right = old->rb_right;
 253         node->rb_left = old->rb_left;
 254
 255         if (rb_parent(old))
 256         {
 257             if (rb_parent(old)->rb_left == old)
 258                 rb_parent(old)->rb_left = node;
 259             else
 260                 rb_parent(old)->rb_right = node;
 261         } else
 262             root->rb_node = node;
 263
 264         rb_set_parent(old->rb_left, node);
 265         if (old->rb_right)
 266             rb_set_parent(old->rb_right, node);
 267         goto color;
 268     }
 269
 270     parent = rb_parent(node);
 271     color = rb_color(node);
 272
 273     if (child)
 274         rb_set_parent(child, parent);
 275     if (parent)
 276     {
 277         if (parent->rb_left == node)
 278             parent->rb_left = child;
 279         else
 280             parent->rb_right = child;
 281     }
 282     else
 283         root->rb_node = child;
 284
 285 color:
 286     if (color == RB_BLACK)
 287         __rb_erase_color(child, parent, root);
 288 }
 289 EXPORT_SYMBOL(rb_erase);
 290
 291 /*
 292  * This function returns the first node (in sort order) of the tree.
 293  */
 294 struct rb_node *rb_first(struct rb_root *root)
 295 {
 296     struct rb_node      *n;
 297
 298     n = root->rb_node;
 299     if (!n)
 300         return NULL;
 301     while (n->rb_left)
 302         n = n->rb_left;
 303     return n;
 304 }
 305 EXPORT_SYMBOL(rb_first);
 306
 307 struct rb_node *rb_last(struct rb_root *root)
 308 {
 309     struct rb_node      *n;
 310
 311     n = root->rb_node;
 312     if (!n)
 313         return NULL;
 314     while (n->rb_right)
 315         n = n->rb_right;
 316     return n;
 317 }
 318 EXPORT_SYMBOL(rb_last);
 319
 320 struct rb_node *rb_next(struct rb_node *node)
 321 {
 322     struct rb_node *parent;
 323
 324     /* If we have a right-hand child, go down and then left as far
 325        as we can. */
 326     if (node->rb_right) {
 327         node = node->rb_right;
 328         while (node->rb_left)
 329             node=node->rb_left;
 330         return node;
 331     }
 332
 333     /* No right-hand children.  Everything down and left is
 334        smaller than us, so any 'next' node must be in the general
 335        direction of our parent. Go up the tree; any time the
 336        ancestor is a right-hand child of its parent, keep going
 337        up. First time it's a left-hand child of its parent, said
 338        parent is our 'next' node. */
 339     while ((parent = rb_parent(node)) && node == parent->rb_right)
 340         node = parent;
 341
 342     return parent;
 343 }
 344 EXPORT_SYMBOL(rb_next);
 345
 346 struct rb_node *rb_prev(struct rb_node *node)
 347 {
 348     struct rb_node *parent;
 349
 350     /* If we have a left-hand child, go down and then right as far
 351        as we can. */
 352     if (node->rb_left) {
 353         node = node->rb_left;
 354         while (node->rb_right)
 355             node=node->rb_right;
 356         return node;
 357     }
 358
 359     /* No left-hand children. Go up till we find an ancestor which
 360        is a right-hand child of its parent */
 361     while ((parent = rb_parent(node)) && node == parent->rb_left)
 362         node = parent;
 363
 364     return parent;
 365 }
 366 EXPORT_SYMBOL(rb_prev);
 367
 368 void rb_replace_node(struct rb_node *victim, struct rb_node *new,
 369                      struct rb_root *root)
 370 {
 371     struct rb_node *parent = rb_parent(victim);
 372
 373     /* Set the surrounding nodes to point to the replacement */
 374     if (parent) {
 375         if (victim == parent->rb_left)
 376             parent->rb_left = new;
 377         else
 378             parent->rb_right = new;
 379     } else {
 380         root->rb_node = new;
 381     }
 382     if (victim->rb_left)
 383         rb_set_parent(victim->rb_left, new);
 384     if (victim->rb_right)
 385         rb_set_parent(victim->rb_right, new);
 386
 387     /* Copy the pointers/colour from the victim to the replacement */
 388     *new = *victim;
 389 }
 390 EXPORT_SYMBOL(rb_replace_node);
 391
 392 void rb_insert(struct rb_root *root, struct rb_node *node,
 393          int (*cmp)(struct rb_node *, struct rb_node *))
 394 {
 395     struct rb_node **new = &(root->rb_node), *parent = NULL;
 396
 397     /* Figure out where to put new node */
 398     while (*new) {
 399         int result = cmp(node, *new);
 400
 401         parent = *new;
 402         if (result < 0)
 403             new = &((*new)->rb_left);
 404         else if (result > 0)
 405             new = &((*new)->rb_right);
 406         else
 407             return;
 408
 409     }
 410
 411     /* Add new node and rebalance tree. */
 412     rb_link_node(node, parent, new);
 413     rb_insert_color(node, root);
 414 }
 415 EXPORT_SYMBOL(rb_insert);