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

Sebastian Huber sebastian.huber at embedded-brains.de
Thu Mar 31 11:57:56 UTC 2016


---
 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(
+  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



More information about the devel mailing list