From 6e93c836e26c28a01e2e6c4a14470b93aed03999 Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Tue, 22 Jul 2014 19:42:54 +0200 Subject: rbtree: Simplify off-tree handling Only use the parent pointer, since this pointer is never NULL for nodes which are part of a tree. Rename functions from *_off_rbtree() to *_off_tree(). --- cpukit/sapi/include/rtems/rbtree.h | 8 +++---- cpukit/score/include/rtems/score/rbtree.h | 37 +++++++++++++++++-------------- testsuites/sptests/sprbtree01/init.c | 8 +++---- 3 files changed, 28 insertions(+), 25 deletions(-) diff --git a/cpukit/sapi/include/rtems/rbtree.h b/cpukit/sapi/include/rtems/rbtree.h index 2005b367e7..dbc6d20d70 100644 --- a/cpukit/sapi/include/rtems/rbtree.h +++ b/cpukit/sapi/include/rtems/rbtree.h @@ -121,11 +121,11 @@ RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize_empty( * This function sets the next and previous fields of the @a node to NULL * indicating the @a node is not part of any rbtree. */ -RTEMS_INLINE_ROUTINE void rtems_rbtree_set_off_rbtree( +RTEMS_INLINE_ROUTINE void rtems_rbtree_set_off_tree( rtems_rbtree_node *node ) { - _RBTree_Set_off_rbtree( node ); + _RBTree_Set_off_tree( node ); } /** @@ -134,11 +134,11 @@ RTEMS_INLINE_ROUTINE void rtems_rbtree_set_off_rbtree( * This function returns true if the @a node is not on a rbtree. A @a node is * off rbtree if the next and previous fields are set to NULL. */ -RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_node_off_rbtree( +RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_node_off_tree( const rtems_rbtree_node *node ) { - return _RBTree_Is_node_off_rbtree( node ); + return _RBTree_Is_node_off_tree( node ); } /** diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h index 2ec77ead4f..94c8ee567e 100644 --- a/cpukit/score/include/rtems/score/rbtree.h +++ b/cpukit/score/include/rtems/score/rbtree.h @@ -245,7 +245,7 @@ RBTree_Node *_RBTree_Insert( * @brief Extracts (removes) the node from the red-black tree. * * This function does not set the node off-tree. In case this is desired, then - * call _RBTree_Set_off_rbtree() after the extraction. + * call _RBTree_Set_off_tree() after the extraction. * * In case the node to extract is not a node of the tree, then this function * yields unpredictable results. @@ -273,32 +273,35 @@ RBTree_Node *_RBTree_Next( ); /** - * @brief Set off RBtree. + * @brief Sets a red-black tree node as off-tree. * - * This function sets the parent and child fields of the @a node to NULL - * indicating the @a node is not part of a rbtree. + * Do not use this function on nodes which are a part of a tree. * + * @param[in] the_node The node to set off-tree. + * + * @see _RBTree_Is_node_off_tree(). */ -RTEMS_INLINE_ROUTINE void _RBTree_Set_off_rbtree( - RBTree_Node *node - ) +RTEMS_INLINE_ROUTINE void _RBTree_Set_off_tree( RBTree_Node *the_node ) { - node->parent = node->child[RBT_LEFT] = node->child[RBT_RIGHT] = NULL; + the_node->parent = NULL; } /** - * @brief Is the node off RBTree. + * @brief Returns true, if this red-black tree node is off-tree, and false + * otherwise. + * + * @param[in] the_node The node to test. + * + * @retval true The node is not a part of a tree (off-tree). + * @retval false Otherwise. * - * This function returns true if the @a node is not on a rbtree. A @a node is - * off rbtree if the parent and child fields are set to NULL. + * @see _RBTree_Set_off_tree(). */ -RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_rbtree( - const RBTree_Node *node - ) +RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_tree( + const RBTree_Node *the_node +) { - return (node->parent == NULL) && - (node->child[RBT_LEFT] == NULL) && - (node->child[RBT_RIGHT] == NULL); + return the_node->parent == NULL; } /** diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c index 2c62d12b6d..68b2c92039 100644 --- a/testsuites/sptests/sprbtree01/init.c +++ b/testsuites/sptests/sprbtree01/init.c @@ -235,8 +235,8 @@ rtems_task Init( rtems_task_argument ignored ) puts( "Init - Initialize rbtree empty" ); rtems_rbtree_initialize_empty( &rbtree1 ); - rtems_rbtree_set_off_rbtree( &node1.Node ); - rtems_test_assert( rtems_rbtree_is_node_off_rbtree( &node1.Node ) ); + rtems_rbtree_set_off_tree( &node1.Node ); + rtems_test_assert( rtems_rbtree_is_node_off_tree( &node1.Node ) ); /* verify that the rbtree insert work */ puts( "INIT - Verify rtems_rbtree_insert with two nodes" ); @@ -247,7 +247,7 @@ rtems_task Init( rtems_task_argument ignored ) rb_insert_unique( &rbtree1, &node1.Node ); rb_insert_unique( &rbtree1, &node2.Node ); - rtems_test_assert( !rtems_rbtree_is_node_off_rbtree( &node1.Node ) ); + rtems_test_assert( !rtems_rbtree_is_node_off_tree( &node1.Node ) ); _RBTree_Rotate(NULL, RBT_LEFT); i = (node1.Node.parent == &node2.Node); @@ -360,7 +360,7 @@ rtems_task Init( rtems_task_argument ignored ) puts( "INIT - rtems_rbtree_extract failed"); rtems_test_exit(0); } - rtems_test_assert( !rtems_rbtree_is_node_off_rbtree( p ) ); + rtems_test_assert( !rtems_rbtree_is_node_off_tree( p ) ); rb_insert_unique(&rbtree1, p); for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ; -- cgit v1.2.3