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
262  * The Maple Tree squeezes various bits in at various points which aren't
300  * potentially alter the height of the tree.  Either half of the tree may need
302  * which nodes have been 'cut' from the tree so that the change can be done
334  * mtree_empty() - Determine if a tree has any present entries.
335  * @mt: Maple Tree.
338  * Return: %true if the tree contains only NULL pointers.
352  * If state->node has bit 0 set then it references a tree location which is not
378  * Maple Tree.
381 	struct maple_tree *tree;	/* The tree we're operating in */  member
388 	unsigned char depth;		/* depth of tree descent during write */
408 #define mas_lock(mas)           spin_lock(&((mas)->tree->ma_lock))
409 #define mas_unlock(mas)         spin_unlock(&((mas)->tree->ma_lock))
414  * MAS_START means we have not searched the tree.
415  * MAS_ROOT means we have searched the tree and the entry we found lives in
416  * the root of the tree (ie it has index 0, length 1 and is the only entry in
417  * the tree).
418  * MAS_NONE means we have searched the tree and there is no node in the
419  * tree for this entry.  For example, we searched for index 1 in an empty
420  * tree.  Or we have a tree which points to a full leaf node and we
425  * top of the tree as the tree may have been modified.
438 		.tree = mt,						\
455 #define MA_TOPIARY(name, tree)						\  argument
459 		.mtree = tree,						\
494 static inline void mas_init(struct ma_state *mas, struct maple_tree *tree,  in mas_init()  argument
498 	mas->tree = tree;  in mas_init()
526  * mas_reset() - Reset a Maple Tree operation state.
527  * @mas: Maple Tree operation state.
541  * mas_for_each() - Iterate over a range of the maple tree.
542  * @__mas: Maple Tree operation state (maple_state)
543  * @__entry: Entry retrieved from the tree
544  * @__max: maximum index to retrieve from the tree
554  * __mas_set_range() - Set up Maple Tree operation state to a sub-range of the
556  * @mas: Maple Tree operation state.
557  * @start: New start of range in the Maple Tree.
558  * @last: New end of range in the Maple Tree.
561  * Please use mas_set_range() if you do not know where you are in the tree.
571  * mas_set_range() - Set up Maple Tree operation state for a different index.
572  * @mas: Maple Tree operation state.
573  * @start: New start of range in the Maple Tree.
574  * @last: New end of range in the Maple Tree.
588  * mas_set() - Set up Maple Tree operation state for a different index.
589  * @mas: Maple Tree operation state.
590  * @index: New index into the Maple Tree.
608  * mt_init_flags() - Initialise an empty maple tree with flags.
609  * @mt: Maple Tree
610  * @flags: maple tree flags.
612  * If you need to initialise a Maple Tree with special flags (eg, an
613  * allocation tree), use this function.
626  * mt_init() - Initialise an empty maple tree.
627  * @mt: Maple Tree
629  * An empty Maple Tree.
647  * mt_clear_in_rcu() - Switch the tree to non-RCU mode.
648  * @mt: The Maple Tree
666  * mt_set_in_rcu() - Switch the tree to RCU safe mode.
667  * @mt: The Maple Tree
697  * @__tree: The Maple Tree
745 		mt_dump((__mas)->tree, mt_dump_hex);			\
762 		mt_dump((__wrmas)->mas->tree, mt_dump_hex);		\
796 		mt_dump((__mas)->tree, mt_dump_hex);			\
815 		mt_dump((__wrmas)->mas->tree, mt_dump_hex);		\