Maple Tree

Author:

Liam R. Howlett

Overview

The Maple Tree is a B-Tree data type which is optimized for storingnon-overlapping ranges, including ranges of size 1. The tree was designed tobe simple to use and does not require a user written search method. Itsupports iterating over a range of entries and going to the previous or nextentry in a cache-efficient manner. The tree can also be put into an RCU-safemode of operation which allows reading and writing concurrently. Writers mustsynchronize on a lock, which can be the default spinlock, or the user can setthe lock to an external lock of a different type.

The Maple Tree maintains a small memory footprint and was designed to usemodern processor cache efficiently. The majority of the users will be able touse the normal API. AnAdvanced API exists for more complexscenarios. The most important usage of the Maple Tree is the tracking of thevirtual memory areas.

The Maple Tree can store values between0 andULONG_MAX. The MapleTree reserves values with the bottom two bits set to ‘10’ which are below 4096(ie 2, 6, 10 .. 4094) for internal use. If the entries may use reservedentries then the users can convert the entries usingxa_mk_value() and convertthem back by callingxa_to_value(). If the user needs to use a reservedvalue, then the user can convert the value when using theAdvanced API, but are blocked by the normal API.

The Maple Tree can also be configured to support searching for a gap of a givensize (or larger).

Pre-allocating of nodes is also supported using theAdvanced API. This is useful for users who must guarantee asuccessful store operation within a givencode segment when allocating cannot be done. Allocations of nodes arerelatively small at around 256 bytes.

Normal API

Start by initialising a maple tree, either withDEFINE_MTREE() for staticallyallocated maple trees ormt_init() for dynamically allocated ones. Afreshly-initialised maple tree contains aNULL pointer for the range0-ULONG_MAX. There are currently two types of maple trees supported: theallocation tree and the regular tree. The regular tree has a higher branchingfactor for internal nodes. The allocation tree has a lower branching factorbut allows the user to search for a gap of a given size or larger from either0 upwards orULONG_MAX down. An allocation tree can be used bypassing in theMT_FLAGS_ALLOC_RANGE flag when initialising the tree.

You can then set entries usingmtree_store() ormtree_store_range().mtree_store() will overwrite any entry with the new entry and return 0 onsuccess or an error code otherwise.mtree_store_range() works in the same waybut takes a range.mtree_load() is used to retrieve the entry stored at agiven index. You can usemtree_erase() to erase an entire range by onlyknowing one value within that range, ormtree_store() call with an entry ofNULL may be used to partially erase a range or many ranges at once.

If you want to only store a new entry to a range (or index) if that range iscurrentlyNULL, you can usemtree_insert_range() ormtree_insert() whichreturn -EEXIST if the range is not empty.

You can search for an entry from an index upwards by usingmt_find().

You can walk each entry within a range by callingmt_for_each(). You mustprovide a temporary variable to store a cursor. If you want to walk eachelement of the tree then0 andULONG_MAX may be used as the range. Ifthe caller is going to hold the lock for the duration of the walk then it isworth looking at themas_for_each() API in theAdvanced APIsection.

Sometimes it is necessary to ensure the next call to store to a maple tree doesnot allocate memory, please seeAdvanced API for this use case.

You can usemtree_dup() to duplicate an entire maple tree. It is a moreefficient way than inserting all elements one by one into a new tree.

Finally, you can remove all entries from a maple tree by callingmtree_destroy(). If the maple tree entries are pointers, you may wish to freethe entries first.

Allocating Nodes

The allocations are handled by the internal tree code. SeeAdvanced Allocating Nodes for other options.

Locking

You do not have to worry about locking. SeeAdvanced Lockingfor other options.

The Maple Tree uses RCU and an internal spinlock to synchronise access:

Takes RCU read lock:
Takes ma_lock internally:

If you want to take advantage of the internal lock to protect the datastructures that you are storing in the Maple Tree, you can callmtree_lock()before callingmtree_load(), then take a reference count on the object youhave found before callingmtree_unlock(). This will prevent stores fromremoving the object from the tree between looking up the object andincrementing the refcount. You can also use RCU to avoid dereferencingfreed memory, but an explanation of that is beyond the scope of thisdocument.

