KiCad PCB EDA Suite
Loading...
Searching...
No Matches
Classes | Public Member Functions | Static Public Attributes | Private Member Functions | Private Attributes | List of all members
KIRTREE::SLAB_ALLOCATOR< NODE > Class Template Reference

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

#include <rtree_node.h>

Classes

struct  PAGE
 

Public Member Functions

 SLAB_ALLOCATOR ()=default
 
 ~SLAB_ALLOCATOR ()=default
 
 SLAB_ALLOCATOR (const SLAB_ALLOCATOR &)=delete
 
SLAB_ALLOCATOR & operator= (const SLAB_ALLOCATOR &)=delete
 
 SLAB_ALLOCATOR (SLAB_ALLOCATOR &&aOther) noexcept
 
SLAB_ALLOCATOR & operator= (SLAB_ALLOCATOR &&aOther) noexcept
 
NODE * Allocate ()
 Allocate a new node, either from the free list or from a new page.
 
void Free (NODE *aNode)
 Return a node to the free list for reuse.
 
size_t MemoryUsage () const
 Return approximate memory usage in bytes.
 
bool Owns (const NODE *aNode) const
 Check if a node was allocated from one of this allocator's pages.
 

Static Public Attributes

static constexpr size_t NODES_PER_PAGE = 256
 

Private Member Functions

PAGE * findOwningPage (const NODE *aNode, size_t &aOffset) const
 Find the page that contains aNode using address-range comparison (no UB).
 
void markUsed (NODE *aNode)
 
void markUnused (NODE *aNode)
 

Private Attributes

std::vector< std::unique_ptr< PAGE > > m_pages
 
std::vector< NODE * > m_freeList
 

Detailed Description

template<class NODE>
class KIRTREE::SLAB_ALLOCATOR< NODE >

Pool allocator for R-tree nodes.

Allocates nodes in fixed-size pages (slabs) to reduce allocation overhead and improve cache locality. Freed nodes are recycled via a free list. All pages are freed on allocator destruction.

Template Parameters
NODEthe RTREE_NODE type

Definition at line 551 of file rtree_node.h.

Constructor & Destructor Documentation

◆ SLAB_ALLOCATOR() [1/3]

template<class NODE>
KIRTREE::SLAB_ALLOCATOR< NODE >::SLAB_ALLOCATOR ( )
default

Referenced by operator=(), operator=(), SLAB_ALLOCATOR(), and SLAB_ALLOCATOR().

◆ ~SLAB_ALLOCATOR()

template<class NODE>
KIRTREE::SLAB_ALLOCATOR< NODE >::~SLAB_ALLOCATOR ( )
default

◆ SLAB_ALLOCATOR() [2/3]

template<class NODE>
KIRTREE::SLAB_ALLOCATOR< NODE >::SLAB_ALLOCATOR ( const SLAB_ALLOCATOR< NODE > & )
delete

References SLAB_ALLOCATOR().

◆ SLAB_ALLOCATOR() [3/3]

template<class NODE>
KIRTREE::SLAB_ALLOCATOR< NODE >::SLAB_ALLOCATOR ( SLAB_ALLOCATOR< NODE > && aOther)
inlinenoexcept

Definition at line 573 of file rtree_node.h.

References SLAB_ALLOCATOR().

Member Function Documentation

◆ Allocate()

template<class NODE>
NODE * KIRTREE::SLAB_ALLOCATOR< NODE >::Allocate ( )
inline

Allocate a new node, either from the free list or from a new page.

Definition at line 593 of file rtree_node.h.

References m_freeList, m_pages, markUsed(), KIRTREE::SLAB_ALLOCATOR< NODE >::PAGE::nodes, NODES_PER_PAGE, and KIRTREE::SLAB_ALLOCATOR< NODE >::PAGE::used.

◆ findOwningPage()

template<class NODE>
PAGE * KIRTREE::SLAB_ALLOCATOR< NODE >::findOwningPage ( const NODE * aNode,
size_t & aOffset ) const
inlineprivate

Find the page that contains aNode using address-range comparison (no UB).

Returns the page and sets aOffset to the slot index, or nullptr if not found.

Definition at line 672 of file rtree_node.h.

References end, m_pages, and NODES_PER_PAGE.

Referenced by markUnused(), markUsed(), and Owns().

◆ Free()

template<class NODE>
void KIRTREE::SLAB_ALLOCATOR< NODE >::Free ( NODE * aNode)
inline

Return a node to the free list for reuse.

Definition at line 637 of file rtree_node.h.

References m_freeList, and markUnused().

◆ markUnused()

template<class NODE>
void KIRTREE::SLAB_ALLOCATOR< NODE >::markUnused ( NODE * aNode)
inlineprivate

Definition at line 701 of file rtree_node.h.

References findOwningPage(), and KIRTREE::SLAB_ALLOCATOR< NODE >::PAGE::used.

Referenced by Free().

◆ markUsed()

template<class NODE>
void KIRTREE::SLAB_ALLOCATOR< NODE >::markUsed ( NODE * aNode)
inlineprivate

Definition at line 692 of file rtree_node.h.

References findOwningPage(), and KIRTREE::SLAB_ALLOCATOR< NODE >::PAGE::used.

Referenced by Allocate().

◆ MemoryUsage()

template<class NODE>
size_t KIRTREE::SLAB_ALLOCATOR< NODE >::MemoryUsage ( ) const
inline

Return approximate memory usage in bytes.

Definition at line 652 of file rtree_node.h.

References m_freeList, and m_pages.

◆ operator=() [1/2]

template<class NODE>
SLAB_ALLOCATOR & KIRTREE::SLAB_ALLOCATOR< NODE >::operator= ( const SLAB_ALLOCATOR< NODE > & )
delete

References SLAB_ALLOCATOR().

◆ operator=() [2/2]

template<class NODE>
SLAB_ALLOCATOR & KIRTREE::SLAB_ALLOCATOR< NODE >::operator= ( SLAB_ALLOCATOR< NODE > && aOther)
inlinenoexcept

Definition at line 579 of file rtree_node.h.

References m_freeList, m_pages, and SLAB_ALLOCATOR().

◆ Owns()

template<class NODE>
bool KIRTREE::SLAB_ALLOCATOR< NODE >::Owns ( const NODE * aNode) const
inline

Check if a node was allocated from one of this allocator's pages.

Definition at line 661 of file rtree_node.h.

References findOwningPage().

Member Data Documentation

◆ m_freeList

template<class NODE>
std::vector<NODE*> KIRTREE::SLAB_ALLOCATOR< NODE >::m_freeList
private

Definition at line 711 of file rtree_node.h.

Referenced by Allocate(), Free(), MemoryUsage(), and operator=().

◆ m_pages

template<class NODE>
std::vector<std::unique_ptr<PAGE> > KIRTREE::SLAB_ALLOCATOR< NODE >::m_pages
private

Definition at line 710 of file rtree_node.h.

Referenced by Allocate(), findOwningPage(), MemoryUsage(), and operator=().

◆ NODES_PER_PAGE

template<class NODE>
size_t KIRTREE::SLAB_ALLOCATOR< NODE >::NODES_PER_PAGE = 256
staticconstexpr

Definition at line 554 of file rtree_node.h.

Referenced by Allocate(), and findOwningPage().

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