From 9f0cee1caa1186fa5fba8c20c48984425e5d1c68 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Wed, 9 Sep 2020 16:32:36 -0400 Subject: [PATCH] maple_tree: Rework mas_next_node again Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 48 +++++++++++++++++++++++++----------------------- 1 file changed, 25 insertions(+), 23 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 8647337a66df..0426085a56ac 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3242,49 +3242,51 @@ static inline unsigned long mas_next_node(struct ma_state *mas, enum maple_type mt; void **slots; + if (mas_is_none(mas)) + return mas->max; + + if (mte_is_root(mas->node)) + goto no_entry; + + offset = mte_parent_slot(mas->node); + start_piv = mas_safe_pivot(mas, offset); restart_next_node: level = 0; - while (!mas_is_none(mas)) { + do { if (mte_is_root(mas->node)) goto no_entry; offset = mte_parent_slot(mas->node); mas_ascend(mas); - start_piv = mas_safe_pivot(mas, offset); + level++; if (mas_dead_node(mas, start_piv)) goto restart_next_node; - level++; mt = mte_node_type(mas->node); slots = ma_get_slots(mas_mn(mas), mt); prev_piv = mas_safe_pivot(mas, offset); if (prev_piv > max) goto no_entry; - if (prev_piv == mas->max) // last in node. - continue; - - if (++offset >= mt_slots[mt]) - continue; - - pivot = mas_safe_pivot(mas, offset); - - // Descend, if necessary. - while (level > 1) { - level--; - mas->node = rcu_dereference(slots[offset]); - mt = mte_node_type(mas->node); - slots = ma_get_slots(mas_mn(mas), mt); - offset = 0; - pivot = mas_safe_pivot(mas, offset); - } + } while (prev_piv == mas->max); + ++offset; + pivot = mas_safe_pivot(mas, offset); + // Descend, if necessary. + while (level > 1) { + level--; mas->node = rcu_dereference(slots[offset]); - mas->min = prev_piv + 1; - mas->max = pivot; - return mas->max; + mt = mte_node_type(mas->node); + slots = ma_get_slots(mas_mn(mas), mt); + offset = 0; + pivot = mas_safe_pivot(mas, offset); } + mas->node = rcu_dereference(slots[offset]); + mas->min = prev_piv + 1; + mas->max = pivot; + return mas->max; + no_entry: mas->node = MAS_NONE; return mas->max; -- 2.50.1