Copy-on-Write wrapper for DYNAMIC_RTREE. More...

#include <dynamic_rtree_cow.h>

Classes
struct	ALLOC_CHAIN

class	Iterator
	Iterator for traversing all data items. More...

Public Types
using	NODE = RTREE_NODE<DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES>

using	ALLOC = SLAB_ALLOCATOR<NODE>

using	BULK_ENTRY = typename DYNAMIC_RTREE<DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES>::BULK_ENTRY
	Bulk load entries using Hilbert curve sorting and bottom-up packing.

Public Member Functions
	COW_RTREE ()

	~COW_RTREE ()

	COW_RTREE (COW_RTREE &&aOther) noexcept

COW_RTREE &	operator= (COW_RTREE &&aOther) noexcept

	COW_RTREE (const COW_RTREE &)=delete

COW_RTREE &	operator= (const COW_RTREE &)=delete

COW_RTREE	Clone () const
	Create a clone that shares the tree structure with this tree.

void	Insert (const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], const DATATYPE &aData)
	Insert an item.

bool	Remove (const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], const DATATYPE &aData)
	Remove an item.

template<class VISITOR>
int	Search (const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], VISITOR &aVisitor) const
	Search for items whose bounding boxes overlap the query rectangle.

void	RemoveAll ()

void	BulkLoad (std::vector< BULK_ENTRY > &aEntries)

size_t	size () const

bool	empty () const

Iterator	begin () const

Iterator	end () const

Private Member Functions
void	ensureWritable (NODE *&aNode)
	Ensure a node is exclusively owned (refcount == 1).

void	releaseNode (NODE *aNode)
	Release a reference to a node.

void	freeToOwningAllocator (NODE *aNode)
	Free a node through the allocator that actually owns its memory.

void	releaseTree (NODE *aNode)
	Release the entire tree rooted at aNode.

void	insertSimple (NODE *aNode, const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], const DATATYPE &aData)
	Simplified insertion (no forced reinsert, just split on overflow).

void	simpleSplit (NODE *aNode, const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], const DATATYPE &aData)
	Simple split for CoW insertion: median split along longest axis.

bool	removeImpl (NODE *aNode, const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], const DATATYPE &aData)

template<class VISITOR>
void	searchImpl (NODE *aNode, const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], VISITOR &aVisitor, int &aFound) const

Private Attributes
NODE *	m_root = nullptr

size_t	m_count = 0

std::shared_ptr< ALLOC >	m_allocator

std::shared_ptr< ALLOC_CHAIN >	m_parentChain

Detailed Description

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>
class KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >

Copy-on-Write wrapper for DYNAMIC_RTREE.

Provides O(1) Clone() for the PNS router's branching pattern. The router frequently creates speculative branches that share most of their spatial index with the parent. Instead of copying all items, Clone() shares the tree structure via reference counting on nodes, only copying nodes along mutation paths.

When a node is shared between parent and clone (refcount > 1), any mutation first copies the node, decrements the old node's refcount, and increments refcounts on children that are now shared with the new copy.

Template Parameters

DATATYPE	Type of data stored in leaf nodes
ELEMTYPE	Coordinate element type (typically int)
NUMDIMS	Number of dimensions (2 or 3)
TMAXNODES	Maximum children per node (fanout)

Definition at line 55 of file dynamic_rtree_cow.h.

Member Typedef Documentation

◆ ALLOC

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

using KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::ALLOC = SLAB_ALLOCATOR<NODE>

Definition at line 59 of file dynamic_rtree_cow.h.

◆ BULK_ENTRY

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

using KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::BULK_ENTRY = typename DYNAMIC_RTREE<DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES>::BULK_ENTRY

Bulk load entries using Hilbert curve sorting and bottom-up packing.

Clears any existing tree first.

Definition at line 224 of file dynamic_rtree_cow.h.

◆ NODE

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

using KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::NODE = RTREE_NODE<DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES>

Definition at line 58 of file dynamic_rtree_cow.h.

Constructor & Destructor Documentation

◆ COW_RTREE() [1/3]

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::COW_RTREE ( )

inline

Definition at line 71 of file dynamic_rtree_cow.h.

◆ ~COW_RTREE()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::~COW_RTREE ( )

