[PATCH 3/4] rbtree: API Changes
Gedare Bloom
gedare at rtems.org
Wed May 2 17:08:53 UTC 2012
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
> 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.
>
> 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
>
>
More information about the devel
mailing list