]> www.infradead.org Git - users/jedix/linux-maple.git/commit
maple_tree: Avoid unnecessary ascending
authorLiam R. Howlett <Liam.Howlett@oracle.com>
Mon, 17 Apr 2023 16:10:57 +0000 (12:10 -0400)
committerLiam R. Howlett <Liam.Howlett@oracle.com>
Thu, 27 Apr 2023 01:31:59 +0000 (21:31 -0400)
commit9f9e6f9545cb321cf0560fea53016ca940ad6947
tree2825a439de1249887d78fefeb92d175b09d7e409
parent19854651eabd99dca43cbed84ca3090f4ed6d93f
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 <Liam.Howlett@oracle.com>
lib/maple_tree.c
tools/testing/radix-tree/maple.c