| Message ID | 20240911142759.20989-2-richard.weiyang@gmail.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | refine mas_mab_cp() | expand |
* 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 > >
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;
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> --- lib/maple_tree.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-)