| Message ID | 20230425140955.3834476-4-Liam.Howlett@oracle.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | Maple tree mas_{next,prev}_range() and cleanup | expand |
在 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:
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:
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> --- lib/maple_tree.c | 6 ++++++ tools/testing/radix-tree/maple.c | 4 ++++ 2 files changed, 10 insertions(+)