Lines Matching +full:external +full:- +full:nodes

1 .. SPDX-License-Identifier: GPL-2.0+
13 The Maple Tree is a B-Tree data type which is optimized for storing
14 non-overlapping ranges, including ranges of size 1.  The tree was designed to
17 entry in a cache-efficient manner.  The tree can also be put into an RCU-safe
20 the lock to an external lock of a different type.
24 use the normal API.  An :ref:`maple-tree-advanced-api` exists for more complex
34 :ref:`maple-tree-advanced-api`, but are blocked by the normal API.
39 Pre-allocating of nodes is also supported using the
40 :ref:`maple-tree-advanced-api`.  This is useful for users who must guarantee a
42 code segment when allocating cannot be done.  Allocations of nodes are
45 .. _maple-tree-normal-api:
52 freshly-initialised maple tree contains a ``NULL`` pointer for the range ``0``
53 - ``ULONG_MAX``.  There are currently two types of maple trees supported: the
55 factor for internal nodes.  The allocation tree has a lower branching factor
70 return -EEXIST if the range is not empty.
78 worth looking at the mas_for_each() API in the :ref:`maple-tree-advanced-api`
82 not allocate memory, please see :ref:`maple-tree-advanced-api` for this use case.
88 Allocating Nodes
89 ----------------
92 :ref:`maple-tree-advanced-alloc` for other options.
95 -------
97 You do not have to worry about locking.  See :ref:`maple-tree-advanced-locks`
128 .. _maple-tree-advanced-api:
136 You can use the ma_lock, RCU or an external lock for protection.
138 as the locking is compatible.  The :ref:`maple-tree-normal-api` is implemented
143 life easier for both internal and external tree users.
145 Initialising the maple tree is the same as in the :ref:`maple-tree-normal-api`.
148 The maple state keeps track of the range start and end in mas->index and
149 mas->last, respectively.
151 mas_walk() will walk the tree to the location of mas->index and set the
152 mas->index and mas->last according to the range for the entry.
191 .. _maple-tree-advanced-alloc:
193 Advanced Allocating Nodes
194 -------------------------
198 allocate the worst-case number of needed nodes to insert the provided number of
203 .. _maple-tree-advanced-locks:
206 ----------------
208 The maple tree uses a spinlock by default, but external locks can be used for
209 tree updates as well.  To use an external lock, the tree must be initialized
211 MTREE_INIT_EXT() #define, which takes an external lock as an argument.
216 .. kernel-doc:: include/linux/maple_tree.h
217 .. kernel-doc:: lib/maple_tree.c