inline

Definition at line 76 of file dynamic_rtree_cow.h.

◆ COW_RTREE() [2/3]

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::COW_RTREE ( COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES > && aOther )

inlinenoexcept

Definition at line 82 of file dynamic_rtree_cow.h.

◆ COW_RTREE() [3/3]

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::COW_RTREE ( const COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES > & )

delete

Member Function Documentation

◆ begin()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

Iterator KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::begin ( ) const

inline

Definition at line 445 of file dynamic_rtree_cow.h.

◆ BulkLoad()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::BulkLoad ( std::vector< BULK_ENTRY > & aEntries )

inline

Definition at line 226 of file dynamic_rtree_cow.h.

◆ Clone()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

COW_RTREE KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Clone ( ) const

inline

Create a clone that shares the tree structure with this tree.

The clone holds a shared_ptr to the parent's allocator to keep nodes alive as long as any tree references them.

Definition at line 118 of file dynamic_rtree_cow.h.

Referenced by BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), and BOOST_AUTO_TEST_CASE().

◆ empty()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

bool KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::empty ( ) const

inline

Definition at line 355 of file dynamic_rtree_cow.h.

◆ end()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

Iterator KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::end ( ) const

inline

Definition at line 446 of file dynamic_rtree_cow.h.

◆ ensureWritable()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::ensureWritable ( NODE *& aNode )

inlineprivate

Ensure a node is exclusively owned (refcount == 1).

If shared, create a copy in our own allocator and decrement the original's refcount.

Definition at line 453 of file dynamic_rtree_cow.h.

Referenced by KIRTREE::COW_RTREE< T, int, 2 >::Insert(), KIRTREE::COW_RTREE< T, int, 2 >::insertSimple(), KIRTREE::COW_RTREE< T, int, 2 >::Remove(), and KIRTREE::COW_RTREE< T, int, 2 >::removeImpl().

◆ freeToOwningAllocator()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::freeToOwningAllocator ( NODE * aNode )

inlineprivate

Free a node through the allocator that actually owns its memory.

Without this, freeing a parent-allocated node through the clone's allocator would corrupt the page bitset and leak the slot.

Definition at line 521 of file dynamic_rtree_cow.h.

Referenced by KIRTREE::COW_RTREE< T, int, 2 >::releaseNode().

◆ Insert()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert	(	const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS],
		const DATATYPE &	aData )

inline

Insert an item.

If nodes along the path are shared, they are copied first.

Definition at line 140 of file dynamic_rtree_cow.h.

Referenced by BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), and BOOST_AUTO_TEST_CASE().

◆ insertSimple()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::insertSimple	(	NODE *	aNode,
		const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS],
		const DATATYPE &	aData )

inlineprivate

Simplified insertion (no forced reinsert, just split on overflow).

Sufficient for PNS router's incremental modifications to cloned trees.

Definition at line 553 of file dynamic_rtree_cow.h.

Referenced by KIRTREE::COW_RTREE< T, int, 2 >::Insert(), and KIRTREE::COW_RTREE< T, int, 2 >::insertSimple().

◆ operator=() [1/2]

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

COW_RTREE & KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::operator= ( const COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES > & )

delete

◆ operator=() [2/2]

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

COW_RTREE & KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::operator= ( COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES > && aOther )

inlinenoexcept

Definition at line 92 of file dynamic_rtree_cow.h.

◆ releaseNode()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::releaseNode ( NODE * aNode )

inlineprivate

Release a reference to a node.

If refcount drops to 0, free it through the allocator that owns the node's memory.

Definition at line 499 of file dynamic_rtree_cow.h.

Referenced by KIRTREE::COW_RTREE< T, int, 2 >::ensureWritable(), KIRTREE::COW_RTREE< T, int, 2 >::releaseNode(), KIRTREE::COW_RTREE< T, int, 2 >::releaseTree(), KIRTREE::COW_RTREE< T, int, 2 >::Remove(), and KIRTREE::COW_RTREE< T, int, 2 >::removeImpl().

◆ releaseTree()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::releaseTree ( NODE * aNode )

inlineprivate

Release the entire tree rooted at aNode.

Definition at line 544 of file dynamic_rtree_cow.h.

