]> www.infradead.org Git - users/jedix/linux-maple.git/commit
maple_tree: Rework walking the tree to combine insert/walk/erase
authorLiam R. Howlett <Liam.Howlett@Oracle.com>
Wed, 9 Jan 2019 20:11:15 +0000 (15:11 -0500)
committerLiam R. Howlett <Liam.Howlett@Oracle.com>
Fri, 30 Oct 2020 18:55:08 +0000 (14:55 -0400)
commit9bfd7de9f1a73837d31f1dba86bd2db6b3575235
tree4e93fe487d66b64c2e55db4c698e982ce5d417f7
parent6031be9a934c343d2d22ab55824ecc854015d59b
maple_tree: Rework walking the tree to combine insert/walk/erase
functions.

This turned out to be a huge deal with many issues resolved for the
following of Thoughts:

1. Nodes can use the last 0x7F bits of the address, so clear them and
such.
2. Root needs to have bit 1 (0x2) set, so be safe around that.
3. mas->node should be encoded (except root needs to remove bit 1 to
avoid being seen as an error).
4. xa_is_node no longer works, so remove BUG_ONs.  Take care that we
know we have a value when we have a slot & an leaf node in mas->node.
5. Store slots in the same place as the alloc requests as their uses do
not overlap.
6. mas_start needs to return a safe root instead of making its own node.
7. Insert was basically rewritten
8. Verify that we are no inserting reserved values
9. Change testcases to not try to insert reserved values.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
include/linux/maple_tree.h
lib/maple_tree.c
lib/test_maple_tree.c