From 58e97f2b8e23be640dcddf07e150d924935f2e91 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Wed, 9 Sep 2020 16:32:46 -0400 Subject: [PATCH] maple_tree: Rework mas_prev_node Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 82 ++++++++++++++++++++---------------------------- 1 file changed, 34 insertions(+), 48 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 0426085a56ac..f72e24d2db3e 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3155,70 +3155,56 @@ static inline int mas_dead_node(struct ma_state *mas, unsigned long index); */ static inline void mas_prev_node(struct ma_state *mas, unsigned long limit) { - unsigned long pivot, start_piv, min; - int offset = mas_offset(mas); - struct maple_enode *mn; - int level; + unsigned long start_piv; + enum maple_type mt; + int offset, level; void **slots; + if (mas_is_none(mas)) + return; + + if (mte_is_root(mas->node)) + goto no_entry; + + offset = mte_parent_slot(mas->node); start_piv = mas_safe_pivot(mas, offset); restart_prev_node: level = 0; - if (mas->node == MAS_NONE) - goto no_entry; - - while (1) { - + do { if (mte_is_root(mas->node)) goto no_entry; + // Walk up. offset = mte_parent_slot(mas->node); mas_ascend(mas); level++; - if (mas_dead_node(mas, start_piv)) goto restart_prev_node; + } while (!offset); - if (!offset) - continue; - - offset--; - slots = ma_get_slots(mas_mn(mas), mte_node_type(mas->node)); - do { - pivot = mas_safe_pivot(mas, offset); - - min = mas_safe_min(mas, offset); - if (pivot < limit) - goto no_entry; - - if (!pivot && offset) // end of node. - break; - - mn = rcu_dereference_check(slots[offset], - lockdep_is_held(mas->tree->ma_lock)); - if (!mn) - continue; - - if (level == 1) { - mas_set_offset(mas, offset); - mas->node = mn; - mas->max = pivot; - mas->min = min; - if (mas_dead_node(mas, start_piv)) - goto restart_prev_node; - return; - } - - level--; - mas->node = mn; - mas->max = pivot; - mas->min = min; - offset = mas_data_end(mas) + 1; - slots = ma_get_slots(mas_mn(mas), - mte_node_type(mas->node)); - } while (offset-- > 0); + offset--; + mt = mte_node_type(mas->node); + slots = ma_get_slots(mas_mn(mas), mte_node_type(mas->node)); + mas->max = mas_safe_pivot(mas, offset); + while (level > 1) { + level--; + mas->node = rcu_dereference(slots[offset]); + if (mas_dead_node(mas, start_piv)) + goto restart_prev_node; + mt = mte_node_type(mas->node); + slots = ma_get_slots(mas_mn(mas), mt); + offset = mt_slots[mt]; + do {} while(!mas_get_slot(mas, --offset)); + mas->max = mas_safe_pivot(mas, offset); } + mas_set_offset(mas, offset); + mas->min = mas_safe_min(mas, offset); + mas->node = rcu_dereference(slots[offset]); + if (mas_dead_node(mas, start_piv)) + goto restart_prev_node; + return; + no_entry: mas->node = MAS_NONE; } -- 2.50.1