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