Lines Matching +full:entry +full:- +full:method

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
15 be simple to use and does not require a user written search method.  It
17 entry in a cache-efficient manner.  The tree can also be put into an RCU-safe
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
61 mtree_store() will overwrite any entry with the new entry and return 0 on
63 but takes a range.  mtree_load() is used to retrieve the entry stored at a
65 knowing one value within that range, or mtree_store() call with an entry of
68 If you want to only store a new entry to a range (or index) if that range is
70 return -EEXIST if the range is not empty.
72 You can search for an entry from an index upwards by using mt_find().
74 You can walk each entry within a range by calling mt_for_each().  You must
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`
132 .. _maple-tree-advanced-api:
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.
158 You can set entries using mas_store().  mas_store() will overwrite any entry
159 with the new entry and return the first existing entry that is overwritten.
165 and last as the range that was erased and return the entry that existed
168 You can walk each entry within a range by using mas_for_each().  If you want
176 return the next entry which occurs after the entry at index.  mas_prev()
177 will return the previous entry which occurs before the entry at index.
179 mas_find() will find the first entry which exists at or above index on
180 the first call, and the next entry from every subsequent calls.
182 mas_find_rev() will find the first entry which exists at or below the last on
183 the first call, and the previous entry from every subsequent calls.
195 .. _maple-tree-advanced-alloc:
198 -------------------------
202 allocate the worst-case number of needed nodes to insert the provided number of
207 .. _maple-tree-advanced-locks:
210 ----------------
220 .. kernel-doc:: include/linux/maple_tree.h
221 .. kernel-doc:: lib/maple_tree.c