-#include <rtems/score/rbtree.h>
#include <rtems/score/thread.h>
#include "edf_types.h"
+#include "rbtree.h"
+#define SI(node) ((RBT_Node*)node->scheduler_info)
+
static void _Rotate_Left(
EDF_Chain_Control *chain,
EDF_Node *node
)
{
- EDF_Node *right = node->right;
+ EDF_Node *right = SI(node)->right;
- if ((node->right = right->left))
- right->left->parent = node;
- right->left = node;
- if ((right->parent = node->parent))
+ if ((SI(node)->right = SI(right)->left))
+ SI(SI(right)->left)->parent = node;
+ SI(right)->left = node;
+ if ((SI(right)->parent = SI(node)->parent))
{
- if (node == node->parent->left)
- node->parent->left = right;
+ if (node == SI(SI(node)->parent)->left)
+ SI(SI(node)->parent)->left = right;
else
- node->parent->right = right;
+ SI(SI(node)->parent)->right = right;
}
else
chain->root = right;
- node->parent = right;
+ SI(node)->parent = right;
}
static void _Rotate_Right(
EDF_Node *node
)
{
- EDF_Node *left = node->left;
+ EDF_Node *left = SI(node)->left;
- if ((node->left = left->right))
- left->right->parent = node;
- left->right = node;
+ if ((SI(node)->left = SI(left)->right))
+ SI(SI(left)->right)->parent = node;
+ SI(left)->right = node;
- if ((left->parent = node->parent))
+ if ((SI(left)->parent = SI(node)->parent))
{
- if (node == node->parent->right)
- node->parent->right = left;
+ if (node == SI(SI(node)->parent)->right)
+ SI(SI(node)->parent)->right = left;
else
- node->parent->left = left;
+ SI(SI(node)->parent)->left = left;
}
else
chain->root = left;
- node->parent = left;
+ SI(node)->parent = left;
}
void _RBT_Insert(
while (child)
{
parent = child;
- child = ( node->abs_deadline < child->abs_deadline ) \
- ? child->left : child->right;
+ child = ( SI(node)->abs_deadline < SI(child)->abs_deadline ) \
+ ? SI(child)->left : SI(child)->right;
}
- node->parent = parent;
- node->left = NULL;
- node->right = NULL;
- node->color = RED;
+ SI(node)->parent = parent;
+ SI(node)->left = NULL;
+ SI(node)->right = NULL;
+ SI(node)->color = N_RED;
if (parent)
{
- if ( node->abs_deadline < parent->abs_deadline )
+ if ( SI(node)->abs_deadline < SI(parent)->abs_deadline )
{
- parent->left = node;
+ SI(parent)->left = node;
if ( parent == chain->first ) chain->first = node;
}
- else parent->right = node;
+ else SI(parent)->right = node;
} else
{
chain->root = node;
/* Insert_FixUp */
/* check and fix red-back properties eventually */
- while ((parent = node->parent) && parent->color == RED)
+ while ((parent = SI(node)->parent) && SI(parent)->color == N_RED)
{
- gparent = parent->parent;
+ gparent = SI(parent)->parent;
- if (parent == gparent->left)
+ if (parent == SI(gparent)->left)
{
- uncle = gparent->right;
+ uncle = SI(gparent)->right;
- if ( uncle && uncle->color == RED)
+ if ( uncle && SI(uncle)->color == N_RED)
{
- parent->color = BLACK;
- uncle->color = BLACK;
- gparent->color = RED;
+ SI(parent)->color = N_BLACK;
+ SI(uncle)->color = N_BLACK;
+ SI(gparent)->color = N_RED;
node = gparent;
continue;
}
- if (node == parent->right)
+ if (node == SI(parent)->right)
{
_Rotate_Left(chain,parent);
tmp = parent;
node = tmp;
}
- parent->color = BLACK;
- gparent->color = RED;
+ SI(parent)->color = N_BLACK;
+ SI(gparent)->color = N_RED;
_Rotate_Right(chain, gparent);
} else {
- uncle = gparent->left;
+ uncle = SI(gparent)->left;
- if (uncle && uncle->color == RED )
+ if (uncle && SI(uncle)->color == N_RED )
{
- parent->color = BLACK;
- uncle->color = BLACK;
- gparent->color = RED;
- node = parent->parent;
+ SI(parent)->color = N_BLACK;
+ SI(uncle)->color = N_BLACK;
+ SI(gparent)->color = N_RED;
+ node = SI(parent)->parent;
continue;
}
- if (node == parent->left)
+ if (node == SI(parent)->left)
{
_Rotate_Right(chain, parent);
tmp = parent;
}
- parent->color = BLACK;
- gparent->color = RED;
+ SI(parent)->color = N_BLACK;
+ SI(gparent)->color = N_RED;
_Rotate_Left(chain, gparent);
}
}
- chain->root->color = BLACK;
+ SI(chain->root)->color = N_BLACK;
}
static void _RBT_Delete_Fixup(
{
EDF_Node *other, *o_child;
- while ((!node || node->color == BLACK) && node != chain->root)
+ while ((!node || SI(node)->color == N_BLACK) && node != chain->root)
{
- if (parent->left == node)
+ if (SI(parent)->left == node)
{
- other = parent->right;
- if (other->color == RED)
+ other = SI(parent)->right;
+ if (SI(other)->color == N_RED)
{
- other->color = BLACK;
- parent->color = RED;
+ SI(other)->color = N_BLACK;
+ SI(parent)->color = N_RED;
_Rotate_Left(chain, parent);
- other = parent->right;
+ other = SI(parent)->right;
}
- if ((!other->left ||
- other->left->color == BLACK)
- && (!other->right ||
- other->right->color == BLACK))
+ if ((!SI(other)->left ||
+ SI(SI(other)->left)->color == N_BLACK)
+ && (!SI(other)->right ||
+ SI(SI(other)->right)->color == N_BLACK))
{
- other->color = RED;
+ SI(other)->color = N_RED;
node = parent;
- parent = node->parent;
+ parent = SI(node)->parent;
}
else
{
- if (!other->right ||
- other->right->color == BLACK)
+ if (!SI(other)->right ||
+ SI(SI(other)->right)->color == N_BLACK)
{
- if ((o_child = other->left))
- o_child->color = BLACK;
- other->color = RED;
+ if ((o_child = SI(other)->left))
+ SI(o_child)->color = N_BLACK;
+ SI(other)->color = N_RED;
_Rotate_Right(chain,other);
- other = parent->right;
+ other = SI(parent)->right;
}
- other->color = parent->color;
- parent->color = BLACK;
- if (other->right)
- other->right->color = BLACK;
+ SI(other)->color = SI(parent)->color;
+ SI(parent)->color = N_BLACK;
+ if (SI(other)->right)
+ SI(SI(other)->right)->color = N_BLACK;
_Rotate_Left(chain,parent);
node = chain->root;
break;
}
else
{
- other = parent->left;
- if (other->color == RED)
+ other = SI(parent)->left;
+ if (SI(other)->color == N_RED)
{
- other->color = BLACK;
- parent->color = RED;
+ SI(other)->color = N_BLACK;
+ SI(parent)->color = N_RED;
_Rotate_Right(chain,parent);
- other = parent->left;
+ other = SI(parent)->left;
}
- if ((!other->left ||
- other->left->color == BLACK)
- && (!other->right ||
- other->right->color == BLACK))
+ if ((!SI(other)->left ||
+ SI(SI(other)->left)->color == N_BLACK)
+ && (!SI(other)->right ||
+ SI(SI(other)->right)->color == N_BLACK))
{
- other->color = RED;
+ SI(other)->color = N_RED;
node = parent;
- parent = node->parent;
+ parent = SI(node)->parent;
}
else
{
- if (!other->left ||
- other->left->color == BLACK)
+ if (!SI(other)->left ||
+ SI(SI(other)->left)->color == N_BLACK)
{
register struct rb_node *o_right;
- if ((o_child = other->right))
- o_child->color = BLACK;
- other->color = RED;
+ if ((o_child = SI(other)->right))
+ SI(o_child)->color = N_BLACK;
+ SI(other)->color = N_RED;
_Rotate_Left(chain,other);
- other = parent->left;
+ other = SI(parent)->left;
}
- other->color = parent->color;
- parent->color = BLACK;
- if (other->left)
- other->left->color = BLACK;
+ SI(other)->color = SI(parent)->color;
+ SI(parent)->color = N_BLACK;
+ if (SI(other)->left)
+ SI(SI(other)->left)->color = N_BLACK;
_Rotate_Right(chain,parent);
node = chain->root;
break;
}
}
if (node)
- node->color = BLACK;
+ SI(node)->color = N_BLACK;
}
if ( chain->first == node )
{
- if ( chain->first->right) chain->first = chain->first->right;
- else chain->first = chain->first->parent;
+ if ( SI(chain->first)->right) chain->first = SI(chain->first)->right;
+ else chain->first = SI(chain->first)->parent;
}
- if (!node->left)
- child = node->right;
- else if (!node->right)
- child = node->left;
+ if (!SI(node)->left)
+ child = SI(node)->right;
+ else if (!SI(node)->right)
+ child = SI(node)->left;
else
{
/* this will never happen since only the first node
EDF_Node *old = node, *left;
- node = node->right;
- while ((left = node->left) != NULL)
+ node = SI(node)->right;
+ while ((left = SI(node)->left) != NULL)
node = left;
- child = node->right;
- parent = node->parent;
- color = node->color;
+ child = SI(node)->right;
+ parent = SI(node)->parent;
+ color = SI(node)->color;
if (child)
- child->parent = parent;
+ SI(child)->parent = parent;
if (parent)
{
- if (parent->left == node)
- parent->left = child;
+ if (SI(parent)->left == node)
+ SI(parent)->left = child;
else
- parent->right = child;
+ SI(parent)->right = child;
}
else
chain->root = child;
- if (node->parent == old)
+ if (SI(node)->parent == old)
parent = node;
- node->parent = old->parent;
- node->color = old->color;
- node->right = old->right;
- node->left = old->left;
+ SI(node)->parent = SI(old)->parent;
+ SI(node)->color = SI(old)->color;
+ SI(node)->right = SI(old)->right;
+ SI(node)->left = SI(old)->left;
- if (old->parent)
+ if (SI(old)->parent)
{
- if (old->parent->left == old)
- old->parent->left = node;
+ if (SI(SI(old)->parent)->left == old)
+ SI(SI(old)->parent)->left = node;
else
- old->parent->right = node;
+ SI(SI(old)->parent)->right = node;
} else
chain->root = node;
- old->left->parent = node;
- if (old->right)
- old->right->parent = node;
+ SI(SI(old)->left)->parent = node;
+ if (SI(old)->right)
+ SI(SI(old)->right)->parent = node;
goto color;
}
- parent = node->parent;
- color = node->color;
+ parent = SI(node)->parent;
+ color = SI(node)->color;
if (child)
- child->parent = parent;
+ SI(child)->parent = parent;
if (parent)
{
- if (parent->left == node)
- parent->left = child;
+ if (SI(parent)->left == node)
+ SI(parent)->left = child;
else
- parent->right = child;
+ SI(parent)->right = child;
}
else
chain->root = child;
color:
- if (color == BLACK)
+ if (color == N_BLACK)
_RBT_Delete_Fixup(chain,child,parent);
}
* TRUE if there is only one node in tree
*/
-boolean _RBT_Has_only_one_node(
+int _RBT_Has_only_one_node(
EDF_Chain_Control *chain
)
{
if ( !chain->root ) return 0;
- return ( chain->root->left == chain->root->right == NULL ) ;
+ return ( ((SI(chain->root)->left == SI(chain->root)->right) == NULL) );
}
/*
current = chain->root;
while (current != NULL) {
- if ( absdeadline == current->abs_deadline) return current;
+ if ( absdeadline == SI(current)->abs_deadline) return current;
else {
- current = (absdeadline < current->abs_deadline) ?
- current->left : current->right;
+ current = (absdeadline < SI(current)->abs_deadline) ?
+ SI(current)->left : SI(current)->right;
}
}
return NULL;