R-tree node with Structure-of-Arrays bounding box layout. More...

#include <rtree_node.h>

Public Member Functions
	RTREE_NODE ()

bool	IsLeaf () const

bool	IsInternal () const

bool	IsFull () const

bool	IsUnderflow () const

void	ComputeEnclosingBounds (ELEMTYPE aMin[NUMDIMS], ELEMTYPE aMax[NUMDIMS]) const
	Compute the bounding box that encloses all children in this node.

int64_t	ChildArea (int i) const
	Compute the area (or volume for 3D) of child slot i's bounding box.

bool	ChildOverlaps (int i, const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS]) const
	Test whether child slot i's bounding box overlaps with the given query box.

uint32_t	ChildOverlapMask (const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS]) const
	Bitmask of children whose bounding boxes overlap the query rectangle.

int64_t	ChildOverlapArea (int i, const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS]) const
	Compute the overlap area between child slot i and the given box.

int64_t	ChildEnlargement (int i, const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS]) const
	Compute how much child slot i's area would increase if it were enlarged to include the given bounding box.

int64_t	ChildPerimeter (int i) const
	Compute the perimeter (or margin for 3D) of child slot i's bounding box.

void	SetChildBounds (int i, const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS])
	Set the bounding box for child slot i.

void	GetChildBounds (int i, ELEMTYPE aMin[NUMDIMS], ELEMTYPE aMax[NUMDIMS]) const
	Get the bounding box for child slot i.

void	SetInsertBounds (int i, const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS])
	Store the insertion bounding box for leaf entry i.

void	GetInsertBounds (int i, ELEMTYPE aMin[NUMDIMS], ELEMTYPE aMax[NUMDIMS]) const
	Get the stored insertion bounding box for leaf entry i.

void	RemoveChild (int i)
	Remove child at slot i by swapping with last entry.

Public Attributes
int	count = 0

int	level = 0

ELEMTYPE	bounds [NUMDIMS *2][MAXNODES]

union {

RTREE_NODE * children [MAXNODES]

DATATYPE data [MAXNODES]

};

ELEMTYPE	insertBounds [NUMDIMS *2][MAXNODES]

std::atomic< int >	refcount

Static Public Attributes
static constexpr int	MINNODES = MAXNODES * 2 / 5

Detailed Description

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>
struct KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >

R-tree node with Structure-of-Arrays bounding box layout.

Bounding boxes are stored in SoA format for cache-efficient scanning: bounds[axis * 2 + 0][slot] = min bound on axis bounds[axis * 2 + 1][slot] = max bound on axis

For 2D with MAXNODES=16, this means 4 arrays of 16 ints each (256 bytes total), fitting in exactly 4 cache lines. This enables compiler auto-vectorization of overlap checks.

Template Parameters

DATATYPE	Type of data stored in leaf nodes
ELEMTYPE	Coordinate element type (typically int)
NUMDIMS	Number of dimensions (2 or 3)
MAXNODES	Maximum children per node (fanout), should be 16 for SIMD alignment

Definition at line 298 of file rtree_node.h.

Constructor & Destructor Documentation

◆ RTREE_NODE()

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::RTREE_NODE ( )

inline

Definition at line 321 of file rtree_node.h.

Member Function Documentation

◆ ChildArea()

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

int64_t KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::ChildArea ( int i ) const

inline

Compute the area (or volume for 3D) of child slot i's bounding box.

Definition at line 360 of file rtree_node.h.

Referenced by KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::ChildEnlargement(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::chooseSubtree(), and KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::chooseSubtreeAtLevel().

◆ ChildEnlargement()

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

int64_t KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::ChildEnlargement	(	int	i,
		const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS] ) const

inline

Compute how much child slot i's area would increase if it were enlarged to include the given bounding box.

Definition at line 436 of file rtree_node.h.

Referenced by KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::chooseSubtree(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::chooseSubtreeAtLevel(), and KIRTREE::COW_RTREE< T, int, 2 >::insertSimple().

◆ ChildOverlapArea()

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

int64_t KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::ChildOverlapArea	(	int	i,
		const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS] ) const

inline

Compute the overlap area between child slot i and the given box.

Definition at line 413 of file rtree_node.h.

Referenced by KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::computeOverlap(), and KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::computeOverlapEnlarged().

◆ ChildOverlapMask()

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

uint32_t KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::ChildOverlapMask	(	const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS] ) const

