RTEMS
rbtreereplace.c
Go to the documentation of this file.
1 
9 /*
10  * Copyright (c) 2015 embedded brains GmbH. All rights reserved.
11  *
12  * embedded brains GmbH
13  * Dornierstr. 4
14  * 82178 Puchheim
15  * Germany
16  * <rtems@embedded-brains.de>
17  *
18  * The license and distribution terms for this file may be
19  * found in the file LICENSE in this distribution or at
20  * http://www.rtems.org/license/LICENSE.
21  */
22 
23 #ifdef HAVE_CONFIG_H
24 #include "config.h"
25 #endif
26 
27 #include <rtems/score/rbtree.h>
28 
30  RBTree_Control *the_rbtree,
31  RBTree_Node *victim,
32  RBTree_Node *replacement
33 )
34 {
35  RBTree_Node *parent = _RBTree_Parent( victim );
36  RBTree_Node **link;
37  RBTree_Node *child;
38 
39  if (parent != NULL) {
40  if ( victim == _RBTree_Left( parent ) ) {
41  link = _RBTree_Left_reference( parent );
42  } else {
43  link = _RBTree_Right_reference( parent );
44  }
45  } else {
46  link = _RBTree_Root_reference( the_rbtree );
47  }
48  *link = replacement;
49 
50  child = _RBTree_Left( victim );
51  if ( child != NULL ) {
52  RB_PARENT( child, Node ) = replacement;
53  }
54 
55  child = _RBTree_Right( victim );
56  if ( child != NULL ) {
57  RB_PARENT( child, Node ) = replacement;
58  }
59 
60  *replacement = *victim;
61 }
static __inline__ RBTree_Node * _RBTree_Right(const RBTree_Node *the_node)
Returns pointer to the right of this node.
Definition: rbtree.h:342
static __inline__ RBTree_Node ** _RBTree_Root_reference(RBTree_Control *the_rbtree)
Returns a reference to the root pointer of the red-black tree.
Definition: rbtree.h:261
Constants and Structures Associated with the Red-Black Tree Handler.
Red-black tree node.
Definition: rbtree.h:55
void _RBTree_Replace_node(RBTree_Control *the_rbtree, RBTree_Node *victim, RBTree_Node *replacement)
Replaces a node in the red-black tree without a rebalance.
Definition: rbtreereplace.c:29
static __inline__ RBTree_Node * _RBTree_Parent(const RBTree_Node *the_node)
Returns a pointer to the parent of this node.
Definition: rbtree.h:295
static __inline__ RBTree_Node * _RBTree_Left(const RBTree_Node *the_node)
Returns pointer to the left of this node.
Definition: rbtree.h:311
static __inline__ RBTree_Node ** _RBTree_Left_reference(RBTree_Node *the_node)
Returns a reference to the left child pointer of the red-black tree node.
Definition: rbtree.h:326
static __inline__ RBTree_Node ** _RBTree_Right_reference(RBTree_Node *the_node)
Returns a reference to the right child pointer of the red-black tree node.
Definition: rbtree.h:357