summaryrefslogtreecommitdiff
path: root/include/linux/xarray.h
diff options
context:
space:
mode:
authorMatthew Wilcox <willy@infradead.org>2017-11-09 09:23:56 -0500
committerMatthew Wilcox <willy@infradead.org>2018-10-21 10:45:56 -0400
commit01959dfe771c6893365482ec78dc1d9cbbbe6de8 (patch)
tree6d6a47f561798ae0ec49c44c55e2334068c97c14 /include/linux/xarray.h
parentf8d5d0cc145cc21bfc56ef807dc28102aebbf228 (diff)
xarray: Define struct xa_node
This is a direct replacement for struct radix_tree_node. A couple of struct members have changed name, so convert those. Use a #define so that radix tree users continue to work without change. Signed-off-by: Matthew Wilcox <willy@infradead.org> Reviewed-by: Josef Bacik <jbacik@fb.com>
Diffstat (limited to 'include/linux/xarray.h')
-rw-r--r--include/linux/xarray.h27
1 files changed, 27 insertions, 0 deletions
diff --git a/include/linux/xarray.h b/include/linux/xarray.h
index 9122cf8bf52a..52141dfc5a90 100644
--- a/include/linux/xarray.h
+++ b/include/linux/xarray.h
@@ -252,6 +252,33 @@ static inline void xa_init(struct xarray *xa)
#endif
#define XA_CHUNK_SIZE (1UL << XA_CHUNK_SHIFT)
#define XA_CHUNK_MASK (XA_CHUNK_SIZE - 1)
+#define XA_MAX_MARKS 3
+#define XA_MARK_LONGS DIV_ROUND_UP(XA_CHUNK_SIZE, BITS_PER_LONG)
+
+/*
+ * @count is the count of every non-NULL element in the ->slots array
+ * whether that is a value entry, a retry entry, a user pointer,
+ * a sibling entry or a pointer to the next level of the tree.
+ * @nr_values is the count of every element in ->slots which is
+ * either a value entry or a sibling of a value entry.
+ */
+struct xa_node {
+ unsigned char shift; /* Bits remaining in each slot */
+ unsigned char offset; /* Slot offset in parent */
+ unsigned char count; /* Total entry count */
+ unsigned char nr_values; /* Value entry count */
+ struct xa_node __rcu *parent; /* NULL at top of tree */
+ struct xarray *array; /* The array we belong to */
+ union {
+ struct list_head private_list; /* For tree user */
+ struct rcu_head rcu_head; /* Used when freeing node */
+ };
+ void __rcu *slots[XA_CHUNK_SIZE];
+ union {
+ unsigned long tags[XA_MAX_MARKS][XA_MARK_LONGS];
+ unsigned long marks[XA_MAX_MARKS][XA_MARK_LONGS];
+ };
+};
/* Private */
static inline bool xa_is_node(const void *entry)