source: rtems/cpukit/score/src/rbtreeinsert.c @ c499856

4.11
Last change on this file since c499856 was c499856, checked in by Chris Johns <chrisj@…>, on Mar 20, 2014 at 9:10:47 PM

Change all references of rtems.com to rtems.org.

  • Property mode set to 100644
File size: 3.8 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
62
63
64/** @brief Insert a Node (unprotected)
65 *
66 *  This routine inserts @a the_node on the Red-Black Tree @a the_rbtree.
67 *
68 *  @retval 0 Successfully inserted.
69 *  @retval -1 NULL @a the_node.
70 *  @retval RBTree_Node* if one with equal key to the key of @a the_node exists
71 *          in an unique @a the_rbtree.
72 *
73 *  @note It does NOT disable interrupts to ensure the atomicity
74 *        of the extract operation.
75 */
76RBTree_Node *_RBTree_Insert(
77    RBTree_Control *the_rbtree,
78    RBTree_Node *the_node
79    )
80{
81  if(!the_node) return (RBTree_Node*)-1;
82
83  RBTree_Node *iter_node = the_rbtree->root;
84  int compare_result;
85
86  if (!iter_node) { /* special case: first node inserted */
87    the_node->color = RBT_BLACK;
88    the_rbtree->root = the_node;
89    the_rbtree->first[0] = the_rbtree->first[1] = the_node;
90    the_node->parent = (RBTree_Node *) the_rbtree;
91    the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL;
92  } else {
93    /* typical binary search tree insert, descend tree to leaf and insert */
94    while (iter_node) {
95      compare_result = the_rbtree->compare_function(the_node, iter_node);
96      if ( the_rbtree->is_unique && _RBTree_Is_equal( compare_result ) )
97        return iter_node;
98      RBTree_Direction dir = !_RBTree_Is_lesser( compare_result );
99      if (!iter_node->child[dir]) {
100        the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL;
101        the_node->color = RBT_RED;
102        iter_node->child[dir] = the_node;
103        the_node->parent = iter_node;
104        /* update min/max */
105        compare_result = the_rbtree->compare_function(
106            the_node,
107            _RBTree_First(the_rbtree, dir)
108        );
109        if ( (!dir && _RBTree_Is_lesser(compare_result)) ||
110              (dir && _RBTree_Is_greater(compare_result)) ) {
111          the_rbtree->first[dir] = the_node;
112        }
113        break;
114      } else {
115        iter_node = iter_node->child[dir];
116      }
117
118    } /* while(iter_node) */
119
120    /* verify red-black properties */
121    _RBTree_Validate_insert(the_node);
122  }
123  return (RBTree_Node*)0;
124}
Note: See TracBrowser for help on using the repository browser.