Classes
class	COW_RTREE
	Copy-on-Write wrapper for DYNAMIC_RTREE. More...

class	DYNAMIC_RTREE
	Dynamic R*-tree with SoA node layout and stored insertion bounding boxes. More...

class	PACKED_RTREE
	Static (immutable) packed R-tree built via Hilbert-curve bulk loading. More...

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

class	SLAB_ALLOCATOR
	Pool allocator for R-tree nodes. More...

Functions
uint64_t	HilbertXY2D (int aOrder, uint32_t aX, uint32_t aY)
	Compute a 64-bit Hilbert curve index from 2D unsigned coordinates.

template<int NUMDIMS>
uint64_t	HilbertND2D (int aOrder, const uint32_t aCoords[NUMDIMS])
	Compute Hilbert index for N-dimensional coordinates.

template<class ELEMTYPE, int FANOUT>
uint32_t	OverlapMask2D (const ELEMTYPE aBoundsMin0, const ELEMTYPE aBoundsMax0, const ELEMTYPE aBoundsMin1, const ELEMTYPE aBoundsMax1, int aCount, const ELEMTYPE aMin[2], const ELEMTYPE aMax[2])
	Compute a bitmask of which child slots overlap a 2D query rectangle.

Function Documentation

◆ HilbertND2D()

template<int NUMDIMS>

uint64_t KIRTREE::HilbertND2D	(	int	aOrder,
		const uint32_t	aCoords[NUMDIMS] )

inline

Compute Hilbert index for N-dimensional coordinates.

For 2D, delegates to the optimized HilbertXY2D. For higher dimensions, uses a generalized algorithm that interleaves bits across dimensions with appropriate rotations.

Template Parameters

NUMDIMS number of dimensions

Parameters

aOrder	Hilbert curve order (bits per axis)
aCoords	array of NUMDIMS unsigned coordinates

Returns: 64-bit Hilbert index

Definition at line 101 of file rtree_node.h.

References HilbertXY2D().

Referenced by KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::Builder::Build(), and KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::BulkLoad().

◆ HilbertXY2D()

uint64_t KIRTREE::HilbertXY2D	(	int	aOrder,
		uint32_t	aX,
		uint32_t	aY )

inline

Compute a 64-bit Hilbert curve index from 2D unsigned coordinates.

Uses the standard iterative bit-manipulation algorithm for order-32 Hilbert curve, mapping 2 uint32 coordinates to a single uint64 index. This provides excellent spatial locality for R-tree bulk loading.

Parameters

aOrder	Hilbert curve order (bits per axis, typically 32)
aX	X coordinate in [0, 2^aOrder)
aY	Y coordinate in [0, 2^aOrder)

Returns: 64-bit Hilbert index

Definition at line 57 of file rtree_node.h.

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

◆ OverlapMask2D()

template<class ELEMTYPE, int FANOUT>

uint32_t KIRTREE::OverlapMask2D	(	const ELEMTYPE *	aBoundsMin0,
		const ELEMTYPE *	aBoundsMax0,
		const ELEMTYPE *	aBoundsMin1,
		const ELEMTYPE *	aBoundsMax1,
		int	aCount,
		const ELEMTYPE	aMin[2],
		const ELEMTYPE	aMax[2] )

inline

Compute a bitmask of which child slots overlap a 2D query rectangle.

Bit i of the result is set when the bounding box in slot i overlaps the query. Each bounds pointer must address FANOUT contiguous elements in SoA layout.

Uses SSE2 on x86-64, NEON on ARM, or an auto-vectorization-friendly scalar fallback on other architectures.

Template Parameters

ELEMTYPE	Coordinate type (SIMD paths require 32-bit integer)
FANOUT	Number of child slots per node (must be a multiple of 4, max 31)

Parameters

aBoundsMin0	Dim-0 lower bounds array [FANOUT]
aBoundsMax0	Dim-0 upper bounds array [FANOUT]
aBoundsMin1	Dim-1 lower bounds array [FANOUT]
aBoundsMax1	Dim-1 upper bounds array [FANOUT]
aCount	Number of valid children (0..FANOUT)
aMin	Query rectangle minimum corner [2]
aMax	Query rectangle maximum corner [2]

Definition at line 148 of file rtree_node.h.

References result.

Referenced by KIRTREE::RTREE_NODE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::ChildOverlapMask(), and KIRTREE::PACKED_RTREE< CREEPAGE_TRACK_ENTRY *, int, 2 >::searchNode().

Classes

Functions

Function Documentation

◆ HilbertND2D()

◆ HilbertXY2D()

◆ OverlapMask2D()