[rtems commit] rbtree: Add _RBTree_Replace_node()
Sebastian Huber
sebh at rtems.org
Thu Sep 3 12:00:36 UTC 2015
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;
+}
More information about the vc
mailing list