[rtems commit] score: Move _RBTree_Find()

Sebastian Huber sebh at rtems.org
Wed Jun 22 12:48:30 UTC 2016


Module:    rtems
Branch:    master
Commit:    69a6802bfa8878d3e9a8296c1516ff5feac77bbc
Changeset: http://git.rtems.org/rtems/commit/?id=69a6802bfa8878d3e9a8296c1516ff5feac77bbc

Author:    Sebastian Huber <sebastian.huber at embedded-brains.de>
Date:      Fri Jun 17 07:50:01 2016 +0200

score: Move _RBTree_Find()

The _RBTree_Find() is no longer used in the score.  Move it to sapi and
make it rtems_rbtree_find().  Move corresponding types and support
functions to sapi.

---

 cpukit/sapi/Makefile.am                       |  1 +
 cpukit/sapi/include/rtems/rbtree.h            | 72 ++++++++++++++++++++++-----
 cpukit/sapi/src/rbtreefind.c                  | 51 +++++++++++++++++++
 cpukit/sapi/src/rbtreeinsert.c                | 16 +++---
 cpukit/score/Makefile.am                      |  2 +-
 cpukit/score/include/rtems/score/rbtree.h     | 48 ------------------
 cpukit/score/include/rtems/score/rbtreeimpl.h | 21 --------
 cpukit/score/src/rbtreefind.c                 | 50 -------------------
 8 files changed, 120 insertions(+), 141 deletions(-)

diff --git a/cpukit/sapi/Makefile.am b/cpukit/sapi/Makefile.am
index 58d2ce5..4e85062 100644
--- a/cpukit/sapi/Makefile.am
+++ b/cpukit/sapi/Makefile.am
@@ -40,6 +40,7 @@ libsapi_a_SOURCES += src/cpucounterconverter.c
 libsapi_a_SOURCES += src/delayticks.c
 libsapi_a_SOURCES += src/delaynano.c
 libsapi_a_SOURCES += src/rbtree.c
+libsapi_a_SOURCES += src/rbtreefind.c
 libsapi_a_SOURCES += src/rbtreeinsert.c
 libsapi_a_SOURCES += src/profilingiterate.c
 libsapi_a_SOURCES += src/profilingreportxml.c
diff --git a/cpukit/sapi/include/rtems/rbtree.h b/cpukit/sapi/include/rtems/rbtree.h
index 2b43eaa..57821cf 100644
--- a/cpukit/sapi/include/rtems/rbtree.h
+++ b/cpukit/sapi/include/rtems/rbtree.h
@@ -55,14 +55,31 @@ typedef RBTree_Node rtems_rbtree_node;
 typedef RBTree_Control rtems_rbtree_control;
 
 /**
- * @copydoc RBTree_Compare_result
+ * @brief Integer type for compare results.
+ *
+ * The type is large enough to represent pointers and 32-bit signed integers.
+ *
+ * @see rtems_rbtree_compare.
  */
-typedef RBTree_Compare_result rtems_rbtree_compare_result;
+typedef long rtems_rbtree_compare_result;
 
 /**
- * @copydoc RBTree_Compare
- */
-typedef RBTree_Compare rtems_rbtree_compare;
+ * @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 rtems_rbtree_compare_result ( *rtems_rbtree_compare )(
+  const RBTree_Node *first,
+  const RBTree_Node *second
+);
 
 /**
  * @brief RBTree initializer for an empty rbtree with designator @a name.
@@ -255,18 +272,47 @@ RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root(
   return _RBTree_Is_root( the_node );
 }
 
+RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_equal(
+  rtems_rbtree_compare_result compare_result
+)
+{
+  return compare_result == 0;
+}
+
+RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_greater(
+  rtems_rbtree_compare_result compare_result
+)
+{
+  return compare_result > 0;
+}
+
+RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_lesser(
+  rtems_rbtree_compare_result compare_result
+)
+{
+  return compare_result < 0;
+}
+
 /**
- * @copydoc _RBTree_Find()
+ * @brief Tries to find a node for the specified key in the tree.
+ *
+ * @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.
+ * @retval NULL No node exists in the tree for the key.
  */
-RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find(
+rtems_rbtree_node* rtems_rbtree_find(
   const rtems_rbtree_control *the_rbtree,
   const rtems_rbtree_node    *the_node,
-  rtems_rbtree_compare        compare,
+  rtems_rbtree_compare              compare,
   bool                        is_unique
-)
-{
-  return _RBTree_Find( the_rbtree, the_node, compare, is_unique );
-}
+);
 
 /**
  * @copydoc _RBTree_Predecessor()
@@ -396,7 +442,7 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_max(
 rtems_rbtree_node *rtems_rbtree_insert(
   RBTree_Control *the_rbtree,
   RBTree_Node    *the_node,
-  RBTree_Compare  compare,
+  rtems_rbtree_compare  compare,
   bool            is_unique
 );
 
diff --git a/cpukit/sapi/src/rbtreefind.c b/cpukit/sapi/src/rbtreefind.c
new file mode 100644
index 0000000..d3f67a6
--- /dev/null
+++ b/cpukit/sapi/src/rbtreefind.c
@@ -0,0 +1,51 @@
+/**
+ * @file
+ *
+ * @brief Find the control structure of the tree containing the given node
+ * @ingroup Scorertems_rbtree
+ */
+
+/*
+ *  Copyright (c) 2010 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.org/license/LICENSE.
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/rbtree.h>
+
+rtems_rbtree_node *rtems_rbtree_find(
+  const rtems_rbtree_control *the_rbtree,
+  const rtems_rbtree_node    *the_node,
+  rtems_rbtree_compare        compare,
+  bool                  is_unique
+)
+{
+  rtems_rbtree_node *iter_node = rtems_rbtree_root( the_rbtree );
+  rtems_rbtree_node *found = NULL;
+
+  while ( iter_node != NULL ) {
+    rtems_rbtree_compare_result compare_result =
+      ( *compare )( the_node, iter_node );
+
+    if ( rtems_rbtree_is_equal( compare_result ) ) {
+      found = iter_node;
+
+      if ( is_unique )
+        break;
+    }
+
+    if ( rtems_rbtree_is_greater( compare_result ) ) {
+      iter_node = rtems_rbtree_right( iter_node );
+    } else {
+      iter_node = rtems_rbtree_left( iter_node );
+    }
+  }
+
+  return found;
+}
diff --git a/cpukit/sapi/src/rbtreeinsert.c b/cpukit/sapi/src/rbtreeinsert.c
index a4850ff..38b2f5b 100644
--- a/cpukit/sapi/src/rbtreeinsert.c
+++ b/cpukit/sapi/src/rbtreeinsert.c
@@ -14,19 +14,19 @@
 #include <rtems/score/rbtreeimpl.h>
 
 RTEMS_STATIC_ASSERT(
-  sizeof( RBTree_Compare_result ) >= sizeof( intptr_t ),
-  RBTree_Compare_result_intptr_t
+  sizeof( rtems_rbtree_compare_result ) >= sizeof( intptr_t ),
+  rtems_rbtree_compare_result_intptr_t
 );
 
 RTEMS_STATIC_ASSERT(
-  sizeof( RBTree_Compare_result ) >= sizeof( int32_t ),
-  RBTree_Compare_result_int32_t
+  sizeof( rtems_rbtree_compare_result ) >= sizeof( int32_t ),
+  rtems_rbtree_compare_result_int32_t
 );
 
 rtems_rbtree_node *rtems_rbtree_insert(
   rtems_rbtree_control *the_rbtree,
   rtems_rbtree_node    *the_node,
-  RBTree_Compare        compare,
+  rtems_rbtree_compare  compare,
   bool                  is_unique
 )
 {
@@ -34,16 +34,16 @@ rtems_rbtree_node *rtems_rbtree_insert(
   rtems_rbtree_node  *parent = NULL;
 
   while ( *which != NULL ) {
-    RBTree_Compare_result compare_result;
+    rtems_rbtree_compare_result compare_result;
 
     parent = *which;
     compare_result = ( *compare )( the_node, parent );
 
-    if ( is_unique && _RBTree_Is_equal( compare_result ) ) {
+    if ( is_unique && rtems_rbtree_is_equal( compare_result ) ) {
       return parent;
     }
 
-    if ( _RBTree_Is_lesser( compare_result ) ) {
+    if ( rtems_rbtree_is_lesser( compare_result ) ) {
       which = _RBTree_Left_reference( parent );
     } else {
       which = _RBTree_Right_reference( parent );
diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am
index 97f0b3d..a58aedc 100644
--- a/cpukit/score/Makefile.am
+++ b/cpukit/score/Makefile.am
@@ -292,7 +292,7 @@ libscore_a_SOURCES += src/freechain.c
 
 ## RBTREE_C_FILES
 libscore_a_SOURCES += \
-    src/rbtreeextract.c src/rbtreefind.c \
+    src/rbtreeextract.c \
     src/rbtreeinsert.c src/rbtreeiterate.c src/rbtreenext.c
 libscore_a_SOURCES += src/rbtreereplace.c
 
diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
index f0590c0..e7e65f7 100644
--- a/cpukit/score/include/rtems/score/rbtree.h
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -57,33 +57,6 @@ typedef struct RBTree_Node {
 typedef RB_HEAD(RBTree_Control, RBTree_Node) RBTree_Control;
 
 /**
- * @brief Integer type for compare results.
- *
- * The type is large enough to represent pointers and 32-bit signed integers.
- *
- * @see RBTree_Compare.
- */
-typedef long RBTree_Compare_result;
-
-/**
- * @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 RBTree_Compare_result ( *RBTree_Compare )(
-  const RBTree_Node *first,
-  const RBTree_Node *second
-);
-
-/**
  * @brief Initializer for an empty red-black tree with designator @a name.
  */
 #define RBTREE_INITIALIZER_EMPTY( name ) \
