From 4a8c1f71f4b2303ac3573c0159e5d26c123bea17 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Wed, 25 Nov 2020 14:04:48 -0500 Subject: [PATCH] maple_tree: Optimize mas_node_walk() and standardize __mas_walk() a bit Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 41 ++++++++++++++++++----------------------- 1 file changed, 18 insertions(+), 23 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 39cf6bf18797..6d2d71e05759 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2938,35 +2938,32 @@ static inline void mas_node_walk(struct ma_state *mas, enum maple_type type, unsigned long *range_min, unsigned long *range_max) { unsigned long *pivots = ma_pivots(mas_mn(mas), type); - unsigned long min, pivot = 0; - min = mas_safe_min(mas, pivots, mas->offset); - if (ma_is_dense(type)) { - // Linear node. - // What if mas->index != mas->last? - pivot = min = mas->index; + if (unlikely(ma_is_dense(type))) { + (*range_max) = (*range_min) = mas->index; mas->offset = mas->index = mas->min; - goto dense; + return; } - while (mas->offset < mt_slots[type]) { - pivot = _mas_safe_pivot(mas, pivots, mas->offset, type); + (*range_min) = mas_safe_min(mas, pivots, mas->offset); + if (unlikely(mas->offset == mt_pivots[type])) + goto max; - if (!pivot && mas->offset) { - pivot = mas->max; - break; - } + while (mas->offset < mt_pivots[type]) { - if (mas->index <= pivot) - break; + (*range_max) = pivots[mas->offset]; + if (!(*range_max) && mas->offset) + goto max; - min = pivot + 1; + if (mas->index <= (*range_max)) + return; + + (*range_min) = (*range_max) + 1; mas->offset++; } -dense: - *range_min = min; - *range_max = pivot; +max: + *range_max = mas->max; } /* @@ -3067,18 +3064,16 @@ static inline bool __mas_walk(struct ma_state *mas, unsigned long *range_min, { struct maple_enode *next; enum maple_type type; - bool ret = false; while (true) { - mas->depth++; type = mte_node_type(mas->node); + mas->depth++; mas_node_walk(mas, type, range_min, range_max); if (ma_is_leaf(type)) // Leaf. return true; next = mas_get_slot(mas, mas->offset); - if (!next) return false; @@ -3088,7 +3083,7 @@ static inline bool __mas_walk(struct ma_state *mas, unsigned long *range_min, mas->node = next; mas->offset = 0; } - return ret; + return false; } /* -- 2.50.1