]> www.infradead.org Git - users/jedix/linux-maple.git/commit
maple_tree: Add coalesce support.
authorLiam R. Howlett <Liam.Howlett@Oracle.com>
Tue, 8 Oct 2019 01:34:08 +0000 (21:34 -0400)
committerLiam R. Howlett <Liam.Howlett@Oracle.com>
Tue, 8 Oct 2019 01:34:08 +0000 (21:34 -0400)
commit2c9cae386ae41c6dfef8b3e59c6c3eb2168f1743
treeafb1070d0798ac55c3862a278e2dbab229901e10
parent0839b0a556b681ec9ff680afcfcba4ac1cef44f9
maple_tree: Add coalesce support.

Coalesce is done in two stages:
  1. Set all adjacent coalesce pivots to the highest value.
  2. rebalance if there is not enough data in the node.

Rebalance is done as follows:
  1. Take data from the right (4 or everything)
  2. if there is no right, rebalance the node to the left.
  3. if there is no left, rebalance the parent.
  4. if there is no parent, remove a level from the tree.

More testing is needed.  The test infrastructure needs to be reworked to
use more knowledge of the tree layout to test when split/erase occurs
and to ensure the testcases fail if they become invalid (ie: dense
support re-enabled).

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