[PATCH 3/3] rbtree: Do not set node off-tree in extract

[Joel Sherrill]

Unless the chain has changed to have the property of
"dangerous to extract if not on", this should be OK.

My thinking is that higher level code would be checking a state
of some sort and know whether to extract from the underlying
chain or rbtree container.

Is this true?  If so, this looks OK.

On 7/21/2014 11:31 AM, Sebastian Huber wrote:
> ---
>  cpukit/score/include/rtems/score/rbtree.h | 11 +++++++++--
>  cpukit/score/src/rbtreeextract.c          |  3 ---
>  testsuites/sptests/sprbtree01/init.c      |  5 +++++
>  3 files changed, 14 insertions(+), 5 deletions(-)
>
> diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
> index aa7b86e..54383aa 100644
> --- a/cpukit/score/include/rtems/score/rbtree.h
> +++ b/cpukit/score/include/rtems/score/rbtree.h
> @@ -241,9 +241,16 @@ RBTree_Node *_RBTree_Insert(
>  );
>  
>  /**
> - *  @brief Extracts (removes) @a the_node from @a the_rbtree.
> + * @brief Extracts (removes) the node from the red-black tree.
>   *
> - *  This routine extracts (removes) @a the_node from @a the_rbtree.
> + * This function does not set the node off-tree.  In case this is desired, then
> + * call _RBTree_Set_off_rbtree() after the extraction.
> + *
> + * In case the node to extract is not a node of the tree, then this function
> + * yields unpredictable results.
> + *
> + * @param[in] the_rbtree The red-black tree control.
> + * @param[in] the_node The node to extract.
>   */
>  void _RBTree_Extract(
>    RBTree_Control *the_rbtree,
> diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c
> index 7775b2f..5a64ac4 100644
> --- a/cpukit/score/src/rbtreeextract.c
> +++ b/cpukit/score/src/rbtreeextract.c
> @@ -201,9 +201,6 @@ void _RBTree_Extract(
>      }
>    }
>  
> -  /* Wipe the_node */
> -  _RBTree_Set_off_rbtree( the_node );
> -
>    /* set root to black, if it exists */
>    if ( the_rbtree->root )
>      the_rbtree->root->color = RBT_BLACK;
> diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c
> index ca79095..2359fac 100644
> --- a/testsuites/sptests/sprbtree01/init.c
> +++ b/testsuites/sptests/sprbtree01/init.c
> @@ -140,6 +140,9 @@ rtems_task Init(
>    puts( "Init - Initialize rbtree empty" );
>    rtems_rbtree_initialize_empty( &rbtree1 );
>  
> +  rtems_rbtree_set_off_rbtree( &node1.Node );
> +  rtems_assert( rtems_rbtree_is_node_off_rbtree( &node1.Node ) );
> +
>    /* verify that the rbtree insert work */
>    puts( "INIT - Verify rtems_rbtree_insert with two nodes" );
>    node1.id = 1;
> @@ -149,6 +152,7 @@ rtems_task Init(
>    rb_insert_unique( &rbtree1, &node1.Node );
>    rb_insert_unique( &rbtree1, &node2.Node );
>  
> +  rtems_assert( !rtems_rbtree_is_node_off_rbtree( &node1.Node ) );
>  
>    _RBTree_Rotate(NULL, RBT_LEFT);
>    i = (node1.Node.parent == &node2.Node);
> @@ -261,6 +265,7 @@ rtems_task Init(
>      puts( "INIT - rtems_rbtree_extract failed");
>      rtems_test_exit(0);
>    }
> +  rtems_assert( !rtems_rbtree_is_node_off_rbtree( p ) );
>    rb_insert_unique(&rbtree1, p);
>  
>    for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;

-- 
Joel Sherrill, Ph.D.             Director of Research & Development
joel.sherrill at OARcorp.com        On-Line Applications Research
Ask me about RTEMS: a free RTOS  Huntsville AL 35805
Support Available                (256) 722-9985