NDEVR
API Documentation
ThreadedRTree< t_dims, t_type >

An RTree extension that supports multi-threaded tree construction and bounding box computation. More...

Public Member Functions

 ThreadedRTree (const RTree< t_dims, t_type > &tree)
 Copy constructs a ThreadedRTree from an existing RTree.
 ThreadedRTree (RTree< t_dims, t_type > &&tree)
 Move constructs a ThreadedRTree from an existing RTree.
 ThreadedRTree (uint04 bucket_size)
 Constructs a ThreadedRTree with the given bucket size.
template<class t_node_type>
bool _balanceLeafNodeThreaded (uint04 level, const uint04 node_index, const Buffer< t_node_type > &elements, Buffer< uint04 > &indices, uint04 start, uint04 end, ProgressInfo &progress)
 Recursively balances leaf nodes using thread splitting when beneficial.
template<class t_node_type>
Bounds< t_dims, t_type > _getBoundingBoxThreaded (uint04 top_level, const Buffer< uint04 > &indices, const Buffer< t_node_type > &elements, uint04 start, uint04 end)
 Computes the bounding box of elements using multi-threaded divide and conquer.
template<class t_node_type>
bool addAllThreaded (const Buffer< t_node_type > &elements, InfoPipe *progress=nullptr)
 Adds all elements to the tree using multi-threaded balancing.
template<class t_node_type>
bool addAllThreaded (const Buffer< t_node_type > &elements, uint04 start_index, uint04 end_index, InfoPipe *progress=nullptr)
 Adds a range of elements to the tree using multi-threaded balancing.
void splitLeafNode (uint04 index) final override
 Thread-safe override that splits a leaf node using a mutex lock.

Public Attributes

uint04 m_number_of_threads
 The number of threads to use for parallel operations.
std::mutex m_split_lock
 Mutex protecting leaf node splits during multi-threaded construction.

Detailed Description

template<uint01 t_dims, class t_type>
class ThreadedRTree< t_dims, t_type >

An RTree extension that supports multi-threaded tree construction and bounding box computation.

Definition at line 43 of file ThreadedRTree.h.

Constructor & Destructor Documentation

◆ ThreadedRTree() [1/3]

template<uint01 t_dims, class t_type>
ThreadedRTree< t_dims, t_type >::ThreadedRTree ( uint04 bucket_size)
inlineexplicit

Constructs a ThreadedRTree with the given bucket size.

Parameters
[in]bucket_sizeThe maximum number of elements per leaf node.

Definition at line 1 of file ThreadedRTree.h.

◆ ThreadedRTree() [2/3]

template<uint01 t_dims, class t_type>
ThreadedRTree< t_dims, t_type >::ThreadedRTree ( const RTree< t_dims, t_type > & tree)
inline

Copy constructs a ThreadedRTree from an existing RTree.

Parameters
[in]treeThe tree to copy.

Definition at line 1 of file ThreadedRTree.h.

◆ ThreadedRTree() [3/3]

template<uint01 t_dims, class t_type>
ThreadedRTree< t_dims, t_type >::ThreadedRTree ( RTree< t_dims, t_type > && tree)
inline

Move constructs a ThreadedRTree from an existing RTree.

Parameters
[in]treeThe tree to move from.

Definition at line 1 of file ThreadedRTree.h.

Member Function Documentation

◆ _balanceLeafNodeThreaded()

template<uint01 t_dims, class t_type>
template<class t_node_type>
bool ThreadedRTree< t_dims, t_type >::_balanceLeafNodeThreaded ( uint04 level,
const uint04 node_index,
const Buffer< t_node_type > & elements,
Buffer< uint04 > & indices,
uint04 start,
uint04 end,
ProgressInfo & progress )
inline

Recursively balances leaf nodes using thread splitting when beneficial.

Parameters
[in]levelThe current recursion level for thread-count decisions.
[in]node_indexThe tree node index to balance.
[in]elementsThe elements buffer.
[in]indicesThe index buffer for partitioning.
[in]startThe start index in the partition.
[in]endThe end index in the partition.
[in]progressProgress reporting interface.
Returns
True if the node was successfully balanced.

Definition at line 125 of file ThreadedRTree.h.

References _balanceLeafNodeThreaded(), and m_number_of_threads.

Referenced by _balanceLeafNodeThreaded(), addAllThreaded(), and addAllThreaded().

◆ _getBoundingBoxThreaded()

template<uint01 t_dims, class t_type>
template<class t_node_type>
Bounds< t_dims, t_type > ThreadedRTree< t_dims, t_type >::_getBoundingBoxThreaded ( uint04 top_level,
const Buffer< uint04 > & indices,
const Buffer< t_node_type > & elements,
uint04 start,
uint04 end )
inline

Computes the bounding box of elements using multi-threaded divide and conquer.

Parameters
[in]top_levelThe current recursion level for thread-count decisions.
[in]indicesThe index buffer.
[in]elementsThe elements buffer.
[in]startThe start index.
[in]endThe end index.
Returns
The bounding box encompassing all specified elements.

Definition at line 157 of file ThreadedRTree.h.

References _getBoundingBoxThreaded(), and m_number_of_threads.

Referenced by _getBoundingBoxThreaded(), and addAllThreaded().

◆ addAllThreaded() [1/2]

template<uint01 t_dims, class t_type>
template<class t_node_type>
bool ThreadedRTree< t_dims, t_type >::addAllThreaded ( const Buffer< t_node_type > & elements,
InfoPipe * progress = nullptr )
inline

Adds all elements to the tree using multi-threaded balancing.

Parameters
[in]elementsThe elements to add.
[in]progressOptional progress pipe for cancellation and reporting.
Returns
True if the tree was successfully balanced.

Definition at line 73 of file ThreadedRTree.h.

References _balanceLeafNodeThreaded(), _getBoundingBoxThreaded(), and cast().

◆ addAllThreaded() [2/2]

template<uint01 t_dims, class t_type>
template<class t_node_type>
bool ThreadedRTree< t_dims, t_type >::addAllThreaded ( const Buffer< t_node_type > & elements,
uint04 start_index,
uint04 end_index,
InfoPipe * progress = nullptr )
inline

Adds a range of elements to the tree using multi-threaded balancing.

Parameters
[in]elementsThe elements to add.
[in]start_indexThe start index in the elements buffer.
[in]end_indexThe end index in the elements buffer.
[in]progressOptional progress pipe for cancellation and reporting.
Returns
True if the tree was successfully balanced.

Definition at line 97 of file ThreadedRTree.h.

References _balanceLeafNodeThreaded(), and cast().

◆ splitLeafNode()

template<uint01 t_dims, class t_type>
void ThreadedRTree< t_dims, t_type >::splitLeafNode ( uint04 index)
inlinefinaloverride

Thread-safe override that splits a leaf node using a mutex lock.

Parameters
[in]indexThe index of the leaf node to split.

Definition at line 181 of file ThreadedRTree.h.

References m_split_lock.

The documentation for this class was generated from the following file: