diff options
| -rw-r--r-- | include/linux/maple_tree.h | 3 | ||||
| -rw-r--r-- | 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 205664f46e58..41c152718000 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4793,13 +4793,10 @@ again: */ 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); } /* @@ -5880,18 +5877,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); @@ -5899,25 +5886,72 @@ 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 * @index: The start index @@ -6026,49 +6060,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; } @@ -6076,24 +6102,70 @@ 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 * mas->index down to %min. |