From a9078db976b69596ec66aa0a5aabdd4140377154 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Sun, 6 Dec 2020 19:53:05 -0500 Subject: [PATCH] maple_tree: mas_first_entry() optimization Remove loop in favour of checking pivot 0 or 1 as one mus have a value. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 34 ++++++++++++++++++++++++---------- 1 file changed, 24 insertions(+), 10 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 8d8e16f8eb36..f3cc0b571789 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1275,9 +1275,12 @@ static inline void mas_update_gap(struct ma_state *mas) static inline unsigned long mas_first_entry(struct ma_state *mas, unsigned long limit) { - void **slots, *entry; unsigned long max = mas->max, range_start = mas->min; unsigned char offset; + unsigned long *pivots; + struct maple_node *mn; + void **slots; + enum maple_type mt; while (likely(!mte_is_leaf(mas->node))) { max = mte_pivot(mas->node, 0); @@ -1285,18 +1288,29 @@ static inline unsigned long mas_first_entry(struct ma_state *mas, } mas->max = max; - slots = ma_slots(mte_to_node(mas->node), mte_node_type(mas->node)); + mn = mas_mn(mas); + mt = mte_node_type(mas->node); + slots = ma_slots(mn, mt); + /* 0 or 1 must be set */ offset = 0; - while ((range_start < limit) && - (offset < mt_slot_count(mas->node))) { - entry = mas_slot(mas, slots, offset); - if (entry) - goto done; - range_start = mas_safe_pivot(mas, offset) + 1; - offset++; - } + range_start = mas->min; + if (range_start > limit) + goto none; + + if(likely(mas_slot(mas, slots, offset))) + goto done; + + pivots = ma_pivots(mn, mt); + range_start = pivots[0] + 1; + + if (range_start > limit) + goto none; + + if(likely(mas_slot(mas, slots, ++offset))) + goto done; +none: mas->node = MAS_NONE; done: mas->offset = offset; -- 2.50.1