lustre/obdclass/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   rb_get_first and rb_get_next written by Theodore Ts'o, 9/8/2002
  22 */
  23
  24 #include <liblustre.h>
  25 #include <linux/rbtree.h>
  26
  27 static void __rb_rotate_left(rb_node_t * node, rb_root_t * root)
  28 {
  29         rb_node_t * right = node->rb_right;
  30
  31         if ((node->rb_right = right->rb_left))
  32                 right->rb_left->rb_parent = node;
  33         right->rb_left = node;
  34
  35         if ((right->rb_parent = node->rb_parent))
  36         {
  37                 if (node == node->rb_parent->rb_left)
  38                         node->rb_parent->rb_left = right;
  39                 else
  40                         node->rb_parent->rb_right = right;
  41         }
  42         else
  43                 root->rb_node = right;
  44         node->rb_parent = right;
  45 }
  46
  47 static void __rb_rotate_right(rb_node_t * node, rb_root_t * root)
  48 {
  49         rb_node_t * left = node->rb_left;
  50
  51         if ((node->rb_left = left->rb_right))
  52                 left->rb_right->rb_parent = node;
  53         left->rb_right = node;
  54
  55         if ((left->rb_parent = node->rb_parent))
  56         {
  57                 if (node == node->rb_parent->rb_right)
  58                         node->rb_parent->rb_right = left;
  59                 else
  60                         node->rb_parent->rb_left = left;
  61         }
  62         else
  63                 root->rb_node = left;
  64         node->rb_parent = left;
  65 }
  66
  67 void rb_insert_color(rb_node_t * node, rb_root_t * root)
  68 {
  69         rb_node_t * parent, * gparent;
  70
  71         while ((parent = node->rb_parent) && parent->rb_color == RB_RED)
  72         {
  73                 gparent = parent->rb_parent;
  74
  75                 if (parent == gparent->rb_left)
  76                 {
  77                         {
  78                                 register rb_node_t * uncle = gparent->rb_right;
  79                                 if (uncle && uncle->rb_color == RB_RED)
  80                                 {
  81                                         uncle->rb_color = RB_BLACK;
  82                                         parent->rb_color = RB_BLACK;
  83                                         gparent->rb_color = RB_RED;
  84                                         node = gparent;
  85                                         continue;
  86                                 }
  87                         }
  88
  89                         if (parent->rb_right == node)
  90                         {
  91                                 register rb_node_t * tmp;
  92                                 __rb_rotate_left(parent, root);
  93                                 tmp = parent;
  94                                 parent = node;
  95                                 node = tmp;
  96                         }
  97
  98                         parent->rb_color = RB_BLACK;
  99                         gparent->rb_color = RB_RED;
 100                         __rb_rotate_right(gparent, root);
 101                 } else {
 102                         {
 103                                 register rb_node_t * uncle = gparent->rb_left;
 104                                 if (uncle && uncle->rb_color == RB_RED)
 105                                 {
 106                                         uncle->rb_color = RB_BLACK;
 107                                         parent->rb_color = RB_BLACK;
 108                                         gparent->rb_color = RB_RED;
 109                                         node = gparent;
 110                                         continue;
 111                                 }
 112                         }
 113
 114                         if (parent->rb_left == node)
 115                         {
 116                                 register rb_node_t * tmp;
 117                                 __rb_rotate_right(parent, root);
 118                                 tmp = parent;
 119                                 parent = node;
 120                                 node = tmp;
 121                         }
 122
 123                         parent->rb_color = RB_BLACK;
 124                         gparent->rb_color = RB_RED;
 125                         __rb_rotate_left(gparent, root);
 126                 }
 127         }
 128
 129         root->rb_node->rb_color = RB_BLACK;
 130 }
 131 EXPORT_SYMBOL(rb_insert_color);
 132
 133 static void __rb_erase_color(rb_node_t * node, rb_node_t * parent,
 134                              rb_root_t * root)
 135 {
 136         rb_node_t * other;
 137
 138         while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node)
 139         {
 140                 if (parent->rb_left == node)
 141                 {
 142                         other = parent->rb_right;
 143                         if (other->rb_color == RB_RED)
 144                         {
 145                                 other->rb_color = RB_BLACK;
 146                                 parent->rb_color = RB_RED;
 147                                 __rb_rotate_left(parent, root);
 148                                 other = parent->rb_right;
 149                         }
 150                         if ((!other->rb_left ||
 151                              other->rb_left->rb_color == RB_BLACK)
 152                             && (!other->rb_right ||
 153                                 other->rb_right->rb_color == RB_BLACK))
 154                         {
 155                                 other->rb_color = RB_RED;
 156                                 node = parent;
 157                                 parent = node->rb_parent;
 158                         }
 159                         else
 160                         {
 161                                 if (!other->rb_right ||
 162                                     other->rb_right->rb_color == RB_BLACK)
 163                                 {
 164                                         register rb_node_t * o_left;
 165                                         if ((o_left = other->rb_left))
 166                                                 o_left->rb_color = RB_BLACK;
 167                                         other->rb_color = RB_RED;
 168                                         __rb_rotate_right(other, root);
 169                                         other = parent->rb_right;
 170                                 }
 171                                 other->rb_color = parent->rb_color;
 172                                 parent->rb_color = RB_BLACK;
 173                                 if (other->rb_right)
 174                                         other->rb_right->rb_color = RB_BLACK;
 175                                 __rb_rotate_left(parent, root);
 176                                 node = root->rb_node;
 177                                 break;
 178                         }
 179                 }
 180                 else
 181                 {
 182                         other = parent->rb_left;
 183                         if (other->rb_color == RB_RED)
 184                         {
 185                                 other->rb_color = RB_BLACK;
 186                                 parent->rb_color = RB_RED;
 187                                 __rb_rotate_right(parent, root);
 188                                 other = parent->rb_left;
 189                         }
 190                         if ((!other->rb_left ||
 191                              other->rb_left->rb_color == RB_BLACK)
 192                             && (!other->rb_right ||
 193                                 other->rb_right->rb_color == RB_BLACK))
 194                         {
 195                                 other->rb_color = RB_RED;
 196                                 node = parent;
 197                                 parent = node->rb_parent;
 198                         }
 199                         else
 200                         {
 201                                 if (!other->rb_left ||
 202                                     other->rb_left->rb_color == RB_BLACK)
 203                                 {
 204                                         register rb_node_t * o_right;
 205                                         if ((o_right = other->rb_right))
 206                                                 o_right->rb_color = RB_BLACK;
 207                                         other->rb_color = RB_RED;
 208                                         __rb_rotate_left(other, root);
 209                                         other = parent->rb_left;
 210                                 }
 211                                 other->rb_color = parent->rb_color;
 212                                 parent->rb_color = RB_BLACK;
 213                                 if (other->rb_left)
 214                                         other->rb_left->rb_color = RB_BLACK;
 215                                 __rb_rotate_right(parent, root);
 216                                 node = root->rb_node;
 217                                 break;
 218                         }
 219                 }
 220         }
 221         if (node)
 222                 node->rb_color = RB_BLACK;
 223 }
 224
 225 void rb_erase(rb_node_t * node, rb_root_t * root)
 226 {
 227         rb_node_t * child, * parent;
 228         int color;
 229
 230         if (!node->rb_left)
 231                 child = node->rb_right;
 232         else if (!node->rb_right)
 233                 child = node->rb_left;
 234         else
 235         {
 236                 rb_node_t * old = node, * left;
 237
 238                 node = node->rb_right;
 239                 while ((left = node->rb_left))
 240                         node = left;
 241                 child = node->rb_right;
 242                 parent = node->rb_parent;
 243                 color = node->rb_color;
 244
 245                 if (child)
 246                         child->rb_parent = parent;
 247                 if (parent)
 248                 {
 249                         if (parent->rb_left == node)
 250                                 parent->rb_left = child;
 251                         else
 252                                 parent->rb_right = child;
 253                 }
 254                 else
 255                         root->rb_node = child;
 256
 257                 if (node->rb_parent == old)
 258                         parent = node;
 259                 node->rb_parent = old->rb_parent;
 260                 node->rb_color = old->rb_color;
 261                 node->rb_right = old->rb_right;
 262                 node->rb_left = old->rb_left;
 263
 264                 if (old->rb_parent)
 265                 {
 266                         if (old->rb_parent->rb_left == old)
 267                                 old->rb_parent->rb_left = node;
 268                         else
 269                                 old->rb_parent->rb_right = node;
 270                 } else
 271                         root->rb_node = node;
 272
 273                 old->rb_left->rb_parent = node;
 274                 if (old->rb_right)
 275                         old->rb_right->rb_parent = node;
 276                 goto color;
 277         }
 278
 279         parent = node->rb_parent;
 280         color = node->rb_color;
 281
 282         if (child)
 283                 child->rb_parent = parent;
 284         if (parent)
 285         {
 286                 if (parent->rb_left == node)
 287                         parent->rb_left = child;
 288                 else
 289                         parent->rb_right = child;
 290         }
 291         else
 292                 root->rb_node = child;
 293
 294  color:
 295         if (color == RB_BLACK)
 296                 __rb_erase_color(child, parent, root);
 297 }
 298 EXPORT_SYMBOL(rb_erase);
 299
 300 /*
 301  * This function returns the first node (in sort order) of the tree.
 302  */
 303 rb_node_t *rb_get_first(rb_root_t *root)
 304 {
 305         rb_node_t       *n;
 306
 307         n = root->rb_node;
 308         if (!n)
 309                 return 0;
 310         while (n->rb_left)
 311                 n = n->rb_left;
 312         return n;
 313 }
 314 EXPORT_SYMBOL(rb_get_first);
 315
 316 /*
 317  * Given a node, this function will return the next node in the tree.
 318  */
 319 rb_node_t *rb_get_next(rb_node_t *n)
 320 {
 321         rb_node_t       *parent;
 322
 323         if (n->rb_right) {
 324                 n = n->rb_right;
 325                 while (n->rb_left)
 326                         n = n->rb_left;
 327                 return n;
 328         } else {
 329                 while ((parent = n->rb_parent)) {
 330                         if (n == parent->rb_left)
 331                                 return parent;
 332                         n = parent;
 333                 }
 334                 return 0;
 335         }
 336 }
 337 EXPORT_SYMBOL(rb_get_next);
 338