lkml.org 
[lkml]   [2023]   [Apr]   [26]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
SubjectRe: [PATCH 03/34] maple_tree: Avoid unnecessary ascending
From

在 2023/4/25 22:09, Liam R. Howlett 写道:
> The maple tree node limits are implied by the parent. When walking up
> the tree, the limit may not be known until a slot that does not have
> implied limits are encountered. However, if the node is the left-most
> or right-most node, the walking up to find that limit can be skipped.
>
> This commit also fixes the debug/testing code that was not setting the
> limit on walking down the tree as that optimization is not compatible
> with this change.
>
> Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
Reviewed-by: Peng Zhang <zhangpeng.00@bytedance.com>
> ---
> lib/maple_tree.c | 6 ++++++
> tools/testing/radix-tree/maple.c | 4 ++++
> 2 files changed, 10 insertions(+)
>
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index ac0245dd88dad..60bae5be008a6 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -1132,6 +1132,12 @@ static int mas_ascend(struct ma_state *mas)
> return 0;
> }
>
> + if (!mas->min)
> + set_min = true;
> +
> + if (mas->max == ULONG_MAX)
> + set_max = true;
> +
> min = 0;
> max = ULONG_MAX;
> do {
> diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
> index 9286d3baa12d6..75df543e019c9 100644
> --- a/tools/testing/radix-tree/maple.c
> +++ b/tools/testing/radix-tree/maple.c
> @@ -35259,6 +35259,7 @@ static void mas_dfs_preorder(struct ma_state *mas)
>
> struct maple_enode *prev;
> unsigned char end, slot = 0;
> + unsigned long *pivots;
>
> if (mas->node == MAS_START) {
> mas_start(mas);
> @@ -35291,6 +35292,9 @@ static void mas_dfs_preorder(struct ma_state *mas)
> mas_ascend(mas);
> goto walk_up;
> }
> + pivots = ma_pivots(mte_to_node(prev), mte_node_type(prev));
> + mas->max = mas_safe_pivot(mas, pivots, slot, mte_node_type(prev));
> + mas->min = mas_safe_min(mas, pivots, slot);
>
> return;
> done:

\
 
 \ /
  Last update: 2023-04-26 07:29    [W:0.606 / U:0.200 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site