]> 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>
Fri, 30 Oct 2020 18:56:20 +0000 (14:56 -0400)
commit2b23c2ee1e9563716e5dda88bfd146e253621d9e
tree3bf26f0ff105fd77e0d121d8679363281b21d922
parentcb6f65eddcae62640a0bbaf0dbf9f2ab18fa0778
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