source: rtems/cpukit/score/src/rbtreeinsert.c @ 13c4f853

4.115
Last change on this file since 13c4f853 was 13c4f853, checked in by Joel Sherrill <joel.sherrill@…>, on 08/02/11 at 19:25:59

2011-08-02 Joel Sherrill <joel.sherrill@…>

PR 1877/cpukit

  • libfs/src/imfs/imfs_mknod.c, libfs/src/imfs/memfile.c, sapi/inline/rtems/rbtree.inl, score/include/rtems/score/rbtree.h, score/inline/rtems/score/rbtree.inl, score/src/rbtree.c, score/src/rbtreefind.c, score/src/rbtreeinsert.c: Add comparison function for RBTrees.
  • Property mode set to 100644
File size: 4.2 KB
Line 
1/*
2 *  Copyright (c) 2010 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.com/license/LICENSE.
7 *
8 *  $Id$
9 */
10
11#if HAVE_CONFIG_H
12#include "config.h"
13#endif
14
15#include <rtems/system.h>
16#include <rtems/score/address.h>
17#include <rtems/score/rbtree.h>
18#include <rtems/score/isr.h>
19
20/** @brief Validate and fix-up tree properties for a new insert/colored node
21 *
22 *  This routine checks and fixes the Red-Black Tree properties based on
23 *  @a the_node being just added to the tree.
24 *
25 *  @note It does NOT disable interrupts to ensure the atomicity of the
26 *        append operation.
27 */
28void _RBTree_Validate_insert_unprotected(
29    RBTree_Node    *the_node
30    )
31{
32  RBTree_Node *u,*g;
33
34  /* note: the insert root case is handled already */
35  /* if the parent is black, nothing needs to be done
36   * otherwise may need to loop a few times */
37  while (_RBTree_Is_red(_RBTree_Parent(the_node))) {
38    u = _RBTree_Parent_sibling(the_node);
39    g = the_node->parent->parent;
40
41    /* if uncle is red, repaint uncle/parent black and grandparent red */
42    if(_RBTree_Is_red(u)) {
43      the_node->parent->color = RBT_BLACK;
44      u->color = RBT_BLACK;
45      g->color = RBT_RED;
46      the_node = g;
47    } else { /* if uncle is black */
48      RBTree_Direction dir = the_node != the_node->parent->child[0];
49      RBTree_Direction pdir = the_node->parent != g->child[0];
50
51      /* ensure node is on the same branch direction as parent */
52      if (dir != pdir) {
53        _RBTree_Rotate(the_node->parent, pdir);
54        the_node = the_node->child[pdir];
55      }
56      the_node->parent->color = RBT_BLACK;
57      g->color = RBT_RED;
58
59      /* now rotate grandparent in the other branch direction (toward uncle) */
60      _RBTree_Rotate(g, (1-pdir));
61    }
62  }
63  if(!the_node->parent->parent) the_node->color = RBT_BLACK;
64}
65
66
67
68/** @brief Insert a Node (unprotected)
69 *
70 *  This routine inserts @a the_node on the Red-Black Tree @a the_rbtree.
71 *
72 *  @retval 0 Successfully inserted.
73 *  @retval -1 NULL @a the_node.
74 *  @retval RBTree_Node* if one with equal key to the key of @a the_node exists
75 *          in @a the_rbtree.
76 *
77 *  @note It does NOT disable interrupts to ensure the atomicity
78 *        of the extract operation.
79 */
80RBTree_Node *_RBTree_Insert_unprotected(
81    RBTree_Control *the_rbtree,
82    RBTree_Node *the_node
83    )
84{
85  if(!the_node) return (RBTree_Node*)-1;
86
87  RBTree_Node *iter_node = the_rbtree->root;
88  int compare_result;
89
90  if (!iter_node) { /* special case: first node inserted */
91    the_node->color = RBT_BLACK;
92    the_rbtree->root = the_node;
93    the_rbtree->first[0] = the_rbtree->first[1] = the_node;
94    the_node->parent = (RBTree_Node *) the_rbtree;
95    the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL;
96  } else {
97    /* typical binary search tree insert, descend tree to leaf and insert */
98    while (iter_node) {
99      compare_result = the_rbtree->compare_function(the_node, iter_node);
100      if ( !compare_result ) return iter_node;
101      RBTree_Direction dir = (compare_result != -1);
102      if (!iter_node->child[dir]) {
103        the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL;
104        the_node->color = RBT_RED;
105        iter_node->child[dir] = the_node;
106        the_node->parent = iter_node;
107        /* update min/max */
108        if (_RBTree_Is_first(the_rbtree, iter_node, dir)) {
109          the_rbtree->first[dir] = the_node;
110        }
111        break;
112      } else {
113        iter_node = iter_node->child[dir];
114      }
115
116    } /* while(iter_node) */
117
118    /* verify red-black properties */
119    _RBTree_Validate_insert_unprotected(the_node);
120  }
121  return (RBTree_Node*)0;
122}
123
124
125/*
126 *  _RBTree_Insert
127 *
128 *  This kernel routine inserts a given node after a specified node
129 *  a requested rbtree.
130 *
131 *  Input parameters:
132 *    tree - pointer to RBTree Control for tree to insert to
133 *    node       - pointer to node to be inserted
134 *
135 *  Output parameters:  NONE
136 *
137 *  INTERRUPT LATENCY:
138 *    only case
139 */
140
141void _RBTree_Insert(
142  RBTree_Control *tree,
143  RBTree_Node *node
144)
145{
146  ISR_Level level;
147
148  _ISR_Disable( level );
149    _RBTree_Insert_unprotected( tree, node );
150  _ISR_Enable( level );
151}
Note: See TracBrowser for help on using the repository browser.