[PATCH 2/2] rbtree: Reduce RBTree_Control size

Gedare Bloom gedare at rtems.org
Sun Jul 13 17:43:43 UTC 2014


These 2 patches looked fine at a glance through.

On Sat, Jul 12, 2014 at 3:22 PM, Sebastian Huber
<sebastian.huber at embedded-brains.de> wrote:
> Remove compare function and is unique indicator from the control
> structure.  Rename RBTree_Compare_function to RBTree_Compare.  Rename
> rtems_rbtree_compare_function to rtems_rbtree_compare.  Provide C++
> compatible initializers.  Add compare function and is unique indicator
> to _RBTree_Find(), _RBTree_Insert(), rtems_rbtree_find() and
> rtems_rbtree_insert().  Remove _RBTree_Is_unique() and
> rtems_rbtree_is_unique().  Remove compare function and is unique
> indicator from _RBTree_Initialize_empty() and
> rtems_rbtree_initialize_empty().
> ---
>  cpukit/posix/include/rtems/posix/keyimpl.h         |  21 +++-
>  cpukit/posix/src/key.c                             |  10 +-
>  cpukit/posix/src/keyfreememory.c                   |   4 +-
>  cpukit/posix/src/keygetspecific.c                  |  13 +--
>  cpukit/posix/src/keysetspecific.c                  |  16 +--
>  cpukit/sapi/include/rtems/rbtree.h                 |  46 ++++-----
>  cpukit/sapi/src/rbheap.c                           |   8 +-
>  cpukit/score/include/rtems/score/rbtree.h          | 111 ++++++++++-----------
>  .../score/include/rtems/score/scheduleredfimpl.h   |  12 ++-
>  cpukit/score/src/rbtree.c                          |  19 ++--
>  cpukit/score/src/rbtreefind.c                      |  22 ++--
>  cpukit/score/src/rbtreeinsert.c                    |  32 ++----
>  cpukit/score/src/scheduleredf.c                    |   9 +-
>  cpukit/score/src/scheduleredfchangepriority.c      |   7 +-
>  cpukit/score/src/scheduleredfyield.c               |   7 +-
>  testsuites/sptests/sprbtree01/init.c               | 102 +++++++++++--------
>  16 files changed, 226 insertions(+), 213 deletions(-)
>
> diff --git a/cpukit/posix/include/rtems/posix/keyimpl.h b/cpukit/posix/include/rtems/posix/keyimpl.h
> index 6aab244..b21c1d3 100644
> --- a/cpukit/posix/include/rtems/posix/keyimpl.h
> +++ b/cpukit/posix/include/rtems/posix/keyimpl.h
> @@ -42,7 +42,7 @@ POSIX_EXTERN Objects_Information  _POSIX_Keys_Information;
>  /**
>   * @brief The rbtree control block used to manage all key values
>   */
> -POSIX_EXTERN RBTree_Control _POSIX_Keys_Key_value_lookup_tree;
> +extern RBTree_Control _POSIX_Keys_Key_value_lookup_tree;
>
>  /**
>   * @brief This freechain is used as a memory pool for POSIX_Keys_Key_value_pair.
> @@ -61,7 +61,7 @@ void _POSIX_Key_Manager_initialization(void);
>   *
>   * This routine compares the rbtree node
>   */
> -int _POSIX_Keys_Key_value_lookup_tree_compare_function(
> +int _POSIX_Keys_Key_value_compare(
>    const RBTree_Node *node1,
>    const RBTree_Node *node2
>  );
> @@ -165,6 +165,23 @@ RTEMS_INLINE_ROUTINE void _POSIX_Keys_Key_value_pair_free(
>    _Freechain_Put( &_POSIX_Keys_Keypool, key_value_pair );
>  }
>
> +RTEMS_INLINE_ROUTINE RBTree_Node *_POSIX_Keys_Find(
> +  pthread_key_t              key,
> +  Objects_Id                 thread_id,
> +  POSIX_Keys_Key_value_pair *search_node
> +)
> +{
> +  search_node->key = key;
> +  search_node->thread_id = thread_id;
> +
> +  return _RBTree_Find(
> +    &_POSIX_Keys_Key_value_lookup_tree,
> +    &search_node->Key_value_lookup_node,
> +    _POSIX_Keys_Key_value_compare,
> +    true
> +  );
> +}
> +
>  /** @} */
>
>  #ifdef __cplusplus
> diff --git a/cpukit/posix/src/key.c b/cpukit/posix/src/key.c
> index de61b43..105706a 100644
> --- a/cpukit/posix/src/key.c
> +++ b/cpukit/posix/src/key.c
> @@ -26,6 +26,8 @@
>  #include <rtems/score/objectimpl.h>
>  #include <rtems/score/wkspace.h>
>
> +RBTREE_DEFINE_EMPTY( _POSIX_Keys_Key_value_lookup_tree );
> +
>  /**
>   * @brief This routine compares the rbtree node by comparing POSIX key first
>   * and comparing thread id second.
> @@ -42,7 +44,7 @@
>   * impossible
>   */
>
> -int _POSIX_Keys_Key_value_lookup_tree_compare_function(
> +int _POSIX_Keys_Key_value_compare(
>    const RBTree_Node *node1,
>    const RBTree_Node *node2
>  )
> @@ -153,11 +155,5 @@ void _POSIX_Key_Manager_initialization(void)
>  #endif
>    );
>
> -  _RBTree_Initialize_empty(
> -      &_POSIX_Keys_Key_value_lookup_tree,
> -      _POSIX_Keys_Key_value_lookup_tree_compare_function,
> -      true
> -  );
> -
>    _POSIX_Keys_Initialize_keypool();
>  }
> diff --git a/cpukit/posix/src/keyfreememory.c b/cpukit/posix/src/keyfreememory.c
> index 04c914f..b419f1f 100644
> --- a/cpukit/posix/src/keyfreememory.c
> +++ b/cpukit/posix/src/keyfreememory.c
> @@ -32,9 +32,7 @@ void _POSIX_Keys_Free_memory(
>    Objects_Id key_id;
>
>    key_id = the_key->Object.id;
> -  search_node.key = key_id;
> -  search_node.thread_id = 0;
> -  iter = _RBTree_Find( &_POSIX_Keys_Key_value_lookup_tree, &search_node.Key_value_lookup_node );
> +  iter = _POSIX_Keys_Find( key_id, 0, &search_node );
>    if ( !iter )
>      return;
>    /**
> diff --git a/cpukit/posix/src/keygetspecific.c b/cpukit/posix/src/keygetspecific.c
> index eeab2e3..9c54112 100644
> --- a/cpukit/posix/src/keygetspecific.c
> +++ b/cpukit/posix/src/keygetspecific.c
> @@ -49,19 +49,14 @@ void *pthread_getspecific(
>    switch ( location ) {
>
>      case OBJECTS_LOCAL:
> -      search_node.key = key;
> -      search_node.thread_id = _Thread_Executing->Object.id;
> -      p = _RBTree_Find( &_POSIX_Keys_Key_value_lookup_tree,
> -                                    &search_node.Key_value_lookup_node );
> -      key_data = NULL;
> -      if ( p ) {
> +      p = _POSIX_Keys_Find( key, _Thread_Executing->Object.id, &search_node );
> +      if ( p != NULL ) {
>          value_pair_p = _RBTree_Container_of( p,
>                                            POSIX_Keys_Key_value_pair,
>                                            Key_value_lookup_node );
> -        /* key_data = _RBTree_Container_of( p, */
> -        /*                                  POSIX_Keys_Key_value_pair, */
> -        /*                                  Key_value_lookup_node )->value; */
>          key_data = value_pair_p->value;
> +      } else {
> +        key_data = NULL;
>        }
>
>        _Objects_Put( &the_key->Object );
> diff --git a/cpukit/posix/src/keysetspecific.c b/cpukit/posix/src/keysetspecific.c
> index 3284991..0f7c682 100644
> --- a/cpukit/posix/src/keysetspecific.c
> +++ b/cpukit/posix/src/keysetspecific.c
> @@ -44,12 +44,8 @@ int pthread_setspecific(
>    switch ( location ) {
>
>      case OBJECTS_LOCAL:
> -      search_node.key = key;
> -      search_node.thread_id = _Thread_Executing->Object.id;
> -      p = _RBTree_Find( &_POSIX_Keys_Key_value_lookup_tree,
> -                                    &search_node.Key_value_lookup_node );
> -
> -      if ( p ) {
> +      p = _POSIX_Keys_Find( key, _Thread_Executing->Object.id, &search_node );
> +      if ( p != NULL ) {
>          value_pair_ptr = _RBTree_Container_of( p,
>                                            POSIX_Keys_Key_value_pair,
>                                            Key_value_lookup_node );
> @@ -69,8 +65,12 @@ int pthread_setspecific(
>          value_pair_ptr->value = value;
>          /* The insert can only go wrong if the same node is already in a unique
>           * tree. This has been already checked with the _RBTree_Find() */
> -        (void) _RBTree_Insert( &_POSIX_Keys_Key_value_lookup_tree,
> -                             &(value_pair_ptr->Key_value_lookup_node) );
> +        _RBTree_Insert(
> +          &_POSIX_Keys_Key_value_lookup_tree,
> +          &value_pair_ptr->Key_value_lookup_node,
> +          _POSIX_Keys_Key_value_compare,
> +          true
> +        );
>
>          /** append rb_node to the thread API extension's chain */
>          _Chain_Append_unprotected(
> diff --git a/cpukit/sapi/include/rtems/rbtree.h b/cpukit/sapi/include/rtems/rbtree.h
> index 7e59e03..2005b36 100644
> --- a/cpukit/sapi/include/rtems/rbtree.h
> +++ b/cpukit/sapi/include/rtems/rbtree.h
> @@ -55,13 +55,11 @@ typedef RBTree_Node rtems_rbtree_node;
>  typedef RBTree_Control rtems_rbtree_control;
>
>  /**
> - * @typedef rtems_rbtree_compare_function
> - *
>   * This type defines function pointers for user-provided comparison
>   * function. The function compares two nodes in order to determine
>   * the order in a red-black tree.
>   */
> -typedef RBTree_Compare_function rtems_rbtree_compare_function;
> +typedef RBTree_Compare rtems_rbtree_compare;
>
>  /**
>   * @brief RBTree initializer for an empty rbtree with designator @a name.
> @@ -93,15 +91,15 @@ typedef RBTree_Compare_function rtems_rbtree_compare_function;
>   * @a starting_address.  Each node is of @a node_size bytes.
>   */
>  RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize(
> -  rtems_rbtree_control          *the_rbtree,
> -  rtems_rbtree_compare_function  compare_function,
> -  void                          *starting_address,
> -  size_t                         number_nodes,
> -  size_t                         node_size,
> -  bool                           is_unique
> +  rtems_rbtree_control *the_rbtree,
> +  rtems_rbtree_compare  compare,
> +  void                 *starting_address,
> +  size_t                number_nodes,
> +  size_t                node_size,
> +  bool                  is_unique
>  )
>  {
> -  _RBTree_Initialize( the_rbtree, compare_function, starting_address,
> +  _RBTree_Initialize( the_rbtree, compare, starting_address,
>      number_nodes, node_size, is_unique);
>  }
>
> @@ -111,12 +109,10 @@ RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize(
>   * This routine initializes @a the_rbtree to contain zero nodes.
>   */
>  RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize_empty(
> -  rtems_rbtree_control          *the_rbtree,
> -  rtems_rbtree_compare_function  compare_function,
> -  bool                           is_unique
> +  rtems_rbtree_control *the_rbtree
>  )
>  {
> -  _RBTree_Initialize_empty( the_rbtree, compare_function, is_unique );
> +  _RBTree_Initialize_empty( the_rbtree );
>  }
>
>  /**
> @@ -277,10 +273,12 @@ RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root(
>   */
>  RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find(
>    const rtems_rbtree_control *the_rbtree,
> -  const rtems_rbtree_node *the_node
> +  const rtems_rbtree_node    *the_node,
> +  rtems_rbtree_compare        compare,
> +  bool                        is_unique
>  )
>  {
> -  return _RBTree_Find( the_rbtree, the_node );
> +  return _RBTree_Find( the_rbtree, the_node, compare, is_unique );
>  }
>
>  /**
> @@ -385,20 +383,12 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_control *rtems_rbtree_find_header(
>   */
>  RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert(
>    rtems_rbtree_control *the_rbtree,
> -  rtems_rbtree_node *the_node
> -)
> -{
> -  return _RBTree_Insert( the_rbtree, the_node );
> -}
> -
> -/**
> - * @brief Determines whether the tree is unique.
> - */
> -RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_unique(
> -  const rtems_rbtree_control *the_rbtree
> +  rtems_rbtree_node    *the_node,
> +  rtems_rbtree_compare  compare,
> +  bool                  is_unique
>  )
>  {
> -  return _RBTree_Is_unique(the_rbtree);
> +  return _RBTree_Insert( the_rbtree, the_node, compare, is_unique );
>  }
>
>  /** @} */
> diff --git a/cpukit/sapi/src/rbheap.c b/cpukit/sapi/src/rbheap.c
> index febd65f..20338eb 100644
> --- a/cpukit/sapi/src/rbheap.c
> +++ b/cpukit/sapi/src/rbheap.c
> @@ -80,7 +80,7 @@ static void insert_into_tree(
>    rtems_rbheap_chunk *chunk
>  )
>  {
> -  _RBTree_Insert(tree, &chunk->tree_node);
> +  rtems_rbtree_insert(tree, &chunk->tree_node, chunk_compare, true);
>  }
>
>  rtems_status_code rtems_rbheap_initialize(
> @@ -107,7 +107,7 @@ rtems_status_code rtems_rbheap_initialize(
>
>        rtems_chain_initialize_empty(free_chain);
>        rtems_chain_initialize_empty(&control->spare_descriptor_chain);
> -      rtems_rbtree_initialize_empty(chunk_tree, chunk_compare, true);
> +      rtems_rbtree_initialize_empty(chunk_tree);
>        control->alignment = alignment;
>        control->handler_arg = handler_arg;
>        control->extend_descriptors = extend_descriptors;
> @@ -198,7 +198,7 @@ static rtems_rbheap_chunk *find(rtems_rbtree_control *chunk_tree, uintptr_t key)
>    rtems_rbheap_chunk chunk = { .begin = key };
>
>    return rtems_rbheap_chunk_of_node(
> -    _RBTree_Find(chunk_tree, &chunk.tree_node)
> +    rtems_rbtree_find(chunk_tree, &chunk.tree_node, chunk_compare, true)
>    );
>  }
>
> @@ -230,7 +230,7 @@ static void check_and_merge(
>      a->size += b->size;
>      rtems_chain_extract_unprotected(&b->chain_node);
>      add_to_chain(free_chain, b);
> -    _RBTree_Extract(chunk_tree, &b->tree_node);
> +    rtems_rbtree_extract(chunk_tree, &b->tree_node);
>    }
>  }
>
> diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
> index 5a296b6..a219a6e 100644
> --- a/cpukit/score/include/rtems/score/rbtree.h
> +++ b/cpukit/score/include/rtems/score/rbtree.h
> @@ -104,13 +104,21 @@ typedef enum {
>  } RBTree_Direction;
>
>  /**
> - * This type defines function pointers for user-provided comparison
> - * function. The function compares two nodes in order to determine
> - * the order in a red-black tree.
> + * @brief Compares two red-black tree nodes.
> + *
> + * @param[in] first The first node.
> + * @param[in] second The second node.
> + *
> + * @retval positive The key value of the first node is greater than the one of
> + *   the second node.
> + * @retval 0 The key value of the first node is equal to the one of the second
> + *   node.
> + * @retval negative The key value of the first node is less than the one of the
> + *   second node.
>   */
> -typedef int (*RBTree_Compare_function)(
> -  const RBTree_Node *node1,
> -  const RBTree_Node *node2
> +typedef int ( *RBTree_Compare )(
> +  const RBTree_Node *first,
> +  const RBTree_Node *second
>  );
>
>  /**
> @@ -139,51 +147,31 @@ typedef struct {
>    RBTree_Node *root;
>    /** This points to the min and max nodes of this RBT. */
>    RBTree_Node *first[2];
> -  /**
> -   * Comparison function pointer. Keys to compare have to be found
> -   * inside to maintain generality. It has to return 1 if first node
> -   * has higher key than second, -1 if lower, 0 if equal.
> -   */
> -  RBTree_Compare_function compare_function;
> -  /** Determines whether the tree accepts duplicate keys. */
> -  bool is_unique;
>  } RBTree_Control;
>
>  /**
>   *  @brief RBTree initializer for an empty rbtree with designator @a name.
>   */
> -#define RBTREE_INITIALIZER_EMPTY(name) \
> -{ \
> -  .permanent_null = NULL, \
> -  .root = NULL, \
> -  .first[0] = NULL, \
> -  .first[1] = NULL, \
> -  .compare_function = NULL, \
> -  .is_unique = 0 \
> -}
> +#define RBTREE_INITIALIZER_EMPTY( name ) \
> +  { NULL, NULL, { NULL, NULL } }
>
>  /**
>   *  @brief RBTree definition for an empty rbtree with designator @a name.
>   */
> -#define RBTREE_DEFINE_EMPTY(name) \
> -RBTree_Control name = RBTREE_INITIALIZER_EMPTY(name)
> +#define RBTREE_DEFINE_EMPTY( name ) \
> +  RBTree_Control name = RBTREE_INITIALIZER_EMPTY( name )
>
>  /**
>   *  @brief RBTree_Node initializer for an empty node with designator @a name.
>   */
> -#define RBTREE_NODE_INITIALIZER_EMPTY(name) \
> -{ \
> -  .parent = NULL, \
> -  .child[0] = NULL, \
> -  .child[1] = NULL, \
> -  RBT_RED \
> -}
> +#define RBTREE_NODE_INITIALIZER_EMPTY( name ) \
> +  { NULL, { NULL, NULL }, RBT_RED }
>
>  /**
>   *  @brief RBTree definition for an empty rbtree with designator @a name.
>   */
> -#define RBTREE_NODE_DEFINE_EMPTY(name) \
> -RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY(name)
> +#define RBTREE_NODE_DEFINE_EMPTY( name ) \
> +  RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY( name )
>
>  /**
>   *  @brief Initialize a RBTree Header.
> @@ -193,17 +181,20 @@ RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY(name)
>   *  @a starting_address.  Each node is of @a node_size bytes.
>   *
>   *  @param[in] the_rbtree is the pointer to rbtree header
> + *  @param[in] compare The node compare function.
>   *  @param[in] starting_address is the starting address of first node
>   *  @param[in] number_nodes is the number of nodes in rbtree
>   *  @param[in] node_size is the size of node in bytes
> + *  @param[in] is_unique If true, then reject nodes with a duplicate key, else
> + *    otherwise.
>   */
>  void _RBTree_Initialize(
> -  RBTree_Control          *the_rbtree,
> -  RBTree_Compare_function  compare_function,
> -  void                    *starting_address,
> -  size_t                   number_nodes,
> -  size_t                   node_size,
> -  bool                     is_unique
> +  RBTree_Control *the_rbtree,
> +  RBTree_Compare  compare,
> +  void           *starting_address,
> +  size_t          number_nodes,
> +  size_t          node_size,
> +  bool            is_unique
>  );
>
>  /**
> @@ -211,6 +202,10 @@ void _RBTree_Initialize(
>   *
>   * @param[in] the_rbtree The red-black tree control.
>   * @param[in] the_node A node specifying the key.
> + * @param[in] compare The node compare function.
> + * @param[in] is_unique If true, then return the first node with a key equal to
> + *   the one of the node specified if it exits, else return the last node if it
> + *   exists.
>   *
>   * @retval node A node corresponding to the key.  If the tree is not unique
>   * and contains duplicate keys, the set of duplicate keys acts as FIFO.
> @@ -218,7 +213,9 @@ void _RBTree_Initialize(
>   */
>  RBTree_Node *_RBTree_Find(
>    const RBTree_Control *the_rbtree,
> -  const RBTree_Node *the_node
> +  const RBTree_Node    *the_node,
> +  RBTree_Compare        compare,
> +  bool                  is_unique
>  );
>
>  /**
> @@ -226,6 +223,12 @@ RBTree_Node *_RBTree_Find(
>   *
>   *  This routine inserts @a the_node on the Red-Black Tree @a the_rbtree.
>   *
> + * @param[in] the_rbtree The red-black tree control.
> + * @param[in] the_node The node to insert.
> + * @param[in] compare The node compare function.
> + * @param[in] is_unique If true, then reject nodes with a duplicate key, else
> + *   otherwise.
> + *
>   *  @retval 0 Successfully inserted.
>   *  @retval -1 NULL @a the_node.
>   *  @retval RBTree_Node* if one with equal value to @a the_node 's key exists
> @@ -233,7 +236,9 @@ RBTree_Node *_RBTree_Find(
>   */
>  RBTree_Node *_RBTree_Insert(
>    RBTree_Control *the_rbtree,
> -  RBTree_Node *the_node
> +  RBTree_Node    *the_node,
> +  RBTree_Compare  compare,
> +  bool            is_unique
>  );
>
>  /**
> @@ -437,17 +442,13 @@ RTEMS_INLINE_ROUTINE RBTree_Control *_RBTree_Find_header(
>   * This routine initializes @a the_rbtree to contain zero nodes.
>   */
>  RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
> -    RBTree_Control          *the_rbtree,
> -    RBTree_Compare_function  compare_function,
> -    bool                     is_unique
> -    )
> +  RBTree_Control *the_rbtree
> +)
>  {
>    the_rbtree->permanent_null   = NULL;
>    the_rbtree->root             = NULL;
> -  the_rbtree->first[0]         = NULL;
> -  the_rbtree->first[1]         = NULL;
> -  the_rbtree->compare_function = compare_function;
> -  the_rbtree->is_unique        = is_unique;
> +  the_rbtree->first[RBT_LEFT]  = NULL;
> +  the_rbtree->first[RBT_RIGHT] = NULL;
>  }
>
>  /**
> @@ -502,16 +503,6 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Get(
>    return the_node;
>  }
>
> -/**
> - * @brief Determines whether the tree is unique.
> - */
> -RTEMS_INLINE_ROUTINE bool _RBTree_Is_unique(
> -  const RBTree_Control *the_rbtree
> -)
> -{
> -  return( the_rbtree && the_rbtree->is_unique );
> -}
> -
>  /**@}*/
>
>  #ifdef __cplusplus
> diff --git a/cpukit/score/include/rtems/score/scheduleredfimpl.h b/cpukit/score/include/rtems/score/scheduleredfimpl.h
> index aab338e..019c544 100644
> --- a/cpukit/score/include/rtems/score/scheduleredfimpl.h
> +++ b/cpukit/score/include/rtems/score/scheduleredfimpl.h
> @@ -44,6 +44,11 @@ RTEMS_INLINE_ROUTINE Scheduler_EDF_Node *_Scheduler_EDF_Thread_get_node(
>    return (Scheduler_EDF_Node *) _Scheduler_Thread_get_node( the_thread );
>  }
>
> +int _Scheduler_EDF_Compare(
> +  const RBTree_Node* n1,
> +  const RBTree_Node* n2
> +);
> +
>  RTEMS_INLINE_ROUTINE void _Scheduler_EDF_Enqueue(
>    const Scheduler_Control *scheduler,
>    Thread_Control          *the_thread
> @@ -53,7 +58,12 @@ RTEMS_INLINE_ROUTINE void _Scheduler_EDF_Enqueue(
>      _Scheduler_EDF_Get_context( scheduler );
>    Scheduler_EDF_Node *node = _Scheduler_EDF_Thread_get_node( the_thread );
>
> -  _RBTree_Insert( &context->Ready, &node->Node );
> +  _RBTree_Insert(
> +    &context->Ready,
> +    &node->Node,
> +    _Scheduler_EDF_Compare,
> +    false
> +  );
>    node->queue_state = SCHEDULER_EDF_QUEUE_STATE_YES;
>  }
>
> diff --git a/cpukit/score/src/rbtree.c b/cpukit/score/src/rbtree.c
> index 958aed0..5e8520d 100644
> --- a/cpukit/score/src/rbtree.c
> +++ b/cpukit/score/src/rbtree.c
> @@ -23,12 +23,12 @@
>  #include <rtems/score/isr.h>
>
>  void _RBTree_Initialize(
> -  RBTree_Control          *the_rbtree,
> -  RBTree_Compare_function  compare_function,
> -  void                    *starting_address,
> -  size_t                   number_nodes,
> -  size_t                   node_size,
> -  bool                     is_unique
> +  RBTree_Control *the_rbtree,
> +  RBTree_Compare  compare,
> +  void           *starting_address,
> +  size_t          number_nodes,
> +  size_t          node_size,
> +  bool            is_unique
>  )
>  {
>    size_t      count;
> @@ -38,13 +38,12 @@ void _RBTree_Initialize(
>    if (!the_rbtree) return;
>
>    /* could do sanity checks here */
> -  _RBTree_Initialize_empty(the_rbtree, compare_function, is_unique);
> +  _RBTree_Initialize_empty( the_rbtree );
>
>    count = number_nodes;
>    next  = starting_address;
>    while ( count-- ) {
> -    _RBTree_Insert(the_rbtree, next);
> -    next           = (RBTree_Node *)
> -                        _Addresses_Add_offset( (void *) next, node_size );
> +    _RBTree_Insert( the_rbtree, next, compare, is_unique );
> +    next = (RBTree_Node *) _Addresses_Add_offset( next, node_size );
>    }
>  }
> diff --git a/cpukit/score/src/rbtreefind.c b/cpukit/score/src/rbtreefind.c
> index 4aaf236..ad0c9fd 100644
> --- a/cpukit/score/src/rbtreefind.c
> +++ b/cpukit/score/src/rbtreefind.c
> @@ -18,28 +18,30 @@
>  #endif
>
>  #include <rtems/score/rbtreeimpl.h>
> -#include <rtems/score/isr.h>
>
>  RBTree_Node *_RBTree_Find(
>    const RBTree_Control *the_rbtree,
> -  const RBTree_Node *the_node
> +  const RBTree_Node    *the_node,
> +  RBTree_Compare        compare,
> +  bool                  is_unique
>  )
>  {
>    RBTree_Node* iter_node = the_rbtree->root;
>    RBTree_Node* found = NULL;
> -  int compare_result;
> -  while (iter_node) {
> -    compare_result = the_rbtree->compare_function(the_node, iter_node);
> +
> +  while ( iter_node != NULL ) {
> +    int compare_result = ( *compare )( the_node, iter_node );
> +    RBTree_Direction dir;
> +
>      if ( _RBTree_Is_equal( compare_result ) ) {
>        found = iter_node;
> -      if ( the_rbtree->is_unique )
> +      if ( is_unique )
>          break;
>      }
>
> -    RBTree_Direction dir =
> -      (RBTree_Direction) _RBTree_Is_greater( compare_result );
> -    iter_node = iter_node->child[dir];
> -  } /* while(iter_node) */
> +    dir = (RBTree_Direction) _RBTree_Is_greater( compare_result );
> +    iter_node = iter_node->child[ dir ];
> +  }
>
>    return found;
>  }
> diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c
> index 39f7c2b..7174529 100644
> --- a/cpukit/score/src/rbtreeinsert.c
> +++ b/cpukit/score/src/rbtreeinsert.c
> @@ -59,24 +59,12 @@ static void _RBTree_Validate_insert(
>    if(!the_node->parent->parent) the_node->color = RBT_BLACK;
>  }
>
> -
> -
> -/** @brief Insert a Node (unprotected)
> - *
> - *  This routine inserts @a the_node on the Red-Black Tree @a the_rbtree.
> - *
> - *  @retval 0 Successfully inserted.
> - *  @retval -1 NULL @a the_node.
> - *  @retval RBTree_Node* if one with equal key to the key of @a the_node exists
> - *          in an unique @a the_rbtree.
> - *
> - *  @note It does NOT disable interrupts to ensure the atomicity
> - *        of the extract operation.
> - */
>  RBTree_Node *_RBTree_Insert(
> -    RBTree_Control *the_rbtree,
> -    RBTree_Node *the_node
> -    )
> +  RBTree_Control *the_rbtree,
> +  RBTree_Node    *the_node,
> +  RBTree_Compare  compare,
> +  bool            is_unique
> +)
>  {
>    if(!the_node) return (RBTree_Node*)-1;
>
> @@ -92,8 +80,8 @@ RBTree_Node *_RBTree_Insert(
>    } else {
>      /* typical binary search tree insert, descend tree to leaf and insert */
>      while (iter_node) {
> -      compare_result = the_rbtree->compare_function(the_node, iter_node);
> -      if ( the_rbtree->is_unique && _RBTree_Is_equal( compare_result ) )
> +      compare_result = ( *compare )( the_node, iter_node );
> +      if ( is_unique && _RBTree_Is_equal( compare_result ) )
>          return iter_node;
>        RBTree_Direction dir = !_RBTree_Is_lesser( compare_result );
>        if (!iter_node->child[dir]) {
> @@ -102,9 +90,9 @@ RBTree_Node *_RBTree_Insert(
>          iter_node->child[dir] = the_node;
>          the_node->parent = iter_node;
>          /* update min/max */
> -        compare_result = the_rbtree->compare_function(
> -            the_node,
> -            _RBTree_First(the_rbtree, dir)
> +        compare_result = ( *compare )(
> +          the_node,
> +          _RBTree_First( the_rbtree, dir )
>          );
>          if ( (!dir && _RBTree_Is_lesser(compare_result)) ||
>                (dir && _RBTree_Is_greater(compare_result)) ) {
> diff --git a/cpukit/score/src/scheduleredf.c b/cpukit/score/src/scheduleredf.c
> index 010d053..01b5244 100644
> --- a/cpukit/score/src/scheduleredf.c
> +++ b/cpukit/score/src/scheduleredf.c
> @@ -20,8 +20,7 @@
>
>  #include <rtems/score/scheduleredfimpl.h>
>
> -static int _Scheduler_EDF_RBTree_compare_function
> -(
> +int _Scheduler_EDF_Compare(
>    const RBTree_Node* n1,
>    const RBTree_Node* n2
>  )
> @@ -43,9 +42,5 @@ void _Scheduler_EDF_Initialize( const Scheduler_Control *scheduler )
>    Scheduler_EDF_Context *context =
>      _Scheduler_EDF_Get_context( scheduler );
>
> -  _RBTree_Initialize_empty(
> -    &context->Ready,
> -    _Scheduler_EDF_RBTree_compare_function,
> -    0
> -  );
> +  _RBTree_Initialize_empty( &context->Ready );
>  }
> diff --git a/cpukit/score/src/scheduleredfchangepriority.c b/cpukit/score/src/scheduleredfchangepriority.c
> index 32b0993..3eabc83 100644
> --- a/cpukit/score/src/scheduleredfchangepriority.c
> +++ b/cpukit/score/src/scheduleredfchangepriority.c
> @@ -32,7 +32,12 @@ Scheduler_Void_or_thread _Scheduler_EDF_Change_priority(
>    Scheduler_EDF_Node *node = _Scheduler_EDF_Thread_get_node( the_thread );
>
>    _RBTree_Extract( &context->Ready, &node->Node );
> -  _RBTree_Insert( &context->Ready, &node->Node );
> +  _RBTree_Insert(
> +    &context->Ready,
> +    &node->Node,
> +    _Scheduler_EDF_Compare,
> +    false
> +  );
>
>    SCHEDULER_RETURN_VOID_OR_NULL;
>  }
> diff --git a/cpukit/score/src/scheduleredfyield.c b/cpukit/score/src/scheduleredfyield.c
> index 5aa2afd..0ad5c32 100644
> --- a/cpukit/score/src/scheduleredfyield.c
> +++ b/cpukit/score/src/scheduleredfyield.c
> @@ -35,7 +35,12 @@ Scheduler_Void_or_thread _Scheduler_EDF_Yield(
>     * with the same priority in case there are such ones.
>     */
>    _RBTree_Extract( &context->Ready, &node->Node );
> -  _RBTree_Insert( &context->Ready, &node->Node );
> +  _RBTree_Insert(
> +    &context->Ready,
> +    &node->Node,
> +    _Scheduler_EDF_Compare,
> +    false
> +  );
>
>    _Scheduler_EDF_Schedule_body( scheduler, the_thread, false );
>
> diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c
> index abec11e..d58a8b5 100644
> --- a/testsuites/sptests/sprbtree01/init.c
> +++ b/testsuites/sptests/sprbtree01/init.c
> @@ -42,6 +42,38 @@ static int test_compare_function (
>    return key1 - key2;
>  }
>
> +static rtems_rbtree_node *rb_insert_unique(
> +  rtems_rbtree_control *rbtree,
> +  rtems_rbtree_node    *node
> +)
> +{
> +  return rtems_rbtree_insert( rbtree, node, test_compare_function, true );
> +}
> +
> +static rtems_rbtree_node *rb_insert_multi(
> +  rtems_rbtree_control *rbtree,
> +  rtems_rbtree_node    *node
> +)
> +{
> +  return rtems_rbtree_insert( rbtree, node, test_compare_function, false );
> +}
> +
> +static rtems_rbtree_node *rb_find_unique(
> +  rtems_rbtree_control *rbtree,
> +  rtems_rbtree_node    *node
> +)
> +{
> +  return rtems_rbtree_find( rbtree, node, test_compare_function, true );
> +}
> +
> +static rtems_rbtree_node *rb_find_multi(
> +  rtems_rbtree_control *rbtree,
> +  rtems_rbtree_node    *node
> +)
> +{
> +  return rtems_rbtree_find( rbtree, node, test_compare_function, false );
> +}
> +
>  /*
>   * recursively checks tree. if the tree is built properly it should only
>   * be a depth of 7 function calls for 100 entries in the tree.
> @@ -106,12 +138,7 @@ rtems_task Init(
>    TEST_BEGIN();
>
>    puts( "Init - Initialize rbtree empty" );
> -  rtems_rbtree_initialize_empty( &rbtree1, &test_compare_function, true );
> -
> -  if ( !rtems_rbtree_is_unique( &rbtree1 ) )
> -    puts( "INIT - FAILED IS UNIQUE CHECK" );
> -  if ( rtems_rbtree_is_unique( NULL ) )
> -    puts( "INIT - FAILED IS UNIQUE CHECK" );
> +  rtems_rbtree_initialize_empty( &rbtree1 );
>
>    /* verify that the rbtree insert work */
>    puts( "INIT - Verify rtems_rbtree_insert with two nodes" );
> @@ -119,10 +146,10 @@ rtems_task Init(
>    node1.key = 1;
>    node2.id = 2;
>    node2.key = 2;
> -  rtems_rbtree_insert( &rbtree1, &node1.Node );
> -  rtems_rbtree_insert( &rbtree1, &node2.Node );
> +  rb_insert_unique( &rbtree1, &node1.Node );
> +  rb_insert_unique( &rbtree1, &node2.Node );
>
> -  p = rtems_rbtree_insert( &rbtree1, NULL );
> +  p = rb_insert_unique( &rbtree1, NULL );
>    if (p != (void *)(-1))
>      puts( "INIT - FAILED NULL NODE INSERT" );
>
> @@ -159,8 +186,8 @@ rtems_task Init(
>
>    puts("INIT - Verify rtems_rbtree_insert with the same value twice");
>    node2.key = node1.key;
> -  rtems_rbtree_insert(&rbtree1, &node1.Node);
> -  p = rtems_rbtree_insert(&rbtree1, &node2.Node);
> +  rb_insert_unique(&rbtree1, &node1.Node);
> +  p = rb_insert_unique(&rbtree1, &node2.Node);
>
>    if (p != &node1.Node)
>      puts( "INIT - FAILED DUPLICATE INSERT" );
> @@ -218,8 +245,8 @@ rtems_task Init(
>    node1.key = 2;
>    node2.id = 1;
>    node2.key = 1;
> -  rtems_rbtree_insert( &rbtree1, &node1.Node );
> -  rtems_rbtree_insert( &rbtree1, &node2.Node );
> +  rb_insert_unique( &rbtree1, &node1.Node );
> +  rb_insert_unique( &rbtree1, &node2.Node );
>
>    puts( "INIT - Verify rtems_rbtree_peek_max/min, rtems_rbtree_extract" );
>    test_node *t1 = rtems_rbtree_container_of(rtems_rbtree_peek_max(&rbtree1),
> @@ -237,7 +264,7 @@ rtems_task Init(
>      puts( "INIT - rtems_rbtree_extract failed");
>      rtems_test_exit(0);
>    }
> -  rtems_rbtree_insert(&rbtree1, p);
> +  rb_insert_unique(&rbtree1, p);
>
>    for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
>        p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
> @@ -256,7 +283,7 @@ rtems_task Init(
>    for (i = 0; i < 100; i++) {
>      node_array[i].id = i;
>      node_array[i].key = i;
> -    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
> +    rb_insert_unique( &rbtree1, &node_array[i].Node );
>
>      if (!rb_assert(rbtree1.root) )
>        puts( "INIT - FAILED TREE CHECK" );
> @@ -289,7 +316,7 @@ rtems_task Init(
>    for (i = 0; i < 100; i++) {
>      node_array[i].id = 99-i;
>      node_array[i].key = 99-i;
> -    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
> +    rb_insert_unique( &rbtree1, &node_array[i].Node );
>
>      if (!rb_assert(rbtree1.root) )
>        puts( "INIT - FAILED TREE CHECK" );
> @@ -324,7 +351,7 @@ rtems_task Init(
>    for (i = 0; i < 100; i++) {
>      node_array[i].id = i;
>      node_array[i].key = i;
> -    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
> +    rb_insert_unique( &rbtree1, &node_array[i].Node );
>
>      if (!rb_assert(rbtree1.root) )
>        puts( "INIT - FAILED TREE CHECK" );
> @@ -376,13 +403,13 @@ rtems_task Init(
>      node_array[i].id = i;
>      node_array[i].key = i;
>    }
> -  rtems_rbtree_insert( &rbtree1, &node_array[3].Node );
> -  rtems_rbtree_insert( &rbtree1, &node_array[1].Node );
> -  rtems_rbtree_insert( &rbtree1, &node_array[5].Node );
> -  rtems_rbtree_insert( &rbtree1, &node_array[0].Node );
> -  rtems_rbtree_insert( &rbtree1, &node_array[2].Node );
> -  rtems_rbtree_insert( &rbtree1, &node_array[4].Node );
> -  rtems_rbtree_insert( &rbtree1, &node_array[6].Node );
> +  rb_insert_unique( &rbtree1, &node_array[3].Node );
> +  rb_insert_unique( &rbtree1, &node_array[1].Node );
> +  rb_insert_unique( &rbtree1, &node_array[5].Node );
> +  rb_insert_unique( &rbtree1, &node_array[0].Node );
> +  rb_insert_unique( &rbtree1, &node_array[2].Node );
> +  rb_insert_unique( &rbtree1, &node_array[4].Node );
> +  rb_insert_unique( &rbtree1, &node_array[6].Node );
>    rtems_rbtree_extract( &rbtree1, &node_array[2].Node );
>    /* node_array[1] has now only a left child. */
>    if ( !node_array[1].Node.child[RBT_LEFT] ||
> @@ -395,7 +422,7 @@ rtems_task Init(
>    for (i = 0; i < 100; i++) {
>      node_array[i].id = 99-i;
>      node_array[i].key = 99-i;
> -    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
> +    rb_insert_unique( &rbtree1, &node_array[i].Node );
>
>      if (!rb_assert(rbtree1.root) )
>        puts( "INIT - FAILED TREE CHECK" );
> @@ -428,7 +455,7 @@ rtems_task Init(
>    for (i = 0; i < 100; i++) {
>      node_array[i].id = i;
>      node_array[i].key = i;
> -    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
> +    rb_insert_unique( &rbtree1, &node_array[i].Node );
>
>      if (!rb_assert(rbtree1.root) )
>        puts( "INIT - FAILED TREE CHECK" );
> @@ -436,7 +463,7 @@ rtems_task Init(
>
>    puts( "INIT - Verify rtems_rbtree_find" );
>    search_node.key = 30;
> -  p = rtems_rbtree_find(&rbtree1, &search_node.Node);
> +  p = rb_find_unique(&rbtree1, &search_node.Node);
>    if(rtems_rbtree_container_of(p,test_node,Node)->id != 30) {
>      puts ("INIT - ERROR ON RBTREE ID MISMATCH");
>      rtems_test_exit(0);
> @@ -448,14 +475,14 @@ rtems_task Init(
>      puts ("INIT - ERROR ON RBTREE ID MISMATCH");
>      rtems_test_exit(0);
>    }
> -  p = rtems_rbtree_find(&rbtree1, &search_node.Node);
> +  p = rb_find_unique(&rbtree1, &search_node.Node);
>    p = rtems_rbtree_successor(p);
>    if(p && rtems_rbtree_container_of(p,test_node,Node)->id != 31) {
>      puts ("INIT - ERROR ON RBTREE ID MISMATCH");
>      rtems_test_exit(0);
>    }
>
> -  p = rtems_rbtree_find(&rbtree1, &search_node.Node);
> +  p = rb_find_unique(&rbtree1, &search_node.Node);
>    puts( "INIT - Verify rtems_rbtree_find_header" );
>    if (rtems_rbtree_find_header(p) != &rbtree1) {
>      puts ("INIT - ERROR ON RBTREE HEADER MISMATCH");
> @@ -509,7 +536,7 @@ rtems_task Init(
>    for (i = 0; i < 20; i++) {
>      node_array[i].id = numbers[i];
>      node_array[i].key = numbers[i];
> -    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
> +    rb_insert_unique( &rbtree1, &node_array[i].Node );
>
>      if (!rb_assert(rbtree1.root) )
>        puts( "INIT - FAILED TREE CHECK" );
> @@ -573,18 +600,13 @@ rtems_task Init(
>
>    /* Initialize the tree for duplicate keys */
>    puts( "Init - Initialize duplicate rbtree empty" );
> -  rtems_rbtree_initialize_empty( &rbtree1, &test_compare_function, false );
> -
> -  if ( rtems_rbtree_is_unique( &rbtree1 ) )
> -    puts( "INIT - FAILED IS UNIQUE CHECK" );
> -  if ( rtems_rbtree_is_unique( NULL ) )
> -    puts( "INIT - FAILED IS UNIQUE CHECK" );
> +  rtems_rbtree_initialize_empty( &rbtree1 );
>
>    puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]" );
>    for (i = 0; i < 100; i++) {
>      node_array[i].id = i;
>      node_array[i].key = i%5;
> -    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
> +    rb_insert_multi( &rbtree1, &node_array[i].Node );
>
>      if (!rb_assert(rbtree1.root) )
>        puts( "INIT - FAILED TREE CHECK" );
> @@ -592,7 +614,7 @@ rtems_task Init(
>
>    puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
>    search_node.key = 2;
> -  p = rtems_rbtree_find(&rbtree1, &search_node.Node);
> +  p = rb_find_multi(&rbtree1, &search_node.Node);
>    if(rtems_rbtree_container_of(p,test_node,Node)->id != 2) {
>      puts ("INIT - ERROR ON RBTREE ID MISMATCH");
>      rtems_test_exit(0);
> @@ -625,7 +647,7 @@ rtems_task Init(
>    for (i = 0; i < 100; i++) {
>      node_array[i].id = 99-i;
>      node_array[i].key = (99-i)%5;
> -    rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
> +    rb_insert_multi( &rbtree1, &node_array[i].Node );
>
>      if (!rb_assert(rbtree1.root) )
>        puts( "INIT - FAILED TREE CHECK" );
> @@ -633,7 +655,7 @@ rtems_task Init(
>
>    puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
>    search_node.key = 2;
> -  p = rtems_rbtree_find(&rbtree1, &search_node.Node);
> +  p = rb_find_multi(&rbtree1, &search_node.Node);
>    if(rtems_rbtree_container_of(p,test_node,Node)->id != 97) {
>      puts ("INIT - ERROR ON RBTREE ID MISMATCH");
>      rtems_test_exit(0);
> --
> 1.8.1.4
>
> _______________________________________________
> devel mailing list
> devel at rtems.org
> http://lists.rtems.org/mailman/listinfo/devel



More information about the devel mailing list