]> www.infradead.org Git - users/jedix/linux-maple.git/commit
maple_tree: Fix coalesce/rebalance when erasing from the front of the
authorLiam R. Howlett <Liam.Howlett@Oracle.com>
Wed, 16 Oct 2019 19:31:37 +0000 (15:31 -0400)
committerLiam R. Howlett <Liam.Howlett@Oracle.com>
Wed, 16 Oct 2019 19:31:37 +0000 (15:31 -0400)
commit16d03b26b87b1a8b6ade7581a287be4824768ab9
tree3122d0ff0917faf08ea0e9b2b940eb98236dd1b9
parentaa253653f9b64f8b6501d3435fef993ef08c1850
maple_tree: Fix coalesce/rebalance when erasing from the front of the
tree.

mas_coalesce_pivots added to set all null entries to the same pivot.
mas_coalesce_empty added to coalesce pivots after setting the entry to
NULL.
mas_rebalance reworked to free empty & coalesce_pivots on allocation
failure.  Parent nodes are then checked.
coalesce_root has a special case for when end == coalesce for handling
allocation failures.
mas_coalesce reworked to better perform when checking parent nodes &
works when allocations fail.
Gaps are now pushed to the right to avoid pulling the 0 pivot to the
left.

Also included:
Add check for dense nodes.
Fix mas_prev_slot called with root node.
typo fix for rebalance comment

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
lib/maple_tree.c