Red-black tree API Was: Re: [PATCH 2/2] score/rbtree: replace _RBTree_Peek_unprotected with _RBTree_First.

[Gedare Bloom]

After further review I would prefer the default behavior of red-black
tree functions be unprotected unless an unprotected variant explicitly
is provided. Such behavior is a little bit arbitrary but relatively
easy to detect and understand.

This "rule" implies that the public API rtems_rbtree_peek_min/max
functions should be made unprotected unless we provide an explicit
rtems_rbtree_peek_min/max_unprotected, which I do not plan right now.
So more patches will be forthcoming.

-Gedare

On Wed, May 2, 2012 at 11:41 AM, Gedare Bloom <gedare at rtems.org> wrote:
> I guess the chain default behavior is unprotected unless the function
> modifies the chain. I would like to rework the red-black tree to be
> the same way. The primary difference is the "Find" function which
> right now defaults to protected but does not modify the red-black
> tree.
>
> If anyone has an objection to the default behavior of unprotected for
> read-only and protected otherwise please let me know. Otherwise I'll
> have a patch coming soon to make the red-black tree more consistently
> apply critical regions with respect to chains.
>
> -Gedare
>
> On Wed, May 2, 2012 at 11:32 AM, Gedare Bloom <gedare at rtems.org> wrote:
>> I noticed that RBTree_First and RBTree_Peek_unprotected implement the
>> same thing. I prefer to simplify to one of them and RBTree_First
>> seemed to be more commonly used and is "unprotected" by default.
>>
>> Right now I'm leaving RBTree_Peek in place as the protected interface.
>> The user API remains unchanged since it lacked an unprotected version
>> previously. I will follow-up with a user API wrapper for RBTree_First.
>>
>> I'm not really satisfied with the mixture of default protected vs
>> unprotected but the behavior generally follows the chains where a
>> function tends to be protected by default if it modifies or iterates a
>> chain and unprotected if it only deals with a single node. It might be
>> nice to formalize the reasoning and make sure the approach is
>> consistent between the two data structures.
>>
>> -Gedare
>>
>> On Wed, May 2, 2012 at 11:26 AM, Gedare Bloom <gedare at rtems.org> wrote:
>>> ---
>>>  cpukit/score/inline/rtems/score/rbtree.inl |   20 +-------------------
>>>  cpukit/score/src/rbtreepeek.c              |    6 ++----
>>>  2 files changed, 3 insertions(+), 23 deletions(-)
>>>
>>> diff --git a/cpukit/score/inline/rtems/score/rbtree.inl b/cpukit/score/inline/rtems/score/rbtree.inl
>>> index d646b06..a079745 100644
>>> --- a/cpukit/score/inline/rtems/score/rbtree.inl
>>> +++ b/cpukit/score/inline/rtems/score/rbtree.inl
>>> @@ -10,13 +10,11 @@
>>>  */
>>>
>>>  /*
>>> - *  Copyright (c) 2010 Gedare Bloom.
>>> + *  Copyright (c) 2010-2012 Gedare Bloom.
>>>  *
>>>  *  The license and distribution terms for this file may be
>>>  *  found in the file LICENSE in this distribution or at
>>>  *  http://www.rtems.com/license/LICENSE.
>>> - *
>>> - *  $Id$
>>>  */
>>>
>>>  #ifndef _RTEMS_SCORE_RBTREE_H
>>> @@ -459,22 +457,6 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Get_unprotected(
>>>   return the_node;
>>>  }
>>>
>>> -/** @brief Peek at the First Node (unprotected)
>>> - *
>>> - *  This function returns a pointer to the first node, minimum if @a dir is 0
>>> - *  or maximum if @a dir is 1, from @a the_rbtree without extracting it.
>>> - *  It does NOT disable interrupts to ensure the atomicity of the peek.
>>> - *
>>> - *  @retval NULL if @a the_rbtree is empty.
>>> - */
>>> -RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Peek_unprotected(
>>> -  const RBTree_Control *the_rbtree,
>>> -  RBTree_Direction dir
>>> -)
>>> -{
>>> -  return(the_rbtree->first[dir]);
>>> -}
>>> -
>>>  /** @brief Rotate the_node in the direction passed as second argument
>>>  *
>>>  *  This routine rotates @a the_node to the direction @a dir, swapping
>>> diff --git a/cpukit/score/src/rbtreepeek.c b/cpukit/score/src/rbtreepeek.c
>>> index 13ea333..81ff0fd 100644
>>> --- a/cpukit/score/src/rbtreepeek.c
>>> +++ b/cpukit/score/src/rbtreepeek.c
>>> @@ -1,11 +1,9 @@
>>>  /*
>>> - *  Copyright (c) 2010 Gedare Bloom.
>>> + *  Copyright (c) 2010-2012 Gedare Bloom.
>>>  *
>>>  *  The license and distribution terms for this file may be
>>>  *  found in the file LICENSE in this distribution or at
>>>  *  http://www.rtems.com/license/LICENSE.
>>> - *
>>> - *  $Id$
>>>  */
>>>
>>>  #if HAVE_CONFIG_H
>>> @@ -45,7 +43,7 @@ RBTree_Node *_RBTree_Peek(
>>>
>>>   return_node = NULL;
>>>   _ISR_Disable( level );
>>> -      return_node = _RBTree_Peek_unprotected( the_rbtree, dir );
>>> +      return_node = _RBTree_First( the_rbtree, dir );
>>>   _ISR_Enable( level );
>>>   return return_node;
>>>  }
>>> --
>>> 1.7.1
>>>