score: Replace watchdog handler implementation

Use a red-black tree instead of delta chains.

Close #2344.
Update #2554.
Update #2555.
Close #2606.

1 files changed, 36 insertions, 96 deletions

diff --git a/cpukit/score/src/watchdoginsert.c b/cpukit/score/src/watchdoginsert.c
index db15f55b0d..22fc7a5f76 100644
--- a/cpukit/score/src/watchdoginsert.c
+++ b/cpukit/score/src/watchdoginsert.c
@@ -1,17 +1,22 @@
 /**
- * @file 
+ * @file
  *
  * @brief Watchdog Insert
  * @ingroup ScoreWatchdog
  */
- 
+
 /*
- *  COPYRIGHT (c) 1989-1999.
- *  On-Line Applications Research Corporation (OAR).
+ * Copyright (c) 2016 embedded brains GmbH.  All rights reserved.
+ *
+ *  embedded brains GmbH
+ *  Dornierstr. 4
+ *  82178 Puchheim
+ *  Germany
+ *  <rtems@embedded-brains.de>
  *
- *  The license and distribution terms for this file may be
- *  found in the file LICENSE in this distribution or at
- *  http://www.rtems.org/license/LICENSE.
+ * The license and distribution terms for this file may be
+ * found in the file LICENSE in this distribution or at
+ * http://www.rtems.org/license/LICENSE.
  */
 
 #if HAVE_CONFIG_H
@@ -20,106 +25,41 @@
 
 #include <rtems/score/watchdogimpl.h>
 
-static void _Watchdog_Insert_fixup(
-  Watchdog_Header   *header,
-  Watchdog_Control  *the_watchdog,
-  Watchdog_Interval  delta,
-  Watchdog_Control  *next_watchdog,
-  Watchdog_Interval  delta_next
-)
-{
-  const Chain_Node *iterator_tail;
-  Chain_Node       *iterator_node;
-
-  next_watchdog->delta_interval = delta_next - delta;
-
-  iterator_node = _Chain_First( &header->Iterators );
-  iterator_tail = _Chain_Immutable_tail( &header->Iterators );
-
-  while ( iterator_node != iterator_tail ) {
-    Watchdog_Iterator *iterator;
-
-    iterator = (Watchdog_Iterator *) iterator_node;
-
-    if ( iterator->current == &next_watchdog->Node ) {
-      iterator->current = &the_watchdog->Node;
-    }
-
-    iterator_node = _Chain_Next( iterator_node );
-  }
-}
-
-void _Watchdog_Insert_locked(
+void _Watchdog_Insert(
   Watchdog_Header  *header,
   Watchdog_Control *the_watchdog,
-  ISR_lock_Context *lock_context
+  uint64_t          expire
 )
 {
-  if ( the_watchdog->state == WATCHDOG_INACTIVE ) {
-    Watchdog_Iterator  iterator;
-    Chain_Node        *current;
-    Chain_Node        *next;
-    Watchdog_Interval  delta;
-
-    the_watchdog->state = WATCHDOG_BEING_INSERTED;
-
-    _Chain_Append_unprotected( &header->Iterators, &iterator.Node );
-
-    delta = the_watchdog->initial;
-    current = _Chain_Head( &header->Watchdogs );
+  RBTree_Node **link;
+  RBTree_Node  *parent;
+  RBTree_Node  *old_first;
+  RBTree_Node  *new_first;
 
-    while (
-      ( next = _Chain_Next( current ) ) != _Chain_Tail( &header->Watchdogs )
-    ) {
-      Watchdog_Control  *next_watchdog;
-      Watchdog_Interval  delta_next;
+  _Assert( _Watchdog_Get_state( the_watchdog ) == WATCHDOG_INACTIVE );
 
-      next_watchdog = (Watchdog_Control *) next;
-      delta_next = next_watchdog->delta_interval;
+  link = _RBTree_Root_reference( &header->Watchdogs );
+  parent = NULL;
+  old_first = header->first;
+  new_first = &the_watchdog->Node.RBTree;
 
-      if ( delta < delta_next ) {
-        _Watchdog_Insert_fixup(
-          header,
-          the_watchdog,
-          delta,
-          next_watchdog,
-          delta_next
-        );
-        break;
-      }
+  the_watchdog->expire = expire;
 
-      iterator.delta_interval = delta - delta_next;
-      iterator.current = next;
+  while ( *link != NULL ) {
+    Watchdog_Control *parent_watchdog;
 
-      _Watchdog_Flash( header, lock_context );
+    parent = *link;
+    parent_watchdog = (Watchdog_Control *) parent;
 
-      if ( the_watchdog->state != WATCHDOG_BEING_INSERTED ) {
-        goto abort_insert;
-      }
-
-      delta = iterator.delta_interval;
-      current = iterator.current;
+    if ( expire < parent_watchdog->expire ) {
+      link = _RBTree_Left_reference( parent );
+    } else {
+      link = _RBTree_Right_reference( parent );
+      new_first = old_first;
     }
-
-    the_watchdog->delta_interval = delta;
-    the_watchdog->start_time = _Watchdog_Ticks_since_boot;
-    _Watchdog_Activate( the_watchdog );
-    _Chain_Insert_unprotected( current, &the_watchdog->Node );
-
-abort_insert:
-
-    _Chain_Extract_unprotected( &iterator.Node );
   }
-}
-
-void _Watchdog_Insert(
-  Watchdog_Header  *header,
-  Watchdog_Control *the_watchdog
-)
-{
-  ISR_lock_Context lock_context;
 
-  _Watchdog_Acquire( header, &lock_context );
-  _Watchdog_Insert_locked( header, the_watchdog, &lock_context );
-  _Watchdog_Release( header, &lock_context );
+  header->first = new_first;
+  _RBTree_Add_child( &the_watchdog->Node.RBTree, parent, link );
+  _RBTree_Insert_color( &header->Watchdogs, &the_watchdog->Node.RBTree );
 }