[PATCH v4 28/35] maple_tree: Add mas_next_range() and mas_find_range() interfaces
From: Liam R. Howlett
Date: Thu May 18 2023 - 15:52:25 EST
Some users of the maple tree may want to move to the next range in the
tree, even if it stores a NULL. This family of function provides that
functionality by advancing one slot at a time and returning the result,
while mas_contiguous() will iterate over the range and stop on
encountering the first NULL.
Signed-off-by: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>
---
include/linux/maple_tree.h | 3 +-
lib/maple_tree.c | 172 ++++++++++++++++++++++++++-----------
2 files changed, 124 insertions(+), 51 deletions(-)
diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
index ed92abf4c1fb..9d040043858a 100644
--- a/include/linux/maple_tree.h
+++ b/include/linux/maple_tree.h
@@ -455,6 +455,7 @@ void *mas_erase(struct ma_state *mas);
int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp);
void mas_store_prealloc(struct ma_state *mas, void *entry);
void *mas_find(struct ma_state *mas, unsigned long max);
+void *mas_find_range(struct ma_state *mas, unsigned long max);
void *mas_find_rev(struct ma_state *mas, unsigned long min);
int mas_preallocate(struct ma_state *mas, gfp_t gfp);
bool mas_is_err(struct ma_state *mas);
@@ -467,6 +468,7 @@ int mas_expected_entries(struct ma_state *mas, unsigned long nr_entries);
void *mas_prev(struct ma_state *mas, unsigned long min);
void *mas_next(struct ma_state *mas, unsigned long max);
+void *mas_next_range(struct ma_state *mas, unsigned long max);
int mas_empty_area(struct ma_state *mas, unsigned long min, unsigned long max,
unsigned long size);
@@ -528,7 +530,6 @@ static inline void mas_reset(struct ma_state *mas)
#define mas_for_each(__mas, __entry, __max) \
while (((__entry) = mas_find((__mas), (__max))) != NULL)
-
/**
* mas_set_range() - Set up Maple Tree operation state for a different index.
* @mas: Maple Tree operation state.
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 860f82e16166..b5df37be7a15 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4792,13 +4792,10 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty)
*/
static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit)
{
- void *entry = NULL;
-
if (mas->last >= limit)
return NULL;
- entry = mas_next_slot(mas, limit, false);
- return entry;
+ return mas_next_slot(mas, limit, false);
}
/*
@@ -5885,18 +5882,8 @@ int mas_expected_entries(struct ma_state *mas, unsigned long nr_entries)
}
EXPORT_SYMBOL_GPL(mas_expected_entries);
-/**
- * mas_next() - Get the next entry.
- * @mas: The maple state
- * @max: The maximum index to check.
- *
- * Returns the next entry after @mas->index.
- * Must hold rcu_read_lock or the write lock.
- * Can return the zero entry.
- *
- * Return: The next entry or %NULL
- */
-void *mas_next(struct ma_state *mas, unsigned long max)
+static inline bool mas_next_setup(struct ma_state *mas, unsigned long max,
+ void **entry)
{
bool was_none = mas_is_none(mas);
@@ -5904,24 +5891,71 @@ void *mas_next(struct ma_state *mas, unsigned long max)
mas->node = MAS_START;
if (mas_is_start(mas))
- mas_walk(mas); /* Retries on dead nodes handled by mas_walk */
+ *entry = mas_walk(mas); /* Retries on dead nodes handled by mas_walk */
if (mas_is_ptr(mas)) {
+ *entry = NULL;
if (was_none && mas->index == 0) {
mas->index = mas->last = 0;
- return mas_root(mas);
+ return true;
}
mas->index = 1;
mas->last = ULONG_MAX;
mas->node = MAS_NONE;
- return NULL;
+ return true;
}
- /* Retries on dead nodes handled by mas_next_entry */
- return mas_next_entry(mas, max);
+ if (mas_is_none(mas))
+ return true;
+ return false;
+}
+
+/**
+ * mas_next() - Get the next entry.
+ * @mas: The maple state
+ * @max: The maximum index to check.
+ *
+ * Returns the next entry after @mas->index.
+ * Must hold rcu_read_lock or the write lock.
+ * Can return the zero entry.
+ *
+ * Return: The next entry or %NULL
+ */
+void *mas_next(struct ma_state *mas, unsigned long max)
+{
+ void *entry = NULL;
+
+ if (mas_next_setup(mas, max, &entry))
+ return entry;
+
+ /* Retries on dead nodes handled by mas_next_slot */
+ return mas_next_slot(mas, max, false);
}
EXPORT_SYMBOL_GPL(mas_next);
+/**
+ * mas_next_range() - Advance the maple state to the next range
+ * @mas: The maple state
+ * @max: The maximum index to check.
+ *
+ * Sets @mas->index and @mas->last to the range.
+ * Must hold rcu_read_lock or the write lock.
+ * Can return the zero entry.
+ *
+ * Return: The next entry or %NULL
+ */
+void *mas_next_range(struct ma_state *mas, unsigned long max)
+{
+ void *entry = NULL;
+
+ if (mas_next_setup(mas, max, &entry))
+ return entry;
+
+ /* Retries on dead nodes handled by mas_next_slot */
+ return mas_next_slot(mas, max, true);
+}
+EXPORT_SYMBOL_GPL(mas_next_range);
+
/**
* mt_next() - get the next value in the maple tree
* @mt: The maple tree
@@ -6031,49 +6065,41 @@ void mas_pause(struct ma_state *mas)
EXPORT_SYMBOL_GPL(mas_pause);
/**
- * mas_find() - On the first call, find the entry at or after mas->index up to
- * %max. Otherwise, find the entry after mas->index.
+ * mas_find_setup() - Internal function to set up mas_find*().
* @mas: The maple state
- * @max: The maximum 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.
+ * @max: The maximum index
+ * @entry: Pointer to the entry
*
- * Return: The entry or %NULL.
+ * Returns: True if entry is the answer, false otherwise.
*/
-void *mas_find(struct ma_state *mas, unsigned long max)
+static inline bool mas_find_setup(struct ma_state *mas, unsigned long max,
+ void **entry)
{
+ *entry = NULL;
+
if (unlikely(mas_is_none(mas))) {
if (unlikely(mas->last >= max))
- return NULL;
+ return true;
mas->index = mas->last;
mas->node = MAS_START;
- }
-
- if (unlikely(mas_is_paused(mas))) {
+ } else if (unlikely(mas_is_paused(mas))) {
if (unlikely(mas->last >= max))
- return NULL;
+ return true;
mas->node = MAS_START;
mas->index = ++mas->last;
- }
-
-
- if (unlikely(mas_is_ptr(mas)))
+ } else if (unlikely(mas_is_ptr(mas)))
goto ptr_out_of_range;
if (unlikely(mas_is_start(mas))) {
/* First run or continue */
- void *entry;
-
if (mas->index > max)
- return NULL;
+ return true;
- entry = mas_walk(mas);
- if (entry)
- return entry;
+ *entry = mas_walk(mas);
+ if (*entry)
+ return true;
}
@@ -6081,23 +6107,69 @@ void *mas_find(struct ma_state *mas, unsigned long max)
if (unlikely(mas_is_ptr(mas)))
goto ptr_out_of_range;
- return NULL;
+ return true;
}
if (mas->index == max)
- return NULL;
+ return true;
- /* Retries on dead nodes handled by mas_next_slot */
- return mas_next_slot(mas, max, false);
+ return false;
ptr_out_of_range:
mas->node = MAS_NONE;
mas->index = 1;
mas->last = ULONG_MAX;
- return NULL;
+ return true;
+}
+
+/**
+ * mas_find() - On the first call, find the entry at or after mas->index up to
+ * %max. Otherwise, find the entry after mas->index.
+ * @mas: The maple state
+ * @max: The maximum 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(struct ma_state *mas, unsigned long max)
+{
+ void *entry = NULL;
+
+ if (mas_find_setup(mas, max, &entry))
+ return entry;
+
+ /* Retries on dead nodes handled by mas_next_slot */
+ return mas_next_slot(mas, max, false);
}
EXPORT_SYMBOL_GPL(mas_find);
+/**
+ * mas_find_range() - On the first call, find the entry at or after
+ * mas->index up to %max. Otherwise, advance to the next slot mas->index.
+ * @mas: The maple state
+ * @max: The maximum 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(struct ma_state *mas, unsigned long max)
+{
+ void *entry;
+
+ if (mas_find_setup(mas, max, &entry))
+ return entry;
+
+ /* Retries on dead nodes handled by mas_next_slot */
+ return mas_next_slot(mas, max, true);
+}
+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
--
2.39.2