inline

Bitmask of children whose bounding boxes overlap the query rectangle.

Bit i is set if child i overlaps. Uses SIMD on x86-64 and ARM for 2D.

Definition at line 388 of file rtree_node.h.

Referenced by KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::searchImpl().

◆ ChildOverlaps()

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

bool KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::ChildOverlaps	(	int	i,
		const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS] ) const

inline

Test whether child slot i's bounding box overlaps with the given query box.

Definition at line 373 of file rtree_node.h.

Referenced by KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::ChildOverlapMask(), KIRTREE::COW_RTREE< T, int, 2 >::removeImpl(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::removeImpl(), and KIRTREE::COW_RTREE< T, int, 2 >::searchImpl().

◆ ChildPerimeter()

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

int64_t KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::ChildPerimeter ( int i ) const

inline

Compute the perimeter (or margin for 3D) of child slot i's bounding box.

Used for split axis selection in R*-tree.

Definition at line 456 of file rtree_node.h.

◆ ComputeEnclosingBounds()

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

void KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::ComputeEnclosingBounds	(	ELEMTYPE	aMin[NUMDIMS],
		ELEMTYPE	aMax[NUMDIMS] ) const

inline

Compute the bounding box that encloses all children in this node.

Definition at line 336 of file rtree_node.h.

Referenced by KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::adjustPath(), KIRTREE::COW_RTREE< T, int, 2 >::BulkLoad(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::forcedReinsert(), KIRTREE::COW_RTREE< T, int, 2 >::insertSimple(), KIRTREE::COW_RTREE< T, int, 2 >::removeImpl(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::removeImpl(), KIRTREE::COW_RTREE< T, int, 2 >::simpleSplit(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::splitNode(), and KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::splitNodeInternal().

◆ GetChildBounds()

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

void KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::GetChildBounds	(	int	i,
		ELEMTYPE	aMin[NUMDIMS],
		ELEMTYPE	aMax[NUMDIMS] ) const

inline

Get the bounding box for child slot i.

Definition at line 481 of file rtree_node.h.

Referenced by KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::computeOverlap(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::computeOverlapEnlarged(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::forcedReinsert(), KIRTREE::COW_RTREE< T, int, 2 >::simpleSplit(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::splitNode(), and KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::splitNodeInternal().

◆ GetInsertBounds()

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

void KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::GetInsertBounds	(	int	i,
		ELEMTYPE	aMin[NUMDIMS],
		ELEMTYPE	aMax[NUMDIMS] ) const

inline

Get the stored insertion bounding box for leaf entry i.

Definition at line 505 of file rtree_node.h.

Referenced by KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::forcedReinsert(), KIRTREE::COW_RTREE< T, int, 2 >::simpleSplit(), and KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::splitNode().

◆ IsFull()

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

bool KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::IsFull ( ) const

inline

Definition at line 330 of file rtree_node.h.

Referenced by KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::insertImpl(), KIRTREE::COW_RTREE< T, int, 2 >::insertSimple(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::reinsertNode(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::splitNode(), and KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::splitNodeInternal().

◆ IsInternal()

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

bool KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::IsInternal ( ) const

inline

Definition at line 329 of file rtree_node.h.

Referenced by KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::chooseSubtree(), KIRTREE::COW_RTREE< T, int, 2 >::insertSimple(), KIRTREE::COW_RTREE< T, int, 2 >::releaseNode(), and KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::removeAllNodes().

◆ IsLeaf()

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

bool KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::IsLeaf ( ) const

inline

Definition at line 328 of file rtree_node.h.

Referenced by KIRTREE::COW_RTREE< T, int, 2 >::ensureWritable(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::forcedReinsert(), KIRTREE::COW_RTREE< T, int, 2 >::insertSimple(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::NearestNeighbors(), KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::RemoveChild(), KIRTREE::COW_RTREE< T, int, 2 >::removeImpl(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::removeImpl(), KIRTREE::COW_RTREE< T, int, 2 >::searchImpl(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::searchImpl(), and KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::splitNode().

◆ IsUnderflow()

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

bool KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::IsUnderflow ( ) const

inline

Definition at line 331 of file rtree_node.h.

◆ RemoveChild()

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

void KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::RemoveChild ( int i )

inline

Remove child at slot i by swapping with last entry.

Definition at line 517 of file rtree_node.h.

Referenced by KIRTREE::COW_RTREE< T, int, 2 >::removeImpl(), and KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::removeImpl().

◆ SetChildBounds()

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

void KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::SetChildBounds	(	int	i,
		const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS] )

inline

Set the bounding box for child slot i.

Definition at line 469 of file rtree_node.h.

Referenced by KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::adjustPath(), KIRTREE::COW_RTREE< T, int, 2 >::BulkLoad(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::forcedReinsert(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::insertImpl(), KIRTREE::COW_RTREE< T, int, 2 >::insertSimple(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::reinsertNode(), KIRTREE::COW_RTREE< T, int, 2 >::removeImpl(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::removeImpl(), KIRTREE::COW_RTREE< T, int, 2 >::simpleSplit(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::splitNode(), and KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::splitNodeInternal().

◆ SetInsertBounds()

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

void KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::SetInsertBounds	(	int	i,
		const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS] )

inline

Store the insertion bounding box for leaf entry i.

Definition at line 493 of file rtree_node.h.

Referenced by KIRTREE::COW_RTREE< T, int, 2 >::BulkLoad(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::forcedReinsert(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::insertImpl(), KIRTREE::COW_RTREE< T, int, 2 >::insertSimple(), KIRTREE::COW_RTREE< T, int, 2 >::simpleSplit(), and KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::splitNode().

Member Data Documentation

◆ [union]

union { ... } KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >

◆ bounds

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

ELEMTYPE KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::bounds[NUMDIMS *2][MAXNODES]

Definition at line 307 of file rtree_node.h.

Referenced by KIRTREE::COW_RTREE< T, int, 2 >::ensureWritable(), and KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::minDistSq().

◆ children

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

RTREE_NODE* KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::children[MAXNODES]

Definition at line 311 of file rtree_node.h.

◆ count

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

int KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::count = 0

Definition at line 302 of file rtree_node.h.

◆ data

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

DATATYPE KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::data[MAXNODES]

Definition at line 312 of file rtree_node.h.

Referenced by KIRTREE::COW_RTREE< T, int, 2 >::BulkLoad(), KIRTREE::COW_RTREE< T, int, 2 >::ensureWritable(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::forcedReinsert(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::insertImpl(), KIRTREE::COW_RTREE< T, int, 2 >::insertSimple(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::NearestNeighbors(), KIRTREE::COW_RTREE< T, int, 2 >::removeImpl(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::removeImpl(), KIRTREE::COW_RTREE< T, int, 2 >::searchImpl(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::searchImpl(), KIRTREE::COW_RTREE< T, int, 2 >::simpleSplit(), and KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::splitNode().

◆ insertBounds

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

ELEMTYPE KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::insertBounds[NUMDIMS *2][MAXNODES]

Definition at line 317 of file rtree_node.h.

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

◆ level

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

int KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::level = 0

Definition at line 303 of file rtree_node.h.

Referenced by KIRTREE::COW_RTREE< T, int, 2 >::BulkLoad(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::chooseSubtree(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::chooseSubtreeAtLevel(), KIRTREE::COW_RTREE< T, int, 2 >::ensureWritable(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::forcedReinsert(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::overflowTreatment(), KIRTREE::COW_RTREE< T, int, 2 >::simpleSplit(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::splitNode(), and KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::splitNodeInternal().

◆ MINNODES

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

int KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::MINNODES = MAXNODES * 2 / 5

staticconstexpr

Definition at line 300 of file rtree_node.h.

◆ refcount

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, int MAXNODES>

std::atomic<int> KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, MAXNODES >::refcount

Definition at line 319 of file rtree_node.h.

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

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

rtree_node.h

Public Member Functions

Public Attributes

Static Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ RTREE_NODE()

Member Function Documentation

◆ ChildArea()

◆ ChildEnlargement()

◆ ChildOverlapArea()

◆ ChildOverlapMask()

◆ ChildOverlaps()

◆ ChildPerimeter()

◆ ComputeEnclosingBounds()

◆ GetChildBounds()

◆ GetInsertBounds()

◆ IsFull()

◆ IsInternal()

◆ IsLeaf()

◆ IsUnderflow()

◆ RemoveChild()

◆ SetChildBounds()

◆ SetInsertBounds()

Member Data Documentation

◆ [union]

◆ bounds

◆ children

◆ count

◆ data

◆ insertBounds

◆ level

◆ MINNODES

◆ refcount