]> 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>
Tue, 2 May 2023 03:00:31 +0000 (23:00 -0400)
commitefdce330eebf115e2a4d84e6c766f9e7ad8396e6
tree424f359205cc7360250bb21670c1d06b30450a1d
parentd124cb5c499873d535a2f81ff58461d2d57c66cc
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