]> 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>
Tue, 5 Jan 2021 17:27:59 +0000 (12:27 -0500)
commit522a2891f8b7225b52a8825b8d7e675a7039e2b3
tree7b22314baf45f2172d4a0c811a38a3db0bc2fffa
parent33f4e78ec339b9b571466cffacba3ffcb63cfbbd
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