Advanced API

The advanced API offers more flexibility and better performance at thecost of an interface which can be harder to use and has fewer safeguards.You must take care of your own locking while using the advanced API.You can use the ma_lock, RCU or an external lock for protection.You can mix advanced and normal operations on the same array, as longas the locking is compatible. TheNormal API is implementedin terms of the advanced API.

The advanced API is based around the ma_state, this is where the ‘mas’prefix originates. The ma_statestructkeeps track of tree operations to makelife easier for both internal and external tree users.

Initialising the maple tree is the same as in theNormal API.Please see above.

The maple state keeps track of the range start and end in mas->index andmas->last, respectively.

mas_walk() will walk the tree to the location of mas->index and set themas->index and mas->last according to the range for the entry.

You can set entries usingmas_store().mas_store() will overwrite any entrywith the new entry and return the first existing entry that is overwritten.The range is passed in as members of the maple state: index and last.

You can usemas_erase() to erase an entire range by setting index andlast of the maple state to the desired range to erase. This will erasethe first range that is found in that range, set the maple state indexand last as the range that was erased and return the entry that existedat that location.

You can walk each entry within a range by usingmas_for_each(). If you wantto walk each element of the tree then0 andULONG_MAX may be used asthe range. If the lock needs to be periodically dropped, see the lockingsectionmas_pause().

Using a maple state allowsmas_next() andmas_prev() to function as if thetree was a linked list. With such a high branching factor the amortizedperformance penalty is outweighed by cache optimization.mas_next() willreturn the next entry which occurs after the entry at index.mas_prev()will return the previous entry which occurs before the entry at index.

mas_find() will find the first entry which exists at or above index onthe first call, and the next entry from every subsequent calls.

mas_find_rev() will find the first entry which exists at or below the last onthe first call, and the previous entry from every subsequent calls.

If the user needs to yield the lock during an operation, then the maple statemust be paused usingmas_pause().

There are a few extra interfaces provided when using an allocation tree.If you wish to search for a gap within a range, thenmas_empty_area()ormas_empty_area_rev() can be used.mas_empty_area() searches for a gapstarting at the lowest index given up to the maximum of the range.mas_empty_area_rev() searches for a gap starting at the highest index givenand continues downward to the lower bound of the range.

Advanced Allocating Nodes

Allocations are usually handled internally to the tree, however if allocationsneed to occur before a write occurs then callingmas_expected_entries() willallocate the worst-case number of needed nodes to insert the provided number ofranges. This also causes the tree to enter mass insertion mode. Onceinsertions are complete callingmas_destroy() on the maple state will free theunused allocations.

Advanced Locking

The maple tree uses a spinlock by default, but external locks can be used fortree updates as well. To use an external lock, the tree must be initializedwith theMT_FLAGS_LOCK_EXTERNflag, this is usually done with theMTREE_INIT_EXT() #define, which takes an external lock as an argument.

Functions and structures

Maple tree flags

  • MT_FLAGS_ALLOC_RANGE - Track gaps in this tree

  • MT_FLAGS_USE_RCU - Operate in RCU mode

  • MT_FLAGS_HEIGHT_OFFSET - The position of the tree height in the flags

  • MT_FLAGS_HEIGHT_MASK - The mask for the maple tree height value

  • MT_FLAGS_LOCK_MASK - How the mt_lock is used

  • MT_FLAGS_LOCK_IRQ - Acquired irq-safe

  • MT_FLAGS_LOCK_BH - Acquired bh-safe

  • MT_FLAGS_LOCK_EXTERN - mt_lock is not used

MAPLE_HEIGHT_MAX The largest height that can be stored

MTREE_INIT

MTREE_INIT(name,__flags)

Initialize a maple tree

Parameters

name

The maple tree name

__flags

The maple tree flags

MTREE_INIT_EXT

MTREE_INIT_EXT(name,__flags,__lock)

