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