[PATCH] score: Simplify _Watchdog_Next_first()

[Gedare Bloom]

ok

On Mon, Oct 11, 2021 at 5:24 AM Sebastian Huber
<sebastian.huber at embedded-brains.de> wrote:
>
> ---
>  cpukit/include/rtems/score/watchdogimpl.h | 55 +++++++++++++++--------
>  1 file 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 );
>    }
>  }
>
> --
> 2.31.1
>
> _______________________________________________
> devel mailing list
> devel at rtems.org
> http://lists.rtems.org/mailman/listinfo/devel