Initialize a maple tree with an external lock.

Parameters

name

The tree name

__flags

The maple tree flags

__lock

The external lock

boolmtree_empty(conststructmaple_tree*mt)

Determine if a tree has any present entries.

Parameters

conststructmaple_tree*mt

Maple Tree.

Context

Any context.

Return

true if the tree contains only NULL pointers.

voidmas_reset(structma_state*mas)

Reset a Maple Tree operation state.

Parameters

structma_state*mas

Maple Tree operation state.

Description

Resets the error or walk state of themas so future walks of thearray will start from the root. Use this if you have dropped thelock and want to reuse the ma_state.

Context

Any context.

mas_for_each

mas_for_each(__mas,__entry,__max)

Iterate over a range of the maple tree.

Parameters

__mas

Maple Tree operation state (maple_state)

__entry

Entry retrieved from the tree

__max

maximum index to retrieve from the tree

Description

When returned, mas->index and mas->last will hold the entire range for theentry.

Note

may return the zero entry.

mas_for_each_rev

mas_for_each_rev(__mas,__entry,__min)

Iterate over a range of the maple tree in reverse order.

Parameters

__mas

Maple Tree operation state (maple_state)

__entry

Entry retrieved from the tree

__min

minimum index to retrieve from the tree

Description

When returned, mas->index and mas->last will hold the entire range for theentry.

Note

may return the zero entry.

void__mas_set_range(structma_state*mas,unsignedlongstart,unsignedlonglast)

Set up Maple Tree operation state to a sub-range of the current location.

Parameters

structma_state*mas

Maple Tree operation state.

unsignedlongstart

New start of range in the Maple Tree.

unsignedlonglast

New end of range in the Maple Tree.

Description

set the internal maple state values to a sub-range.Please usemas_set_range() if you do not know where you are in the tree.

voidmas_set_range(structma_state*mas,unsignedlongstart,unsignedlonglast)

Set up Maple Tree operation state for a different index.

Parameters

structma_state*mas

Maple Tree operation state.

unsignedlongstart

New start of range in the Maple Tree.

unsignedlonglast

New end of range in the Maple Tree.

Description

Move the operation state to refer to a different range. This willhave the effect of starting a walk from the top; seemas_next()to move to an adjacent index.

voidmas_set(structma_state*mas,unsignedlongindex)

Set up Maple Tree operation state for a different index.

Parameters

structma_state*mas

Maple Tree operation state.

unsignedlongindex

New index into the Maple Tree.

Description

Move the operation state to refer to a different index. This willhave the effect of starting a walk from the top; seemas_next()to move to an adjacent index.

voidmt_init_flags(structmaple_tree*mt,unsignedintflags)

Initialise an empty maple tree with flags.

Parameters

structmaple_tree*mt

Maple Tree

unsignedintflags

maple tree flags.

Description

If you need to initialise a Maple Tree with special flags (eg, anallocation tree), use this function.

Context

Any context.

voidmt_init(structmaple_tree*mt)

Initialise an empty maple tree.

Parameters

structmaple_tree*mt

Maple Tree

Description

An empty Maple Tree.

Context

Any context.

voidmt_clear_in_rcu(structmaple_tree*mt)

Switch the tree to non-RCU mode.

Parameters

structmaple_tree*mt

The Maple Tree

voidmt_set_in_rcu(structmaple_tree*mt)

Switch the tree to RCU safe mode.

Parameters

structmaple_tree*mt

The Maple Tree

mt_for_each

mt_for_each(__tree,__entry,__index,__max)

Iterate over each entry starting at index until max.

Parameters

__tree

The Maple Tree

__entry

The current entry

__index

The index to start the search from. Subsequently used as iterator.

__max

The maximum limit forindex

Description

This iterator skips all entries, which resolve to a NULL pointer,e.g. entries which has been reserved with XA_ZERO_ENTRY.

voidmas_prealloc_calc(structma_wr_state*wr_mas,void*entry)

Calculate number of nodes needed for a given store oepration

Parameters

