diff options
author | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2015-08-31 13:11:04 +0200 |
---|---|---|
committer | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2015-09-03 13:58:24 +0200 |
commit | edf640f8cfdbb695153be61e2318921ac1baf83e (patch) | |
tree | 23e1b837e86ba33f71dec54a7ada5cfa44e2f3f4 /cpukit | |
parent | rbtree: Replace implementation (diff) | |
download | rtems-edf640f8cfdbb695153be61e2318921ac1baf83e.tar.bz2 |
rbtree: Add _RBTree_Replace_node()
Diffstat (limited to '')
-rw-r--r-- | cpukit/score/Makefile.am | 1 | ||||
-rw-r--r-- | cpukit/score/include/rtems/score/rbtree.h | 13 | ||||
-rw-r--r-- | cpukit/score/src/rbtreereplace.c | 61 |
3 files changed, 75 insertions, 0 deletions
diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am index 507d49f739..f727e60033 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 077f2b181d..7e41c7a4c5 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 0000000000..7a54000854 --- /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@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; +} |