rbtree.c: readjusted the operation for the current data structures

Some bug fixes also accomplished, however, does not work yet.

diff --git a/rtems-omk-template/appfoo/rbtree.c b/rtems-omk-template/appfoo/rbtree.c
index cd9840c9606da9a49a6ad80ed3c0c0c31c7eb131..edbd562ffa55450e1b98cfb13395e15f90968cf0 100644 (file)
--- a/rtems-omk-template/appfoo/rbtree.c
+++ b/rtems-omk-template/appfoo/rbtree.c
@@ -1,28 +1,30 @@
-#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(
@@ -30,22 +32,22 @@ 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(
@@ -63,23 +65,23 @@ 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;
@@ -88,24 +90,24 @@ void _RBT_Insert(
    
    /* 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;
@@ -113,23 +115,23 @@ void _RBT_Insert(
                           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;
@@ -138,13 +140,13 @@ void _RBT_Insert(
                           
                   }
                    
-                  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(
@@ -155,42 +157,42 @@ 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;
@@ -198,39 +200,39 @@ static void _RBT_Delete_Fixup(
                }
                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;
@@ -238,7 +240,7 @@ static void _RBT_Delete_Fixup(
                }
        }
        if (node)
-               node->color = BLACK;
+               SI(node)->color = N_BLACK;
 }
 
 
@@ -252,14 +254,14 @@ void  _RBT_Extract(
 
    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 
@@ -268,64 +270,64 @@ void  _RBT_Extract(
 
        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);
 }
 
@@ -333,12 +335,12 @@ void  _RBT_Extract(
  * 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) );
 }
 
 /*
@@ -354,10 +356,10 @@ EDF_Node* _RBT_Search(
     
    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;

diff --git a/rtems-omk-template/appfoo/rbtree.h b/rtems-omk-template/appfoo/rbtree.h
index 77e77abe43c5f7faea2114260e783ef4e34c8807..4a7af6d3fee1222ff3cd9fb1c2d1162c5cbbd660 100644 (file)
--- a/rtems-omk-template/appfoo/rbtree.h
+++ b/rtems-omk-template/appfoo/rbtree.h
@@ -22,7 +22,7 @@ typedef struct RBT_node_struct {
 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);
 
 
 #ifdef __cplusplus

diff --git a/rtems-omk-template/appfoo/scheduler_edf.c b/rtems-omk-template/appfoo/scheduler_edf.c
index 35cfd4ec8c85c88030222c731e5179c346a9780b..7df3342ce191d9729b4970393b26ee8a84616d8f 100644 (file)
--- a/rtems-omk-template/appfoo/scheduler_edf.c
+++ b/rtems-omk-template/appfoo/scheduler_edf.c
@@ -3,9 +3,10 @@
 #include <stdio.h>
 #include <rtems/system.h>
 #include <rtems/score/isr.h>
+#include <rtems/score/wkspace.h>
 
 /* let the scheduler talk */
-//#define SCHED_VERBOSE
+#define SCHED_VERBOSE
 
 
 void _Scheduler_edf_Initialize(void) {
@@ -37,9 +38,9 @@ void * _Scheduler_edf_Allocate(  Thread_Control      *the_thread) {
        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) {
@@ -71,13 +72,13 @@ void _Scheduler_edf_Yield( void ) {
        printf("Sched: Yield");
        #endif
        
-       RBT_node *sched_info;
+       RBT_Node *sched_info;
        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 ) ) {
@@ -102,7 +103,7 @@ void _Scheduler_edf_Enqueue(  Thread_Control    *the_thread) {
        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);
 }
 
@@ -111,7 +112,7 @@ void _Scheduler_edf_Enqueue_first(  Thread_Control    *the_thread) {
        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);
 }
 
@@ -119,7 +120,7 @@ void _Scheduler_edf_Extract(  Thread_Control     *the_thread) {
        #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);
 }
 

diff --git a/rtems-omk-template/appfoo/system.h b/rtems-omk-template/appfoo/system.h
index 7d725015e4610a0d8c740bd990b08c60b91ced44..4bff97ec24bd97a3e3c2022116c9f1cb98d78e92 100644 (file)
--- a/rtems-omk-template/appfoo/system.h
+++ b/rtems-omk-template/appfoo/system.h
@@ -92,8 +92,8 @@ rtems_task Init(
 #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)