structma_wr_state*wr_mas

The maple write state

void*entry

The entry to store into the tree

Return

Number of nodes required for preallocation.

voidmas_wr_preallocate(structma_wr_state*wr_mas,void*entry)

Preallocate enough nodes for a store operation

Parameters

structma_wr_state*wr_mas

The maple write state

void*entry

The entry that will be stored

void*mas_insert(structma_state*mas,void*entry)

Internal call to insert a value

Parameters

structma_state*mas

The maple state

void*entry

The entry to store

Return

NULL or the contents that already exists at the requested indexotherwise. The maple state needs to be checked for error conditions.

intmas_alloc_cyclic(structma_state*mas,unsignedlong*startp,void*entry,unsignedlongrange_lo,unsignedlongrange_hi,unsignedlong*next,gfp_tgfp)

Internal call to find somewhere to store an entry

Parameters

structma_state*mas

The maple state.

unsignedlong*startp

Pointer to ID.

void*entry

The entry to store.

unsignedlongrange_lo

Lower bound of range to search.

unsignedlongrange_hi

Upper bound of range to search.

unsignedlong*next

Pointer to next ID to allocate.

gfp_tgfp

The GFP_FLAGS to use for allocations.

Return

0 if the allocation succeeded without wrapping, 1 if theallocation succeeded after wrapping, or -EBUSY if there are nofree entries.

void*mas_walk(structma_state*mas)

Search formas->index in the tree.

Parameters

structma_state*mas

The maple state.

Description

mas->index and mas->last will be set to the range if there is a value. Ifmas->status is ma_none, reset to ma_start

Return

the entry at the location orNULL.

void__rcu**mte_dead_walk(structmaple_enode**enode,unsignedcharoffset)

Walk down a dead tree to just before the leaves

Parameters

structmaple_enode**enode

The maple encoded node

unsignedcharoffset

The starting offset

Note

This can only be used from the RCU callback context.

voidmt_free_walk(structrcu_head*head)

Walk & free a tree in the RCU callback context

Parameters

structrcu_head*head

The RCU head that’s within the node.

Note

This can only be used from the RCU callback context.

void*mas_store(structma_state*mas,void*entry)

Store anentry.

Parameters

structma_state*mas

The maple state.

void*entry

The entry to store.

Description

Themas->index andmas->last is used to set the range for theentry.

Return

the first entry between mas->index and mas->last orNULL.

intmas_store_gfp(structma_state*mas,void*entry,gfp_tgfp)

Store a value into the tree.

Parameters

structma_state*mas

The maple state

void*entry

The entry to store

gfp_tgfp

The GFP_FLAGS to use for allocations if necessary.

Return

0 on success, -EINVAL on invalid request, -ENOMEM if memory could notbe allocated.

voidmas_store_prealloc(structma_state*mas,void*entry)

Store a value into the tree using memory preallocated in the maple state.

Parameters

structma_state*mas

The maple state

void*entry

The entry to store.

intmas_preallocate(structma_state*mas,void*entry,gfp_tgfp)

Preallocate enough nodes for a store operation

Parameters

structma_state*mas

The maple state

void*entry

The entry that will be stored

gfp_tgfp

The GFP_FLAGS to use for allocations.

Return

0 on success, -ENOMEM if memory could not be allocated.

void*mas_next(structma_state*mas,unsignedlongmax)

Get the next entry.

Parameters

structma_state*mas

The maple state

unsignedlongmax

The maximum index to check.

Description

Returns the next entry aftermas->index.Must hold rcu_read_lock or the write lock.Can return the zero entry.

Return

The next entry orNULL

void*mas_next_range(structma_state*mas,unsignedlongmax)

Advance the maple state to the next range

Parameters

structma_state*mas

The maple state

unsignedlongmax

The maximum index to check.

Description

Setsmas->index andmas->last to the range.Must hold rcu_read_lock or the write lock.Can return the zero entry.

Return

The next entry orNULL

void*mt_next(structmaple_tree*mt,unsignedlongindex,unsignedlongmax)

get the next value in the maple tree

