From 2fd8bf0c964c21980df703236a88f2ea3679aaef Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 15 Feb 2019 15:58:50 -0500 Subject: [PATCH] maple_tree: Make walk faster. Avoid looking up duplicate information. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 28 ++++++++++++++-------------- 1 file changed, 14 insertions(+), 14 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 935fae1f07e0..3859870d88c3 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1279,11 +1279,10 @@ done: return ret; } -static inline bool mas_search_slots(struct ma_state *mas, unsigned long val, - enum maple_type type) +static inline struct maple_node *mas_search_slots(struct ma_state *mas, + unsigned long val, enum maple_type type) { int i; - bool ret = false; unsigned char pivot_cnt = mt_pivots[type]; unsigned long pivot = 0; @@ -1298,7 +1297,7 @@ static inline bool mas_search_slots(struct ma_state *mas, unsigned long val, pivot = _ma_get_pivot(mas->node, i, type); if (i != 0 && pivot == 0) { ma_set_slot(mas, MAPLE_NODE_SLOTS); - return ret; + return NULL; } if (val <= pivot) @@ -1311,20 +1310,19 @@ static inline bool mas_search_slots(struct ma_state *mas, unsigned long val, } linear_node: - if (_ma_get_rcu_slot(mas->node, i, type)) - ret = true; - ma_set_slot(mas, i); - return ret; + return _ma_get_rcu_slot(mas->node, i, type); } -static inline bool mas_traverse(struct ma_state *mas, enum maple_type type) +static inline bool mas_traverse(struct ma_state *mas, struct maple_node *next, + enum maple_type type) { - unsigned char slot = ma_get_slot(mas); + unsigned char slot; - mas_update_limits(mas, slot, type); if (type < maple_range_16) return false; - mas->node = _ma_get_rcu_slot(mas->node, slot, type); + slot = ma_get_slot(mas); + mas_update_limits(mas, slot, type); + mas->node = next; return true; } @@ -1332,11 +1330,13 @@ static inline bool _mas_walk(struct ma_state *mas) { mas->node = mas_start(mas); enum maple_type type; + struct maple_node *next; do { type = mt_node_type(mas->node); - if (!mas_search_slots(mas, mas->index, type)) + next = mas_search_slots(mas, mas->index, type); + if (!next) return type < maple_range_16; - } while (mas_traverse(mas, type)); + } while (mas_traverse(mas, next, type)); return true; } -- 2.50.1