[PATCH 3/4] rbtree: API Changes
Gedare Bloom
gedare at rtems.org
Wed May 2 17:19:44 UTC 2012
On Wed, May 2, 2012 at 1:14 PM, Joel Sherrill <joel.sherrill at oarcorp.com> wrote:
> On 05/02/2012 12:08 PM, Gedare Bloom wrote:
>>
>> On Wed, May 2, 2012 at 1:02 PM, Joel Sherrill<joel.sherrill at oarcorp.com>
>> wrote:
>>>
>>> Copyright should be a plain comment not a Doxygen one.
>>>
>> OK
>
> Just don't want it in generated docs all over the place.
>
>>> In _RBTree_Initialize at bottom of patch "next =" appears
>>> to be formatted strangely.
>>>
>> I'd prefer to deal with style issues separately. This formatting was
>> copied from Chain_Initialize and probably occurs there.
>
> Yep. and that code is old. It isn't particularly ugly but I
> wouldn't use initialized variables that way today. I would
> also probably declare a void * pointer to assign the
> result of _Addresses_Add_offset and put the cast on a line
> by itself.
>
> Leave it for a second round but I definitely think when you
> do enough to break onto two lines during variable
> initialization, it is impacting readability.
>
I agree. Let's formalize this into our coding conventions and we can
deal with it later. A simple rule like "Use one line per variable
declaration." should suffice. We generally avoid declaring multiple
variables on one line already so that covers two style conventions.
Alternately "Use at most one line when declaring variables."
We probably need to refresh our coding conventions and make them more
clear in general. There are a lot of unspoken rules that we follow in
the cpukit and libbsp/shared.
If it's ok with you I'd prefer to just commit this with the correction
for the copyright comment. I'm also going to wait a bit to see if
Sebastian has any comments since he has been using the red-black
trees.
>>> On 05/02/2012 11:35 AM, Gedare Bloom wrote:
>>>>
>>>> Make default for rtems_rbtree functions be unprotected (preemption
>>>> enabled)
>>>> unless an unprotected variant e.g. rtems_rbtree_xxx_unprotected is
>>>> available.
>>>> ---
>>>> cpukit/sapi/inline/rtems/rbtree.inl | 87
>>>> ++++++++++++++++++++++++++++++----
>>>> cpukit/score/src/rbtree.c | 2 +-
>>>> 2 files changed, 77 insertions(+), 12 deletions(-)
>>>>
>>>> diff --git a/cpukit/sapi/inline/rtems/rbtree.inl
>>>> b/cpukit/sapi/inline/rtems/rbtree.inl
>>>> index ab81baf..0d507fb 100644
>>>> --- a/cpukit/sapi/inline/rtems/rbtree.inl
>>>> +++ b/cpukit/sapi/inline/rtems/rbtree.inl
>>>> @@ -5,17 +5,14 @@
>>>> * with the RBTree API in RTEMS. The rbtree is a Red Black Tree that
>>>> * is part of the Super Core. This is the published interface to that
>>>> * code.
>>>> - *
>>>> */
>>>>
>>>> -/*
>>>> - * 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_RBTREE_H
>>>> @@ -254,6 +251,17 @@ RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root(
>>>> return _RBTree_Is_root( the_rbtree, the_node );
>>>> }
>>>>
>>>> +/**
>>>> + * @copydoc _RBTree_Find_unprotected()
>>>> + */
>>>> +RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find_unprotected(
>>>> + rtems_rbtree_control *the_rbtree,
>>>> + rtems_rbtree_node *the_node
>>>> +)
>>>> +{
>>>> + return _RBTree_Find_unprotected( the_rbtree, the_node );
>>>> +}
>>>> +
>>>> /** @brief Find the node with given key in the tree
>>>> *
>>>> * This function returns a pointer to the node having key equal to the
>>>> key
>>>> @@ -316,6 +324,17 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node*
>>>> rtems_rbtree_successor(
>>>> }
>>>>
>>>> /**
>>>> + * @copydoc _RBTree_Extract_unprotected()
>>>> + */
>>>> +RTEMS_INLINE_ROUTINE void rtems_rbtree_extract_unprotected(
>>>> + rtems_rbtree_control *the_rbtree,
>>>> + rtems_rbtree_node *the_node
>>>> +)
>>>> +{
>>>> + _RBTree_Extract_unprotected( the_rbtree, the_node );
>>>> +}
>>>> +
>>>> +/**
>>>> * @brief Extract the specified node from a rbtree
>>>> *
>>>> * This routine extracts @a the_node from @a the_rbtree on which it
>>>> resides.
>>>> @@ -334,6 +353,20 @@ RTEMS_INLINE_ROUTINE void rtems_rbtree_extract(
>>>> *
>>>> * This function removes the min node from @a the_rbtree and returns
>>>> * a pointer to that node. If @a the_rbtree is empty, then NULL is
>>>> returned.
>>>> + */
>>>> +
>>>> +RTEMS_INLINE_ROUTINE rtems_rbtree_node
>>>> *rtems_rbtree_get_min_unprotected(
>>>> + rtems_rbtree_control *the_rbtree
>>>> +)
>>>> +{
>>>> + return _RBTree_Get_unprotected( the_rbtree, RBT_LEFT );
>>>> +}
>>>> +
>>>> +/**
>>>> + * @brief Obtain the min node on a rbtree
>>>> + *
>>>> + * This function removes the min node from @a the_rbtree and returns
>>>> + * a pointer to that node. If @a the_rbtree is empty, then NULL is
>>>> returned.
>>>> * It disables interrupts to ensure the atomicity of the get
>>>> operation.
>>>> */
>>>> RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_min(
>>>> @@ -348,6 +381,20 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node
>>>> *rtems_rbtree_get_min(
>>>> *
>>>> * This function removes the max node from @a the_rbtree and returns
>>>> * a pointer to that node. If @a the_rbtree is empty, then NULL is
>>>> returned.
>>>> + */
>>>> +
>>>> +RTEMS_INLINE_ROUTINE rtems_rbtree_node
>>>> *rtems_rbtree_get_max_unprotected(
>>>> + rtems_rbtree_control *the_rbtree
>>>> +)
>>>> +{
>>>> + return _RBTree_Get_unprotected( the_rbtree, RBT_RIGHT );
>>>> +}
>>>> +
>>>> +/**
>>>> + * @brief Obtain the max node on a rbtree
>>>> + *
>>>> + * This function removes the max node from @a the_rbtree and returns
>>>> + * a pointer to that node. If @a the_rbtree is empty, then NULL is
>>>> returned.
>>>> * It disables interrupts to ensure the atomicity of the get
>>>> operation.
>>>> */
>>>> RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_max(
>>>> @@ -363,13 +410,12 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node
>>>> *rtems_rbtree_get_max(
>>>> * This function returns a pointer to the min node from @a the_rbtree
>>>> * without changing the tree. If @a the_rbtree is empty,
>>>> * then NULL is returned.
>>>> - * It disables interrupts to ensure the atomicity of the peek
>>>> operation.
>>>> */
>>>> RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_min(
>>>> const rtems_rbtree_control *the_rbtree
>>>> )
>>>> {
>>>> - return _RBTree_Peek( the_rbtree, RBT_LEFT );
>>>> + return _RBTree_First( the_rbtree, RBT_LEFT );
>>>> }
>>>>
>>>> /**
>>>> @@ -378,15 +424,23 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node
>>>> *rtems_rbtree_peek_min(
>>>> * This function returns a pointer to the max node from @a the_rbtree
>>>> * without changing the tree. If @a the_rbtree is empty,
>>>> * then NULL is returned.
>>>> - * It disables interrupts to ensure the atomicity of the peek
>>>> operation.
>>>> */
>>>> RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_max(
>>>> const rtems_rbtree_control *the_rbtree
>>>> )
>>>> {
>>>> - return _RBTree_Peek( the_rbtree, RBT_RIGHT );
>>>> + return _RBTree_First( the_rbtree, RBT_RIGHT );
>>>> }
>>>>
>>>> +/**
>>>> + * @copydoc _RBTree_Find_header_unprotected()
>>>> + */
>>>> +RTEMS_INLINE_ROUTINE rtems_rbtree_control
>>>> *rtems_rbtree_find_header_unprotected(
>>>> + rtems_rbtree_node *the_node
>>>> +)
>>>> +{
>>>> + return _RBTree_Find_header_unprotected( the_node );
>>>> +}
>>>>
>>>> /**
>>>> * @brief Find the control header of the tree containing a given node.
>>>> @@ -399,7 +453,18 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_control
>>>> *rtems_rbtree_find_header(
>>>> rtems_rbtree_node *the_node
>>>> )
>>>> {
>>>> - return(_RBTree_Find_header( the_node ));
>>>> + return _RBTree_Find_header( the_node );
>>>> +}
>>>> +
>>>> +/**
>>>> + * @copydoc _RBTree_Insert_unprotected()
>>>> + */
>>>> +RTEMS_INLINE_ROUTINE rtems_rbtree_node
>>>> *rtems_rbtree_insert_unprotected(
>>>> + rtems_rbtree_control *the_rbtree,
>>>> + rtems_rbtree_node *the_node
>>>> +)
>>>> +{
>>>> + return _RBTree_Insert_unprotected( the_rbtree, the_node );
>>>> }
>>>>
>>>> /**
>>>> @@ -427,7 +492,7 @@ RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_unique(
>>>> const rtems_rbtree_control *the_rbtree
>>>> )
>>>> {
>>>> - return( _RBTree_Is_unique(the_rbtree) );
>>>> + return _RBTree_Is_unique(the_rbtree);
>>>> }
>>>>
>>>> #endif
>>>> diff --git a/cpukit/score/src/rbtree.c b/cpukit/score/src/rbtree.c
>>>> index e0fc560..387e66b 100644
>>>> --- a/cpukit/score/src/rbtree.c
>>>> +++ b/cpukit/score/src/rbtree.c
>>>> @@ -52,7 +52,7 @@ void _RBTree_Initialize(
>>>> count = number_nodes;
>>>> next = starting_address;
>>>> while ( count-- ) {
>>>> - _RBTree_Insert(the_rbtree, next);
>>>> + _RBTree_Insert_unprotected(the_rbtree, next);
>>>> next = (RBTree_Node *)
>>>> _Addresses_Add_offset( (void *) next, node_size
>>>> );
>>>> }
>>>
>>>
>>>
>>> --
>>> 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
>>>
>>>
>
>
> --
> 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
>
>
More information about the devel
mailing list