Some bug fixes also accomplished, however, does not work yet.
-#include <rtems/score/rbtree.h>
#include <rtems/score/thread.h>
#include "edf_types.h"
#include <rtems/score/thread.h>
#include "edf_types.h"
+#define SI(node) ((RBT_Node*)node->scheduler_info)
+
static void _Rotate_Left(
EDF_Chain_Control *chain,
EDF_Node *node
)
{
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;
- node->parent->right = right;
+ SI(SI(node)->parent)->right = right;
}
else
chain->root = right;
}
else
chain->root = right;
+ SI(node)->parent = right;
}
static void _Rotate_Right(
}
static void _Rotate_Right(
- 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;
- node->parent->left = left;
+ SI(SI(node)->parent)->left = left;
}
else
chain->root = left;
}
else
chain->root = left;
+ SI(node)->parent = left;
while (child)
{
parent = child;
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 ( node->abs_deadline < parent->abs_deadline )
+ if ( SI(node)->abs_deadline < SI(parent)->abs_deadline )
+ SI(parent)->left = node;
if ( parent == chain->first ) chain->first = node;
}
if ( parent == chain->first ) chain->first = node;
}
- else parent->right = node;
+ else SI(parent)->right = node;
} else
{
chain->root = node;
} else
{
chain->root = node;
/* Insert_FixUp */
/* check and fix red-back properties eventually */
/* 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;
}
node = gparent;
continue;
}
- if (node == parent->right)
+ if (node == SI(parent)->right)
{
_Rotate_Left(chain,parent);
tmp = parent;
{
_Rotate_Left(chain,parent);
tmp = parent;
- parent->color = BLACK;
- gparent->color = RED;
+ SI(parent)->color = N_BLACK;
+ SI(gparent)->color = N_RED;
_Rotate_Right(chain, gparent);
} else {
_Rotate_Right(chain, gparent);
} else {
+ 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;
- if (node == parent->left)
+ if (node == SI(parent)->left)
{
_Rotate_Right(chain, parent);
tmp = parent;
{
_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);
}
}
_Rotate_Left(chain, gparent);
}
}
- chain->root->color = BLACK;
+ SI(chain->root)->color = N_BLACK;
}
static void _RBT_Delete_Fixup(
}
static void _RBT_Delete_Fixup(
{
EDF_Node *other, *o_child;
{
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);
_Rotate_Left(chain, parent);
+ 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))
+ SI(other)->color = N_RED;
+ parent = SI(node)->parent;
- 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);
_Rotate_Right(chain,other);
+ 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;
_Rotate_Left(chain,parent);
node = chain->root;
break;
- 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);
_Rotate_Right(chain,parent);
+ 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))
+ SI(other)->color = N_RED;
+ parent = SI(node)->parent;
- if (!other->left ||
- other->left->color == BLACK)
+ if (!SI(other)->left ||
+ SI(SI(other)->left)->color == N_BLACK)
{
register struct rb_node *o_right;
{
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);
_Rotate_Left(chain,other);
+ 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;
_Rotate_Right(chain,parent);
node = chain->root;
break;
+ SI(node)->color = N_BLACK;
if ( chain->first == node )
{
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
else
{
/* this will never happen since only the first node
EDF_Node *old = node, *left;
EDF_Node *old = node, *left;
- node = node->right;
- while ((left = node->left) != NULL)
+ node = SI(node)->right;
+ while ((left = SI(node)->left) != NULL)
- child = node->right;
- parent = node->parent;
- color = node->color;
+ child = SI(node)->right;
+ parent = SI(node)->parent;
+ color = SI(node)->color;
- child->parent = parent;
+ SI(child)->parent = parent;
- if (parent->left == node)
- parent->left = child;
+ if (SI(parent)->left == node)
+ SI(parent)->left = child;
+ SI(parent)->right = child;
}
else
chain->root = child;
}
else
chain->root = child;
- if (node->parent == old)
+ if (SI(node)->parent == old)
- 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->left == old)
- old->parent->left = node;
+ if (SI(SI(old)->parent)->left == old)
+ SI(SI(old)->parent)->left = node;
- old->parent->right = node;
+ SI(SI(old)->parent)->right = node;
} else
chain->root = 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;
- parent = node->parent;
- color = node->color;
+ parent = SI(node)->parent;
+ color = SI(node)->color;
- child->parent = parent;
+ SI(child)->parent = parent;
- if (parent->left == node)
- parent->left = child;
+ if (SI(parent)->left == node)
+ SI(parent)->left = child;
+ SI(parent)->right = child;
}
else
chain->root = child;
color:
}
else
chain->root = child;
color:
_RBT_Delete_Fixup(chain,child,parent);
}
_RBT_Delete_Fixup(chain,child,parent);
}
* TRUE if there is only one node in tree
*/
* 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;
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) {
current = chain->root;
while (current != NULL) {
- if ( absdeadline == current->abs_deadline) return current;
+ if ( absdeadline == SI(current)->abs_deadline) return current;
- current = (absdeadline < current->abs_deadline) ?
- current->left : current->right;
+ current = (absdeadline < SI(current)->abs_deadline) ?
+ SI(current)->left : SI(current)->right;
void _RBT_Insert(EDF_Chain_Control *chain,EDF_Node *node);
void _RBT_Extract(EDF_Chain_Control *chain,EDF_Node *node);
EDF_Node* _RBT_Search(EDF_Chain_Control *chain,Deadline_Control absdeadline);
void _RBT_Insert(EDF_Chain_Control *chain,EDF_Node *node);
void _RBT_Extract(EDF_Chain_Control *chain,EDF_Node *node);
EDF_Node* _RBT_Search(EDF_Chain_Control *chain,Deadline_Control absdeadline);
-boolean _RBT_Has_only_one_node(EDF_Chain_Control *chain);
+int _RBT_Has_only_one_node(EDF_Chain_Control *chain);
#include <stdio.h>
#include <rtems/system.h>
#include <rtems/score/isr.h>
#include <stdio.h>
#include <rtems/system.h>
#include <rtems/score/isr.h>
+#include <rtems/score/wkspace.h>
/* let the scheduler talk */
/* let the scheduler talk */
void _Scheduler_edf_Initialize(void) {
void _Scheduler_edf_Initialize(void) {
printf("Sched: Allocate");
#endif
void * sched;
printf("Sched: Allocate");
#endif
void * sched;
- mem = _Workspace_Allocate (sizeof(RBT_node));
- the_thread->scheduler_info = (RBT_node *) sched;
- return mem;
+ sched = _Workspace_Allocate (sizeof(RBT_Node));
+ the_thread->scheduler_info = (RBT_Node *) sched;
+ return sched;
}
void _Scheduler_edf_Free( Thread_Control *the_thread) {
}
void _Scheduler_edf_Free( Thread_Control *the_thread) {
printf("Sched: Yield");
#endif
printf("Sched: Yield");
#endif
ISR_Level level;
Thread_Control *executing;
EDF_Chain_Control *ready;
executing = _Thread_Executing;
ISR_Level level;
Thread_Control *executing;
EDF_Chain_Control *ready;
executing = _Thread_Executing;
- sched_info = (RBT_node *) executing->scheduler_info;
+ sched_info = (RBT_Node *) executing->scheduler_info;
ready = sched_info->ready_chain;
_ISR_Disable( level );
if ( !_RBT_Has_only_one_node( ready ) ) {
ready = sched_info->ready_chain;
_ISR_Disable( level );
if ( !_RBT_Has_only_one_node( ready ) ) {
printf("Sched: Enqueue");
#endif
// insert do stromu
printf("Sched: Enqueue");
#endif
// insert do stromu
- EDF_Chain_Control* chain = the_thread->scheduler_info->ready_chain;
+ EDF_Chain_Control* chain = ((RBT_Node*)the_thread->scheduler_info)->ready_chain;
_RBT_Insert(chain,the_thread);
}
_RBT_Insert(chain,the_thread);
}
printf("Sched: Enqueue_first");
#endif
// FIXME: force first position
printf("Sched: Enqueue_first");
#endif
// FIXME: force first position
- EDF_Chain_Control* chain = the_thread->scheduler_info->ready_chain;
+ EDF_Chain_Control* chain = ((RBT_Node*)the_thread->scheduler_info)->ready_chain;
_RBT_Insert(chain,the_thread);
}
_RBT_Insert(chain,the_thread);
}
#ifdef SCHED_VERBOSE
printf("Sched: Extract");
#endif
#ifdef SCHED_VERBOSE
printf("Sched: Extract");
#endif
- EDF_Chain_Control* chain = the_thread->scheduler_info->ready_chain;
+ EDF_Chain_Control* chain = ((RBT_Node*)the_thread->scheduler_info)->ready_chain;
_RBT_Extract(chain,the_thread);
}
_RBT_Extract(chain,the_thread);
}
#include "scheduler_edf.h"
#define SCHEDULER_ENTRY_POINTS SCHEDULER_EDF_ENTRY_POINTS
// Priority
#include "scheduler_edf.h"
#define SCHEDULER_ENTRY_POINTS SCHEDULER_EDF_ENTRY_POINTS
// Priority
-#include "scheduler_priority.h"
-#define SCHEDULER_ENTRY_POINTS SCHEDULER_PRIORITY_ENTRY_POINTS
+//#include "scheduler_priority.h"
+//#define SCHEDULER_ENTRY_POINTS SCHEDULER_PRIORITY_ENTRY_POINTS
#define CONFIGURE_MEMORY_FOR_SCHEDULER (1024)
#define CONFIGURE_MEMORY_PER_TASK_FOR_SCHEDULER (256)
#define CONFIGURE_MEMORY_FOR_SCHEDULER (1024)
#define CONFIGURE_MEMORY_PER_TASK_FOR_SCHEDULER (256)