Lines Matching full:tree
5 * Maple Tree - An RCU-safe adaptive tree for storing ranges
18 * Allocated nodes are mutable until they have been inserted into the tree,
20 * from the tree and an RCU grace period has passed.
26 * Nodes in the tree point to their parent unless bit 0 is set.
48 * is a pointer to the tree itself. No more bits are available in this pointer
52 * parent pointer is 256B aligned like all other tree nodes. When storing a 32
59 * type is done by examining the immutable tree flag for the MAPLE_ALLOC_RANGE
99 * In regular B-Tree terms, pivots are called keys. The term pivot is used to
100 * indicate that the tree is specifying ranges, Pivots may appear in the
102 * specific position of a B-tree. Pivot values are inclusive of the slot with
119 * At tree creation time, the user can specify that they're willing to trade off
120 * storing fewer entries in a tree in return for storing more information in
123 * The maple tree supports recording the largest range of NULL entries available
124 * in this node, also called gaps. This optimises the tree for allocating a
156 * DOC: Maple tree flags
158 * * MT_FLAGS_ALLOC_RANGE - Track gaps in this tree
160 * * MT_FLAGS_HEIGHT_OFFSET - The position of the tree height in the flags
161 * * MT_FLAGS_HEIGHT_MASK - The mask for the maple tree height value
198 * If the tree contains a single entry at index 0, it is usually stored in
199 * tree->ma_root. To optimise for the page cache, an entry which ends in '00',
203 * The flags are used both to store some immutable information about this tree
204 * (set at tree creation time) and dynamic information set under the spinlock.
206 * Another use of flags are to indicate global states of the tree. This is the
207 * case with the MAPLE_USE_RCU flag, which indicates the tree is currently in
208 * RCU mode. This mode was added to allow the tree to reuse nodes instead of
221 * MTREE_INIT() - Initialize a maple tree
222 * @name: The maple tree name
223 * @__flags: The maple tree flags
233 * MTREE_INIT_EXT() - Initialize a maple tree with an external lock.
234 * @name: The tree name
235 * @__flags: The maple tree flags
255 * The Maple Tree squeezes various bits in at various points which aren't
293 * potentially alter the height of the tree. Either half of the tree may need
295 * which nodes have been 'cut' from the tree so that the change can be done
327 * mtree_empty() - Determine if a tree has any present entries.
328 * @mt: Maple Tree.
331 * Return: %true if the tree contains only NULL pointers.
345 * If state->node has bit 0 set then it references a tree location which is not
371 * Maple Tree.
374 struct maple_tree *tree; /* The tree we're operating in */ member
381 unsigned char depth; /* depth of tree descent during write */
401 #define mas_lock(mas) spin_lock(&((mas)->tree->ma_lock))
402 #define mas_unlock(mas) spin_unlock(&((mas)->tree->ma_lock))
407 * MAS_START means we have not searched the tree.
408 * MAS_ROOT means we have searched the tree and the entry we found lives in
409 * the root of the tree (ie it has index 0, length 1 and is the only entry in
410 * the tree).
411 * MAS_NONE means we have searched the tree and there is no node in the
412 * tree for this entry. For example, we searched for index 1 in an empty
413 * tree. Or we have a tree which points to a full leaf node and we
418 * top of the tree as the tree may have been modified.
429 .tree = mt, \
445 #define MA_TOPIARY(name, tree) \ argument
449 .mtree = tree, \
496 * mas_reset() - Reset a Maple Tree operation state.
497 * @mas: Maple Tree operation state.
511 * mas_for_each() - Iterate over a range of the maple tree.
512 * @__mas: Maple Tree operation state (maple_state)
513 * @__entry: Entry retrieved from the tree
514 * @__max: maximum index to retrieve from the tree
527 * mas_set_range() - Set up Maple Tree operation state for a different index.
528 * @mas: Maple Tree operation state.
529 * @start: New start of range in the Maple Tree.
530 * @last: New end of range in the Maple Tree.
545 * mas_set() - Set up Maple Tree operation state for a different index.
546 * @mas: Maple Tree operation state.
547 * @index: New index into the Maple Tree.
565 * mt_init_flags() - Initialise an empty maple tree with flags.
566 * @mt: Maple Tree
567 * @flags: maple tree flags.
569 * If you need to initialise a Maple Tree with special flags (eg, an
570 * allocation tree), use this function.
583 * mt_init() - Initialise an empty maple tree.
584 * @mt: Maple Tree
586 * An empty Maple Tree.
604 * mt_clear_in_rcu() - Switch the tree to non-RCU mode.
605 * @mt: The Maple Tree
623 * mt_set_in_rcu() - Switch the tree to RCU safe mode.
624 * @mt: The Maple Tree
655 * @__tree: The Maple Tree
657 * @__index: The index to update to track the location in the tree