Re: [PATCH 1/2] maple_tree: i is always less than or equal to mas_end

["Liam R. Howlett" <Liam.Howlett@oracle.com>]

* Wei Yang <richard.weiyang@gmail.com> [240911 10:29]:
> mas_mab_cp() copy range [mas_start, mas_end] inclusively from a
> maple_node to maple_big_node. This implies mas_start <= mas_end.
> 
> Based on the relationship of mas_start and mas_end, we can have the
> following four cases:
> 
>                  | mas_start == mas_end |  mas_start < mas_end
>   ---------------+----------------------+----------------------
>   mas_start == 0 |         1            |          2
>   ---------------+----------------------+----------------------
>   mas_start != 0 |         3            |          4
> 
> We can see in all these four cases, i is always less than or equal to
> mas_end after finish the loop:
> 
>   Case 1: After assign pivot 0, i is set to 1, which is bigger than
>           mas_end 0. So it jumps to complete and skip the check.
>   Case 2: After assign pivot 0, i is set to 1.
>           ∵ (mas_start < mas_end) && (mas_start == 0)
>              ==>  (1 <= mas_end)
>           ∵ (i == 1) && (1 <= mas_end)
>              ==>  (i <= mas_end)
>           ∴ Before loop, we have (i <= mas_end). And we still hold this
>              if it skips the loop. For example, (i == mas_end).
> 
>           Now let's see what happens in the loop:
>           ∵ piv_end = min(mas_end, mt_pivots[mt])
>              ==>  (piv_end <= mas_end)
> 	  ∵ loop condition is (i < piv_end)
> 	     ==>  (i <= piv_end) on finish the loop both normally or break
>           ∵ (i <= piv_end) && (piv_end <= mas_end)
>              ==>  (i <= mas_end)
>           ∴ After loop, we still get (i <= mas_end) in this case
>   Case 3: This case would skip both if clause and loop. So when it comes
>           to the check, i is still mas_start which equals to mas_end.
>   Case 4: This case would skip the if clause.
>           ∵ (mas_start < mas_end) && (i == mas_start)
>              ==>  (i < mas_end)
>           ∴ Before loop, we have (i < mas_end).
>           The loop process is similar with Case 2, so we get the same
> 	  result.
> 
> Now we can conclude in all cases, we get (i <= mas_end) when doing
> check. Then it is not necessary to do the check.
> 
> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>

Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

> ---
>  lib/maple_tree.c | 3 +--
>  1 file changed, 1 insertion(+), 2 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 76b68568f77b..6fd62b7ef240 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -1948,8 +1948,7 @@ static inline void mas_mab_cp(struct ma_state *mas, unsigned char mas_start,
>  			goto complete;
>  	}
>  
> -	if (likely(i <= mas_end))
> -		b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt);
> +	b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt);
>  
>  complete:
>  	b_node->b_end = ++j;
> -- 
> 2.34.1
> 
>