diff options
author | Matthew Wilcox <willy@infradead.org> | 2017-12-01 00:06:52 -0500 |
---|---|---|
committer | Matthew Wilcox <willy@infradead.org> | 2018-10-21 10:45:59 -0400 |
commit | 64d3e9a9e0cc51957d243dd2b0adc5d74ff5e128 (patch) | |
tree | 2e829cc456ea717293f388f283e2c29242cb8df7 /include/linux/xarray.h | |
parent | 687149fca1f37c447e5d161e0a4a04cb2c880cb6 (diff) | |
download | linux-stable-64d3e9a9e0cc51957d243dd2b0adc5d74ff5e128.tar.gz linux-stable-64d3e9a9e0cc51957d243dd2b0adc5d74ff5e128.tar.bz2 linux-stable-64d3e9a9e0cc51957d243dd2b0adc5d74ff5e128.zip |
xarray: Step through an XArray
The xas_next and xas_prev functions move the xas index by one position,
and adjust the rest of the iterator state to match it. This is more
efficient than calling xas_set() as it keeps the iterator at the leaves
of the tree instead of walking the iterator from the root each time.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
Diffstat (limited to 'include/linux/xarray.h')
-rw-r--r-- | include/linux/xarray.h | 67 |
1 files changed, 67 insertions, 0 deletions
diff --git a/include/linux/xarray.h b/include/linux/xarray.h index 0a758fa3ed2c..381f94a66762 100644 --- a/include/linux/xarray.h +++ b/include/linux/xarray.h @@ -828,6 +828,12 @@ static inline bool xas_not_node(struct xa_node *node) return ((unsigned long)node & 3) || !node; } +/* True if the node represents RESTART or an error */ +static inline bool xas_frozen(struct xa_node *node) +{ + return (unsigned long)node & 2; +} + /* True if the node represents head-of-tree, RESTART or BOUNDS */ static inline bool xas_top(struct xa_node *node) { @@ -1082,4 +1088,65 @@ enum { for (entry = xas_find_marked(xas, max, mark); entry; \ entry = xas_next_marked(xas, max, mark)) +void *__xas_next(struct xa_state *); +void *__xas_prev(struct xa_state *); + +/** + * xas_prev() - Move iterator to previous index. + * @xas: XArray operation state. + * + * If the @xas was in an error state, it will remain in an error state + * and this function will return %NULL. If the @xas has never been walked, + * it will have the effect of calling xas_load(). Otherwise one will be + * subtracted from the index and the state will be walked to the correct + * location in the array for the next operation. + * + * If the iterator was referencing index 0, this function wraps + * around to %ULONG_MAX. + * + * Return: The entry at the new index. This may be %NULL or an internal + * entry. + */ +static inline void *xas_prev(struct xa_state *xas) +{ + struct xa_node *node = xas->xa_node; + + if (unlikely(xas_not_node(node) || node->shift || + xas->xa_offset == 0)) + return __xas_prev(xas); + + xas->xa_index--; + xas->xa_offset--; + return xa_entry(xas->xa, node, xas->xa_offset); +} + +/** + * xas_next() - Move state to next index. + * @xas: XArray operation state. + * + * If the @xas was in an error state, it will remain in an error state + * and this function will return %NULL. If the @xas has never been walked, + * it will have the effect of calling xas_load(). Otherwise one will be + * added to the index and the state will be walked to the correct + * location in the array for the next operation. + * + * If the iterator was referencing index %ULONG_MAX, this function wraps + * around to 0. + * + * Return: The entry at the new index. This may be %NULL or an internal + * entry. + */ +static inline void *xas_next(struct xa_state *xas) +{ + struct xa_node *node = xas->xa_node; + + if (unlikely(xas_not_node(node) || node->shift || + xas->xa_offset == XA_CHUNK_MASK)) + return __xas_next(xas); + + xas->xa_index++; + xas->xa_offset++; + return xa_entry(xas->xa, node, xas->xa_offset); +} + #endif /* _LINUX_XARRAY_H */ |