Lines Matching +full:lock +full:- +full:state

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
19 synchronize on a lock, which can be the default spinlock, or the user can set
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
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
70 return -EEXIST if the range is not empty.
77 the caller is going to hold the lock for the duration of the walk then it is
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.
92 ----------------
95 :ref:`maple-tree-advanced-alloc` for other options.
98 -------
100 You do not have to worry about locking.  See :ref:`maple-tree-advanced-locks`
105 Takes RCU read lock:
123 If you want to take advantage of the internal lock to protect the data
132 .. _maple-tree-advanced-api:
140 You can use the ma_lock, RCU or an external lock for protection.
142 as the locking is compatible.  The :ref:`maple-tree-normal-api` is implemented
149 Initialising the maple tree is the same as in the :ref:`maple-tree-normal-api`.
152 The maple state keeps track of the range start and end in mas->index and
153 mas->last, respectively.
155 mas_walk() will walk the tree to the location of mas->index and set the
156 mas->index and mas->last according to the range for the entry.
160 The range is passed in as members of the maple state: index and last.
163 last of the maple state to the desired range to erase.  This will erase
164 the first range that is found in that range, set the maple state index
170 the range.  If the lock needs to be periodically dropped, see the locking
173 Using a maple state allows mas_next() and mas_prev() to function as if the
185 If the user needs to yield the lock during an operation, then the maple state
195 .. _maple-tree-advanced-alloc:
198 -------------------------
202 allocate the worst-case number of needed nodes to insert the provided number of
204 insertions are complete calling mas_destroy() on the maple state will free the
207 .. _maple-tree-advanced-locks:
210 ----------------
213 tree updates as well.  To use an external lock, the tree must be initialized
215 MTREE_INIT_EXT() #define, which takes an external lock as an argument.
220 .. kernel-doc:: include/linux/maple_tree.h
221 .. kernel-doc:: lib/maple_tree.c