]> 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, 5 Jan 2021 17:28:12 +0000 (12:28 -0500)
commit8e12ce6f71247098e0bb20d4526e6a8b5162cd3e
tree41e331f2e8c7bc7c256e9a203ea2b0ac90afe1ce
parent47722e55ff616693895f41ac277b04a6e3ad93a3
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