On Fri, May 05, 2023 at 01:41:59PM -0400, Liam R. Howlett wrote:
> Some users of the maple tree may want to move to the previous range
> regardless of the value stored there. Add this interface as well as the
> 'find' variant to support walking to the first value, then iterating
> over the previous ranges.
>
> Signed-off-by: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>
> ---
> include/linux/maple_tree.h | 1 +
> lib/maple_tree.c | 160 +++++++++++++++++++++++++++----------
> 2 files changed, 121 insertions(+), 40 deletions(-)
>
> diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
> index a4cd8f891a090..542b09118a09f 100644
> --- a/include/linux/maple_tree.h
> +++ b/include/linux/maple_tree.h
> @@ -467,6 +467,7 @@ void mas_destroy(struct ma_state *mas);
> int mas_expected_entries(struct ma_state *mas, unsigned long nr_entries);
>
> void *mas_prev(struct ma_state *mas, unsigned long min);
> +void *mas_prev_range(struct ma_state *mas, unsigned long max);
> void *mas_next(struct ma_state *mas, unsigned long max);
> void *mas_next_range(struct ma_state *mas, unsigned long max);
>
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index e050fd1f7cce8..f060c71965c0d 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -5924,18 +5924,8 @@ void *mt_next(struct maple_tree *mt, unsigned long index, unsigned long max)
> }
> EXPORT_SYMBOL_GPL(mt_next);
>
> -/**
> - * mas_prev() - Get the previous entry
> - * @mas: The maple state
> - * @min: The minimum value to check.
> - *
> - * Must hold rcu_read_lock or the write lock.
> - * Will reset mas to MAS_START if the node is MAS_NONE. Will stop on not
> - * searchable nodes.
> - *
> - * Return: the previous value or %NULL.
> - */
> -void *mas_prev(struct ma_state *mas, unsigned long min)
> +static inline bool mas_prev_setup(struct ma_state *mas, unsigned long min,
> + void **entry)
> {
> if (mas->index <= min)
> goto none;
> @@ -5953,7 +5943,8 @@ void *mas_prev(struct ma_state *mas, unsigned long min)
> if (!mas->index)
> goto none;
> mas->index = mas->last = 0;
> - return mas_root(mas);
> + *entry = mas_root(mas);
> + return true;
> }
>
> if (mas_is_none(mas)) {
> @@ -5961,18 +5952,64 @@ void *mas_prev(struct ma_state *mas, unsigned long min)
> /* Walked to out-of-range pointer? */
> mas->index = mas->last = 0;
> mas->node = MAS_ROOT;
> - return mas_root(mas);
> + *entry = mas_root(mas);
> + return true;
> }
> - return NULL;
> + return true;
> }
> - return mas_prev_slot(mas, min, false);
> +
> + return false;
>
> none:
> mas->node = MAS_NONE;
> - return NULL;
> + return true;
> +}
> +
> +/**
> + * mas_prev() - Get the previous entry
> + * @mas: The maple state
> + * @min: The minimum value to check.
> + *
> + * Must hold rcu_read_lock or the write lock.
> + * Will reset mas to MAS_START if the node is MAS_NONE. Will stop on not
> + * searchable nodes.
> + *
> + * Return: the previous value or %NULL.
> + */
> +void *mas_prev(struct ma_state *mas, unsigned long min)
> +{
> + void *entry = NULL;
> +
> + if (mas_prev_setup(mas, min, &entry))
> + return entry;
> +
> + return mas_prev_slot(mas, min, false);
> }
> EXPORT_SYMBOL_GPL(mas_prev);
>
> +/**
> + * mas_prev_range() - Advance to the previous range
> + * @mas: The maple state
> + * @min: The minimum value to check.
> + *
> + * Sets @mas->index and @mas->last to the range.
> + * Must hold rcu_read_lock or the write lock.
> + * Will reset mas to MAS_START if the node is MAS_NONE. Will stop on not
> + * searchable nodes.
> + *
> + * Return: the previous value or %NULL.
> + */
> +void *mas_prev_range(struct ma_state *mas, unsigned long min)
> +{
> + void *entry = NULL;
> +
> + if (mas_prev_setup(mas, min, &entry))
> + return entry;
> +
> + return mas_prev_slot(mas, min, true);
> +}
> +EXPORT_SYMBOL_GPL(mas_prev_slot);
Hi Liam,
I guess you want to export mas_prev_range symbol instead of mas_prev_slot.
> +
> /**
> * mt_prev() - get the previous value in the maple tree
> * @mt: The maple tree
> @@ -6116,20 +6153,15 @@ void *mas_find_range(struct ma_state *mas, unsigned long max)
> EXPORT_SYMBOL_GPL(mas_find_range);
>
> /**
> - * mas_find_rev: On the first call, find the first non-null entry at or below
> - * mas->index down to %min. Otherwise find the first non-null entry below
> - * mas->index down to %min.
> - * @mas: The maple state
> - * @min: The minimum value to check.
> + * mas_find_rev_setup() - Internal function to set up mas_find_*_rev()
> *
> - * Must hold rcu_read_lock or the write lock.
> - * If an entry exists, last and index are updated accordingly.
> - * May set @mas->node to MAS_NONE.
> - *
> - * Return: The entry or %NULL.
> + * Returns: True if entry is the answer, false otherwise.
> */
> -void *mas_find_rev(struct ma_state *mas, unsigned long min)
> +static inline bool mas_find_rev_setup(struct ma_state *mas, unsigned long min,
> + void **entry)
> {
> + *entry = NULL;
> +
> if (unlikely(mas_is_none(mas))) {
> if (mas->index <= min)
> goto none;
> @@ -6141,7 +6173,7 @@ void *mas_find_rev(struct ma_state *mas, unsigned long min)
> if (unlikely(mas_is_paused(mas))) {
> if (unlikely(mas->index <= min)) {
> mas->node = MAS_NONE;
> - return NULL;
> + return true;
> }
> mas->node = MAS_START;
> mas->last = --mas->index;
> @@ -6149,14 +6181,12 @@ void *mas_find_rev(struct ma_state *mas, unsigned long min)
>
> if (unlikely(mas_is_start(mas))) {
> /* First run or continue */
> - void *entry;
> -
> if (mas->index < min)
> - return NULL;
> + return true;
>
> - entry = mas_walk(mas);
> - if (entry)
> - return entry;
> + *entry = mas_walk(mas);
> + if (*entry)
> + return true;
> }
>
> if (unlikely(!mas_searchable(mas))) {
> @@ -6170,22 +6200,72 @@ void *mas_find_rev(struct ma_state *mas, unsigned long min)
> */
> mas->last = mas->index = 0;
> mas->node = MAS_ROOT;
> - return mas_root(mas);
> + *entry = mas_root(mas);
> + return true;
> }
> }
>
> if (mas->index < min)
> - return NULL;
> + return true;
>
> - /* Retries on dead nodes handled by mas_prev_slot */
> - return mas_prev_slot(mas, min, false);
> + return false;
>
> none:
> mas->node = MAS_NONE;
> - return NULL;
> + return true;
> +}
> +
> +/**
> + * mas_find_rev: On the first call, find the first non-null entry at or below
> + * mas->index down to %min. Otherwise find the first non-null entry below
> + * mas->index down to %min.
> + * @mas: The maple state
> + * @min: The minimum value to check.
> + *
> + * Must hold rcu_read_lock or the write lock.
> + * If an entry exists, last and index are updated accordingly.
> + * May set @mas->node to MAS_NONE.
> + *
> + * Return: The entry or %NULL.
> + */
> +void *mas_find_rev(struct ma_state *mas, unsigned long min)
> +{
> + void *entry;
> +
> + if (mas_find_rev_setup(mas, min, &entry))
> + return entry;
> +
> + /* Retries on dead nodes handled by mas_prev_slot */
> + return mas_prev_slot(mas, min, false);
> +
> }
> EXPORT_SYMBOL_GPL(mas_find_rev);
>
> +/**
> + * mas_find_range_rev: On the first call, find the first non-null entry at or
> + * below mas->index down to %min. Otherwise advance to the previous slot after
> + * mas->index down to %min.
> + * @mas: The maple state
> + * @min: The minimum value to check.
> + *
> + * Must hold rcu_read_lock or the write lock.
> + * If an entry exists, last and index are updated accordingly.
> + * May set @mas->node to MAS_NONE.
> + *
> + * Return: The entry or %NULL.
> + */
> +void *mas_find_range_rev(struct ma_state *mas, unsigned long min)
> +{
> + void *entry;
> +
> + if (mas_find_rev_setup(mas, min, &entry))
> + return entry;
> +
> + /* Retries on dead nodes handled by mas_prev_slot */
> + return mas_prev_slot(mas, min, true);
> +}
> +EXPORT_SYMBOL_GPL(mas_find_range_rev);
> +
> /**
> * mas_erase() - Find the range in which index resides and erase the entire
> * range.
>
> --
> 2.39.2
>
