Messages in this thread | | | Date | Fri, 28 Apr 2023 14:48:13 +0800 | Subject | Re: [PATCH 27/34] maple_tree: Introduce mas_next_slot() interface | From | Peng Zhang <> |
| |
在 2023/4/25 22:09, Liam R. Howlett 写道: > 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 <Liam.Howlett@oracle.com> > --- > 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 31cbfd7b44728..fe6c9da6f2bd5 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; Unnecessary check due to mas->max < max. > + > 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 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, > 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) > +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 @@ static inline void mas_rewalk(struct ma_state *mas, unsigned long index) > 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_limit(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_limit(mas, limit); > } > > /* > @@ -4845,10 +4815,8 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit, > 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 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit, > 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 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit, > > 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;
| |