From d73f8565566c1756996f937b793614d9dc3573ba Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Mon, 17 Apr 2023 12:10:57 -0400 Subject: [PATCH] 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. Signed-off-by: Liam R. Howlett --- 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 39f34ea7a9be..b791bcc48ed5 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1130,6 +1130,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 18e319e6ce33..1049f934caa8 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -35234,6 +35234,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); @@ -35266,6 +35267,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: -- 2.50.1