lib/rbtree.c

   1 /*
   2   Red Black Trees
   3   (C) 1999  Andrea Arcangeli <andrea@suse.de>
   4
   5   This program is free software; you can redistribute it and/or modify
   6   it under the terms of the GNU General Public License as published by
   7   the Free Software Foundation; either version 2 of the License, or
   8   (at your option) any later version.
   9
  10   This program is distributed in the hope that it will be useful,
  11   but WITHOUT ANY WARRANTY; without even the implied warranty of
  12   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13   GNU General Public License for more details.
  14
  15   You should have received a copy of the GNU General Public License
  16   along with this program; if not, write to the Free Software
  17   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  18
  19   linux/lib/rbtree.c
  20 */
  21
  22 #include <linux/rbtree.h>
  23 #include <linux/module.h>
  24
  25 static void __rb_rotate_left(rb_node_t * node, rb_root_t * root)
  26 {
  27         rb_node_t * 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(rb_node_t * node, rb_root_t * root)
  46 {
  47         rb_node_t * 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(rb_node_t * node, rb_root_t * root)
  66 {
  67         rb_node_t * 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 rb_node_t * 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 rb_node_t * 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 rb_node_t * 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 rb_node_t * 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 EXPORT_SYMBOL(rb_insert_color);
 130
 131 static void __rb_erase_color(rb_node_t * node, rb_node_t * parent,
 132                              rb_root_t * root)
 133 {
 134         rb_node_t * other;
 135
 136         while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node)
 137         {
 138                 if (parent->rb_left == node)
 139                 {
 140                         other = parent->rb_right;
 141                         if (other->rb_color == RB_RED)
 142                         {
 143                                 other->rb_color = RB_BLACK;
 144                                 parent->rb_color = RB_RED;
 145                                 __rb_rotate_left(parent, root);
 146                                 other = parent->rb_right;
 147                         }
 148                         if ((!other->rb_left ||
 149                              other->rb_left->rb_color == RB_BLACK)
 150                             && (!other->rb_right ||
 151                                 other->rb_right->rb_color == RB_BLACK))
 152                         {
 153                                 other->rb_color = RB_RED;
 154                                 node = parent;
 155                                 parent = node->rb_parent;
 156                         }
 157                         else
 158                         {
 159                                 if (!other->rb_right ||
 160                                     other->rb_right->rb_color == RB_BLACK)
 161                                 {
 162                                         register rb_node_t * o_left;
 163                                         if ((o_left = other->rb_left))
 164                                                 o_left->rb_color = RB_BLACK;
 165                                         other->rb_color = RB_RED;
 166                                         __rb_rotate_right(other, root);
 167                                         other = parent->rb_right;
 168                                 }
 169                                 other->rb_color = parent->rb_color;
 170                                 parent->rb_color = RB_BLACK;
 171                                 if (other->rb_right)
 172                                         other->rb_right->rb_color = RB_BLACK;
 173                                 __rb_rotate_left(parent, root);
 174                                 node = root->rb_node;
 175                                 break;
 176                         }
 177                 }
 178                 else
 179                 {
 180                         other = parent->rb_left;
 181                         if (other->rb_color == RB_RED)
 182                         {
 183                                 other->rb_color = RB_BLACK;
 184                                 parent->rb_color = RB_RED;
 185                                 __rb_rotate_right(parent, root);
 186                                 other = parent->rb_left;
 187                         }
 188                         if ((!other->rb_left ||
 189                              other->rb_left->rb_color == RB_BLACK)
 190                             && (!other->rb_right ||
 191                                 other->rb_right->rb_color == RB_BLACK))
 192                         {
 193                                 other->rb_color = RB_RED;
 194                                 node = parent;
 195                                 parent = node->rb_parent;
 196                         }
 197                         else
 198                         {
 199                                 if (!other->rb_left ||
 200                                     other->rb_left->rb_color == RB_BLACK)
 201                                 {
 202                                         register rb_node_t * o_right;
 203                                         if ((o_right = other->rb_right))
 204                                                 o_right->rb_color = RB_BLACK;
 205                                         other->rb_color = RB_RED;
 206                                         __rb_rotate_left(other, root);
 207                                         other = parent->rb_left;
 208                                 }
 209                                 other->rb_color = parent->rb_color;
 210                                 parent->rb_color = RB_BLACK;
 211                                 if (other->rb_left)
 212                                         other->rb_left->rb_color = RB_BLACK;
 213                                 __rb_rotate_right(parent, root);
 214                                 node = root->rb_node;
 215                                 break;
 216                         }
 217                 }
 218         }
 219         if (node)
 220                 node->rb_color = RB_BLACK;
 221 }
 222
 223 void rb_erase(rb_node_t * node, rb_root_t * root)
 224 {
 225         rb_node_t * child, * parent;
 226         int 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                 rb_node_t * old = node, * left;
 235
 236                 node = node->rb_right;
 237                 while ((left = node->rb_left))
 238                         node = left;
 239                 child = node->rb_right;
 240                 parent = node->rb_parent;
 241                 color = node->rb_color;
 242
 243                 if (child)
 244                         child->rb_parent = parent;
 245                 if (parent)
 246                 {
 247                         if (parent->rb_left == node)
 248                                 parent->rb_left = child;
 249                         else
 250                                 parent->rb_right = child;
 251                 }
 252                 else
 253                         root->rb_node = child;
 254
 255                 if (node->rb_parent == old)
 256                         parent = node;
 257                 node->rb_parent = old->rb_parent;
 258                 node->rb_color = old->rb_color;
 259                 node->rb_right = old->rb_right;
 260                 node->rb_left = old->rb_left;
 261
 262                 if (old->rb_parent)
 263                 {
 264                         if (old->rb_parent->rb_left == old)
 265                                 old->rb_parent->rb_left = node;
 266                         else
 267                                 old->rb_parent->rb_right = node;
 268                 } else
 269                         root->rb_node = node;
 270
 271                 old->rb_left->rb_parent = node;
 272                 if (old->rb_right)
 273                         old->rb_right->rb_parent = node;
 274                 goto color;
 275         }
 276
 277         parent = node->rb_parent;
 278         color = node->rb_color;
 279
 280         if (child)
 281                 child->rb_parent = parent;
 282         if (parent)
 283         {
 284                 if (parent->rb_left == node)
 285                         parent->rb_left = child;
 286                 else
 287                         parent->rb_right = child;
 288         }
 289         else
 290                 root->rb_node = child;
 291
 292  color:
 293         if (color == RB_BLACK)
 294                 __rb_erase_color(child, parent, root);
 295 }
 296 EXPORT_SYMBOL(rb_erase);