score: Add red-black tree node to Scheduler_Node

In SMP configurations, add a red-black tree node to Scheduler_Node to
enable an EDF scheduler implementation.

Update #3056.

3 files changed, 24 insertions, 22 deletions

diff --git a/cpukit/score/include/rtems/score/schedulernode.h b/cpukit/score/include/rtems/score/schedulernode.h
index 09d03d4e59..1474b0c13c 100644
--- a/cpukit/score/include/rtems/score/schedulernode.h
+++ b/cpukit/score/include/rtems/score/schedulernode.h
@@ -67,14 +67,16 @@ struct Scheduler_Node {
   /**
    * @brief Chain node for usage in various scheduler data structures.
    *
-   * Strictly this is the wrong place for this field since the data structures
+   * Strictly, this is the wrong place for this field since the data structures
    * to manage scheduler nodes belong to the particular scheduler
-   * implementation.  Currently all SMP scheduler implementations use chains.
-   * The node is here to simplify things, just like the object node in the
-   * thread control block.  It may be replaced with a union to add a red-black
-   * tree node in the future.
+   * implementation.  Currently, all SMP scheduler implementations use chains
+   * or red-black trees.  The node is here to simplify things, just like the
+   * object node in the thread control block.
    */
-  Chain_Node Node;
+  union {
+    Chain_Node Chain;
+    RBTree_Node RBTree;
+  } Node;
 
   /**
    * @brief The sticky level determines if this scheduler node should use an
diff --git a/cpukit/score/include/rtems/score/schedulerprioritysmpimpl.h b/cpukit/score/include/rtems/score/schedulerprioritysmpimpl.h
index 5136565bbe..f37414c7a8 100644
--- a/cpukit/score/include/rtems/score/schedulerprioritysmpimpl.h
+++ b/cpukit/score/include/rtems/score/schedulerprioritysmpimpl.h
@@ -75,9 +75,9 @@ static inline void _Scheduler_priority_SMP_Move_from_scheduled_to_ready(
   Scheduler_priority_SMP_Node *node =
     _Scheduler_priority_SMP_Node_downcast( scheduled_to_ready );
 
-  _Chain_Extract_unprotected( &node->Base.Base.Node );
+  _Chain_Extract_unprotected( &node->Base.Base.Node.Chain );
   _Scheduler_priority_Ready_queue_enqueue_first(
-    &node->Base.Base.Node,
+    &node->Base.Base.Node.Chain,
     &node->Ready_queue,
     &self->Bit_map
   );
@@ -94,13 +94,13 @@ static inline void _Scheduler_priority_SMP_Move_from_ready_to_scheduled(
     _Scheduler_priority_SMP_Node_downcast( ready_to_scheduled );
 
   _Scheduler_priority_Ready_queue_extract(
-    &node->Base.Base.Node,
+    &node->Base.Base.Node.Chain,
     &node->Ready_queue,
     &self->Bit_map
   );
   _Chain_Insert_ordered_unprotected(
     &self->Base.Scheduled,
-    &node->Base.Base.Node,
+    &node->Base.Base.Node.Chain,
     _Scheduler_SMP_Insert_priority_fifo_order
   );
 }
@@ -116,7 +116,7 @@ static inline void _Scheduler_priority_SMP_Insert_ready_lifo(
     _Scheduler_priority_SMP_Node_downcast( thread );
 
   _Scheduler_priority_Ready_queue_enqueue(
-    &node->Base.Base.Node,
+    &node->Base.Base.Node.Chain,
     &node->Ready_queue,
     &self->Bit_map
   );
@@ -133,7 +133,7 @@ static inline void _Scheduler_priority_SMP_Insert_ready_fifo(
     _Scheduler_priority_SMP_Node_downcast( thread );
 
   _Scheduler_priority_Ready_queue_enqueue_first(
-    &node->Base.Base.Node,
+    &node->Base.Base.Node.Chain,
     &node->Ready_queue,
     &self->Bit_map
   );
@@ -150,7 +150,7 @@ static inline void _Scheduler_priority_SMP_Extract_from_ready(
     _Scheduler_priority_SMP_Node_downcast( thread );
 
   _Scheduler_priority_Ready_queue_extract(
-    &node->Base.Base.Node,
+    &node->Base.Base.Node.Chain,
     &node->Ready_queue,
     &self->Bit_map
   );
diff --git a/cpukit/score/include/rtems/score/schedulersmpimpl.h b/cpukit/score/include/rtems/score/schedulersmpimpl.h
index d91a62c3ca..b90c359d4c 100644
--- a/cpukit/score/include/rtems/score/schedulersmpimpl.h
+++ b/cpukit/score/include/rtems/score/schedulersmpimpl.h
@@ -608,9 +608,9 @@ static inline Scheduler_Node *_Scheduler_SMP_Get_lowest_scheduled(
   (void) filter;
   (void) order;
 
-  _Assert( &lowest_scheduled->Node != _Chain_Tail( scheduled ) );
+  _Assert( &lowest_scheduled->Node.Chain != _Chain_Tail( scheduled ) );
   _Assert(
-    _Chain_Next( &lowest_scheduled->Node ) == _Chain_Tail( scheduled )
+    _Chain_Next( &lowest_scheduled->Node.Chain ) == _Chain_Tail( scheduled )
   );
 
   return lowest_scheduled;
@@ -708,7 +708,7 @@ static inline bool _Scheduler_SMP_Enqueue_ordered(
 
   lowest_scheduled = ( *get_lowest_scheduled )( context, node, order );
 
-  if ( ( *order )( &node->Node, &lowest_scheduled->Node ) ) {
+  if ( ( *order )( &node->Node.Chain, &lowest_scheduled->Node.Chain ) ) {
     _Scheduler_SMP_Enqueue_to_scheduled(
       context,
       node,
@@ -769,7 +769,7 @@ static inline bool _Scheduler_SMP_Enqueue_scheduled_ordered(
      */
     if (
       node->sticky_level > 0
-        && ( *order )( &node->Node, &highest_ready->Node )
+        && ( *order )( &node->Node.Chain, &highest_ready->Node.Chain )
     ) {
       ( *insert_scheduled )( context, node );
 
@@ -859,7 +859,7 @@ static inline void _Scheduler_SMP_Extract_from_scheduled(
   Scheduler_Node *node
 )
 {
-  _Chain_Extract_unprotected( &node->Node );
+  _Chain_Extract_unprotected( &node->Node.Chain );
 }
 
 static inline void _Scheduler_SMP_Schedule_highest_ready(
@@ -1109,7 +1109,7 @@ static inline void _Scheduler_SMP_Insert_scheduled_lifo(
 
   _Chain_Insert_ordered_unprotected(
     &self->Scheduled,
-    &node_to_insert->Node,
+    &node_to_insert->Node.Chain,
     _Scheduler_SMP_Insert_priority_lifo_order
   );
 }
@@ -1123,7 +1123,7 @@ static inline void _Scheduler_SMP_Insert_scheduled_fifo(
 
   _Chain_Insert_ordered_unprotected(
     &self->Scheduled,
-    &node_to_insert->Node,
+    &node_to_insert->Node.Chain,
     _Scheduler_SMP_Insert_priority_fifo_order
   );
 }
@@ -1154,7 +1154,7 @@ static inline bool _Scheduler_SMP_Ask_for_help(
     node_state = _Scheduler_SMP_Node_state( node );
 
     if ( node_state == SCHEDULER_SMP_NODE_BLOCKED ) {
-      if ( ( *order )( &node->Node, &lowest_scheduled->Node ) ) {
+      if ( ( *order )( &node->Node.Chain, &lowest_scheduled->Node.Chain ) ) {
         _Thread_Scheduler_cancel_need_for_help(
           thread,
           _Thread_Get_CPU( thread )
@@ -1297,7 +1297,7 @@ static inline void _Scheduler_SMP_Add_processor(
   if ( ( *has_ready )( &self->Base ) ) {
     ( *enqueue_scheduled_fifo )( &self->Base, node );
   } else {
-    _Chain_Append_unprotected( &self->Scheduled, &node->Node );
+    _Chain_Append_unprotected( &self->Scheduled, &node->Node.Chain );
   }
 }