diff options
| author | Liam R. Howlett <Liam.Howlett@oracle.com> | 2023-05-18 16:55:12 +0200 |
|---|---|---|
| committer | Andrew Morton <akpm@linux-foundation.org> | 2023-06-10 01:25:27 +0200 |
| commit | 633769c9267fadadffd31e27655bf028538238ad (patch) | |
| tree | 7e087d5b6b6f0ef2fd27e46dc7993abec52200e4 /tools/testing/radix-tree | |
| parent | maple_tree: clean up mas_parent_enum() and rename to mas_parent_type() (diff) | |
| download | linux-633769c9267fadadffd31e27655bf028538238ad.tar.xz linux-633769c9267fadadffd31e27655bf028538238ad.zip | |
maple_tree: avoid unnecessary ascending
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.
Link: https://lkml.kernel.org/r/20230518145544.1722059-4-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
Reviewed-by: Peng Zhang <zhangpeng.00@bytedance.com>
Cc: David Binderman <dcb314@hotmail.com>
Cc: Sergey Senozhatsky <senozhatsky@chromium.org>
Cc: Vernon Yang <vernon2gm@gmail.com>
Cc: Wei Yang <richard.weiyang@gmail.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Diffstat (limited to 'tools/testing/radix-tree')
| -rw-r--r-- | tools/testing/radix-tree/maple.c | 4 |
1 files changed, 4 insertions, 0 deletions
diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index 9286d3baa12d..75df543e019c 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 @@ walk_up: 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: |