From 45b22aaeea191eda48bb8883acd9fab6ee4edb51 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 10 Dec 2020 13:20:54 -0500 Subject: [PATCH] maple_tree: Optimize mas_prev_node() Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 57 +++++++++++++++++++++++++----------------------- 1 file changed, 30 insertions(+), 27 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 7454c42b8bd4..12524a4e5589 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3657,59 +3657,62 @@ no_entry: static inline unsigned long mas_next_node(struct ma_state *mas, unsigned long max) { - unsigned long start_piv, prev_piv, pivot; - int offset, level = 0; + unsigned long start_piv, min, pivot; + unsigned long *pivots; + struct maple_node *node; + int level = 0; + unsigned char offset, end; 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); + if (mas->max >= max) + goto no_entry; + + // Save the location in case of dead node. + start_piv = mas->index; + restart_next_node: level = 0; - -ascend_again: do { if (mte_is_root(mas->node)) goto no_entry; offset = mte_parent_slot(mas->node); + min = mas->max + 1; + if (min > max) + goto no_entry; mas_ascend(mas); - level++; - if (mas_dead_node(mas, start_piv)) + if (unlikely(mas_dead_node(mas, start_piv))) goto restart_next_node; + level++; + end = mas_data_end(mas); + node = mas_mn(mas); mt = mte_node_type(mas->node); - slots = ma_slots(mas_mn(mas), mt); - prev_piv = mas_safe_pivot(mas, offset); - if (prev_piv > max) - goto no_entry; - } while (prev_piv == mas->max); - - if (++offset >= mt_slots[mt]) - goto ascend_again; - - if (!mas_slot(mas, slots, offset)) // beyond the end of data - goto ascend_again; + slots = ma_slots(node, mt); + pivots = ma_pivots(node, mt); + } while (unlikely(offset == end)); - pivot = mas_safe_pivot(mas, offset); + pivot = _mas_safe_pivot(mas, pivots, ++offset, mt); // Descend, if necessary. - while (level > 1) { + while (unlikely(level > 1)) { level--; mas->node = mas_slot(mas, slots, offset); + node = mas_mn(mas); mt = mte_node_type(mas->node); - slots = ma_slots(mas_mn(mas), mt); + slots = ma_slots(node, mt); + pivots = ma_pivots(node, mt); offset = 0; - pivot = mas_safe_pivot(mas, offset); + pivot = pivots[0]; } mas->node = mas_slot(mas, slots, offset); - mas->min = prev_piv + 1; + if (unlikely(mas_dead_node(mas, start_piv))) + goto restart_next_node; + mas->min = min; mas->max = pivot; return mas->max; -- 2.49.0