Lines Matching +full:in +full:- +full:tree
1 .. SPDX-License-Identifier: GPL-2.0+
5 Maple Tree
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
22 The Maple Tree maintains a small memory footprint and was designed to use
24 use the normal API. An :ref:`maple-tree-advanced-api` exists for more complex
25 scenarios. The most important usage of the Maple Tree is the tracking of the
28 The Maple Tree can store values between ``0`` and ``ULONG_MAX``. The Maple
29 Tree reserves values with the bottom two bits set to '10' which are below 4096
34 :ref:`maple-tree-advanced-api`, but are blocked by the normal API.
36 The Maple Tree can also be configured to support searching for a gap of a given
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:
50 Start by initialising a maple tree, either with DEFINE_MTREE() for statically
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
54 allocation tree and the regular tree. The regular tree has a higher branching
55 factor for internal nodes. The allocation tree has a lower branching factor
57 ``0`` upwards or ``ULONG_MAX`` down. An allocation tree can be used by
58 passing in the ``MT_FLAGS_ALLOC_RANGE`` flag when initialising the tree.
62 success or an error code otherwise. mtree_store_range() works in the same way
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`
81 Sometimes it is necessary to ensure the next call to store to a maple tree does
82 not allocate memory, please see :ref:`maple-tree-advanced-api` for this use case.
84 You can use mtree_dup() to duplicate an entire maple tree. It is a more
85 efficient way than inserting all elements one by one into a new tree.
87 Finally, you can remove all entries from a maple tree by calling
88 mtree_destroy(). If the maple tree entries are pointers, you may wish to free
92 ----------------
94 The allocations are handled by the internal tree code. See
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`
103 The Maple Tree uses RCU and an internal spinlock to synchronise access:
124 structures that you are storing in the Maple Tree, you can call mtree_lock()
127 removing the object from the tree between looking up the object and
132 .. _maple-tree-advanced-api:
142 as the locking is compatible. The :ref:`maple-tree-normal-api` is implemented
143 in terms of the advanced API.
146 prefix originates. The ma_state struct keeps track of tree operations to make
147 life easier for both internal and external tree users.
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.
164 the first range that is found in that range, set the maple state index
169 to walk each element of the tree then ``0`` and ``ULONG_MAX`` may be used as
174 tree was a linked list. With such a high branching factor the amortized
188 There are a few extra interfaces provided when using an allocation tree.
195 .. _maple-tree-advanced-alloc:
198 -------------------------
200 Allocations are usually handled internally to the tree, however if allocations
202 allocate the worst-case number of needed nodes to insert the provided number of
203 ranges. This also causes the tree to enter mass insertion mode. Once
207 .. _maple-tree-advanced-locks:
210 ----------------
212 The maple tree uses a spinlock by default, but external locks can be used for
213 tree updates as well. To use an external lock, the tree must be initialized
220 .. kernel-doc:: include/linux/maple_tree.h
221 .. kernel-doc:: lib/maple_tree.c