Parameters

structmaple_tree*mt

The maple tree

unsignedlongindex

The start index

unsignedlongmax

The maximum index to check

Description

Takes RCU read lock internally to protect the search, which does notprotect the returned pointer after dropping RCU read lock.See also:Maple Tree

Return

The entry higher thanindex orNULL if nothing is found.

void*mas_prev(structma_state*mas,unsignedlongmin)

Get the previous entry

Parameters

structma_state*mas

The maple state

unsignedlongmin

The minimum value to check.

Description

Must hold rcu_read_lock or the write lock.Will reset mas to ma_start if the status is ma_none. Will stop on notsearchable nodes.

Return

the previous value orNULL.

void*mas_prev_range(structma_state*mas,unsignedlongmin)

Advance to the previous range

Parameters

structma_state*mas

The maple state

unsignedlongmin

The minimum value to check.

Description

Setsmas->index andmas->last to the range.Must hold rcu_read_lock or the write lock.Will reset mas to ma_start if the node is ma_none. Will stop on notsearchable nodes.

Return

the previous value orNULL.

void*mt_prev(structmaple_tree*mt,unsignedlongindex,unsignedlongmin)

get the previous value in the maple tree

Parameters

structmaple_tree*mt

The maple tree

unsignedlongindex

The start index

unsignedlongmin

The minimum index to check

Description

Takes RCU read lock internally to protect the search, which does notprotect the returned pointer after dropping RCU read lock.See also:Maple Tree

Return

The entry beforeindex orNULL if nothing is found.

voidmas_pause(structma_state*mas)

Pause a mas_find/mas_for_each to drop the lock.

Parameters

structma_state*mas

The maple state to pause

Description

Some users need to pause a walk and drop the lock they’re holding inorder to yield to a higher priority thread or carry out an operationon an entry. Those users should call this function before they dropthe lock. It resets themas to be suitable for the next iterationof the loop after the user has reacquired the lock. If most entriesfound during a walk require you to callmas_pause(), themt_for_each()iterator may be more appropriate.

boolmas_find_setup(structma_state*mas,unsignedlongmax,void**entry)

Internal function to set up mas_find*().

Parameters

structma_state*mas

The maple state

unsignedlongmax

The maximum index

void**entry

Pointer to the entry

Return

True if entry is the answer, false otherwise.

void*mas_find(structma_state*mas,unsignedlongmax)

On the first call, find the entry at or after mas->index up tomax. Otherwise, find the entry after mas->index.

Parameters

structma_state*mas

The maple state

unsignedlongmax

The maximum value to check.

Description

Must hold rcu_read_lock or the write lock.If an entry exists, last and index are updated accordingly.May setmas->status to ma_overflow.

Return

The entry orNULL.

void*mas_find_range(structma_state*mas,unsignedlongmax)

On the first call, find the entry at or after mas->index up tomax. Otherwise, advance to the next slot mas->index.

Parameters

structma_state*mas

The maple state

unsignedlongmax

The maximum value to check.

Description

Must hold rcu_read_lock or the write lock.If an entry exists, last and index are updated accordingly.May setmas->status to ma_overflow.

Return

The entry orNULL.

boolmas_find_rev_setup(structma_state*mas,unsignedlongmin,void**entry)

Internal function to set up mas_find_*_rev()

Parameters

structma_state*mas

The maple state

unsignedlongmin

The minimum index

void**entry

Pointer to the entry

Return

True if entry is the answer, false otherwise.

void*mas_find_rev(structma_state*mas,unsignedlongmin)

On the first call, find the first non-null entry at or below mas->index down tomin. Otherwise find the first non-null entry below mas->index down tomin.

Parameters

structma_state*mas

The maple state

unsignedlongmin

The minimum value to check.

Description

Must hold rcu_read_lock or the write lock.If an entry exists, last and index are updated accordingly.May setmas->status to ma_underflow.

Return

The entry orNULL.

void*mas_find_range_rev(structma_state*mas,unsignedlongmin)

