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