diff options
author | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2014-07-23 13:19:09 +0200 |
---|---|---|
committer | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2014-08-07 15:59:25 +0200 |
commit | 4752550f80206d7ab15daefb68532374f1b5a527 (patch) | |
tree | 2b8adf3a4a75cf46d7f1b65022298876122650e7 /cpukit | |
parent | sptests/sprbtree01: Check tree layout (diff) | |
download | rtems-4752550f80206d7ab15daefb68532374f1b5a527.tar.bz2 |
rbtree: Simplify _RBTree_Rotate()
Add and use _RBTree_Direction().
Diffstat (limited to 'cpukit')
-rw-r--r-- | cpukit/score/include/rtems/score/rbtreeimpl.h | 78 |
1 files changed, 61 insertions, 17 deletions
diff --git a/cpukit/score/include/rtems/score/rbtreeimpl.h b/cpukit/score/include/rtems/score/rbtreeimpl.h index 451b5f453a..5f5e78367a 100644 --- a/cpukit/score/include/rtems/score/rbtreeimpl.h +++ b/cpukit/score/include/rtems/score/rbtreeimpl.h @@ -77,6 +77,21 @@ RTEMS_INLINE_ROUTINE RBTree_Direction _RBTree_Opposite_direction( } /** + * @brief Returns the direction of the node. + * + * @param[in] the_node The node of interest. + * @param[in] parent The parent of the node. The parent must exist, thus it is + * invalid to use this function for the root node. + */ +RTEMS_INLINE_ROUTINE RBTree_Direction _RBTree_Direction( + const RBTree_Node *the_node, + const RBTree_Node *parent +) +{ + return (RBTree_Direction) ( the_node != parent->child[ 0 ] ); +} + +/** * @brief Is this node red. * * This function returns true if @a the_node is red and false otherwise. @@ -166,32 +181,61 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_lesser( } /** - * @brief Rotate the_node in the direction passed as second argument. + * @brief Rotates the node in the specified direction. * - * This routine rotates @a the_node to the direction @a dir, swapping - * @a the_node with its child\[@a dir\]. + * The node is swapped with its child in the opposite direction if it exists. + * + * Sub-tree before rotation: + * @dot + * digraph state { + * parent -> the_node; + * the_node -> sibling [label="dir"]; + * the_node -> child [label="opp_dir"]; + * child -> grandchild [label="dir"]; + * child -> grandchildsibling [label="opp_dir"]; + * } + * @enddot + * + * Sub-tree after rotation: + * @dot + * digraph state { + * parent -> child; + * the_node -> sibling [label="dir"]; + * the_node -> grandchild [label="opp_dir"]; + * child -> the_node [label="dir"]; + * child -> grandchildsibling [label="opp_dir"]; + * } + * @enddot + * + * @param[in] the_node The node to rotate. + * @param[in] dir The rotation direction. */ RTEMS_INLINE_ROUTINE void _RBTree_Rotate( - RBTree_Node *the_node, - RBTree_Direction dir - ) + RBTree_Node *the_node, + RBTree_Direction dir +) { - RBTree_Node *c; - if (the_node == NULL) return; - if (the_node->child[_RBTree_Opposite_direction(dir)] == NULL) return; + RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir ); + RBTree_Node *child = the_node->child[ opp_dir ]; + RBTree_Node *grandchild; + RBTree_Node *parent; + + if ( child == NULL) + return; - c = the_node->child[_RBTree_Opposite_direction(dir)]; - the_node->child[_RBTree_Opposite_direction(dir)] = c->child[dir]; + grandchild = child->child[ dir ]; + the_node->child[ opp_dir ] = grandchild; - if (c->child[dir]) - c->child[dir]->parent = the_node; + if ( grandchild != NULL ) + grandchild->parent = the_node; - c->child[dir] = the_node; + child->child[ dir ] = the_node; - the_node->parent->child[the_node != the_node->parent->child[0]] = c; + parent = _RBTree_Parent( the_node ); + parent->child[ _RBTree_Direction( the_node, parent ) ] = child; - c->parent = the_node->parent; - the_node->parent = c; + child->parent = parent; + the_node->parent = child; } /** @} */ |