]> 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>
Fri, 30 Oct 2020 18:56:34 +0000 (14:56 -0400)
commita33bcf0dbfdb88f286ea0a502e9bf7df6fad410b
tree22a6f4c6aba2c5c0d2b0c31a987b777cb3c80cf0
parentf3cbaabd4bc90344a92e1ad4c9478306e4ef6477
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