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-12 13:52:25 +0200 |
commit | edb956a0a125d282b9960e0a4f519d18984281c7 (patch) | |
tree | c319a8c4855141fb7bf3af3c2a49c5df34355558 | |
parent | 1df2666ca1d73807a338e0d209ed1f42f67f00a9 (diff) |
score: Simplify _Watchdog_Next_first()
-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 ); } } |