On the first call, find the first non-null entry at or below mas->index down tomin. Otherwise advance to the previous slot after mas->index down tomin.

Parameters

structma_state*mas

The maple state

unsignedlongmin

The minimum value to check.

Description

Must hold rcu_read_lock or the write lock.If an entry exists, last and index are updated accordingly.May setmas->status to ma_underflow.

Return

The entry orNULL.

void*mas_erase(structma_state*mas)

Find the range in which index resides and erase the entire range.

Parameters

structma_state*mas

The maple state

Description

Must hold the write lock.Searches formas->index, setsmas->index andmas->last to the range anderases that range.

Return

the entry that was erased orNULL,mas->index andmas->last are updated.

boolmas_nomem(structma_state*mas,gfp_tgfp)

Check if there was an error allocating and do the allocation if necessary If there are allocations, then free them.

Parameters

structma_state*mas

The maple state

gfp_tgfp

The GFP_FLAGS to use for allocations

Return

true on allocation, false otherwise.

void*mtree_load(structmaple_tree*mt,unsignedlongindex)

Load a value stored in a maple tree

Parameters

structmaple_tree*mt

The maple tree

unsignedlongindex

The index to load

Return

the entry orNULL

intmtree_store_range(structmaple_tree*mt,unsignedlongindex,unsignedlonglast,void*entry,gfp_tgfp)

Store an entry at a given range.

Parameters

structmaple_tree*mt

The maple tree

unsignedlongindex

The start of the range

unsignedlonglast

The end of the range

void*entry

The entry to store

gfp_tgfp

The GFP_FLAGS to use for allocations

Return

0 on success, -EINVAL on invalid request, -ENOMEM if memory could notbe allocated.

intmtree_store(structmaple_tree*mt,unsignedlongindex,void*entry,gfp_tgfp)

Store an entry at a given index.

Parameters

structmaple_tree*mt

The maple tree

unsignedlongindex

The index to store the value

void*entry

The entry to store

gfp_tgfp

The GFP_FLAGS to use for allocations

Return

0 on success, -EINVAL on invalid request, -ENOMEM if memory could notbe allocated.

intmtree_insert_range(structmaple_tree*mt,unsignedlongfirst,unsignedlonglast,void*entry,gfp_tgfp)

Insert an entry at a given range if there is no value.

Parameters

structmaple_tree*mt

The maple tree

unsignedlongfirst

The start of the range

unsignedlonglast

The end of the range

void*entry

The entry to store

gfp_tgfp

The GFP_FLAGS to use for allocations.

Return

0 on success, -EEXISTS if the range is occupied, -EINVAL on invalidrequest, -ENOMEM if memory could not be allocated.

intmtree_insert(structmaple_tree*mt,unsignedlongindex,void*entry,gfp_tgfp)

Insert an entry at a given index if there is no value.

Parameters

structmaple_tree*mt

The maple tree

unsignedlongindex

The index to store the value

void*entry

The entry to store

gfp_tgfp

The GFP_FLAGS to use for allocations.

Return

0 on success, -EEXISTS if the range is occupied, -EINVAL on invalidrequest, -ENOMEM if memory could not be allocated.

intmtree_alloc_cyclic(structmaple_tree*mt,unsignedlong*startp,void*entry,unsignedlongrange_lo,unsignedlongrange_hi,unsignedlong*next,gfp_tgfp)

Find somewhere to store this entry in the tree.

Parameters

structmaple_tree*mt

The maple tree.

unsignedlong*startp

Pointer to ID.

void*entry

The entry to store.

unsignedlongrange_lo

Lower bound of range to search.

unsignedlongrange_hi

Upper bound of range to search.

unsignedlong*next

Pointer to next ID to allocate.

gfp_tgfp

The GFP_FLAGS to use for allocations.

Description

Finds an empty entry inmt afternext, stores the new index intotheid pointer, stores the entry at that index, then updatesnext.

mt must be initialized with the MT_FLAGS_ALLOC_RANGE flag.

Context

Any context. Takes and releases the mt.lock. May sleep ifthegfp flags permit.

