summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/maple_tree.c161
1 files changed, 122 insertions, 39 deletions
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 9c7e765c809d..59c15f8b4793 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5919,18 +5919,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;
@@ -5948,7 +5938,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)) {
@@ -5956,19 +5947,65 @@ 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_range);
+
+/**
* mt_prev() - get the previous value in the maple tree
* @mt: The maple tree
* @index: The start index
@@ -6114,20 +6151,18 @@ 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_find_rev_setup() - Internal function to set up mas_find_*_rev()
* @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.
+ * @min: The minimum index
+ * @entry: Pointer to the entry
*
- * 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;
@@ -6139,7 +6174,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;
@@ -6147,14 +6182,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))) {
@@ -6168,23 +6201,73 @@ 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.
* @mas: The maple state
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-17 11:19:00 +0000