5  * Maple Tree - An RCU-safe adaptive tree for storing ranges
17  * Allocated nodes are mutable until they have been inserted into the tree,
19  * from the tree and an RCU grace period has passed.
25  * Nodes in the tree point to their parent unless bit 0 is set.
45  * is a pointer to the tree itself.  No more bits are available in this pointer
49  * parent pointer is 256B aligned like all other tree nodes.  When storing a 32
56  * type is done by examining the immutable tree flag for the MAPLE_ALLOC_RANGE
96  * In regular B-Tree terms, pivots are called keys.  The term pivot is used to
97  * indicate that the tree is specifying ranges,  Pivots may appear in the
99  * specific position of a B-tree.  Pivot values are inclusive of the slot with
116  * At tree creation time, the user can specify that they're willing to trade off
117  * storing fewer entries in a tree in return for storing more information in
120  * The maple tree supports recording the largest range of NULL entries available
121  * in this node, also called gaps.  This optimises the tree for allocating a
153  * DOC: Maple tree flags
155  * * MT_FLAGS_ALLOC_RANGE	- Track gaps in this tree
157  * * MT_FLAGS_HEIGHT_OFFSET	- The position of the tree height in the flags
158  * * MT_FLAGS_HEIGHT_MASK	- The mask for the maple tree height value
205  * If the tree contains a single entry at index 0, it is usually stored in
206  * tree->ma_root.  To optimise for the page cache, an entry which ends in '00',
210  * The flags are used both to store some immutable information about this tree
211  * (set at tree creation time) and dynamic information set under the spinlock.
213  * Another use of flags are to indicate global states of the tree.  This is the
214  * case with the MAPLE_USE_RCU flag, which indicates the tree is currently in
215  * RCU mode.  This mode was added to allow the tree to reuse nodes instead of
228  * MTREE_INIT() - Initialize a maple tree
229  * @name: The maple tree name
230  * @__flags: The maple tree flags
240  * MTREE_INIT_EXT() - Initialize a maple tree with an external lock.
241  * @name: The tree name
242  * @__flags: The maple tree flags
264  * The Maple Tree squeezes various bits in at various points which aren't
302  * potentially alter the height of the tree.  Either half of the tree may need
304  * which nodes have been 'cut' from the tree so that the change can be done
339  * mtree_empty() - Determine if a tree has any present entries.
340  * @mt: Maple Tree.
343  * Return: %true if the tree contains only NULL pointers.
355  * continue operating on the tree.
356  * ma_start means we have not searched the tree.
357  * ma_root means we have searched the tree and the entry we found lives in
358  * the root of the tree (ie it has index 0, length 1 and is the only entry in
359  * the tree).
360  * ma_none means we have searched the tree and there is no node in the
361  * tree for this entry.  For example, we searched for index 1 in an empty
362  * tree.  Or we have a tree which points to a full leaf node and we
387  * If state->node has bit 0 set then it references a tree location which is not
413  * Maple Tree.
417  * should start at the root of the tree and walk down.  If the status is
423 	struct maple_tree *tree;	/* The tree we're operating in */  member
431 	unsigned char depth;		/* depth of tree descent during write */
451 #define mas_lock(mas)           spin_lock(&((mas)->tree->ma_lock))
453 		spin_lock_nested(&((mas)->tree->ma_lock), subclass)
454 #define mas_unlock(mas)         spin_unlock(&((mas)->tree->ma_lock))
460  * top of the tree as the tree may have been modified.
467 		.tree = mt,						\
485 #define MA_TOPIARY(name, tree)						\  argument
489 		.mtree = tree,						\
523 static inline void mas_init(struct ma_state *mas, struct maple_tree *tree,  in mas_init()  argument
527 	mas->tree = tree;  in mas_init()
545  * mas_reset() - Reset a Maple Tree operation state.
546  * @mas: Maple Tree operation state.
561  * mas_for_each() - Iterate over a range of the maple tree.
562  * @__mas: Maple Tree operation state (maple_state)
563  * @__entry: Entry retrieved from the tree
564  * @__max: maximum index to retrieve from the tree
609 		mt_dump((__mas)->tree, mt_dump_hex);			\
626 		mt_dump((__wrmas)->mas->tree, mt_dump_hex);		\
660 		mt_dump((__mas)->tree, mt_dump_hex);			\
679 		mt_dump((__wrmas)->mas->tree, mt_dump_hex);		\
699  * __mas_set_range() - Set up Maple Tree operation state to a sub-range of the
701  * @mas: Maple Tree operation state.
702  * @start: New start of range in the Maple Tree.
703  * @last: New end of range in the Maple Tree.
706  * Please use mas_set_range() if you do not know where you are in the tree.
719  * mas_set_range() - Set up Maple Tree operation state for a different index.
720  * @mas: Maple Tree operation state.
721  * @start: New start of range in the Maple Tree.
722  * @last: New end of range in the Maple Tree.
736  * mas_set() - Set up Maple Tree operation state for a different index.
737  * @mas: Maple Tree operation state.
738  * @index: New index into the Maple Tree.
756  * mt_init_flags() - Initialise an empty maple tree with flags.
757  * @mt: Maple Tree
758  * @flags: maple tree flags.
760  * If you need to initialise a Maple Tree with special flags (eg, an
761  * allocation tree), use this function.
774  * mt_init() - Initialise an empty maple tree.
775  * @mt: Maple Tree
777  * An empty Maple Tree.
795  * mt_clear_in_rcu() - Switch the tree to non-RCU mode.
796  * @mt: The Maple Tree
814  * mt_set_in_rcu() - Switch the tree to RCU safe mode.
815  * @mt: The Maple Tree
845  * @__tree: The Maple Tree