[PATCH 2/3] rbtree: Add _RBTree_Replace_node()

[Gedare Bloom]

It's on the caller to ensure no ordering violation?

On Mon, Aug 31, 2015 at 7:54 AM, Sebastian Huber
<sebastian.huber at embedded-brains.de> wrote:
> ---
>  cpukit/score/Makefile.am                  |  1 +
>  cpukit/score/include/rtems/score/rbtree.h | 13 +++++++
>  cpukit/score/src/rbtreereplace.c          | 61 +++++++++++++++++++++++++++++++
>  3 files changed, 75 insertions(+)
>  create mode 100644 cpukit/score/src/rbtreereplace.c
>
> 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;
> +}
> --
> 1.8.4.5
>
> _______________________________________________
> devel mailing list
> devel at rtems.org
> http://lists.rtems.org/mailman/listinfo/devel