LCOV - code coverage report
Current view: top level - lib/util - rbtree.c (source / functions) Hit Total Coverage
Test: coverage report for abartlet/fix-coverage dd10fb34 Lines: 193 223 86.5 %
Date: 2021-09-23 10:06:22 Functions: 10 13 76.9 %

          Line data    Source code
       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 "replace.h"
      24             : #include "rbtree.h"
      25             : #include "fault.h"
      26             : 
      27             : #define RB_RED          0
      28             : #define RB_BLACK        1
      29             : 
      30             : #define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
      31             : #define rb_color(r)   ((r)->rb_parent_color & 1)
      32             : #define rb_is_red(r)   (!rb_color(r))
      33             : #define rb_is_black(r) rb_color(r)
      34             : #define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
      35             : #define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)
      36             : 
      37     4552615 : static void rb_set_parent(struct rb_node *rb, struct rb_node *p)
      38             : {
      39     4560956 :         rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
      40     4552615 : }
      41       57687 : static void rb_set_color(struct rb_node *rb, int color)
      42             : {
      43       57993 :         rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
      44       57687 : }
      45             : 
      46             : #define RB_EMPTY_ROOT(root)     ((root)->rb_node == NULL)
      47             : #define RB_EMPTY_NODE(node)     (rb_parent(node) == node)
      48             : #define RB_CLEAR_NODE(node)     (rb_set_parent(node, node))
      49             : 
      50      943477 : static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
      51             : {
      52      943477 :         struct rb_node *right = node->rb_right;
      53      943477 :         struct rb_node *parent = rb_parent(node);
      54             : 
      55      943477 :         if ((node->rb_right = right->rb_left))
      56      210735 :                 rb_set_parent(right->rb_left, node);
      57      943477 :         right->rb_left = node;
      58             : 
      59      944916 :         rb_set_parent(right, parent);
      60             : 
      61      943477 :         if (parent)
      62             :         {
      63      777275 :                 if (node == parent->rb_left)
      64      511109 :                         parent->rb_left = right;
      65             :                 else
      66      266166 :                         parent->rb_right = right;
      67             :         }
      68             :         else
      69      166202 :                 root->rb_node = right;
      70      944916 :         rb_set_parent(node, right);
      71      943477 : }
      72             : 
      73      861856 : static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
      74             : {
      75      861856 :         struct rb_node *left = node->rb_left;
      76      861856 :         struct rb_node *parent = rb_parent(node);
      77             : 
      78      861856 :         if ((node->rb_left = left->rb_right))
      79      226647 :                 rb_set_parent(left->rb_right, node);
      80      861856 :         left->rb_right = node;
      81             : 
      82      863721 :         rb_set_parent(left, parent);
      83             : 
      84      861856 :         if (parent)
      85             :         {
      86      719290 :                 if (node == parent->rb_right)
      87      498443 :                         parent->rb_right = left;
      88             :                 else
      89      220847 :                         parent->rb_left = left;
      90             :         }
      91             :         else
      92      142566 :                 root->rb_node = left;
      93      863721 :         rb_set_parent(node, left);
      94      861856 : }
      95             : 
      96     3460449 : void rb_insert_color(struct rb_node *node, struct rb_root *root)
      97             : {
      98             :         struct rb_node *parent, *gparent;
      99             : 
     100     8451548 :         while ((parent = rb_parent(node)) && rb_is_red(parent))
     101             :         {
     102     2041669 :                 gparent = rb_parent(parent);
     103             : 
     104     2041669 :                 if (parent == gparent->rb_left)
     105             :                 {
     106             :                         {
     107     1010591 :                                 register struct rb_node *uncle = gparent->rb_right;
     108     1010591 :                                 if (uncle && rb_is_red(uncle))
     109             :                                 {
     110      434886 :                                         rb_set_black(uncle);
     111      434886 :                                         rb_set_black(parent);
     112      434886 :                                         rb_set_red(gparent);
     113      434886 :                                         node = gparent;
     114      434886 :                                         continue;
     115             :                                 }
     116             :                         }
     117             : 
     118      575705 :                         if (parent->rb_right == node)
     119             :                         {
     120             :                                 register struct rb_node *tmp;
     121      323862 :                                 __rb_rotate_left(parent, root);
     122      323862 :                                 tmp = parent;
     123      323862 :                                 parent = node;
     124      323862 :                                 node = tmp;
     125             :                         }
     126             : 
     127      575705 :                         rb_set_black(parent);
     128      575705 :                         rb_set_red(gparent);
     129      575705 :                         __rb_rotate_right(gparent, root);
     130             :                 } else {
     131             :                         {
     132     1031078 :                                 register struct rb_node *uncle = gparent->rb_left;
     133     1031078 :                                 if (uncle && rb_is_red(uncle))
     134             :                                 {
     135      472642 :                                         rb_set_black(uncle);
     136      472642 :                                         rb_set_black(parent);
     137      472642 :                                         rb_set_red(gparent);
     138      472642 :                                         node = gparent;
     139      472642 :                                         continue;
     140             :                                 }
     141             :                         }
     142             : 
     143      558436 :                         if (parent->rb_left == node)
     144             :                         {
     145             :                                 register struct rb_node *tmp;
     146      209706 :                                 __rb_rotate_right(parent, root);
     147      209706 :                                 tmp = parent;
     148      209706 :                                 parent = node;
     149      209706 :                                 node = tmp;
     150             :                         }
     151             : 
     152      558436 :                         rb_set_black(parent);
     153      558436 :                         rb_set_red(gparent);
     154      558436 :                         __rb_rotate_left(gparent, root);
     155             :                 }
     156             :         }
     157             : 
     158     3460449 :         rb_set_black(root->rb_node);
     159     3460449 : }
     160             : 
     161      489248 : static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
     162             :                              struct rb_root *root)
     163             : {
     164             :         struct rb_node *other;
     165             : 
     166     1086776 :         while ((!node || rb_is_black(node)) && node != root->rb_node)
     167             :         {
     168      245821 :                 if (parent->rb_left == node)
     169             :                 {
     170      100064 :                         other = parent->rb_right;
     171      100064 :                         if (other == NULL) {
     172             :                                 /* we should never get here */
     173           0 :                                 smb_panic("corrupted rb tree");
     174             :                                 /* satisfy static checkers */
     175             :                                 return;
     176             :                         }
     177      100064 :                         if (rb_is_red(other))
     178             :                         {
     179       18512 :                                 rb_set_black(other);
     180       18512 :                                 rb_set_red(parent);
     181       18512 :                                 __rb_rotate_left(parent, root);
     182       18512 :                                 other = parent->rb_right;
     183             :                         }
     184      166847 :                         if ((!other->rb_left || rb_is_black(other->rb_left)) &&
     185      115137 :                             (!other->rb_right || rb_is_black(other->rb_right)))
     186             :                         {
     187       69258 :                                 rb_set_red(other);
     188       69258 :                                 node = parent;
     189       69258 :                                 parent = rb_parent(node);
     190             :                         }
     191             :                         else
     192             :                         {
     193       30806 :                                 if (!other->rb_right || rb_is_black(other->rb_right))
     194             :                                 {
     195             :                                         struct rb_node *o_left;
     196       11246 :                                         if ((o_left = other->rb_left))
     197       11246 :                                                 rb_set_black(o_left);
     198       11246 :                                         rb_set_red(other);
     199       11246 :                                         __rb_rotate_right(other, root);
     200       11246 :                                         other = parent->rb_right;
     201             :                                 }
     202       30986 :                                 rb_set_color(other, rb_color(parent));
     203       30806 :                                 rb_set_black(parent);
     204       30806 :                                 if (other->rb_right)
     205       30806 :                                         rb_set_black(other->rb_right);
     206       30806 :                                 __rb_rotate_left(parent, root);
     207       30806 :                                 node = root->rb_node;
     208       30806 :                                 break;
     209             :                         }
     210             :                 }
     211             :                 else
     212             :                 {
     213      145757 :                         other = parent->rb_left;
     214      145757 :                         if (rb_is_red(other))
     215             :                         {
     216       38012 :                                 rb_set_black(other);
     217       38012 :                                 rb_set_red(parent);
     218       38012 :                                 __rb_rotate_right(parent, root);
     219       38012 :                                 other = parent->rb_left;
     220             :                         }
     221      251475 :                         if ((!other->rb_left || rb_is_black(other->rb_left)) &&
     222      179792 :                             (!other->rb_right || rb_is_black(other->rb_right)))
     223             :                         {
     224      118570 :                                 rb_set_red(other);
     225      118570 :                                 node = parent;
     226      118570 :                                 parent = rb_parent(node);
     227             :                         }
     228             :                         else
     229             :                         {
     230       27187 :                                 if (!other->rb_left || rb_is_black(other->rb_left))
     231             :                                 {
     232             :                                         register struct rb_node *o_right;
     233       11861 :                                         if ((o_right = other->rb_right))
     234       11861 :                                                 rb_set_black(o_right);
     235       11861 :                                         rb_set_red(other);
     236       11861 :                                         __rb_rotate_left(other, root);
     237       11861 :                                         other = parent->rb_left;
     238             :                                 }
     239       27313 :                                 rb_set_color(other, rb_color(parent));
     240       27187 :                                 rb_set_black(parent);
     241       27187 :                                 if (other->rb_left)
     242       27187 :                                         rb_set_black(other->rb_left);
     243       27187 :                                 __rb_rotate_right(parent, root);
     244       27187 :                                 node = root->rb_node;
     245       27187 :                                 break;
     246             :                         }
     247             :                 }
     248             :         }
     249      489248 :         if (node)
     250      275581 :                 rb_set_black(node);
     251      409700 : }
     252             : 
     253     1302203 : void rb_erase(struct rb_node *node, struct rb_root *root)
     254             : {
     255             :         struct rb_node *child, *parent;
     256             :         int color;
     257             : 
     258     1302203 :         if (!node->rb_left)
     259      956752 :                 child = node->rb_right;
     260      345451 :         else if (!node->rb_right)
     261       61138 :                 child = node->rb_left;
     262             :         else
     263             :         {
     264      283676 :                 struct rb_node *old = node, *left;
     265             : 
     266      283676 :                 node = node->rb_right;
     267      723178 :                 while ((left = node->rb_left) != NULL)
     268      202243 :                         node = left;
     269      284119 :                 child = node->rb_right;
     270      284119 :                 parent = rb_parent(node);
     271      284119 :                 color = rb_color(node);
     272             : 
     273      284119 :                 if (child)
     274       32864 :                         rb_set_parent(child, parent);
     275      284119 :                 if (parent == old) {
     276      186518 :                         parent->rb_right = child;
     277      186518 :                         parent = node;
     278             :                 } else
     279       97601 :                         parent->rb_left = child;
     280             : 
     281      284119 :                 node->rb_parent_color = old->rb_parent_color;
     282      284119 :                 node->rb_right = old->rb_right;
     283      284119 :                 node->rb_left = old->rb_left;
     284             : 
     285      284119 :                 if (rb_parent(old))
     286             :                 {
     287      229727 :                         if (rb_parent(old)->rb_left == old)
     288       56234 :                                 rb_parent(old)->rb_left = node;
     289             :                         else
     290      173493 :                                 rb_parent(old)->rb_right = node;
     291             :                 } else
     292       54392 :                         root->rb_node = node;
     293             : 
     294      284562 :                 rb_set_parent(old->rb_left, node);
     295      284119 :                 if (old->rb_right)
     296      106798 :                         rb_set_parent(old->rb_right, node);
     297      283676 :                 goto color;
     298             :         }
     299             : 
     300     1018084 :         parent = rb_parent(node);
     301     1018084 :         color = rb_color(node);
     302             : 
     303     1018084 :         if (child)
     304       89127 :                 rb_set_parent(child, parent);
     305     1018084 :         if (parent)
     306             :         {
     307      801952 :                 if (parent->rb_left == node)
     308      235715 :                         parent->rb_left = child;
     309             :                 else
     310      566237 :                         parent->rb_right = child;
     311             :         }
     312             :         else
     313      216132 :                 root->rb_node = child;
     314             : 
     315     1302203 :  color:
     316     1302203 :         if (color == RB_BLACK)
     317      489248 :                 __rb_erase_color(child, parent, root);
     318     1302203 : }
     319             : 
     320             : /*
     321             :  * This function returns the first node (in sort order) of the tree.
     322             :  */
     323           0 : struct rb_node *rb_first(struct rb_root *root)
     324             : {
     325             :         struct rb_node  *n;
     326             : 
     327           0 :         n = root->rb_node;
     328           0 :         if (!n)
     329           0 :                 return NULL;
     330           0 :         while (n->rb_left)
     331           0 :                 n = n->rb_left;
     332           0 :         return n;
     333             : }
     334             : 
     335           0 : struct rb_node *rb_last(struct rb_root *root)
     336             : {
     337             :         struct rb_node  *n;
     338             : 
     339           0 :         n = root->rb_node;
     340           0 :         if (!n)
     341           0 :                 return NULL;
     342           0 :         while (n->rb_right)
     343           0 :                 n = n->rb_right;
     344           0 :         return n;
     345             : }
     346             : 
     347        4303 : struct rb_node *rb_next(struct rb_node *node)
     348             : {
     349             :         struct rb_node *parent;
     350             : 
     351        4303 :         if (rb_parent(node) == node)
     352           0 :                 return NULL;
     353             : 
     354             :         /* If we have a right-hand child, go down and then left as far
     355             :            as we can. */
     356        4303 :         if (node->rb_right) {
     357         519 :                 node = node->rb_right; 
     358         967 :                 while (node->rb_left)
     359           2 :                         node=node->rb_left;
     360         519 :                 return node;
     361             :         }
     362             : 
     363             :         /* No right-hand children.  Everything down and left is
     364             :            smaller than us, so any 'next' node must be in the general
     365             :            direction of our parent. Go up the tree; any time the
     366             :            ancestor is a right-hand child of its parent, keep going
     367             :            up. First time it's a left-hand child of its parent, said
     368             :            parent is our 'next' node. */
     369        8588 :         while ((parent = rb_parent(node)) && node == parent->rb_right)
     370        1314 :                 node = parent;
     371             : 
     372        3783 :         return parent;
     373             : }
     374             : 
     375        3648 : struct rb_node *rb_prev(struct rb_node *node)
     376             : {
     377             :         struct rb_node *parent;
     378             : 
     379        3648 :         if (rb_parent(node) == node)
     380           0 :                 return NULL;
     381             : 
     382             :         /* If we have a left-hand child, go down and then right as far
     383             :            as we can. */
     384        3648 :         if (node->rb_left) {
     385         208 :                 node = node->rb_left; 
     386         430 :                 while (node->rb_right)
     387          14 :                         node=node->rb_right;
     388         208 :                 return node;
     389             :         }
     390             : 
     391             :         /* No left-hand children. Go up till we find an ancestor which
     392             :            is a right-hand child of its parent */
     393        9035 :         while ((parent = rb_parent(node)) && node == parent->rb_left)
     394        2503 :                 node = parent;
     395             : 
     396        3439 :         return parent;
     397             : }
     398             : 
     399           0 : void rb_replace_node(struct rb_node *victim, struct rb_node *new_node,
     400             :                      struct rb_root *root)
     401             : {
     402           0 :         struct rb_node *parent = rb_parent(victim);
     403             : 
     404             :         /* Set the surrounding nodes to point to the replacement */
     405           0 :         if (parent) {
     406           0 :                 if (victim == parent->rb_left)
     407           0 :                         parent->rb_left = new_node;
     408             :                 else
     409           0 :                         parent->rb_right = new_node;
     410             :         } else {
     411           0 :                 root->rb_node = new_node;
     412             :         }
     413           0 :         if (victim->rb_left)
     414           0 :                 rb_set_parent(victim->rb_left, new_node);
     415           0 :         if (victim->rb_right)
     416           0 :                 rb_set_parent(victim->rb_right, new_node);
     417             : 
     418             :         /* Copy the pointers/colour from the victim to the replacement */
     419           0 :         *new_node = *victim;
     420           0 : }
     421             : 
     422     3460449 : void rb_link_node(struct rb_node * node, struct rb_node * parent,
     423             :                   struct rb_node ** rb_link)
     424             : {
     425     3460449 :         node->rb_parent_color = (unsigned long )parent;
     426     3460449 :         node->rb_left = node->rb_right = NULL;
     427             : 
     428     3460449 :         *rb_link = node;
     429     3460449 : }

Generated by: LCOV version 1.13