[rtems commit] rbtree: Add _RBTree_Replace_node()

[Sebastian Huber]

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

Author:    Sebastian Huber <sebastian.huber at embedded-brains.de>
Date:      Mon Aug 31 13:11:04 2015 +0200

rbtree: Add _RBTree_Replace_node()

---

 cpukit/score/Makefile.am                  |  1 +
 cpukit/score/include/rtems/score/rbtree.h | 13 +++++++
 cpukit/score/src/rbtreereplace.c          | 61 +++++++++++++++++++++++++++++++
 3 files changed, 75 insertions(+)

diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am
index 507d49f..f727e60 100644
--- a/cpukit/score/Makefile.am
+++ b/cpukit/score/Makefile.am
@@ -286,6 +286,7 @@ libscore_a_SOURCES += src/freechain.c
 libscore_a_SOURCES += \
     src/rbtreeextract.c src/rbtreefind.c \
     src/rbtreeinsert.c src/rbtreeiterate.c src/rbtreenext.c
+libscore_a_SOURCES += src/rbtreereplace.c
 
 ## THREAD_C_FILES
 libscore_a_SOURCES += src/thread.c src/threadchangepriority.c \
diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
index 077f2b1..7e41c7a 100644
--- a/cpukit/score/include/rtems/score/rbtree.h
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -470,6 +470,19 @@ RBTree_Node *_RBTree_Predecessor( const RBTree_Node *node );
  */
 RBTree_Node *_RBTree_Successor( const RBTree_Node *node );
 
+/**
+ * @brief Replaces a node in the red-black tree without a rebalance.
+ *
+ * @param[in] the_rbtree The red-black tree control.
+ * @param[in] victim The victim node.
+ * @param[in] replacement The replacement node.
+ */
+void _RBTree_Replace_node(
+  RBTree_Control *the_rbtree,
+  RBTree_Node    *victim,
+  RBTree_Node    *replacement
+);
+
 /**@}*/
 
 #ifdef __cplusplus
diff --git a/cpukit/score/src/rbtreereplace.c b/cpukit/score/src/rbtreereplace.c
new file mode 100644
index 0000000..7a54000
--- /dev/null
+++ b/cpukit/score/src/rbtreereplace.c
@@ -0,0 +1,61 @@
+/**
+ * @file
+ *
+ * @ingroup ScoreRBTree
+ *
+ * @brief _RBTree_Replace_node() implementation.
+ */
+
+/*
+ * Copyright (c) 2015 embedded brains GmbH.  All rights reserved.
+ *
+ *  embedded brains GmbH
+ *  Dornierstr. 4
+ *  82178 Puchheim
+ *  Germany
+ *  <rtems at embedded-brains.de>
+ *
+ * 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/rbtree.h>
+
+void _RBTree_Replace_node(
+  RBTree_Control *the_rbtree,
+  RBTree_Node    *victim,
+  RBTree_Node    *replacement
+)
+{
+  RBTree_Node  *parent = _RBTree_Parent( victim );
+  RBTree_Node **link;
+  RBTree_Node  *child;
+
+  if (parent != NULL) {
+    if ( victim == _RBTree_Left( parent ) ) {
+      link = _RBTree_Left_reference( parent );
+    } else {
+      link = _RBTree_Right_reference( parent );
+    }
+  } else {
+    link = _RBTree_Root_reference( the_rbtree );
+  }
+  *link = replacement;
+
+  child = _RBTree_Left( victim );
+  if ( child != NULL ) {
+    RB_PARENT( child, Node ) = replacement;
+  }
+
+  child = _RBTree_Right( victim );
+  if ( child != NULL ) {
+    RB_PARENT( child, Node ) = replacement;
+  }
+
+  *replacement = *victim;
+}