source: rtems/cpukit/score/src/rbtreeinsert.c @ 64939bc

4.11
Last change on this file since 64939bc was 64939bc, checked in by Sebastian Huber <sebastian.huber@…>, on Jul 12, 2014 at 7:22:22 PM

rbtree: Reduce RBTree_Control size

Remove compare function and is unique indicator from the control
structure. Rename RBTree_Compare_function to RBTree_Compare. Rename
rtems_rbtree_compare_function to rtems_rbtree_compare. Provide C++
compatible initializers. Add compare function and is unique indicator
to _RBTree_Find(), _RBTree_Insert(), rtems_rbtree_find() and
rtems_rbtree_insert(). Remove _RBTree_Is_unique() and
rtems_rbtree_is_unique(). Remove compare function and is unique
indicator from _RBTree_Initialize_empty() and
rtems_rbtree_initialize_empty().

  • Property mode set to 100644
File size: 3.4 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#include <rtems/score/isr.h>
15
16/** @brief Validate and fix-up tree properties for a new insert/colored node
17 *
18 *  This routine checks and fixes the Red-Black Tree properties based on
19 *  @a the_node being just added to the tree.
20 *
21 *  @note It does NOT disable interrupts to ensure the atomicity of the
22 *        append operation.
23 */
24static void _RBTree_Validate_insert(
25    RBTree_Node    *the_node
26    )
27{
28  RBTree_Node *u,*g;
29
30  /* note: the insert root case is handled already */
31  /* if the parent is black, nothing needs to be done
32   * otherwise may need to loop a few times */
33  while (_RBTree_Is_red(_RBTree_Parent(the_node))) {
34    u = _RBTree_Parent_sibling(the_node);
35    g = the_node->parent->parent;
36
37    /* if uncle is red, repaint uncle/parent black and grandparent red */
38    if(_RBTree_Is_red(u)) {
39      the_node->parent->color = RBT_BLACK;
40      u->color = RBT_BLACK;
41      g->color = RBT_RED;
42      the_node = g;
43    } else { /* if uncle is black */
44      RBTree_Direction dir = the_node != the_node->parent->child[0];
45      RBTree_Direction pdir = the_node->parent != g->child[0];
46
47      /* ensure node is on the same branch direction as parent */
48      if (dir != pdir) {
49        _RBTree_Rotate(the_node->parent, pdir);
50        the_node = the_node->child[pdir];
51      }
52      the_node->parent->color = RBT_BLACK;
53      g->color = RBT_RED;
54
55      /* now rotate grandparent in the other branch direction (toward uncle) */
56      _RBTree_Rotate(g, (1-pdir));
57    }
58  }
59  if(!the_node->parent->parent) the_node->color = RBT_BLACK;
60}
61
62RBTree_Node *_RBTree_Insert(
63  RBTree_Control *the_rbtree,
64  RBTree_Node    *the_node,
65  RBTree_Compare  compare,
66  bool            is_unique
67)
68{
69  if(!the_node) return (RBTree_Node*)-1;
70
71  RBTree_Node *iter_node = the_rbtree->root;
72  int compare_result;
73
74  if (!iter_node) { /* special case: first node inserted */
75    the_node->color = RBT_BLACK;
76    the_rbtree->root = the_node;
77    the_rbtree->first[0] = the_rbtree->first[1] = the_node;
78    the_node->parent = (RBTree_Node *) the_rbtree;
79    the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL;
80  } else {
81    /* typical binary search tree insert, descend tree to leaf and insert */
82    while (iter_node) {
83      compare_result = ( *compare )( the_node, iter_node );
84      if ( is_unique && _RBTree_Is_equal( compare_result ) )
85        return iter_node;
86      RBTree_Direction dir = !_RBTree_Is_lesser( compare_result );
87      if (!iter_node->child[dir]) {
88        the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL;
89        the_node->color = RBT_RED;
90        iter_node->child[dir] = the_node;
91        the_node->parent = iter_node;
92        /* update min/max */
93        compare_result = ( *compare )(
94          the_node,
95          _RBTree_First( the_rbtree, dir )
96        );
97        if ( (!dir && _RBTree_Is_lesser(compare_result)) ||
98              (dir && _RBTree_Is_greater(compare_result)) ) {
99          the_rbtree->first[dir] = the_node;
100        }
101        break;
102      } else {
103        iter_node = iter_node->child[dir];
104      }
105
106    } /* while(iter_node) */
107
108    /* verify red-black properties */
109    _RBTree_Validate_insert(the_node);
110  }
111  return (RBTree_Node*)0;
112}
Note: See TracBrowser for help on using the repository browser.