git.itanic.dy.fi Git - scan-pagemap/blob - 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 <stdlib.h>
  24
  25 #include "rbtree.h"
  26
  27 #define EXPORT_SYMBOL(foo)
  28
  29 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
  30 {
  31         struct rb_node *right = node->rb_right;
  32         struct rb_node *parent = rb_parent(node);
  33
  34         if ((node->rb_right = right->rb_left))
  35                 rb_set_parent(right->rb_left, node);
  36         right->rb_left = node;
  37
  38         rb_set_parent(right, parent);
  39
  40         if (parent)
  41         {
  42                 if (node == parent->rb_left)
  43                         parent->rb_left = right;
  44                 else
  45                         parent->rb_right = right;
  46         }
  47         else
  48                 root->rb_node = right;
  49         rb_set_parent(node, right);
  50 }
  51
  52 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
  53 {
  54         struct rb_node *left = node->rb_left;
  55         struct rb_node *parent = rb_parent(node);
  56
  57         if ((node->rb_left = left->rb_right))
  58                 rb_set_parent(left->rb_right, node);
  59         left->rb_right = node;
  60
  61         rb_set_parent(left, parent);
  62
  63         if (parent)
  64         {
  65                 if (node == parent->rb_right)
  66                         parent->rb_right = left;
  67                 else
  68                         parent->rb_left = left;
  69         }
  70         else
  71                 root->rb_node = left;
  72         rb_set_parent(node, left);
  73 }
  74
  75 void rb_insert_color(struct rb_node *node, struct rb_root *root)
  76 {
  77         struct rb_node *parent, *gparent;
  78
  79         while ((parent = rb_parent(node)) && rb_is_red(parent))
  80         {
  81                 gparent = rb_parent(parent);
  82
  83                 if (parent == gparent->rb_left)
  84                 {
  85                         {
  86                                 register struct rb_node *uncle = gparent->rb_right;
  87                                 if (uncle && rb_is_red(uncle))
  88                                 {
  89                                         rb_set_black(uncle);
  90                                         rb_set_black(parent);
  91                                         rb_set_red(gparent);
  92                                         node = gparent;
  93                                         continue;
  94                                 }
  95                         }
  96
  97                         if (parent->rb_right == node)
  98                         {
  99                                 register struct rb_node *tmp;
 100                                 __rb_rotate_left(parent, root);
 101                                 tmp = parent;
 102                                 parent = node;
 103                                 node = tmp;
 104                         }
 105
 106                         rb_set_black(parent);
 107                         rb_set_red(gparent);
 108                         __rb_rotate_right(gparent, root);
 109                 } else {
 110                         {
 111                                 register struct rb_node *uncle = gparent->rb_left;
 112                                 if (uncle && rb_is_red(uncle))
 113                                 {
 114                                         rb_set_black(uncle);
 115                                         rb_set_black(parent);
 116                                         rb_set_red(gparent);
 117                                         node = gparent;
 118                                         continue;
 119                                 }
 120                         }
 121
 122                         if (parent->rb_left == node)
 123                         {
 124                                 register struct rb_node *tmp;
 125                                 __rb_rotate_right(parent, root);
 126                                 tmp = parent;
 127                                 parent = node;
 128                                 node = tmp;
 129                         }
 130
 131                         rb_set_black(parent);
 132                         rb_set_red(gparent);
 133                         __rb_rotate_left(gparent, root);
 134                 }
 135         }
 136
 137         rb_set_black(root->rb_node);
 138 }
 139 EXPORT_SYMBOL(rb_insert_color);
 140
 141 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 142                              struct rb_root *root)
 143 {
 144         struct rb_node *other;
 145
 146         while ((!node || rb_is_black(node)) && node != root->rb_node)
 147         {
 148                 if (parent->rb_left == node)
 149                 {
 150                         other = parent->rb_right;
 151                         if (rb_is_red(other))
 152                         {
 153                                 rb_set_black(other);
 154                                 rb_set_red(parent);
 155                                 __rb_rotate_left(parent, root);
 156                                 other = parent->rb_right;
 157                         }
 158                         if ((!other->rb_left || rb_is_black(other->rb_left)) &&
 159                             (!other->rb_right || rb_is_black(other->rb_right)))
 160                         {
 161                                 rb_set_red(other);
 162                                 node = parent;
 163                                 parent = rb_parent(node);
 164                         }
 165                         else
 166                         {
 167                                 if (!other->rb_right || rb_is_black(other->rb_right))
 168                                 {
 169                                         rb_set_black(other->rb_left);
 170                                         rb_set_red(other);
 171                                         __rb_rotate_right(other, root);
 172                                         other = parent->rb_right;
 173                                 }
 174                                 rb_set_color(other, rb_color(parent));
 175                                 rb_set_black(parent);
 176                                 rb_set_black(other->rb_right);
 177                                 __rb_rotate_left(parent, root);
 178                                 node = root->rb_node;
 179                                 break;
 180                         }
 181                 }
 182                 else
 183                 {
 184                         other = parent->rb_left;
 185                         if (rb_is_red(other))
 186                         {
 187                                 rb_set_black(other);
 188                                 rb_set_red(parent);
 189                                 __rb_rotate_right(parent, root);
 190                                 other = parent->rb_left;
 191                         }
 192                         if ((!other->rb_left || rb_is_black(other->rb_left)) &&
 193                             (!other->rb_right || rb_is_black(other->rb_right)))
 194                         {
 195                                 rb_set_red(other);
 196                                 node = parent;
 197                                 parent = rb_parent(node);
 198                         }
 199                         else
 200                         {
 201                                 if (!other->rb_left || rb_is_black(other->rb_left))
 202                                 {
 203                                         rb_set_black(other->rb_right);
 204                                         rb_set_red(other);
 205                                         __rb_rotate_left(other, root);
 206                                         other = parent->rb_left;
 207                                 }
 208                                 rb_set_color(other, rb_color(parent));
 209                                 rb_set_black(parent);
 210                                 rb_set_black(other->rb_left);
 211                                 __rb_rotate_right(parent, root);
 212                                 node = root->rb_node;
 213                                 break;
 214                         }
 215                 }
 216         }
 217         if (node)
 218                 rb_set_black(node);
 219 }
 220
 221 void rb_erase(struct rb_node *node, struct rb_root *root)
 222 {
 223         struct rb_node *child, *parent;
 224         int color;
 225
 226         if (!node->rb_left)
 227                 child = node->rb_right;
 228         else if (!node->rb_right)
 229                 child = node->rb_left;
 230         else
 231         {
 232                 struct rb_node *old = node, *left;
 233
 234                 node = node->rb_right;
 235                 while ((left = node->rb_left) != NULL)
 236                         node = left;
 237
 238                 if (rb_parent(old)) {
 239                         if (rb_parent(old)->rb_left == old)
 240                                 rb_parent(old)->rb_left = node;
 241                         else
 242                                 rb_parent(old)->rb_right = node;
 243                 } else
 244                         root->rb_node = node;
 245
 246                 child = node->rb_right;
 247                 parent = rb_parent(node);
 248                 color = rb_color(node);
 249
 250                 if (parent == old) {
 251                         parent = node;
 252                 } else {
 253                         if (child)
 254                                 rb_set_parent(child, parent);
 255                         parent->rb_left = child;
 256
 257                         node->rb_right = old->rb_right;
 258                         rb_set_parent(old->rb_right, node);
 259                 }
 260
 261                 node->rb_parent_color = old->rb_parent_color;
 262                 node->rb_left = old->rb_left;
 263                 rb_set_parent(old->rb_left, node);
 264
 265                 goto color;
 266         }
 267
 268         parent = rb_parent(node);
 269         color = rb_color(node);
 270
 271         if (child)
 272                 rb_set_parent(child, parent);
 273         if (parent)
 274         {
 275                 if (parent->rb_left == node)
 276                         parent->rb_left = child;
 277                 else
 278                         parent->rb_right = child;
 279         }
 280         else
 281                 root->rb_node = child;
 282
 283  color:
 284         if (color == RB_BLACK)
 285                 __rb_erase_color(child, parent, root);
 286 }
 287 EXPORT_SYMBOL(rb_erase);
 288
 289 static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data)
 290 {
 291         struct rb_node *parent;
 292
 293 up:
 294         func(node, data);
 295         parent = rb_parent(node);
 296         if (!parent)
 297                 return;
 298
 299         if (node == parent->rb_left && parent->rb_right)
 300                 func(parent->rb_right, data);
 301         else if (parent->rb_left)
 302                 func(parent->rb_left, data);
 303
 304         node = parent;
 305         goto up;
 306 }
 307
 308 /*
 309  * after inserting @node into the tree, update the tree to account for
 310  * both the new entry and any damage done by rebalance
 311  */
 312 void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)
 313 {
 314         if (node->rb_left)
 315                 node = node->rb_left;
 316         else if (node->rb_right)
 317                 node = node->rb_right;
 318
 319         rb_augment_path(node, func, data);
 320 }
 321 EXPORT_SYMBOL(rb_augment_insert);
 322
 323 /*
 324  * before removing the node, find the deepest node on the rebalance path
 325  * that will still be there after @node gets removed
 326  */
 327 struct rb_node *rb_augment_erase_begin(struct rb_node *node)
 328 {
 329         struct rb_node *deepest;
 330
 331         if (!node->rb_right && !node->rb_left)
 332                 deepest = rb_parent(node);
 333         else if (!node->rb_right)
 334                 deepest = node->rb_left;
 335         else if (!node->rb_left)
 336                 deepest = node->rb_right;
 337         else {
 338                 deepest = rb_next(node);
 339                 if (deepest->rb_right)
 340                         deepest = deepest->rb_right;
 341                 else if (rb_parent(deepest) != node)
 342                         deepest = rb_parent(deepest);
 343         }
 344
 345         return deepest;
 346 }
 347 EXPORT_SYMBOL(rb_augment_erase_begin);
 348
 349 /*
 350  * after removal, update the tree to account for the removed entry
 351  * and any rebalance damage.
 352  */
 353 void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)
 354 {
 355         if (node)
 356                 rb_augment_path(node, func, data);
 357 }
 358 EXPORT_SYMBOL(rb_augment_erase_end);
 359
 360 /*
 361  * This function returns the first node (in sort order) of the tree.
 362  */
 363 struct rb_node *rb_first(const struct rb_root *root)
 364 {
 365         struct rb_node  *n;
 366
 367         n = root->rb_node;
 368         if (!n)
 369                 return NULL;
 370         while (n->rb_left)
 371                 n = n->rb_left;
 372         return n;
 373 }
 374 EXPORT_SYMBOL(rb_first);
 375
 376 struct rb_node *rb_last(const struct rb_root *root)
 377 {
 378         struct rb_node  *n;
 379
 380         n = root->rb_node;
 381         if (!n)
 382                 return NULL;
 383         while (n->rb_right)
 384                 n = n->rb_right;
 385         return n;
 386 }
 387 EXPORT_SYMBOL(rb_last);
 388
 389 struct rb_node *rb_next(const struct rb_node *node)
 390 {
 391         struct rb_node *parent;
 392
 393         if (rb_parent(node) == node)
 394                 return NULL;
 395
 396         /* If we have a right-hand child, go down and then left as far
 397            as we can. */
 398         if (node->rb_right) {
 399                 node = node->rb_right;
 400                 while (node->rb_left)
 401                         node=node->rb_left;
 402                 return (struct rb_node *)node;
 403         }
 404
 405         /* No right-hand children.  Everything down and left is
 406            smaller than us, so any 'next' node must be in the general
 407            direction of our parent. Go up the tree; any time the
 408            ancestor is a right-hand child of its parent, keep going
 409            up. First time it's a left-hand child of its parent, said
 410            parent is our 'next' node. */
 411         while ((parent = rb_parent(node)) && node == parent->rb_right)
 412                 node = parent;
 413
 414         return parent;
 415 }
 416 EXPORT_SYMBOL(rb_next);
 417
 418 struct rb_node *rb_prev(const struct rb_node *node)
 419 {
 420         struct rb_node *parent;
 421
 422         if (rb_parent(node) == node)
 423                 return NULL;
 424
 425         /* If we have a left-hand child, go down and then right as far
 426            as we can. */
 427         if (node->rb_left) {
 428                 node = node->rb_left;
 429                 while (node->rb_right)
 430                         node=node->rb_right;
 431                 return (struct rb_node *)node;
 432         }
 433
 434         /* No left-hand children. Go up till we find an ancestor which
 435            is a right-hand child of its parent */
 436         while ((parent = rb_parent(node)) && node == parent->rb_left)
 437                 node = parent;
 438
 439         return parent;
 440 }
 441 EXPORT_SYMBOL(rb_prev);
 442
 443 void rb_replace_node(struct rb_node *victim, struct rb_node *new,
 444                      struct rb_root *root)
 445 {
 446         struct rb_node *parent = rb_parent(victim);
 447
 448         /* Set the surrounding nodes to point to the replacement */
 449         if (parent) {
 450                 if (victim == parent->rb_left)
 451                         parent->rb_left = new;
 452                 else
 453                         parent->rb_right = new;
 454         } else {
 455                 root->rb_node = new;
 456         }
 457         if (victim->rb_left)
 458                 rb_set_parent(victim->rb_left, new);
 459         if (victim->rb_right)
 460                 rb_set_parent(victim->rb_right, new);
 461
 462         /* Copy the pointers/colour from the victim to the replacement */
 463         *new = *victim;
 464 }
 465 EXPORT_SYMBOL(rb_replace_node);