[PATCH 1/2] score: Add and use _RBTree_Find_inline()
Gedare Bloom
gedare at rtems.org
Thu Mar 31 13:29:17 UTC 2016
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
More information about the devel
mailing list