[PATCH 1/2] score: Add and use _RBTree_Find_inline()

[Gedare Bloom]

On Thu, Mar 31, 2016 at 7:57 AM, Sebastian Huber
<sebastian.huber at embedded-brains.de> wrote:
> ---
>  cpukit/posix/include/rtems/posix/keyimpl.h | 54 ++++++++++++++++++------------
>  cpukit/score/include/rtems/score/rbtree.h  | 41 +++++++++++++++++++++++
>  2 files changed, 73 insertions(+), 22 deletions(-)
>
> diff --git a/cpukit/posix/include/rtems/posix/keyimpl.h b/cpukit/posix/include/rtems/posix/keyimpl.h
> index 28666aa..ca70e24 100644
> --- a/cpukit/posix/include/rtems/posix/keyimpl.h
> +++ b/cpukit/posix/include/rtems/posix/keyimpl.h
> @@ -111,35 +111,45 @@ RTEMS_INLINE_ROUTINE void _POSIX_Keys_Key_value_free(
>    _Freechain_Put( &_POSIX_Keys_Keypool, key_value_pair );
>  }
>
> -RTEMS_INLINE_ROUTINE RBTree_Node *_POSIX_Keys_Key_value_find(
> -  pthread_key_t     key,
> -  Thread_Control   *the_thread
> +RTEMS_INLINE_ROUTINE bool _POSIX_Keys_Key_value_find_equal(
> +  const void        *left,
> +  const RBTree_Node *right
>  )
>  {
> -  RBTree_Node **link;
> -  RBTree_Node  *parent;
> +  const pthread_key_t             *the_left;
> +  const POSIX_Keys_Key_value_pair *the_right;
>
> -  link = _RBTree_Root_reference( &the_thread->Keys.Key_value_pairs );
> -  parent = NULL;
> +  the_left = left;
> +  the_right = POSIX_KEYS_RBTREE_NODE_TO_KEY_VALUE_PAIR( right );
>
> -  while ( *link != NULL ) {
> -    POSIX_Keys_Key_value_pair *parent_key_value_pair;
> -    pthread_key_t              parent_key;
> +  return *the_left == the_right->key;
> +}
>
> -    parent = *link;
> -    parent_key_value_pair = POSIX_KEYS_RBTREE_NODE_TO_KEY_VALUE_PAIR( parent );
> -    parent_key = parent_key_value_pair->key;
> +RTEMS_INLINE_ROUTINE bool _POSIX_Keys_Key_value_find_less(
Patch looks fine. I was just curious, does the compiler actually
inline this too when it is called through a function pointer?

> +  const void        *left,
> +  const RBTree_Node *right
> +)
> +{
> +  const pthread_key_t             *the_left;
> +  const POSIX_Keys_Key_value_pair *the_right;
>
> -    if ( key == parent_key ) {
> -      return parent;
> -    } else if ( key < parent_key ) {
> -      link = _RBTree_Left_reference( parent );
> -    } else {
> -      link = _RBTree_Right_reference( parent );
> -    }
> -  }
> +  the_left = left;
> +  the_right = POSIX_KEYS_RBTREE_NODE_TO_KEY_VALUE_PAIR( right );
> +
> +  return *the_left < the_right->key;
> +}
>
> -  return NULL;
> +RTEMS_INLINE_ROUTINE RBTree_Node *_POSIX_Keys_Key_value_find(
> +  pthread_key_t     key,
> +  Thread_Control   *the_thread
> +)
> +{
> +  return _RBTree_Find_inline(
> +    &the_thread->Keys.Key_value_pairs,
> +    &key,
> +    _POSIX_Keys_Key_value_find_equal,
> +    _POSIX_Keys_Key_value_find_less
> +  );
>  }
>
>  RTEMS_INLINE_ROUTINE void _POSIX_Keys_Key_value_insert(
> diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
> index 7e41c7a..111b231 100644
> --- a/cpukit/score/include/rtems/score/rbtree.h
> +++ b/cpukit/score/include/rtems/score/rbtree.h
> @@ -483,6 +483,47 @@ void _RBTree_Replace_node(
>    RBTree_Node    *replacement
>  );
>
> +/**
> + * @brief Finds a node in the red-black tree with the specified key.
> + *
> + * @param the_rbtree The red-black tree control.
> + * @param key The key to look after.
> + * @param equal Must return true if the specified key equals the key of the
> + *   node, otherwise false.
> + * @param less Must return true if the specified key is less than the key of
> + *   the node, otherwise false.
> + *
> + * @retval node A node with the specified key.
> + * @retval NULL No node with the specified key exists in the red-black tree.
> + */
> +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Find_inline(
> +  RBTree_Control *the_rbtree,
> +  const void     *key,
> +  bool         ( *equal )( const void *, const RBTree_Node * ),
> +  bool         ( *less )( const void *, const RBTree_Node * )
> +)
> +{
> +  RBTree_Node **link;
> +  RBTree_Node  *parent;
> +
> +  link = _RBTree_Root_reference( the_rbtree );
> +  parent = NULL;
> +
> +  while ( *link != NULL ) {
> +    parent = *link;
> +
> +    if ( ( *equal )( key, parent ) ) {
> +      return parent;
> +    } else if ( ( *less )( key, parent ) ) {
> +      link = _RBTree_Left_reference( parent );
> +    } else {
> +      link = _RBTree_Right_reference( parent );
> +    }
> +  }
> +
> +  return NULL;
> +}
> +
>  /**@}*/
>
>  #ifdef __cplusplus
> --
> 1.8.4.5
>
> _______________________________________________
> devel mailing list
> devel at rtems.org
> http://lists.rtems.org/mailman/listinfo/devel