]> 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>
Tue, 5 Jan 2021 17:28:14 +0000 (12:28 -0500)
commit67a33fff7895e6067c6f11bb99f93863efd0824c
tree1541679938eba861f70736ff079f6369a309e6fe
parent1c191f9eac546a4520055b0f677c7a3cfc62b8c4
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