Documentation/core-api/maple_tree.rst

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
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
57 ``0`` upwards or ``ULONG_MAX`` down.  An allocation tree can be used by
63 but takes a range.  mtree_load() is used to retrieve the entry stored at a
66 NULL may be used to partially erase a range or many ranges at once.
70 return -EEXIST if the range is not empty.
76 element of the tree then ``0`` and ``ULONG_MAX`` may be used as the range.  If
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.
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
165 and last as the range that was erased and return the entry that existed
169 to walk each element of the tree then ``0`` and ``ULONG_MAX`` may be used as
182 mas_find_rev() will find the first entry which exists at or below the last on
190 or mas_empty_area_rev() can be used.  mas_empty_area() searches for a gap
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 ----------------
212 The maple tree uses a spinlock by default, but external locks can be used for
220 .. kernel-doc:: include/linux/maple_tree.h
221 .. kernel-doc:: lib/maple_tree.c