From 3fca2c687c6c53a722d4e583077238f950627c8e Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Mon, 30 Nov 2020 15:28:21 -0500 Subject: [PATCH] maple_tree: Fix mas_next() and mas_walk() setting index/last. Ensure that the last/index is set regardless of if there is a value found. This is necessary to ensure prev/next work as expected. Also update mas_find() to this new functionality Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 25 ++++++++++++++++++------- 1 file changed, 18 insertions(+), 7 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 65341848f944..3dc2ccc5dcf5 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3619,18 +3619,21 @@ static inline bool mas_next_nentry(struct ma_state *mas, unsigned long max, { enum maple_type type = mte_node_type(mas->node); unsigned long pivot = mas->min; - unsigned long r_start = *range_start; + unsigned long r_start; unsigned char offset = mas->offset; unsigned long *pivots = ma_pivots(mas_mn(mas), type); void **slots = ma_slots(mas_mn(mas), type); + r_start = mas_safe_min(mas, pivots, offset); while (offset < mt_slots[type]) { pivot = _mas_safe_pivot(mas, pivots, offset, type); if (!pivot && offset) goto no_entry; - if (r_start > max) + if (r_start > max) { + mas->index = max; goto no_entry; + } if (r_start > mas->max) goto no_entry; @@ -3740,6 +3743,8 @@ retry: break; if (*range_start > limit) { + *range_start = limit; + mas->index = mas->last = limit; mas->offset = offset; mas->node = prev_node; return NULL; @@ -3753,8 +3758,11 @@ next_node: mt = mte_node_type(mas->node); } - if (mas_is_none(mas)) + if (mas_is_none(mas)) { + *range_start = limit; + mas->last = limit; return NULL; + } entry = mas_get_slot(mas, mas->offset); if (mas_dead_node(mas, index)) @@ -4026,6 +4034,9 @@ retry: if (mas->offset == MAPLE_NODE_SLOTS) return NULL; // Not found. + mas->index = range_min; + mas->last = range_max; + return mas_get_slot(mas, mas->offset); } @@ -4440,12 +4451,15 @@ static inline void *_mas_next(struct ma_state *mas, unsigned long limit, *range_start = 0; entry = mas_range_load(mas, range_start, &range_max); mas->last = range_max; + mas->index = *range_start; if (entry) return entry; } else if (!mas_searchable(mas)) return NULL; - return __mas_next(mas, limit, range_start); + entry = __mas_next(mas, limit, range_start); + mas->index = *range_start; + return entry; } /* @@ -4465,9 +4479,6 @@ void *mas_find(struct ma_state *mas, unsigned long max) while (mas_search_cont(mas, index, max, entry)) entry = _mas_next(mas, max, &index); - if (entry) - mas->index = index; - return entry; } EXPORT_SYMBOL_GPL(mas_find); -- 2.50.1