Return

0 if the allocation succeeded without wrapping, 1 if theallocation succeeded after wrapping, -ENOMEM if memory could not beallocated, -EINVAL ifmt cannot be used, or -EBUSY if there are nofree entries.

void*mtree_erase(structmaple_tree*mt,unsignedlongindex)

Find an index and erase the entire range.

Parameters

structmaple_tree*mt

The maple tree

unsignedlongindex

The index to erase

Description

Erasing is the same as a walk to an entry then a store of a NULL to thatENTIRE range. In fact, it is implemented as such using the advanced API.

Return

The entry stored at theindex orNULL

int__mt_dup(structmaple_tree*mt,structmaple_tree*new,gfp_tgfp)

Duplicate an entire maple tree

Parameters

structmaple_tree*mt

The source maple tree

structmaple_tree*new

The new maple tree

gfp_tgfp

The GFP_FLAGS to use for allocations

Description

This function duplicates a maple tree in Depth-First Search (DFS) pre-ordertraversal. It usesmemcpy() to copy nodes in the source tree and allocatenew child nodes in non-leaf nodes. The new node is exactly the same as thesource node except for all the addresses stored in it. It will be faster thantraversing all elements in the source tree and inserting them one by one intothe new tree.The user needs to ensure that the attributes of the source tree and the newtree are the same, and the new tree needs to be an empty tree, otherwise-EINVAL will be returned.Note that the user needs to manually lock the source tree and the new tree.

Return

0 on success, -ENOMEM if memory could not be allocated, -EINVAL Ifthe attributes of the two trees are different or the new tree is not an emptytree.

intmtree_dup(structmaple_tree*mt,structmaple_tree*new,gfp_tgfp)

Duplicate an entire maple tree

Parameters

structmaple_tree*mt

The source maple tree

structmaple_tree*new

The new maple tree

gfp_tgfp

The GFP_FLAGS to use for allocations

Description

This function duplicates a maple tree in Depth-First Search (DFS) pre-ordertraversal. It usesmemcpy() to copy nodes in the source tree and allocatenew child nodes in non-leaf nodes. The new node is exactly the same as thesource node except for all the addresses stored in it. It will be faster thantraversing all elements in the source tree and inserting them one by one intothe new tree.The user needs to ensure that the attributes of the source tree and the newtree are the same, and the new tree needs to be an empty tree, otherwise-EINVAL will be returned.

Return

0 on success, -ENOMEM if memory could not be allocated, -EINVAL Ifthe attributes of the two trees are different or the new tree is not an emptytree.

void__mt_destroy(structmaple_tree*mt)

Walk and free all nodes of a locked maple tree.

Parameters

structmaple_tree*mt

The maple tree

Note

Does not handle locking.

voidmtree_destroy(structmaple_tree*mt)

Destroy a maple tree

Parameters

structmaple_tree*mt

The maple tree

Description

Frees all resources used by the tree. Handles locking.

void*mt_find(structmaple_tree*mt,unsignedlong*index,unsignedlongmax)

Search from the start up until an entry is found.

Parameters

structmaple_tree*mt

The maple tree

unsignedlong*index

Pointer which contains the start location of the search

unsignedlongmax

The maximum value of the search range

Description

Takes RCU read lock internally to protect the search, which does notprotect the returned pointer after dropping RCU read lock.See also:Maple Tree

In case that an entry is foundindex is updated to point to the nextpossible entry independent whether the found entry is occupying asingle index or a range if indices.

Return

The entry at or after theindex orNULL

void*mt_find_after(structmaple_tree*mt,unsignedlong*index,unsignedlongmax)

Search from the start up until an entry is found.

Parameters

structmaple_tree*mt

The maple tree

unsignedlong*index

Pointer which contains the start location of the search

unsignedlongmax

The maximum value to check

Description

Same asmt_find() except that it checksindex for 0 beforesearching. Ifindex == 0, the search is aborted. This covers a wraparound ofindex to 0 in an iterator loop.

Return

The entry at or after theindex orNULL