[rtems commit] score: Move _RBTree_Insert()

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


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

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

score: Move _RBTree_Insert()

The _RBTree_Insert() is no longer used in the score.  Move it to sapi
and make it rtems_rbtree_insert().

---

 cpukit/sapi/Makefile.am                   |  1 +
 cpukit/sapi/include/rtems/rbtree.h        | 32 +++++++++++------
 cpukit/sapi/src/rbtreeinsert.c            | 57 +++++++++++++++++++++++++++++++
 cpukit/score/include/rtems/score/rbtree.h | 23 -------------
 cpukit/score/src/rbtreeinsert.c           | 43 -----------------------
 5 files changed, 79 insertions(+), 77 deletions(-)

diff --git a/cpukit/sapi/Makefile.am b/cpukit/sapi/Makefile.am
index 8970e3d..58d2ce5 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/rbtreeinsert.c
 libsapi_a_SOURCES += src/profilingiterate.c
 libsapi_a_SOURCES += src/profilingreportxml.c
 libsapi_a_SOURCES += src/tcsimpleinstall.c
diff --git a/cpukit/sapi/include/rtems/rbtree.h b/cpukit/sapi/include/rtems/rbtree.h
index 271e4b5..2b43eaa 100644
--- a/cpukit/sapi/include/rtems/rbtree.h
+++ b/cpukit/sapi/include/rtems/rbtree.h
@@ -378,17 +378,27 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_max(
 }
 
 /**
- * @copydoc _RBTree_Insert()
- */
-RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert(
-  rtems_rbtree_control *the_rbtree,
-  rtems_rbtree_node    *the_node,
-  rtems_rbtree_compare  compare,
-  bool                  is_unique
-)
-{
-  return _RBTree_Insert( the_rbtree, the_node, compare, is_unique );
-}
+ * @brief Inserts the node into the red-black tree.
+ *
+ * In case the node is already a node of a tree, then this function yields
+ * unpredictable results.
+ *
+ * @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
+ *   insert nodes in FIFO order in case the key value is equal to existing nodes.
+ *
+ * @retval NULL Successfully inserted.
+ * @retval existing_node This is a unique insert and there exists a node with
+ *   an equal key in the tree already.
+ */
+rtems_rbtree_node *rtems_rbtree_insert(
+  RBTree_Control *the_rbtree,
+  RBTree_Node    *the_node,
+  RBTree_Compare  compare,
+  bool            is_unique
+);
 
 /** @} */
 
diff --git a/cpukit/sapi/src/rbtreeinsert.c b/cpukit/sapi/src/rbtreeinsert.c
new file mode 100644
index 0000000..a4850ff
--- /dev/null
+++ b/cpukit/sapi/src/rbtreeinsert.c
@@ -0,0 +1,57 @@
+/*
+ *  Copyright (c) 2010-2012 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>
+#include <rtems/score/rbtreeimpl.h>
+
+RTEMS_STATIC_ASSERT(
+  sizeof( RBTree_Compare_result ) >= sizeof( intptr_t ),
+  RBTree_Compare_result_intptr_t
+);
+
+RTEMS_STATIC_ASSERT(
+  sizeof( RBTree_Compare_result ) >= sizeof( int32_t ),
+  RBTree_Compare_result_int32_t
+);
+
+rtems_rbtree_node *rtems_rbtree_insert(
+  rtems_rbtree_control *the_rbtree,
+  rtems_rbtree_node    *the_node,
+  RBTree_Compare        compare,
+  bool                  is_unique
+)
+{
+  rtems_rbtree_node **which = _RBTree_Root_reference( the_rbtree );
+  rtems_rbtree_node  *parent = NULL;
+
+  while ( *which != NULL ) {
+    RBTree_Compare_result compare_result;
+
+    parent = *which;
+    compare_result = ( *compare )( the_node, parent );
+
+    if ( is_unique && _RBTree_Is_equal( compare_result ) ) {
+      return parent;
+    }
+
+    if ( _RBTree_Is_lesser( compare_result ) ) {
+      which = _RBTree_Left_reference( parent );
+    } else {
+      which = _RBTree_Right_reference( parent );
+    }
+  }
+
+  _RBTree_Add_child( the_node, parent, which );
+  _RBTree_Insert_color( the_rbtree, the_node );
+
+  return NULL;
+}
diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
index dd56f1b..f0590c0 100644
--- a/cpukit/score/include/rtems/score/rbtree.h
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -117,29 +117,6 @@ RBTree_Node *_RBTree_Find(
 );
 
 /**
- * @brief Inserts the node into the red-black tree.
- *
- * In case the node is already a node of a tree, then this function yields
- * unpredictable results.
- *
- * @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
- *   insert nodes in FIFO order in case the key value is equal to existing nodes.
- *
- * @retval NULL Successfully inserted.
- * @retval existing_node This is a unique insert and there exists a node with
- *   an equal key in the tree already.
- */
-RBTree_Node *_RBTree_Insert(
-  RBTree_Control *the_rbtree,
-  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/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c
index 464fc60..c8bbef9 100644
--- a/cpukit/score/src/rbtreeinsert.c
+++ b/cpukit/score/src/rbtreeinsert.c
@@ -12,49 +12,6 @@
 
 #include <rtems/score/rbtreeimpl.h>
 
-RTEMS_STATIC_ASSERT(
-  sizeof( RBTree_Compare_result ) >= sizeof( intptr_t ),
-  RBTree_Compare_result_intptr_t
-);
-
-RTEMS_STATIC_ASSERT(
-  sizeof( RBTree_Compare_result ) >= sizeof( int32_t ),
-  RBTree_Compare_result_int32_t
-);
-
-RBTree_Node *_RBTree_Insert(
-  RBTree_Control *the_rbtree,
-  RBTree_Node    *the_node,
-  RBTree_Compare  compare,
-  bool            is_unique
-)
-{
-  RBTree_Node **which = _RBTree_Root_reference( the_rbtree );
-  RBTree_Node  *parent = NULL;
-
-  while ( *which != NULL ) {
-    RBTree_Compare_result compare_result;
-
-    parent = *which;
-    compare_result = ( *compare )( the_node, parent );
-
-    if ( is_unique && _RBTree_Is_equal( compare_result ) ) {
-      return parent;
-    }
-
-    if ( _RBTree_Is_lesser( compare_result ) ) {
-      which = _RBTree_Left_reference( parent );
-    } else {
-      which = _RBTree_Right_reference( parent );
-    }
-  }
-
-  _RBTree_Add_child( the_node, parent, which );
-  _RBTree_Insert_color( the_rbtree, the_node );
-
-  return NULL;
-}
-
 RB_GENERATE_INSERT_COLOR( RBTree_Control, RBTree_Node, Node, static inline )
 
 void _RBTree_Insert_color(



More information about the vc mailing list