LCOV - code coverage report
Current view: top level - crtools - rbtree.c (source / functions) Hit Total Coverage
Test: crtools.info Lines: 66 181 36.5 %
Date: 2012-12-28 Functions: 3 10 30.0 %
Branches: 30 126 23.8 %

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

Generated by: LCOV version 1.9