library/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
  17 #include <stdio.h>
  18 #include "rbtree.h"
  19
  20 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
  21 {
  22         struct rb_node *right = node->rb_right;
  23         struct rb_node *parent = rb_parent(node);
  24
  25         if ((node->rb_right = right->rb_left))
  26                 rb_set_parent(right->rb_left, node);
  27         right->rb_left = node;
  28
  29         rb_set_parent(right, parent);
  30
  31         if (parent)
  32         {
  33                 if (node == parent->rb_left)
  34                         parent->rb_left = right;
  35                 else
  36                         parent->rb_right = right;
  37         }
  38         else
  39                 root->rb_node = right;
  40         rb_set_parent(node, right);
  41 }
  42
  43 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
  44 {
  45         struct rb_node *left = node->rb_left;
  46         struct rb_node *parent = rb_parent(node);
  47
  48         if ((node->rb_left = left->rb_right))
  49                 rb_set_parent(left->rb_right, node);
  50         left->rb_right = node;
  51
  52         rb_set_parent(left, parent);
  53
  54         if (parent)
  55         {
  56                 if (node == parent->rb_right)
  57                         parent->rb_right = left;
  58                 else
  59                         parent->rb_left = left;
  60         }
  61         else
  62                 root->rb_node = left;
  63         rb_set_parent(node, left);
  64 }
  65
  66 void rb_insert_color(struct rb_node *node, struct rb_root *root)
  67 {
  68         struct rb_node *parent, *gparent;
  69
  70         while ((parent = rb_parent(node)) && rb_is_red(parent))
  71         {
  72                 gparent = rb_parent(parent);
  73
  74                 if (parent == gparent->rb_left)
  75                 {
  76                         {
  77                                 register struct rb_node *uncle = gparent->rb_right;
  78                                 if (uncle && rb_is_red(uncle))
  79                                 {
  80                                         rb_set_black(uncle);
  81                                         rb_set_black(parent);
  82                                         rb_set_red(gparent);
  83                                         node = gparent;
  84                                         continue;
  85                                 }
  86                         }
  87
  88                         if (parent->rb_right == node)
  89                         {
  90                                 register struct rb_node *tmp;
  91                                 __rb_rotate_left(parent, root);
  92                                 tmp = parent;
  93                                 parent = node;
  94                                 node = tmp;
  95                         }
  96
  97                         rb_set_black(parent);
  98                         rb_set_red(gparent);
  99                         __rb_rotate_right(gparent, root);
 100                 } else {
 101                         {
 102                                 register struct rb_node *uncle = gparent->rb_left;
 103                                 if (uncle && rb_is_red(uncle))
 104                                 {
 105                                         rb_set_black(uncle);
 106                                         rb_set_black(parent);
 107                                         rb_set_red(gparent);
 108                                         node = gparent;
 109                                         continue;
 110                                 }
 111                         }
 112
 113                         if (parent->rb_left == node)
 114                         {
 115                                 register struct rb_node *tmp;
 116                                 __rb_rotate_right(parent, root);
 117                                 tmp = parent;
 118                                 parent = node;
 119                                 node = tmp;
 120                         }
 121
 122                         rb_set_black(parent);
 123                         rb_set_red(gparent);
 124                         __rb_rotate_left(gparent, root);
 125                 }
 126         }
 127
 128         rb_set_black(root->rb_node);
 129 }
 130
 131 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 132                              struct rb_root *root)
 133 {
 134         struct rb_node *other;
 135
 136         while ((!node || rb_is_black(node)) && node != root->rb_node)
 137         {
 138                 if (parent->rb_left == node)
 139                 {
 140                         other = parent->rb_right;
 141                         if (rb_is_red(other))
 142                         {
 143                                 rb_set_black(other);
 144                                 rb_set_red(parent);
 145                                 __rb_rotate_left(parent, root);
 146                                 other = parent->rb_right;
 147                         }
 148                         if ((!other->rb_left || rb_is_black(other->rb_left)) &&
 149                             (!other->rb_right || rb_is_black(other->rb_right)))
 150                         {
 151                                 rb_set_red(other);
 152                                 node = parent;
 153                                 parent = rb_parent(node);
 154                         }
 155                         else
 156                         {
 157                                 if (!other->rb_right || rb_is_black(other->rb_right))
 158                                 {
 159                                         struct rb_node *o_left;
 160                                         if ((o_left = other->rb_left))
 161                                                 rb_set_black(o_left);
 162                                         rb_set_red(other);
 163                                         __rb_rotate_right(other, root);
 164                                         other = parent->rb_right;
 165                                 }
 166                                 rb_set_color(other, rb_color(parent));
 167                                 rb_set_black(parent);
 168                                 if (other->rb_right)
 169                                         rb_set_black(other->rb_right);
 170                                 __rb_rotate_left(parent, root);
 171                                 node = root->rb_node;
 172                                 break;
 173                         }
 174                 }
 175                 else
 176                 {
 177                         other = parent->rb_left;
 178                         if (rb_is_red(other))
 179                         {
 180                                 rb_set_black(other);
 181                                 rb_set_red(parent);
 182                                 __rb_rotate_right(parent, root);
 183                                 other = parent->rb_left;
 184                         }
 185                         if ((!other->rb_left || rb_is_black(other->rb_left)) &&
 186                             (!other->rb_right || rb_is_black(other->rb_right)))
 187                         {
 188                                 rb_set_red(other);
 189                                 node = parent;
 190                                 parent = rb_parent(node);
 191                         }
 192                         else
 193                         {
 194                                 if (!other->rb_left || rb_is_black(other->rb_left))
 195                                 {
 196                                         register struct rb_node *o_right;
 197                                         if ((o_right = other->rb_right))
 198                                                 rb_set_black(o_right);
 199                                         rb_set_red(other);
 200                                         __rb_rotate_left(other, root);
 201                                         other = parent->rb_left;
 202                                 }
 203                                 rb_set_color(other, rb_color(parent));
 204                                 rb_set_black(parent);
 205                                 if (other->rb_left)
 206                                         rb_set_black(other->rb_left);
 207                                 __rb_rotate_right(parent, root);
 208                                 node = root->rb_node;
 209                                 break;
 210                         }
 211                 }
 212         }
 213         if (node)
 214                 rb_set_black(node);
 215 }
 216
 217 void rb_erase(struct rb_node *node, struct rb_root *root)
 218 {
 219         struct rb_node *child, *parent;
 220         int color;
 221
 222         if (!node->rb_left)
 223                 child = node->rb_right;
 224         else if (!node->rb_right)
 225                 child = node->rb_left;
 226         else
 227         {
 228                 struct rb_node *old = node, *left;
 229
 230                 node = node->rb_right;
 231                 while ((left = node->rb_left) != NULL)
 232                         node = left;
 233                 child = node->rb_right;
 234                 parent = rb_parent(node);
 235                 color = rb_color(node);
 236
 237                 if (child)
 238                         rb_set_parent(child, parent);
 239                 if (parent == old) {
 240                         parent->rb_right = child;
 241                         parent = node;
 242                 } else
 243                         parent->rb_left = child;
 244
 245                 node->rb_parent_color = old->rb_parent_color;
 246                 node->rb_right = old->rb_right;
 247                 node->rb_left = old->rb_left;
 248
 249                 if (rb_parent(old))
 250                 {
 251                         if (rb_parent(old)->rb_left == old)
 252                                 rb_parent(old)->rb_left = node;
 253                         else
 254                                 rb_parent(old)->rb_right = node;
 255                 } else
 256                         root->rb_node = node;
 257
 258                 rb_set_parent(old->rb_left, node);
 259                 if (old->rb_right)
 260                         rb_set_parent(old->rb_right, node);
 261                 goto color;
 262         }
 263
 264         parent = rb_parent(node);
 265         color = rb_color(node);
 266
 267         if (child)
 268                 rb_set_parent(child, parent);
 269         if (parent)
 270         {
 271                 if (parent->rb_left == node)
 272                         parent->rb_left = child;
 273                 else
 274                         parent->rb_right = child;
 275         }
 276         else
 277                 root->rb_node = child;
 278
 279  color:
 280         if (color == RB_BLACK)
 281                 __rb_erase_color(child, parent, root);
 282 }
 283
 284 /*
 285  * This function returns the first node (in sort order) of the tree.
 286  */
 287 struct rb_node *rb_first(struct rb_root *root)
 288 {
 289         struct rb_node  *n;
 290
 291         n = root->rb_node;
 292         if (!n)
 293                 return NULL;
 294         while (n->rb_left)
 295                 n = n->rb_left;
 296         return n;
 297 }
 298
 299 struct rb_node *rb_last(struct rb_root *root)
 300 {
 301         struct rb_node  *n;
 302
 303         n = root->rb_node;
 304         if (!n)
 305                 return NULL;
 306         while (n->rb_right)
 307                 n = n->rb_right;
 308         return n;
 309 }
 310
 311 struct rb_node *rb_next(struct rb_node *node)
 312 {
 313         struct rb_node *parent;
 314
 315         if (rb_parent(node) == node)
 316                 return NULL;
 317
 318         /* If we have a right-hand child, go down and then left as far
 319            as we can. */
 320         if (node->rb_right) {
 321                 node = node->rb_right;
 322                 while (node->rb_left)
 323                         node=node->rb_left;
 324                 return node;
 325         }
 326
 327         /* No right-hand children.  Everything down and left is
 328            smaller than us, so any 'next' node must be in the general
 329            direction of our parent. Go up the tree; any time the
 330            ancestor is a right-hand child of its parent, keep going
 331            up. First time it's a left-hand child of its parent, said
 332            parent is our 'next' node. */
 333         while ((parent = rb_parent(node)) && node == parent->rb_right)
 334                 node = parent;
 335
 336         return parent;
 337 }
 338
 339 struct rb_node *rb_prev(struct rb_node *node)
 340 {
 341         struct rb_node *parent;
 342
 343         if (rb_parent(node) == node)
 344                 return NULL;
 345
 346         /* If we have a left-hand child, go down and then right as far
 347            as we can. */
 348         if (node->rb_left) {
 349                 node = node->rb_left;
 350                 while (node->rb_right)
 351                         node=node->rb_right;
 352                 return node;
 353         }
 354
 355         /* No left-hand children. Go up till we find an ancestor which
 356            is a right-hand child of its parent */
 357         while ((parent = rb_parent(node)) && node == parent->rb_left)
 358                 node = parent;
 359
 360         return parent;
 361 }
 362
 363 void rb_replace_node(struct rb_node *victim, struct rb_node *newp,
 364                      struct rb_root *root)
 365 {
 366         struct rb_node *parent = rb_parent(victim);
 367
 368         /* Set the surrounding nodes to point to the replacement */
 369         if (parent) {
 370                 if (victim == parent->rb_left)
 371                         parent->rb_left = newp;
 372                 else
 373                         parent->rb_right = newp;
 374         } else {
 375                 root->rb_node = newp;
 376         }
 377         if (victim->rb_left)
 378                 rb_set_parent(victim->rb_left, newp);
 379         if (victim->rb_right)
 380                 rb_set_parent(victim->rb_right, newp);
 381
 382         /* Copy the pointers/colour from the victim to the replacement */
 383         *newp = *victim;
 384 }