diff options
author | Matthew Wilcox <willy@infradead.org> | 2017-11-14 16:42:22 -0500 |
---|---|---|
committer | Matthew Wilcox <willy@infradead.org> | 2018-10-21 10:45:58 -0400 |
commit | 80a0a1a9a3cde9b23851e8eb7160e2786549306a (patch) | |
tree | 9f90a533bb16d5f91407e6d04d102ea4dbca225e /lib | |
parent | b803b42823d0d9e8b6deccf01ffc2aba5d0738df (diff) | |
download | linux-stable-80a0a1a9a3cde9b23851e8eb7160e2786549306a.tar.gz linux-stable-80a0a1a9a3cde9b23851e8eb7160e2786549306a.tar.bz2 linux-stable-80a0a1a9a3cde9b23851e8eb7160e2786549306a.zip |
xarray: Extract entries from an XArray
The xa_extract function combines the functionality of
radix_tree_gang_lookup() and radix_tree_gang_lookup_tagged().
It extracts entries matching the specified filter into a normal array.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
Diffstat (limited to 'lib')
-rw-r--r-- | lib/xarray.c | 80 |
1 files changed, 80 insertions, 0 deletions
diff --git a/lib/xarray.c b/lib/xarray.c index 24494f42daa6..70e04810c8c2 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -1444,6 +1444,86 @@ void *xa_find_after(struct xarray *xa, unsigned long *indexp, } EXPORT_SYMBOL(xa_find_after); +static unsigned int xas_extract_present(struct xa_state *xas, void **dst, + unsigned long max, unsigned int n) +{ + void *entry; + unsigned int i = 0; + + rcu_read_lock(); + xas_for_each(xas, entry, max) { + if (xas_retry(xas, entry)) + continue; + dst[i++] = entry; + if (i == n) + break; + } + rcu_read_unlock(); + + return i; +} + +static unsigned int xas_extract_marked(struct xa_state *xas, void **dst, + unsigned long max, unsigned int n, xa_mark_t mark) +{ + void *entry; + unsigned int i = 0; + + rcu_read_lock(); + xas_for_each_marked(xas, entry, max, mark) { + if (xas_retry(xas, entry)) + continue; + dst[i++] = entry; + if (i == n) + break; + } + rcu_read_unlock(); + + return i; +} + +/** + * xa_extract() - Copy selected entries from the XArray into a normal array. + * @xa: The source XArray to copy from. + * @dst: The buffer to copy entries into. + * @start: The first index in the XArray eligible to be selected. + * @max: The last index in the XArray eligible to be selected. + * @n: The maximum number of entries to copy. + * @filter: Selection criterion. + * + * Copies up to @n entries that match @filter from the XArray. The + * copied entries will have indices between @start and @max, inclusive. + * + * The @filter may be an XArray mark value, in which case entries which are + * marked with that mark will be copied. It may also be %XA_PRESENT, in + * which case all entries which are not NULL will be copied. + * + * The entries returned may not represent a snapshot of the XArray at a + * moment in time. For example, if another thread stores to index 5, then + * index 10, calling xa_extract() may return the old contents of index 5 + * and the new contents of index 10. Indices not modified while this + * function is running will not be skipped. + * + * If you need stronger guarantees, holding the xa_lock across calls to this + * function will prevent concurrent modification. + * + * Context: Any context. Takes and releases the RCU lock. + * Return: The number of entries copied. + */ +unsigned int xa_extract(struct xarray *xa, void **dst, unsigned long start, + unsigned long max, unsigned int n, xa_mark_t filter) +{ + XA_STATE(xas, xa, start); + + if (!n) + return 0; + + if ((__force unsigned int)filter < XA_MAX_MARKS) + return xas_extract_marked(&xas, dst, max, n, filter); + return xas_extract_present(&xas, dst, max, n); +} +EXPORT_SYMBOL(xa_extract); + #ifdef XA_DEBUG void xa_dump_node(const struct xa_node *node) { |