From 8c2535ce0d60b492dd9c77f43a7085c3197f3e7d Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 6 Apr 2023 21:05:55 -0400 Subject: [PATCH] maple_tree: Introduce mas_next_slot() interface Sometimes, during a tree walk, the user needs the next slot regardless of if it is empty or not. Add an interface to get the next slot. Since there are no consecutive NULLs allowed in the tree, the mas_next() function can only advance two slots at most. So use the new mas_next_slot() interface to align both implementations. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 178 +++++++++++++++++++---------------------------- 1 file changed, 71 insertions(+), 107 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 8c98d1ab8744..e699e87e9d91 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4619,15 +4619,16 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, if (mas->max >= max) goto no_entry; + min = mas->max + 1; + if (min > max) + goto no_entry; + level = 0; do { if (ma_is_root(node)) goto no_entry; - min = mas->max + 1; - if (min > max) - goto no_entry; - + /* Walk up. */ if (unlikely(mas_ascend(mas))) return 1; @@ -4645,13 +4646,12 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, slots = ma_slots(node, mt); pivot = mas_safe_pivot(mas, pivots, ++offset, mt); while (unlikely(level > 1)) { - /* Descend, if necessary */ + level--; enode = mas_slot(mas, slots, offset); if (unlikely(ma_dead_node(node))) return 1; mas->node = enode; - level--; node = mas_mn(mas); mt = mte_node_type(mas->node); slots = ma_slots(node, mt); @@ -4680,85 +4680,84 @@ no_entry: return 0; } +static inline void mas_rewalk(struct ma_state *mas, unsigned long index) +{ +retry: + mas_set(mas, index); + mas_state_walk(mas); + if (mas_is_start(mas)) + goto retry; +} + +static inline bool mas_rewalk_if_dead(struct ma_state *mas, + struct maple_node *node, const unsigned long index) +{ + if (unlikely(ma_dead_node(node))) { + mas_rewalk(mas, index); + return true; + } + return false; +} + /* - * mas_next_nentry() - Get the next node entry - * @mas: The maple state - * @max: The maximum value to check - * @*range_start: Pointer to store the start of the range. + * mas_next_slot() - Get the entry in the next slot * - * Sets @mas->offset to the offset of the next node entry, @mas->last to the - * pivot of the entry. + * @mas: The maple state + * @max: The maximum starting range * - * Return: The next entry, %NULL otherwise + * Return: The entry in the next slot which is possibly NULL */ -static inline void *mas_next_nentry(struct ma_state *mas, - struct maple_node *node, unsigned long max, enum maple_type type) +static inline void *mas_next_slot(struct ma_state *mas, unsigned long max) { - unsigned char count; - unsigned long pivot; - unsigned long *pivots; void __rcu **slots; + unsigned long *pivots; + unsigned long pivot; + enum maple_type type; + struct maple_node *node; + unsigned char data_end; + unsigned long save_point = mas->last; void *entry; - if (mas->last == mas->max) { - mas->index = mas->max; - return NULL; - } - - slots = ma_slots(node, type); +retry: + node = mas_mn(mas); + type = mte_node_type(mas->node); pivots = ma_pivots(node, type); - count = ma_data_end(node, type, pivots, mas->max); - if (unlikely(ma_dead_node(node))) - return NULL; - - mas->index = mas_safe_min(mas, pivots, mas->offset); - if (unlikely(ma_dead_node(node))) - return NULL; - - if (mas->index > max) - return NULL; + data_end = ma_data_end(node, type, pivots, mas->max); + pivot = mas_logical_pivot(mas, pivots, mas->offset, type); + if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) + goto retry; - if (mas->offset > count) + if (pivot >= max) return NULL; - while (mas->offset < count) { - pivot = pivots[mas->offset]; - entry = mas_slot(mas, slots, mas->offset); - if (ma_dead_node(node)) - return NULL; - - mas->last = pivot; - if (entry) - return entry; - - if (pivot >= max) - return NULL; + if (likely(data_end > mas->offset)) { + mas->offset++; + mas->index = mas->last + 1; + } else { + if (mas_next_node(mas, node, max)) { + mas_rewalk(mas, save_point); + goto retry; + } - if (pivot >= mas->max) + if (mas_is_none(mas)) return NULL; - mas->index = pivot + 1; - mas->offset++; + mas->offset = 0; + mas->index = mas->min; + node = mas_mn(mas); + type = mte_node_type(mas->node); + pivots = ma_pivots(node, type); } - pivot = mas_logical_pivot(mas, pivots, mas->offset, type); + slots = ma_slots(node, type); + mas->last = mas_logical_pivot(mas, pivots, mas->offset, type); entry = mas_slot(mas, slots, mas->offset); - if (ma_dead_node(node)) - return NULL; + if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) + goto retry; - mas->last = pivot; return entry; } -static inline void mas_rewalk(struct ma_state *mas, unsigned long index) -{ -retry: - mas_set(mas, index); - mas_state_walk(mas); - if (mas_is_start(mas)) - goto retry; -} - /* * mas_next_entry() - Internal function to get the next entry. * @mas: The maple state @@ -4774,47 +4773,18 @@ retry: static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit) { void *entry = NULL; - struct maple_node *node; - unsigned long last; - enum maple_type mt; if (mas->last >= limit) return NULL; - last = mas->last; -retry: - node = mas_mn(mas); - mt = mte_node_type(mas->node); - mas->offset++; - if (unlikely(mas->offset >= mt_slots[mt])) { - mas->offset = mt_slots[mt] - 1; - goto next_node; - } - - while (!mas_is_none(mas)) { - entry = mas_next_nentry(mas, node, limit, mt); - if (unlikely(ma_dead_node(node))) { - mas_rewalk(mas, last); - goto retry; - } - - if (likely(entry)) - return entry; - - if (unlikely((mas->last >= limit))) - return NULL; + entry = mas_next_slot(mas, limit); + if (entry) + return entry; -next_node: - if (unlikely(mas_next_node(mas, node, limit))) { - mas_rewalk(mas, last); - goto retry; - } - mas->offset = 0; - node = mas_mn(mas); - mt = mte_node_type(mas->node); - } + if (mas_is_none(mas)) + return NULL; - return NULL; + return mas_next_slot(mas, limit); } /* @@ -4845,10 +4815,8 @@ retry: slots = ma_slots(mn, mt); pivots = ma_pivots(mn, mt); count = ma_data_end(mn, mt, pivots, mas->max); - if (unlikely(ma_dead_node(mn))) { - mas_rewalk(mas, index); + if (unlikely(mas_rewalk_if_dead(mas, mn, index))) goto retry; - } offset = mas->offset - 1; if (offset >= mt_slots[mt]) @@ -4861,10 +4829,8 @@ retry: pivot = pivots[offset]; } - if (unlikely(ma_dead_node(mn))) { - mas_rewalk(mas, index); + if (unlikely(mas_rewalk_if_dead(mas, mn, index))) goto retry; - } while (offset && !mas_slot(mas, slots, offset)) { pivot = pivots[--offset]; @@ -4881,10 +4847,8 @@ retry: min = mas_safe_min(mas, pivots, offset); entry = mas_slot(mas, slots, offset); - if (unlikely(ma_dead_node(mn))) { - mas_rewalk(mas, index); + if (unlikely(mas_rewalk_if_dead(mas, mn, index))) goto retry; - } mas->offset = offset; mas->last = pivot; -- 2.50.1