From 768c483b7063025dfd130b29dc3466b6360042e0 Mon Sep 17 00:00:00 2001
From: Sebastian Huber <sebastian.huber@embedded-brains.de>
Date: Fri, 17 Jun 2016 07:38:17 +0200
Subject: 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 ++++++++++++++++++++++++++++++++++++++
 3 files changed, 79 insertions(+), 11 deletions(-)
 create mode 100644 cpukit/sapi/src/rbtreeinsert.c

(limited to 'cpukit/sapi')

diff --git a/cpukit/sapi/Makefile.am b/cpukit/sapi/Makefile.am
index 8970e3d799..58d2ce509d 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 271e4b5a6d..2b43eaaae1 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 0000000000..a4850ff4cf
--- /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;
+}
-- 
cgit v1.2.3