LCOV - code coverage report
Current view: top level - lib/os - rb.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 0 234 0.0 %
Date: 2022-08-18 11:36:24 Functions: 0 20 0.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 120 0.0 %

           Branch data     Line data    Source code
       1                 :            : /*
       2                 :            :  * Copyright (c) 2018 Intel Corporation
       3                 :            :  *
       4                 :            :  * SPDX-License-Identifier: Apache-2.0
       5                 :            :  */
       6                 :            : 
       7                 :            : /* These assertions are very useful when debugging the tree code
       8                 :            :  * itself, but produce significant performance degradation as they are
       9                 :            :  * checked many times per operation.  Leave them off unless you're
      10                 :            :  * working on the rbtree code itself
      11                 :            :  */
      12                 :            : #define CHECK(n) /**/
      13                 :            : /* #define CHECK(n) __ASSERT_NO_MSG(n) */
      14                 :            : 
      15                 :            : #include <kernel.h>
      16                 :            : #include <sys/rb.h>
      17                 :            : #include <stdbool.h>
      18                 :            : 
      19                 :            : enum rb_color { RED = 0U, BLACK = 1U };
      20                 :            : 
      21                 :          0 : static struct rbnode *get_child(struct rbnode *n, uint8_t side)
      22                 :            : {
      23                 :            :         CHECK(n);
      24         [ #  # ]:          0 :         if (side != 0U) {
      25                 :          0 :                 return n->children[1];
      26                 :            :         }
      27                 :            : 
      28                 :          0 :         uintptr_t l = (uintptr_t) n->children[0];
      29                 :            : 
      30                 :          0 :         l &= ~1UL;
      31                 :          0 :         return (struct rbnode *) l;
      32                 :            : }
      33                 :            : 
      34                 :          0 : static void set_child(struct rbnode *n, uint8_t side, void *val)
      35                 :            : {
      36                 :            :         CHECK(n);
      37         [ #  # ]:          0 :         if (side != 0U) {
      38                 :          0 :                 n->children[1] = val;
      39                 :            :         } else {
      40                 :          0 :                 uintptr_t old = (uintptr_t) n->children[0];
      41                 :          0 :                 uintptr_t new = (uintptr_t) val;
      42                 :            : 
      43                 :          0 :                 n->children[0] = (void *) (new | (old & 1UL));
      44                 :            :         }
      45                 :          0 : }
      46                 :            : 
      47                 :          0 : static enum rb_color get_color(struct rbnode *n)
      48                 :            : {
      49                 :            :         CHECK(n);
      50                 :          0 :         return ((uintptr_t)n->children[0]) & 1UL;
      51                 :            : }
      52                 :            : 
      53                 :          0 : static bool is_black(struct rbnode *n)
      54                 :            : {
      55                 :          0 :         return get_color(n) == BLACK;
      56                 :            : }
      57                 :            : 
      58                 :          0 : static bool is_red(struct rbnode *n)
      59                 :            : {
      60                 :          0 :         return get_color(n) == RED;
      61                 :            : }
      62                 :            : 
      63                 :          0 : static void set_color(struct rbnode *n, enum rb_color color)
      64                 :            : {
      65                 :            :         CHECK(n);
      66                 :            : 
      67                 :          0 :         uintptr_t *p = (void *) &n->children[0];
      68                 :            : 
      69                 :          0 :         *p = (*p & ~1UL) | (uint8_t)color;
      70                 :          0 : }
      71                 :            : 
      72                 :            : /* Searches the tree down to a node that is either identical with the
      73                 :            :  * "node" argument or has an empty/leaf child pointer where "node"
      74                 :            :  * should be, leaving all nodes found in the resulting stack.  Note
      75                 :            :  * that tree must not be empty and that stack should be allocated to
      76                 :            :  * contain at least tree->max_depth entries!  Returns the number of
      77                 :            :  * entries pushed onto the stack.
      78                 :            :  */
      79                 :          0 : static int find_and_stack(struct rbtree *tree, struct rbnode *node,
      80                 :            :                           struct rbnode **stack)
      81                 :            : {
      82                 :          0 :         int sz = 0;
      83                 :            : 
      84                 :          0 :         stack[sz++] = tree->root;
      85                 :            : 
      86         [ #  # ]:          0 :         while (stack[sz - 1] != node) {
      87                 :          0 :                 uint8_t side = tree->lessthan_fn(node, stack[sz - 1]) ? 0U : 1U;
      88                 :          0 :                 struct rbnode *ch = get_child(stack[sz - 1], side);
      89                 :            : 
      90         [ #  # ]:          0 :                 if (ch != NULL) {
      91                 :          0 :                         stack[sz++] = ch;
      92                 :            :                 } else {
      93                 :          0 :                         break;
      94                 :            :                 }
      95                 :            :         }
      96                 :            : 
      97                 :          0 :         return sz;
      98                 :            : }
      99                 :            : 
     100                 :          0 : struct rbnode *z_rb_get_minmax(struct rbtree *tree, uint8_t side)
     101                 :            : {
     102                 :            :         struct rbnode *n;
     103                 :            : 
     104   [ #  #  #  # ]:          0 :         for (n = tree->root; (n != NULL) && (get_child(n, side) != NULL);
     105                 :          0 :                         n = get_child(n, side)) {
     106                 :            :                 ;
     107                 :            :         }
     108                 :          0 :         return n;
     109                 :            : }
     110                 :            : 
     111                 :          0 : static uint8_t get_side(struct rbnode *parent, struct rbnode *child)
     112                 :            : {
     113                 :            :         CHECK(get_child(parent, 0U) == child || get_child(parent, 1U) == child);
     114                 :            : 
     115         [ #  # ]:          0 :         return (get_child(parent, 1U) == child) ? 1U : 0U;
     116                 :            : }
     117                 :            : 
     118                 :            : /* Swaps the position of the two nodes at the top of the provided
     119                 :            :  * stack, modifying the stack accordingly. Does not change the color
     120                 :            :  * of either node.  That is, it effects the following transition (or
     121                 :            :  * its mirror if N is on the other side of P, of course):
     122                 :            :  *
     123                 :            :  *    P          N
     124                 :            :  *  N  c  -->  a   P
     125                 :            :  * a b            b c
     126                 :            :  *
     127                 :            :  */
     128                 :          0 : static void rotate(struct rbnode **stack, int stacksz)
     129                 :            : {
     130                 :            :         CHECK(stacksz >= 2);
     131                 :            : 
     132                 :          0 :         struct rbnode *parent = stack[stacksz - 2];
     133                 :          0 :         struct rbnode *child = stack[stacksz - 1];
     134                 :          0 :         uint8_t side = get_side(parent, child);
     135                 :          0 :         struct rbnode *a = get_child(child, side);
     136         [ #  # ]:          0 :         struct rbnode *b = get_child(child, (side == 0U) ? 1U : 0U);
     137                 :            : 
     138         [ #  # ]:          0 :         if (stacksz >= 3) {
     139                 :          0 :                 struct rbnode *grandparent = stack[stacksz - 3];
     140                 :            : 
     141                 :          0 :                 set_child(grandparent, get_side(grandparent, parent), child);
     142                 :            :         }
     143                 :            : 
     144                 :          0 :         set_child(child, side, a);
     145         [ #  # ]:          0 :         set_child(child, (side == 0U) ? 1U : 0U, parent);
     146                 :          0 :         set_child(parent, side, b);
     147                 :          0 :         stack[stacksz - 2] = child;
     148                 :          0 :         stack[stacksz - 1] = parent;
     149                 :          0 : }
     150                 :            : 
     151                 :            : /* The node at the top of the provided stack is red, and its parent is
     152                 :            :  * too.  Iteratively fix the tree so it becomes a valid red black tree
     153                 :            :  * again
     154                 :            :  */
     155                 :          0 : static void fix_extra_red(struct rbnode **stack, int stacksz)
     156                 :            : {
     157         [ #  # ]:          0 :         while (stacksz > 1) {
     158                 :          0 :                 struct rbnode *node = stack[stacksz - 1];
     159                 :          0 :                 struct rbnode *parent = stack[stacksz - 2];
     160                 :            : 
     161                 :            :                 /* Correct child colors are a precondition of the loop */
     162                 :            :                 CHECK((get_child(node, 0U) == NULL) ||
     163                 :            :                       is_black(get_child(node, 0U)));
     164                 :            :                 CHECK((get_child(node, 1U) == NULL) ||
     165                 :            :                       is_black(get_child(node, 1U)));
     166                 :            : 
     167         [ #  # ]:          0 :                 if (is_black(parent)) {
     168                 :          0 :                         return;
     169                 :            :                 }
     170                 :            : 
     171                 :            :                 /* We are guaranteed to have a grandparent if our
     172                 :            :                  * parent is red, as red nodes cannot be the root
     173                 :            :                  */
     174                 :            :                 CHECK(stacksz >= 2);
     175                 :            : 
     176                 :          0 :                 struct rbnode *grandparent = stack[stacksz - 3];
     177                 :          0 :                 uint8_t side = get_side(grandparent, parent);
     178         [ #  # ]:          0 :                 struct rbnode *aunt = get_child(grandparent,
     179                 :            :                                                 (side == 0U) ? 1U : 0U);
     180                 :            : 
     181   [ #  #  #  # ]:          0 :                 if ((aunt != NULL) && is_red(aunt)) {
     182                 :          0 :                         set_color(grandparent, RED);
     183                 :          0 :                         set_color(parent, BLACK);
     184                 :          0 :                         set_color(aunt, BLACK);
     185                 :            : 
     186                 :            :                         /* We colored the grandparent red, which might
     187                 :            :                          * have a red parent, so continue iterating
     188                 :            :                          * from there.
     189                 :            :                          */
     190                 :          0 :                         stacksz -= 2;
     191                 :          0 :                         continue;
     192                 :            :                 }
     193                 :            : 
     194                 :            :                 /* We can rotate locally to fix the whole tree.  First
     195                 :            :                  * make sure that node is on the same side of parent
     196                 :            :                  * as parent is of grandparent.
     197                 :            :                  */
     198                 :          0 :                 uint8_t parent_side = get_side(parent, node);
     199                 :            : 
     200         [ #  # ]:          0 :                 if (parent_side != side) {
     201                 :          0 :                         rotate(stack, stacksz);
     202                 :          0 :                         node = stack[stacksz - 1];
     203                 :            :                 }
     204                 :            : 
     205                 :            :                 /* Rotate the grandparent with parent, swapping colors */
     206                 :          0 :                 rotate(stack, stacksz - 1);
     207                 :          0 :                 set_color(stack[stacksz - 3], BLACK);
     208                 :          0 :                 set_color(stack[stacksz - 2], RED);
     209                 :          0 :                 return;
     210                 :            :         }
     211                 :            : 
     212                 :            :         /* If we exit the loop, it's because our node is now the root,
     213                 :            :          * which must be black.
     214                 :            :          */
     215                 :          0 :         set_color(stack[0], BLACK);
     216                 :            : }
     217                 :            : 
     218                 :          0 : void rb_insert(struct rbtree *tree, struct rbnode *node)
     219                 :          0 : {
     220                 :          0 :         set_child(node, 0U, NULL);
     221                 :          0 :         set_child(node, 1U, NULL);
     222                 :            : 
     223         [ #  # ]:          0 :         if (tree->root == NULL) {
     224                 :          0 :                 tree->root = node;
     225                 :          0 :                 tree->max_depth = 1;
     226                 :          0 :                 set_color(node, BLACK);
     227                 :          0 :                 return;
     228                 :            :         }
     229                 :            : 
     230                 :            : #ifdef CONFIG_MISRA_SANE
     231                 :            :         struct rbnode **stack = &tree->iter_stack[0];
     232                 :            : #else
     233                 :          0 :         struct rbnode *stack[tree->max_depth + 1];
     234                 :            : #endif
     235                 :            : 
     236                 :          0 :         int stacksz = find_and_stack(tree, node, stack);
     237                 :            : 
     238                 :          0 :         struct rbnode *parent = stack[stacksz - 1];
     239                 :            : 
     240                 :          0 :         uint8_t side = tree->lessthan_fn(node, parent) ? 0U : 1U;
     241                 :            : 
     242                 :          0 :         set_child(parent, side, node);
     243                 :          0 :         set_color(node, RED);
     244                 :            : 
     245                 :          0 :         stack[stacksz++] = node;
     246                 :          0 :         fix_extra_red(stack, stacksz);
     247                 :            : 
     248         [ #  # ]:          0 :         if (stacksz > tree->max_depth) {
     249                 :          0 :                 tree->max_depth = stacksz;
     250                 :            :         }
     251                 :            : 
     252                 :            :         /* We may have rotated up into the root! */
     253                 :          0 :         tree->root = stack[0];
     254                 :            :         CHECK(is_black(tree->root));
     255                 :            : }
     256                 :            : 
     257                 :            : /* Called for a node N (at the top of the stack) which after a
     258                 :            :  * deletion operation is "missing a black" in its subtree.  By
     259                 :            :  * construction N must be black (because if it was red it would be
     260                 :            :  * trivially fixed by recoloring and we wouldn't be here).  Fixes up
     261                 :            :  * the tree to preserve red/black rules.  The "null_node" pointer is
     262                 :            :  * for situations where we are removing a childless black node.  The
     263                 :            :  * tree munging needs a real node for simplicity, so we use it and
     264                 :            :  * then clean it up (replace it with a simple NULL child in the
     265                 :            :  * parent) when finished.
     266                 :            :  */
     267                 :          0 : static void fix_missing_black(struct rbnode **stack, int stacksz,
     268                 :            :                               struct rbnode *null_node)
     269                 :            : {
     270                 :            :         /* Loop upward until we reach the root */
     271         [ #  # ]:          0 :         while (stacksz > 1) {
     272                 :            :                 struct rbnode *c0, *c1, *inner, *outer;
     273                 :          0 :                 struct rbnode *n = stack[stacksz - 1];
     274                 :          0 :                 struct rbnode *parent = stack[stacksz - 2];
     275                 :          0 :                 uint8_t n_side = get_side(parent, n);
     276         [ #  # ]:          0 :                 struct rbnode *sib = get_child(parent,
     277                 :            :                                                (n_side == 0U) ? 1U : 0U);
     278                 :            : 
     279                 :            :                 CHECK(is_black(n));
     280                 :            : 
     281                 :            :                 /* Guarantee the sibling is black, rotating N down a
     282                 :            :                  * level if needed (after rotate() our parent is the
     283                 :            :                  * child of our previous-sibling, so N is lower in the
     284                 :            :                  * tree)
     285                 :            :                  */
     286         [ #  # ]:          0 :                 if (!is_black(sib)) {
     287                 :          0 :                         stack[stacksz - 1] = sib;
     288                 :          0 :                         rotate(stack, stacksz);
     289                 :          0 :                         set_color(parent, RED);
     290                 :          0 :                         set_color(sib, BLACK);
     291                 :          0 :                         stack[stacksz++] = n;
     292                 :            : 
     293                 :          0 :                         parent = stack[stacksz - 2];
     294         [ #  # ]:          0 :                         sib = get_child(parent, (n_side == 0U) ? 1U : 0U);
     295                 :            :                 }
     296                 :            : 
     297                 :            :                 CHECK(sib);
     298                 :            : 
     299                 :            :                 /* Cases where the sibling has only black children
     300                 :            :                  * have simple resolutions
     301                 :            :                  */
     302                 :          0 :                 c0 = get_child(sib, 0U);
     303                 :          0 :                 c1 = get_child(sib, 1U);
     304   [ #  #  #  #  :          0 :                 if (((c0 == NULL) || is_black(c0)) && ((c1 == NULL) ||
             #  #  #  # ]
     305                 :          0 :                                         is_black(c1))) {
     306         [ #  # ]:          0 :                         if (n == null_node) {
     307                 :          0 :                                 set_child(parent, n_side, NULL);
     308                 :            :                         }
     309                 :            : 
     310                 :          0 :                         set_color(sib, RED);
     311         [ #  # ]:          0 :                         if (is_black(parent)) {
     312                 :            :                                 /* Balance the sibling's subtree by
     313                 :            :                                  * coloring it red, then our parent
     314                 :            :                                  * has a missing black so iterate
     315                 :            :                                  * upward
     316                 :            :                                  */
     317                 :          0 :                                 stacksz--;
     318                 :          0 :                                 continue;
     319                 :            :                         } else {
     320                 :            :                                 /* Recoloring makes the whole tree OK */
     321                 :          0 :                                 set_color(parent, BLACK);
     322                 :          0 :                                 return;
     323                 :            :                         }
     324                 :            :                 }
     325                 :            : 
     326                 :            :                 CHECK((c0 && is_red(c0)) || (c1 && is_red(c1)));
     327                 :            : 
     328                 :            :                 /* We know sibling has at least one red child.  Fix it
     329                 :            :                  * so that the far/outer position (i.e. on the
     330                 :            :                  * opposite side from N) is definitely red.
     331                 :            :                  */
     332         [ #  # ]:          0 :                 outer = get_child(sib, (n_side == 0U) ? 1U : 0U);
     333   [ #  #  #  # ]:          0 :                 if (!((outer != NULL) && is_red(outer))) {
     334                 :          0 :                         inner = get_child(sib, n_side);
     335                 :            : 
     336                 :          0 :                         stack[stacksz - 1] = sib;
     337                 :          0 :                         stack[stacksz++] = inner;
     338                 :          0 :                         rotate(stack, stacksz);
     339                 :          0 :                         set_color(sib, RED);
     340                 :          0 :                         set_color(inner, BLACK);
     341                 :            : 
     342                 :            :                         /* Restore stack state to have N on the top
     343                 :            :                          * and make sib reflect the new sibling
     344                 :            :                          */
     345                 :          0 :                         sib = stack[stacksz - 2];
     346         [ #  # ]:          0 :                         outer = get_child(sib, (n_side == 0U) ? 1U : 0U);
     347                 :          0 :                         stack[stacksz - 2] = n;
     348                 :          0 :                         stacksz--;
     349                 :            :                 }
     350                 :            : 
     351                 :            :                 /* Finally, the sibling must have a red child in the
     352                 :            :                  * far/outer slot.  We can rotate sib with our parent
     353                 :            :                  * and recolor to produce a valid tree.
     354                 :            :                  */
     355                 :            :                 CHECK(is_red(outer));
     356                 :          0 :                 set_color(sib, get_color(parent));
     357                 :          0 :                 set_color(parent, BLACK);
     358                 :          0 :                 set_color(outer, BLACK);
     359                 :          0 :                 stack[stacksz - 1] = sib;
     360                 :          0 :                 rotate(stack, stacksz);
     361         [ #  # ]:          0 :                 if (n == null_node) {
     362                 :          0 :                         set_child(parent, n_side, NULL);
     363                 :            :                 }
     364                 :          0 :                 return;
     365                 :            :         }
     366                 :            : }
     367                 :            : 
     368                 :          0 : void rb_remove(struct rbtree *tree, struct rbnode *node)
     369                 :          0 : {
     370                 :            :         struct rbnode *tmp;
     371                 :            : #ifdef CONFIG_MISRA_SANE
     372                 :            :         struct rbnode **stack = &tree->iter_stack[0];
     373                 :            : #else
     374                 :          0 :         struct rbnode *stack[tree->max_depth + 1];
     375                 :            : #endif
     376                 :            : 
     377                 :          0 :         int stacksz = find_and_stack(tree, node, stack);
     378                 :            : 
     379         [ #  # ]:          0 :         if (node != stack[stacksz - 1]) {
     380                 :          0 :                 return;
     381                 :            :         }
     382                 :            : 
     383                 :            :         /* We can only remove a node with zero or one child, if we
     384                 :            :          * have two then pick the "biggest" child of side 0 (smallest
     385                 :            :          * of 1 would work too) and swap our spot in the tree with
     386                 :            :          * that one
     387                 :            :          */
     388   [ #  #  #  # ]:          0 :         if ((get_child(node, 0U) != NULL) && (get_child(node, 1U) != NULL)) {
     389                 :          0 :                 int stacksz0 = stacksz;
     390                 :            :                 struct rbnode *hiparent, *loparent;
     391                 :          0 :                 struct rbnode *node2 = get_child(node, 0U);
     392                 :            : 
     393         [ #  # ]:          0 :                 hiparent = (stacksz > 1) ? stack[stacksz - 2] : NULL;
     394                 :          0 :                 stack[stacksz++] = node2;
     395         [ #  # ]:          0 :                 while (get_child(node2, 1U) != NULL) {
     396                 :          0 :                         node2 = get_child(node2, 1U);
     397                 :          0 :                         stack[stacksz++] = node2;
     398                 :            :                 }
     399                 :            : 
     400                 :          0 :                 loparent = stack[stacksz - 2];
     401                 :            : 
     402                 :            :                 /* Now swap the position of node/node2 in the tree.
     403                 :            :                  * Design note: this is a spot where being an
     404                 :            :                  * intrusive data structure hurts us fairly badly.
     405                 :            :                  * The trees you see in textbooks do this by swapping
     406                 :            :                  * the "data" pointers between the two nodes, but we
     407                 :            :                  * have a few special cases to check.  In principle
     408                 :            :                  * this works by swapping the child pointers between
     409                 :            :                  * the nodes and retargeting the nodes pointing to
     410                 :            :                  * them from their parents, but: (1) the upper node
     411                 :            :                  * may be the root of the tree and not have a parent,
     412                 :            :                  * and (2) the lower node may be a direct child of the
     413                 :            :                  * upper node.  Remember to swap the color bits of the
     414                 :            :                  * two nodes also.  And of course we don't have parent
     415                 :            :                  * pointers, so the stack tracking this structure
     416                 :            :                  * needs to be swapped too!
     417                 :            :                  */
     418         [ #  # ]:          0 :                 if (hiparent != NULL) {
     419                 :          0 :                         set_child(hiparent, get_side(hiparent, node), node2);
     420                 :            :                 } else {
     421                 :          0 :                         tree->root = node2;
     422                 :            :                 }
     423                 :            : 
     424         [ #  # ]:          0 :                 if (loparent == node) {
     425                 :          0 :                         set_child(node, 0U, get_child(node2, 0U));
     426                 :          0 :                         set_child(node2, 0U, node);
     427                 :            :                 } else {
     428                 :          0 :                         set_child(loparent, get_side(loparent, node2), node);
     429                 :          0 :                         tmp = get_child(node, 0U);
     430                 :          0 :                         set_child(node, 0U, get_child(node2, 0U));
     431                 :          0 :                         set_child(node2, 0U, tmp);
     432                 :            :                 }
     433                 :            : 
     434                 :          0 :                 set_child(node2, 1U, get_child(node, 1U));
     435                 :          0 :                 set_child(node, 1U, NULL);
     436                 :            : 
     437                 :          0 :                 tmp = stack[stacksz0 - 1];
     438                 :          0 :                 stack[stacksz0 - 1] = stack[stacksz - 1];
     439                 :          0 :                 stack[stacksz - 1] = tmp;
     440                 :            : 
     441                 :          0 :                 enum rb_color ctmp = get_color(node);
     442                 :            : 
     443                 :          0 :                 set_color(node, get_color(node2));
     444                 :          0 :                 set_color(node2, ctmp);
     445                 :            :         }
     446                 :            : 
     447                 :            :         CHECK((get_child(node, 0U) == NULL) ||
     448                 :            :               (get_child(node, 1U) == NULL));
     449                 :            : 
     450                 :          0 :         struct rbnode *child = get_child(node, 0U);
     451                 :            : 
     452         [ #  # ]:          0 :         if (child == NULL) {
     453                 :          0 :                 child = get_child(node, 1U);
     454                 :            :         }
     455                 :            : 
     456                 :            :         /* Removing the root */
     457         [ #  # ]:          0 :         if (stacksz < 2) {
     458                 :          0 :                 tree->root = child;
     459         [ #  # ]:          0 :                 if (child != NULL) {
     460                 :          0 :                         set_color(child, BLACK);
     461                 :            :                 } else {
     462                 :          0 :                         tree->max_depth = 0;
     463                 :            :                 }
     464                 :          0 :                 return;
     465                 :            :         }
     466                 :            : 
     467                 :          0 :         struct rbnode *parent = stack[stacksz - 2];
     468                 :            : 
     469                 :            :         /* Special case: if the node to be removed is childless, then
     470                 :            :          * we leave it in place while we do the missing black
     471                 :            :          * rotations, which will replace it with a proper NULL when
     472                 :            :          * they isolate it.
     473                 :            :          */
     474         [ #  # ]:          0 :         if (child == NULL) {
     475         [ #  # ]:          0 :                 if (is_black(node)) {
     476                 :          0 :                         fix_missing_black(stack, stacksz, node);
     477                 :            :                 } else {
     478                 :            :                         /* Red childless nodes can just be dropped */
     479                 :          0 :                         set_child(parent, get_side(parent, node), NULL);
     480                 :            :                 }
     481                 :            :         } else {
     482                 :          0 :                 set_child(parent, get_side(parent, node), child);
     483                 :            : 
     484                 :            :                 /* Check colors, if one was red (at least one must have been
     485                 :            :                  * black in a valid tree), then we're done.
     486                 :            :                  */
     487   [ #  #  #  # ]:          0 :                 __ASSERT(is_black(node) || is_black(child), "both nodes red?!");
     488   [ #  #  #  # ]:          0 :                 if (is_red(node) || is_red(child)) {
     489                 :          0 :                         set_color(child, BLACK);
     490                 :            :                 }
     491                 :            :         }
     492                 :            : 
     493                 :            :         /* We may have rotated up into the root! */
     494                 :          0 :         tree->root = stack[0];
     495                 :            : }
     496                 :            : 
     497                 :            : #ifndef CONFIG_MISRA_SANE
     498                 :          0 : void z_rb_walk(struct rbnode *node, rb_visit_t visit_fn, void *cookie)
     499                 :            : {
     500         [ #  # ]:          0 :         if (node != NULL) {
     501                 :          0 :                 z_rb_walk(get_child(node, 0U), visit_fn, cookie);
     502                 :          0 :                 visit_fn(node, cookie);
     503                 :          0 :                 z_rb_walk(get_child(node, 1U), visit_fn, cookie);
     504                 :            :         }
     505                 :          0 : }
     506                 :            : #endif
     507                 :            : 
     508                 :          0 : struct rbnode *z_rb_child(struct rbnode *node, uint8_t side)
     509                 :            : {
     510                 :          0 :         return get_child(node, side);
     511                 :            : }
     512                 :            : 
     513                 :          0 : int z_rb_is_black(struct rbnode *node)
     514                 :            : {
     515                 :          0 :         return is_black(node);
     516                 :            : }
     517                 :            : 
     518                 :          0 : bool rb_contains(struct rbtree *tree, struct rbnode *node)
     519                 :            : {
     520                 :          0 :         struct rbnode *n = tree->root;
     521                 :            : 
     522   [ #  #  #  # ]:          0 :         while ((n != NULL) && (n != node)) {
     523                 :          0 :                 n = get_child(n, tree->lessthan_fn(n, node));
     524                 :            :         }
     525                 :            : 
     526                 :          0 :         return n == node;
     527                 :            : }
     528                 :            : 
     529                 :            : /* Pushes the node and its chain of left-side children onto the stack
     530                 :            :  * in the foreach struct, returning the last node, which is the next
     531                 :            :  * node to iterate.  By construction node will always be a right child
     532                 :            :  * or the root, so is_left must be false.
     533                 :            :  */
     534                 :          0 : static inline struct rbnode *stack_left_limb(struct rbnode *n,
     535                 :            :                                              struct _rb_foreach *f)
     536                 :            : {
     537                 :          0 :         f->top++;
     538                 :          0 :         f->stack[f->top] = n;
     539                 :          0 :         f->is_left[f->top] = 0U;
     540                 :            : 
     541         [ #  # ]:          0 :         while ((n = get_child(n, 0U)) != NULL) {
     542                 :          0 :                 f->top++;
     543                 :          0 :                 f->stack[f->top] = n;
     544                 :          0 :                 f->is_left[f->top] = 1;
     545                 :            :         }
     546                 :            : 
     547                 :          0 :         return f->stack[f->top];
     548                 :            : }
     549                 :            : 
     550                 :            : /* The foreach tracking works via a dynamic stack allocated via
     551                 :            :  * alloca().  The current node is found in stack[top] (and its parent
     552                 :            :  * is thus stack[top-1]).  The side of each stacked node from its
     553                 :            :  * parent is stored in is_left[] (i.e. if is_left[top] is true, then
     554                 :            :  * node/stack[top] is the left child of stack[top-1]).  The special
     555                 :            :  * case of top == -1 indicates that the stack is uninitialized and we
     556                 :            :  * need to push an initial stack starting at the root.
     557                 :            :  */
     558                 :          0 : struct rbnode *z_rb_foreach_next(struct rbtree *tree, struct _rb_foreach *f)
     559                 :            : {
     560                 :            :         struct rbnode *n;
     561                 :            : 
     562         [ #  # ]:          0 :         if (tree->root == NULL) {
     563                 :          0 :                 return NULL;
     564                 :            :         }
     565                 :            : 
     566                 :            :         /* Initialization condition, pick the leftmost child of the
     567                 :            :          * root as our first node, initializing the stack on the way.
     568                 :            :          */
     569         [ #  # ]:          0 :         if (f->top == -1) {
     570                 :          0 :                 return stack_left_limb(tree->root, f);
     571                 :            :         }
     572                 :            : 
     573                 :            :         /* The next child from a given node is the leftmost child of
     574                 :            :          * it's right subtree if it has a right child
     575                 :            :          */
     576                 :          0 :         n = get_child(f->stack[f->top], 1U);
     577         [ #  # ]:          0 :         if (n != NULL) {
     578                 :          0 :                 return stack_left_limb(n, f);
     579                 :            :         }
     580                 :            : 
     581                 :            :         /* Otherwise if the node is a left child of its parent, the
     582                 :            :          * next node is the parent (note that the root is stacked
     583                 :            :          * above with is_left set to 0, so this condition still works
     584                 :            :          * even if node has no parent).
     585                 :            :          */
     586         [ #  # ]:          0 :         if (f->is_left[f->top] != 0U) {
     587                 :          0 :                 return f->stack[--f->top];
     588                 :            :         }
     589                 :            : 
     590                 :            :         /* If we had no left tree and are a right child then our
     591                 :            :          * parent was already walked, so walk up the stack looking for
     592                 :            :          * a left child (whose parent is unwalked, and thus next).
     593                 :            :          */
     594   [ #  #  #  # ]:          0 :         while ((f->top > 0) && (f->is_left[f->top] == 0U)) {
     595                 :          0 :                 f->top--;
     596                 :            :         }
     597                 :            : 
     598                 :          0 :         f->top--;
     599         [ #  # ]:          0 :         return (f->top >= 0) ? f->stack[f->top] : NULL;
     600                 :            : }

Generated by: LCOV version 1.14