diff options
author | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2021-10-09 16:12:07 +0200 |
---|---|---|
committer | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2021-10-25 08:01:02 +0200 |
commit | a4112bd8af586f724192a19982c3b4c6a6235ecc (patch) | |
tree | fe127207e3ebd4ae338537dd94a0982d545ccb66 /cpukit | |
parent | spec/libdebugger: Only enable for supported architectures (diff) | |
download | rtems-a4112bd8af586f724192a19982c3b4c6a6235ecc.tar.bz2 |
score: Simplify _Watchdog_Next_first()
Diffstat (limited to 'cpukit')
-rw-r--r-- | cpukit/include/rtems/score/watchdogimpl.h | 55 |
1 files changed, 36 insertions, 19 deletions
diff --git a/cpukit/include/rtems/score/watchdogimpl.h b/cpukit/include/rtems/score/watchdogimpl.h index 7b364b8828..ba1a884a3d 100644 --- a/cpukit/include/rtems/score/watchdogimpl.h +++ b/cpukit/include/rtems/score/watchdogimpl.h @@ -351,33 +351,50 @@ RTEMS_INLINE_ROUTINE bool _Watchdog_Is_scheduled( } /** - * @brief Sets the first node of the header. + * @brief Sets the first watchdog of the watchdog collection to the next + * watchdog of the current first watchdog. * - * Sets the first node of the header to either the leftmost child node of the - * watchdog control node, or if not present sets it to the right child node of - * the watchdog control node. if both are not present, the new first node is - * the parent node of the current first node. + * This function may be used during watchdog removals, see _Watchdog_Remove() + * and _Watchdog_Tickle(). * - * @param[in, out] header The watchdog header. - * @param the_watchdog The watchdog control node for the operation. + * @param[in, out] header is the watchdog collection header. + * + * @param first is the current first watchdog which should be removed + * afterwards. */ RTEMS_INLINE_ROUTINE void _Watchdog_Next_first( - Watchdog_Header *header, - Watchdog_Control *the_watchdog + Watchdog_Header *header, + const Watchdog_Control *first ) { - RBTree_Node *node = _RBTree_Right( &the_watchdog->Node.RBTree ); - - if ( node != NULL ) { - RBTree_Node *left; - - while ( ( left = _RBTree_Left( node ) ) != NULL ) { - node = left; - } + RBTree_Node *right; - header->first = node; + /* + * This function uses the following properties of red-black trees: + * + * 1. Every leaf (NULL) is black. + * + * 2. If a node is red, then both its children are black. + * + * 3. Every simple path from a node to a descendant leaf contains the same + * number of black nodes. + * + * The first node has no left child. So every path from the first node has + * exactly one black node (including leafs). The first node cannot have a + * non-leaf black right child. It may have a red right child. In this case + * both children must be leafs. + */ + _Assert( header->first == &first->Node.RBTree ); + _Assert( _RBTree_Left( &first->Node.RBTree ) == NULL ); + right = _RBTree_Right( &first->Node.RBTree ); + + if ( right != NULL ) { + _Assert( RB_COLOR( right, Node ) == RB_RED ); + _Assert( _RBTree_Left( right ) == NULL ); + _Assert( _RBTree_Right( right ) == NULL ); + header->first = right; } else { - header->first = _RBTree_Parent( &the_watchdog->Node.RBTree ); + header->first = _RBTree_Parent( &first->Node.RBTree ); } } |