From: Petr Benes <benesp16@fel.cvut.cz>
Date: Thu, 24 Mar 2011 17:14:33 +0000 (+0100)
Subject: rbtree.c: readjusted the operation for the current data structures
X-Git-Url: http://rtime.felk.cvut.cz/gitweb/rtems-pluggable-edf.git/commitdiff_plain/8dfabe2d2f75f24009ceaab051ab8ba4df03bf3e

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 cd9840c..edbd562 100644
--- 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 77e77ab..4a7af6d 100644
--- 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 35cfd4e..7df3342 100644
--- 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 7d72501..4bff97e 100644
--- 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)