diff options
author | 2017-11-09 09:23:56 -0500 | |
---|---|---|
committer | 2018-10-21 10:45:56 -0400 | |
commit | 01959dfe771c6893365482ec78dc1d9cbbbe6de8 (patch) | |
tree | 6d6a47f561798ae0ec49c44c55e2334068c97c14 /include/linux/xarray.h | |
parent | xarray: Add definition of struct xarray (diff) | |
download | linux-01959dfe771c6893365482ec78dc1d9cbbbe6de8.tar.gz linux-01959dfe771c6893365482ec78dc1d9cbbbe6de8.tar.bz2 linux-01959dfe771c6893365482ec78dc1d9cbbbe6de8.zip |
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.h | 27 |
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) |