Referenced by KIRTREE::COW_RTREE< T, int, 2 >::operator=(), KIRTREE::COW_RTREE< T, int, 2 >::RemoveAll(), and KIRTREE::COW_RTREE< T, int, 2 >::~COW_RTREE().

◆ Remove()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

bool KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Remove	(	const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS],
		const DATATYPE &	aData )

inline

Remove an item.

If nodes along the path are shared, they are copied first.

Definition at line 161 of file dynamic_rtree_cow.h.

◆ RemoveAll()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::RemoveAll ( )

inline

Definition at line 213 of file dynamic_rtree_cow.h.

Referenced by KIRTREE::COW_RTREE< T, int, 2 >::BulkLoad().

◆ removeImpl()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

bool KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::removeImpl	(	NODE *	aNode,
		const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS],
		const DATATYPE &	aData )

inlineprivate

Definition at line 755 of file dynamic_rtree_cow.h.

Referenced by KIRTREE::COW_RTREE< T, int, 2 >::Remove(), and KIRTREE::COW_RTREE< T, int, 2 >::removeImpl().

◆ Search()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

template<class VISITOR>

int KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Search	(	const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS],
		VISITOR &	aVisitor ) const

inline

Search for items whose bounding boxes overlap the query rectangle.

Read-only, no CoW needed.

Definition at line 202 of file dynamic_rtree_cow.h.

Referenced by BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), and BOOST_AUTO_TEST_CASE().

◆ searchImpl()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

template<class VISITOR>

void KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::searchImpl	(	NODE *	aNode,
		const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS],
		VISITOR &	aVisitor,
		int &	aFound ) const

inlineprivate

Definition at line 804 of file dynamic_rtree_cow.h.

Referenced by KIRTREE::COW_RTREE< T, int, 2 >::Search(), and KIRTREE::COW_RTREE< T, int, 2 >::searchImpl().

◆ simpleSplit()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::simpleSplit	(	NODE *	aNode,
		const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS],
		const DATATYPE &	aData )

inlineprivate

Simple split for CoW insertion: median split along longest axis.

Definition at line 613 of file dynamic_rtree_cow.h.

Referenced by KIRTREE::COW_RTREE< T, int, 2 >::insertSimple().

◆ size()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

size_t KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size ( ) const

inline

Definition at line 354 of file dynamic_rtree_cow.h.

Referenced by BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), and BOOST_AUTO_TEST_CASE().

Member Data Documentation

◆ m_allocator

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

std::shared_ptr<ALLOC> KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::m_allocator

private

Definition at line 832 of file dynamic_rtree_cow.h.

Referenced by KIRTREE::COW_RTREE< T, int, 2 >::Clone().

◆ m_count

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

size_t KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::m_count = 0

private

Definition at line 831 of file dynamic_rtree_cow.h.

Referenced by KIRTREE::COW_RTREE< T, int, 2 >::Clone().

◆ m_parentChain

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

std::shared_ptr<ALLOC_CHAIN> KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::m_parentChain

private

Definition at line 833 of file dynamic_rtree_cow.h.

Referenced by KIRTREE::COW_RTREE< T, int, 2 >::Clone().

◆ m_root

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

NODE* KIRTREE::COW_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::m_root = nullptr

private

Definition at line 830 of file dynamic_rtree_cow.h.

Referenced by KIRTREE::COW_RTREE< T, int, 2 >::Clone().

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

dynamic_rtree_cow.h

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ ALLOC

◆ BULK_ENTRY

◆ NODE

Constructor & Destructor Documentation

◆ COW_RTREE() [1/3]

◆ ~COW_RTREE()

◆ COW_RTREE() [2/3]

◆ COW_RTREE() [3/3]

Member Function Documentation

◆ begin()

◆ BulkLoad()

◆ Clone()

◆ empty()

◆ end()

◆ ensureWritable()

◆ freeToOwningAllocator()

◆ Insert()

◆ insertSimple()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ releaseNode()

◆ releaseTree()

◆ Remove()

◆ RemoveAll()

◆ removeImpl()

◆ Search()

◆ searchImpl()

◆ simpleSplit()

◆ size()

Member Data Documentation

◆ m_allocator

◆ m_count

◆ m_parentChain

◆ m_root