1 #include <rtems/score/thread.h>
6 #define SI(node) ((RBT_Node*)node->scheduler_info)
8 static void _Rotate_Left(
9 EDF_Chain_Control *chain,
13 EDF_Node *right = SI(node)->right;
15 if ((SI(node)->right = SI(right)->left))
16 SI(SI(right)->left)->parent = node;
17 SI(right)->left = node;
18 if ((SI(right)->parent = SI(node)->parent))
20 if (node == SI(SI(node)->parent)->left)
21 SI(SI(node)->parent)->left = right;
23 SI(SI(node)->parent)->right = right;
27 SI(node)->parent = right;
30 static void _Rotate_Right(
31 EDF_Chain_Control *chain,
35 EDF_Node *left = SI(node)->left;
37 if ((SI(node)->left = SI(left)->right))
38 SI(SI(left)->right)->parent = node;
39 SI(left)->right = node;
41 if ((SI(left)->parent = SI(node)->parent))
43 if (node == SI(SI(node)->parent)->right)
44 SI(SI(node)->parent)->right = left;
46 SI(SI(node)->parent)->left = left;
50 SI(node)->parent = left;
54 EDF_Chain_Control *chain,
58 EDF_Node *parent, *child, *uncle, *gparent, *tmp;
63 /* Insert new node into tree */
68 child = ( SI(node)->abs_deadline < SI(child)->abs_deadline ) \
69 ? SI(child)->left : SI(child)->right;
72 SI(node)->parent = parent;
73 SI(node)->left = NULL;
74 SI(node)->right = NULL;
75 SI(node)->color = N_RED;
79 if ( SI(node)->abs_deadline < SI(parent)->abs_deadline )
81 SI(parent)->left = node;
82 if ( parent == chain->first ) chain->first = node;
84 else SI(parent)->right = node;
92 /* check and fix red-back properties eventually */
93 while ((parent = SI(node)->parent) && SI(parent)->color == N_RED)
95 gparent = SI(parent)->parent;
97 if (parent == SI(gparent)->left)
99 uncle = SI(gparent)->right;
101 if ( uncle && SI(uncle)->color == N_RED)
103 SI(parent)->color = N_BLACK;
104 SI(uncle)->color = N_BLACK;
105 SI(gparent)->color = N_RED;
110 if (node == SI(parent)->right)
112 _Rotate_Left(chain,parent);
118 SI(parent)->color = N_BLACK;
119 SI(gparent)->color = N_RED;
120 _Rotate_Right(chain, gparent);
123 uncle = SI(gparent)->left;
125 if (uncle && SI(uncle)->color == N_RED )
127 SI(parent)->color = N_BLACK;
128 SI(uncle)->color = N_BLACK;
129 SI(gparent)->color = N_RED;
130 node = SI(parent)->parent;
134 if (node == SI(parent)->left)
136 _Rotate_Right(chain, parent);
143 SI(parent)->color = N_BLACK;
144 SI(gparent)->color = N_RED;
145 _Rotate_Left(chain, gparent);
149 SI(chain->root)->color = N_BLACK;
152 static void _RBT_Delete_Fixup(
153 EDF_Chain_Control *chain,
158 EDF_Node *other, *o_child;
160 while ((!node || SI(node)->color == N_BLACK) && node != chain->root)
162 if (SI(parent)->left == node)
164 other = SI(parent)->right;
165 if (SI(other)->color == N_RED)
167 SI(other)->color = N_BLACK;
168 SI(parent)->color = N_RED;
169 _Rotate_Left(chain, parent);
170 other = SI(parent)->right;
172 if ((!SI(other)->left ||
173 SI(SI(other)->left)->color == N_BLACK)
174 && (!SI(other)->right ||
175 SI(SI(other)->right)->color == N_BLACK))
177 SI(other)->color = N_RED;
179 parent = SI(node)->parent;
183 if (!SI(other)->right ||
184 SI(SI(other)->right)->color == N_BLACK)
186 if ((o_child = SI(other)->left))
187 SI(o_child)->color = N_BLACK;
188 SI(other)->color = N_RED;
189 _Rotate_Right(chain,other);
190 other = SI(parent)->right;
192 SI(other)->color = SI(parent)->color;
193 SI(parent)->color = N_BLACK;
194 if (SI(other)->right)
195 SI(SI(other)->right)->color = N_BLACK;
196 _Rotate_Left(chain,parent);
203 other = SI(parent)->left;
204 if (SI(other)->color == N_RED)
206 SI(other)->color = N_BLACK;
207 SI(parent)->color = N_RED;
208 _Rotate_Right(chain,parent);
209 other = SI(parent)->left;
211 if ((!SI(other)->left ||
212 SI(SI(other)->left)->color == N_BLACK)
213 && (!SI(other)->right ||
214 SI(SI(other)->right)->color == N_BLACK))
216 SI(other)->color = N_RED;
218 parent = SI(node)->parent;
222 if (!SI(other)->left ||
223 SI(SI(other)->left)->color == N_BLACK)
225 register struct rb_node *o_right;
226 if ((o_child = SI(other)->right))
227 SI(o_child)->color = N_BLACK;
228 SI(other)->color = N_RED;
229 _Rotate_Left(chain,other);
230 other = SI(parent)->left;
232 SI(other)->color = SI(parent)->color;
233 SI(parent)->color = N_BLACK;
235 SI(SI(other)->left)->color = N_BLACK;
236 _Rotate_Right(chain,parent);
243 SI(node)->color = N_BLACK;
248 EDF_Chain_Control *chain,
252 EDF_Node *child, *parent;
255 if ( chain->first == node )
257 if ( SI(chain->first)->right) chain->first = SI(chain->first)->right;
258 else chain->first = SI(chain->first)->parent;
262 child = SI(node)->right;
263 else if (!SI(node)->right)
264 child = SI(node)->left;
267 /* this will never happen since only the first node
268 * is being removed every time
271 EDF_Node *old = node, *left;
273 node = SI(node)->right;
274 while ((left = SI(node)->left) != NULL)
276 child = SI(node)->right;
277 parent = SI(node)->parent;
278 color = SI(node)->color;
281 SI(child)->parent = parent;
284 if (SI(parent)->left == node)
285 SI(parent)->left = child;
287 SI(parent)->right = child;
292 if (SI(node)->parent == old)
294 SI(node)->parent = SI(old)->parent;
295 SI(node)->color = SI(old)->color;
296 SI(node)->right = SI(old)->right;
297 SI(node)->left = SI(old)->left;
301 if (SI(SI(old)->parent)->left == old)
302 SI(SI(old)->parent)->left = node;
304 SI(SI(old)->parent)->right = node;
308 SI(SI(old)->left)->parent = node;
310 SI(SI(old)->right)->parent = node;
314 parent = SI(node)->parent;
315 color = SI(node)->color;
318 SI(child)->parent = parent;
321 if (SI(parent)->left == node)
322 SI(parent)->left = child;
324 SI(parent)->right = child;
330 if (color == N_BLACK)
331 _RBT_Delete_Fixup(chain,child,parent);
335 * TRUE if there is only one node in tree
338 int _RBT_Has_only_one_node(
339 EDF_Chain_Control *chain
342 if ( !chain->root ) return 0;
343 return ( ((SI(chain->root)->left == SI(chain->root)->right) == NULL) );
347 * Returns node with specific absolute deadline
350 EDF_Node* _RBT_Search(
351 EDF_Chain_Control *chain,
352 Deadline_Control absdeadline
357 current = chain->root;
358 while (current != NULL) {
359 if ( absdeadline == SI(current)->abs_deadline) return current;
361 current = (absdeadline < SI(current)->abs_deadline) ?
362 SI(current)->left : SI(current)->right;