@@ -96,27 +69,6 @@ typedef RBTree_Compare_result ( *RBTree_Compare )(
   RBTree_Control name = RBTREE_INITIALIZER_EMPTY( name )
 
 /**
- * @brief Tries to find a node for the specified key in the tree.
- *
- * @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.
- * @retval NULL No node exists in the tree for the key.
- */
-RBTree_Node *_RBTree_Find(
-  const RBTree_Control *the_rbtree,
-  const RBTree_Node    *the_node,
-  RBTree_Compare        compare,
-  bool                  is_unique
-);
-
-/**
  * @brief Rebalances the red-black tree after insertion of the node.
  *
  * @param[in] the_rbtree The red-black tree control.
diff --git a/cpukit/score/include/rtems/score/rbtreeimpl.h b/cpukit/score/include/rtems/score/rbtreeimpl.h
index 9c748eb..bf92e29 100644
--- a/cpukit/score/include/rtems/score/rbtreeimpl.h
+++ b/cpukit/score/include/rtems/score/rbtreeimpl.h
@@ -62,27 +62,6 @@ void _RBTree_Iterate(
   void *visitor_arg
 );
 
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_equal(
-  RBTree_Compare_result compare_result
-)
-{
-  return compare_result == 0;
-}
-
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_greater(
-  RBTree_Compare_result compare_result
-)
-{
-  return compare_result > 0;
-}
-
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_lesser(
-  RBTree_Compare_result compare_result
-)
-{
-  return compare_result < 0;
-}
-
 /** @} */
 
 #ifdef __cplusplus
diff --git a/cpukit/score/src/rbtreefind.c b/cpukit/score/src/rbtreefind.c
deleted file mode 100644
index f920feb..0000000
--- a/cpukit/score/src/rbtreefind.c
+++ /dev/null
@@ -1,50 +0,0 @@
-/**
- * @file
- *
- * @brief Find the control structure of the tree containing the given node
- * @ingroup ScoreRBTree
- */
-
-/*
- *  Copyright (c) 2010 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.org/license/LICENSE.
- */
-
-#if HAVE_CONFIG_H
-#include "config.h"
-#endif
-
-#include <rtems/score/rbtreeimpl.h>
-
-RBTree_Node *_RBTree_Find(
-  const RBTree_Control *the_rbtree,
-  const RBTree_Node    *the_node,
-  RBTree_Compare        compare,
-  bool                  is_unique
-)
-{
-  RBTree_Node *iter_node = _RBTree_Root( the_rbtree );
-  RBTree_Node *found = NULL;
-
-  while ( iter_node != NULL ) {
-    RBTree_Compare_result compare_result = ( *compare )( the_node, iter_node );
-
-    if ( _RBTree_Is_equal( compare_result ) ) {
-      found = iter_node;
-
-      if ( is_unique )
-        break;
-    }
-
-    if ( _RBTree_Is_greater( compare_result ) ) {
-      iter_node = _RBTree_Right( iter_node );
-    } else {
-      iter_node = _RBTree_Left( iter_node );
-    }
-  }
-
-  return found;
-}



More information about the vc mailing list