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  * range type is done by examining the immutable tree flag for the
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
165  * DOC: Maple tree flags
167  * * MT_FLAGS_ALLOC_RANGE	- Track gaps in this tree
169  * * MT_FLAGS_HEIGHT_OFFSET	- The position of the tree height in the flags
170  * * MT_FLAGS_HEIGHT_MASK	- The mask for the maple tree height value
218  * If the tree contains a single entry at index 0, it is usually stored in
219  * tree->ma_root.  To optimise for the page cache, an entry which ends in '00',
223  * The flags are used both to store some immutable information about this tree
224  * (set at tree creation time) and dynamic information set under the spinlock.
226  * Another use of flags are to indicate global states of the tree.  This is the
227  * case with the MAPLE_USE_RCU flag, which indicates the tree is currently in
228  * RCU mode.  This mode was added to allow the tree to reuse nodes instead of
241  * MTREE_INIT() - Initialize a maple tree
242  * @name: The maple tree name
243  * @__flags: The maple tree flags
253  * MTREE_INIT_EXT() - Initialize a maple tree with an external lock.
254  * @name: The tree name
255  * @__flags: The maple tree flags
277  * The Maple Tree squeezes various bits in at various points which aren't
315  * potentially alter the height of the tree.  Either half of the tree may need
317  * which nodes have been 'cut' from the tree so that the change can be done
355  * mtree_empty() - Determine if a tree has any present entries.
356  * @mt: Maple Tree.
359  * Return: %true if the tree contains only NULL pointers.
371  * continue operating on the tree.
372  * ma_start means we have not searched the tree.
373  * ma_root means we have searched the tree and the entry we found lives in
374  * the root of the tree (ie it has index 0, length 1 and is the only entry in
375  * the tree).
376  * ma_none means we have searched the tree and there is no node in the
377  * tree for this entry.  For example, we searched for index 1 in an empty
378  * tree.  Or we have a tree which points to a full leaf node and we
403  * If state->node has bit 0 set then it references a tree location which is not
429  * Maple Tree.
433  * should start at the root of the tree and walk down.  If the status is
439 	struct maple_tree *tree;	/* The tree we're operating in */  member
447 	unsigned char depth;		/* depth of tree descent during write */
468 #define mas_lock(mas)           spin_lock(&((mas)->tree->ma_lock))
470 		spin_lock_nested(&((mas)->tree->ma_lock), subclass)
471 #define mas_unlock(mas)         spin_unlock(&((mas)->tree->ma_lock))
477  * top of the tree as the tree may have been modified.
484 		.tree = mt,						\
503 #define MA_TOPIARY(name, tree)						\  argument
507 		.mtree = tree,						\
544 static inline void mas_init(struct ma_state *mas, struct maple_tree *tree,  in mas_init()  argument
548 	mas->tree = tree;  in mas_init()
566  * mas_reset() - Reset a Maple Tree operation state.
567  * @mas: Maple Tree operation state.
582  * mas_for_each() - Iterate over a range of the maple tree.
583  * @__mas: Maple Tree operation state (maple_state)
584  * @__entry: Entry retrieved from the tree
585  * @__max: maximum index to retrieve from the tree
630 		mt_dump((__mas)->tree, mt_dump_hex);			\
647 		mt_dump((__wrmas)->mas->tree, mt_dump_hex);		\
681 		mt_dump((__mas)->tree, mt_dump_hex);			\
700 		mt_dump((__wrmas)->mas->tree, mt_dump_hex);		\
720  * __mas_set_range() - Set up Maple Tree operation state to a sub-range of the
722  * @mas: Maple Tree operation state.
723  * @start: New start of range in the Maple Tree.
724  * @last: New end of range in the Maple Tree.
727  * Please use mas_set_range() if you do not know where you are in the tree.
740  * mas_set_range() - Set up Maple Tree operation state for a different index.
741  * @mas: Maple Tree operation state.
742  * @start: New start of range in the Maple Tree.
743  * @last: New end of range in the Maple Tree.
757  * mas_set() - Set up Maple Tree operation state for a different index.
758  * @mas: Maple Tree operation state.
759  * @index: New index into the Maple Tree.
777  * mt_init_flags() - Initialise an empty maple tree with flags.
778  * @mt: Maple Tree
779  * @flags: maple tree flags.
781  * If you need to initialise a Maple Tree with special flags (eg, an
782  * allocation tree), use this function.
795  * mt_init() - Initialise an empty maple tree.
796  * @mt: Maple Tree
798  * An empty Maple Tree.
816  * mt_clear_in_rcu() - Switch the tree to non-RCU mode.
817  * @mt: The Maple Tree
835  * mt_set_in_rcu() - Switch the tree to RCU safe mode.
836  * @mt: The Maple Tree
866  * @__tree: The Maple Tree