source: rtems/cpukit/score/src/rbtreeinsert.c @ 993f5ac

4.115
Last change on this file since 993f5ac was 993f5ac, checked in by Sebastian Huber <sebastian.huber@…>, on 07/23/14 at 11:03:54

rbtree: Simplify insert and extract

Simplify _RBTree_Insert() and _RBTree_Extract(). Remove more
superfluous NULL pointer checks. Change _RBTree_Is_root() to use only
the node. Add parent parameter to _RBTree_Sibling(). Delete
_RBTree_Grandparent() and _RBTree_Parent_sibling().

  • Property mode set to 100644
File size: 4.2 KB
Line 
1/*
2 *  Copyright (c) 2010-2012 Gedare Bloom.
3 *
4 *  The license and distribution terms for this file may be
5 *  found in the file LICENSE in this distribution or at
6 *  http://www.rtems.org/license/LICENSE.
7 */
8
9#if HAVE_CONFIG_H
10#include "config.h"
11#endif
12
13#include <rtems/score/rbtreeimpl.h>
14
15RTEMS_STATIC_ASSERT(
16  sizeof( RBTree_Compare_result ) >= sizeof( intptr_t ),
17  RBTree_Compare_result_intptr_t
18);
19
20RTEMS_STATIC_ASSERT(
21  sizeof( RBTree_Compare_result ) >= sizeof( int32_t ),
22  RBTree_Compare_result_int32_t
23);
24
25/** @brief Validate and fix-up tree properties for a new insert/colored node
26 *
27 *  This routine checks and fixes the Red-Black Tree properties based on
28 *  @a the_node being just added to the tree.
29 *
30 *  @note It does NOT disable interrupts to ensure the atomicity of the
31 *        append operation.
32 */
33static void _RBTree_Validate_insert( RBTree_Node *the_node )
34{
35  RBTree_Node *parent = _RBTree_Parent( the_node );
36  RBTree_Node *grandparent = _RBTree_Parent( parent );
37
38  /* note: the insert root case is handled already */
39  /* if the parent is black, nothing needs to be done
40   * otherwise may need to loop a few times */
41  while ( parent->color == RBT_RED ) {
42    /* The root is black, so the grandparent must exist */
43    RBTree_Node *uncle = _RBTree_Sibling( parent, grandparent );
44
45    /*
46     * If uncle exists and is red, repaint uncle/parent black and grandparent
47     * red.
48     */
49    if ( uncle != NULL && uncle->color == RBT_RED ) {
50      parent->color = RBT_BLACK;
51      uncle->color = RBT_BLACK;
52      grandparent->color = RBT_RED;
53      the_node = grandparent;
54      parent = _RBTree_Parent( the_node );
55      grandparent = _RBTree_Parent( parent );
56
57      if ( grandparent == NULL )
58        break;
59    } else { /* If uncle does not exist or is black */
60      RBTree_Direction dir = _RBTree_Direction( the_node, parent );
61      RBTree_Direction parentdir = _RBTree_Direction( parent, grandparent );
62
63      /* ensure node is on the same branch direction as parent */
64      if ( dir != parentdir ) {
65        RBTree_Node *oldparent = parent;
66
67        parent = the_node;
68        the_node = oldparent;
69        _RBTree_Rotate( oldparent, parentdir );
70      }
71
72      parent->color = RBT_BLACK;
73      grandparent->color = RBT_RED;
74
75      /* now rotate grandparent in the other branch direction (toward uncle) */
76      _RBTree_Rotate( grandparent, _RBTree_Opposite_direction( parentdir ) );
77
78      grandparent = _RBTree_Parent( parent );
79      break;
80    }
81  }
82
83  if ( grandparent == NULL )
84    the_node->color = RBT_BLACK;
85}
86
87RBTree_Node *_RBTree_Insert(
88  RBTree_Control *the_rbtree,
89  RBTree_Node    *the_node,
90  RBTree_Compare  compare,
91  bool            is_unique
92)
93{
94  RBTree_Node *iter_node = the_rbtree->root;
95
96  if ( !iter_node ) { /* special case: first node inserted */
97    the_node->color = RBT_BLACK;
98    the_rbtree->root = the_node;
99    the_rbtree->first[ 0 ] = the_rbtree->first[ 1 ] = the_node;
100    the_node->parent = (RBTree_Node *) the_rbtree;
101    the_node->child[ RBT_LEFT ] = the_node->child[ RBT_RIGHT ] = NULL;
102  } else {
103    /* typical binary search tree insert, descend tree to leaf and insert */
104    while ( iter_node ) {
105      RBTree_Compare_result compare_result =
106        ( *compare )( the_node, iter_node );
107
108      if ( is_unique && _RBTree_Is_equal( compare_result ) )
109        return iter_node;
110
111      RBTree_Direction dir = !_RBTree_Is_lesser( compare_result );
112
113      if ( !iter_node->child[ dir ] ) {
114        the_node->child[ RBT_LEFT ] = the_node->child[ RBT_RIGHT ] = NULL;
115        the_node->color = RBT_RED;
116        iter_node->child[ dir ] = the_node;
117        the_node->parent = iter_node;
118        /* update min/max */
119        compare_result = ( *compare )(
120          the_node,
121          _RBTree_First( the_rbtree, dir )
122        );
123
124        if (
125          ( dir == RBT_LEFT && _RBTree_Is_lesser( compare_result ) )
126            || ( dir == RBT_RIGHT && !_RBTree_Is_lesser( compare_result ) )
127        ) {
128          the_rbtree->first[ dir ] = the_node;
129        }
130
131        break;
132      } else {
133        iter_node = iter_node->child[ dir ];
134      }
135    } /* while(iter_node) */
136
137    /* verify red-black properties */
138    _RBTree_Validate_insert( the_node );
139  }
140
141  return (RBTree_Node *) 0;
142}
Note: See TracBrowser for help on using the repository browser.