]> 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>
Wed, 31 Jul 2019 14:52:34 +0000 (10:52 -0400)
commit43b24d4fdd84725490559fbf02f6414a07d25d4b
tree84f70571b7c641091c148d4743bb8b1809cd294b
parente488c76ab93d502505d110132a2492669f9db693
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