[PATCH 30/62] xarray: Add xas_find_any / xas_next_any

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@xxxxxxxxxxxxx>

These variations will find any entry (whether it be NULL or an internal
entry).  The only thing they won't return is a node pointer (because it
will walk down the tree).  xas_next_any() is an inline version of
xas_find_any() which avoids making a function call for the common cases.

Signed-off-by: Matthew Wilcox <mawilcox@xxxxxxxxxxxxx>
---
 include/linux/xarray.h | 25 +++++++++++++++++++++++++
 lib/xarray.c           | 51 ++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 76 insertions(+)

diff --git a/include/linux/xarray.h b/include/linux/xarray.h
index e0cfe6944752..8ab6c4468c21 100644
--- a/include/linux/xarray.h
+++ b/include/linux/xarray.h
@@ -466,6 +466,7 @@ void *xas_load(struct xarray *, struct xa_state *);
 void *xas_store(struct xarray *, struct xa_state *, void *entry);
 void *xas_create(struct xarray *, struct xa_state *);
 void *xas_find(struct xarray *, struct xa_state *, unsigned long max);
+void *xas_find_any(struct xarray *, struct xa_state *);
 void *xas_prev_any(struct xarray *, struct xa_state *);
 
 bool xas_get_tag(const struct xarray *, const struct xa_state *, xa_tag_t);
@@ -540,6 +541,30 @@ static inline bool xa_iter_skip(void *entry)
 			(xa_is_internal(entry) && entry < XA_RETRY_ENTRY));
 }
 
+/**
+ * xas_next_any() - Advance iterator to next entry of any kind.
+ * @xa: XArray.
+ * @xas: XArray operation state.
+ *
+ * xas_next_any() is an inline function to optimise xarray traversal for speed.
+ * It is equivalent to calling xas_find_any(), and will call xas_find_any()
+ * for all the hard cases.
+ *
+ * Return: The next entry after the one currently referred to by @xas.
+ */
+static inline void *xas_next_any(struct xarray *xa, 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_find_any(xa, xas);
+
+	xas->xa_index++;
+	xas->xa_offset++;
+	return xa_entry(xa, node, xas->xa_offset);
+}
+
 /**
  * xas_next() - Advance iterator to next present entry.
  * @xa: XArray.
diff --git a/lib/xarray.c b/lib/xarray.c
index 202e5aae596d..38e5fe39bb97 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -805,6 +805,57 @@ void xas_pause(struct xa_state *xas)
 }
 EXPORT_SYMBOL_GPL(xas_pause);
 
+/**
+ * xas_find_any() - Find the next entry in the XArray.
+ * @xa: XArray.
+ * @xas: XArray operation state.
+ *
+ * If the xas has not yet been walked to an entry, return the entry
+ * which has an index >= xas.xa_index.  If it has been walked, the entry
+ * currently being pointed at has been processed, and so we move to the
+ * next entry.
+ *
+ * Return: The entry at that location.
+ */
+void *xas_find_any(struct xarray *xa, struct xa_state *xas)
+{
+	void *entry;
+
+	if (xas_error(xas))
+		return NULL;
+
+	if (xas->xa_node == XAS_RESTART) {
+		return xas_load(xa, xas);
+	} else if (!xas->xa_node) {
+		xas->xa_index = 1;
+		xas->xa_node = XAS_RESTART;
+		return NULL;
+	}
+
+	xas->xa_index = next_index(xas->xa_index, xas->xa_node);
+	xas->xa_offset++;
+
+	while (xas->xa_node) {
+		if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) {
+			xas->xa_offset = xas->xa_node->offset + 1;
+			xas->xa_node = xa_parent(xa, xas->xa_node);
+			continue;
+		}
+
+		entry = xa_entry(xa, xas->xa_node, xas->xa_offset);
+		if (!xa_is_node(entry))
+			return entry;
+
+		xas->xa_node = xa_to_node(entry);
+		xas->xa_offset = 0;
+	}
+
+	if (!xas->xa_node)
+		xas->xa_node = XAS_RESTART;
+	return NULL;
+}
+EXPORT_SYMBOL_GPL(xas_find_any);
+
 /**
  * xas_find() - Find the next present entry in the XArray.
  * @xa: XArray.
-- 
2.15.0