C/C++ API Reference
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Private Member Functions | List of all members
pw::allocator::BestFitAllocator< BlockType > Class Template Reference
pw_allocator » Concrete allocators » Block allocators

Overview

template<typename BlockType = BestFitBlock<uintptr_t>>
class pw::allocator::BestFitAllocator< BlockType >

Block allocator that uses a "best-fit" allocation strategy.

In this strategy, the allocator handles an allocation request by looking at all unused blocks and finding the smallest one which can satisfy the request.

This algorithm may make better use of available memory by wasting less on unused fragments, but may also lead to worse fragmentation as those fragments are more likely to be too small to be useful to other requests.

Inheritance diagram for pw::allocator::BestFitAllocator< BlockType >:
pw::allocator::BlockAllocator< BlockType_ > pw::allocator::internal::GenericBlockAllocator pw::Allocator pw::Deallocator

Public Types

using Base = BlockAllocator< BlockType >
 
- Public Types inherited from pw::allocator::BlockAllocator< BlockType_ >
using BlockType = BlockType_
 
using Range = typename BlockType::Range
 
- Public Types inherited from pw::Allocator
using Fragmentation = allocator::Fragmentation
 
- Public Types inherited from pw::Deallocator
using Capabilities = allocator::Capabilities
 
using Capability = allocator::Capability
 
using Layout = allocator::Layout
 

Public Member Functions

constexpr BestFitAllocator ()=default
 Constexpr constructor. Callers must explicitly call Init.
 
 BestFitAllocator (ByteSpan region)
 
- Public Member Functions inherited from pw::allocator::BlockAllocator< BlockType_ >
Range blocks () const
 Returns a Range of blocks tracking the memory of this allocator.
 
void Init (ByteSpan region)
 
size_t GetMaxAllocatable ()
 
- Public Member Functions inherited from pw::allocator::internal::GenericBlockAllocator
 GenericBlockAllocator (const GenericBlockAllocator &)=delete
 
GenericBlockAllocator & operator= (const GenericBlockAllocator &)=delete
 
 GenericBlockAllocator (GenericBlockAllocator &&)=delete
 
GenericBlockAllocator & operator= (GenericBlockAllocator &&)=delete
 
- Public Member Functions inherited from pw::Allocator
void * Allocate (Layout layout)
 
template<typename T , int &... kExplicitGuard, std::enable_if_t<!std::is_array_v< T >, int > = 0, typename... Args>
T * New (Args &&... args)
 
template<typename T , int &... kExplicitGuard, typename ElementType = std::remove_extent_t<T>, std::enable_if_t< is_bounded_array_v< T >, int > = 0>
ElementType * New ()
 
template<typename T , int &... kExplicitGuard, typename ElementType = std::remove_extent_t<T>, std::enable_if_t< is_unbounded_array_v< T >, int > = 0>
ElementType * New (size_t count)
 
template<typename T , int &... kExplicitGuard, typename ElementType = std::remove_extent_t<T>, std::enable_if_t< is_unbounded_array_v< T >, int > = 0>
ElementType * New (size_t count, size_t alignment)
 Constructs an alignment-byte aligned array of count objects.
 
template<typename T , int &... kExplicitGuard, std::enable_if_t<!std::is_array_v< T >, int > = 0, typename... Args>
UniquePtr< T > MakeUnique (Args &&... args)
 
template<typename T , std::enable_if_t< is_unbounded_array_v< T >, int > = 0>
UniquePtr< T > MakeUnique (size_t size)
 
template<typename T , std::enable_if_t< is_unbounded_array_v< T >, int > = 0>
UniquePtr< T > MakeUnique (size_t size, size_t alignment)
 
template<typename T , std::enable_if_t< is_bounded_array_v< T >, int > = 0>
UniquePtr< T > MakeUnique ()
 
template<typename T , int &... kExplicitGuard, std::enable_if_t<!std::is_array_v< T >, int > = 0, typename... Args>
SharedPtr< T > MakeShared (Args &&... args)
 
template<typename T , std::enable_if_t< is_unbounded_array_v< T >, int > = 0>
SharedPtr< T > MakeShared (size_t size)
 
template<typename T , std::enable_if_t< is_unbounded_array_v< T >, int > = 0>
SharedPtr< T > MakeShared (size_t size, size_t alignment)
 
template<typename T , std::enable_if_t< is_bounded_array_v< T >, int > = 0>
SharedPtr< T > MakeShared ()
 
bool Resize (void *ptr, size_t new_size)
 
void * Reallocate (void *ptr, Layout new_layout)
 
size_t GetAllocated () const
 
std::optional< Fragmentation > MeasureFragmentation () const
 Returns fragmentation information for the allocator's memory region.
 
- Public Member Functions inherited from pw::Deallocator
constexpr const Capabilities & capabilities () const
 
constexpr bool HasCapability (Capability capability) const
 Returns whether a given capability is enabled for this object.
 
void Deallocate (void *ptr)
 
template<typename ElementType >
void DeleteArray (ElementType *ptr, size_t count)
 
StatusWithSize GetCapacity () const
 
bool IsEqual (const Deallocator &other) const
 
template<typename T , int &... kExplicitGuard, std::enable_if_t<!std::is_array_v< T >, int > = 0>
void Delete (T *ptr)
 
template<typename T , int &... kExplicitGuard, typename ElementType = std::remove_extent_t<T>, std::enable_if_t< is_bounded_array_v< T >, int > = 0>
void Delete (ElementType *ptr)
 
template<typename T , int &... kExplicitGuard, typename ElementType = std::remove_extent_t<T>, std::enable_if_t< is_unbounded_array_v< T >, int > = 0>
void Delete (ElementType *ptr, size_t count)
 

Private Member Functions

size_t DoGetMaxAllocatable () override
 
BlockResult< BlockType > ChooseBlock (Layout layout) override
 
void ReserveBlock (BlockType &block) override
 
void RecycleBlock (BlockType &block) override
 

Additional Inherited Members

- Static Public Attributes inherited from pw::allocator::BlockAllocator< BlockType_ >
static constexpr Capabilities kCapabilities
 
static constexpr size_t kPoisonInterval = PW_ALLOCATOR_BLOCK_POISON_INTERVAL
 
- Protected Types inherited from pw::Deallocator
enum class  InfoType {
  kRequestedLayoutOf , kUsableLayoutOf , kAllocatedLayoutOf , kCapacity ,
  kRecognizes
}
 
- Protected Member Functions inherited from pw::allocator::BlockAllocator< BlockType_ >
void * DoAllocate (Layout layout) override
 
void DoDeallocate (void *ptr) override
 
bool DoResize (void *ptr, size_t new_size) override
 
size_t DoGetAllocated () const override
 
std::optional< Fragmentation > DoMeasureFragmentation () const override
 Returns fragmentation information for the allocator's memory region.
 
Result< Layout > DoGetInfo (InfoType info_type, const void *ptr) const override
 
void Init (BlockType *begin)
 
template<typename Ptr >
internal::copy_const_ptr_t< Ptr, BlockType * > FromUsableSpace (Ptr ptr) const
 
virtual void DeallocateBlock (BlockType *&&block)
 
- Protected Member Functions inherited from pw::allocator::internal::GenericBlockAllocator
constexpr GenericBlockAllocator (Capabilities capabilities)
 
- Protected Member Functions inherited from pw::Allocator
constexpr Allocator ()=default
 TODO(b/326509341): Remove when downstream consumers migrate.
 
constexpr Allocator (const Capabilities &capabilities)
 
virtual void * DoAllocate (Layout layout)=0
 
virtual bool DoResize (void *ptr, size_t new_size)
 
virtual void * DoReallocate (void *ptr, Layout new_layout)
 
virtual size_t DoGetAllocated () const
 
virtual std::optional< Fragmentation > DoMeasureFragmentation () const
 Returns fragmentation information for the allocator's memory region.
 
- Protected Member Functions inherited from pw::Deallocator
constexpr Deallocator ()=default
 TODO(b/326509341): Remove when downstream consumers migrate.
 
constexpr Deallocator (const Capabilities &capabilities)
 
Result< Layout > GetInfo (InfoType info_type, const void *ptr) const
 
Result< Layout > GetRequestedLayout (const void *ptr) const
 
Result< Layout > GetUsableLayout (const void *ptr) const
 
Result< Layout > GetAllocatedLayout (const void *ptr) const
 
bool Recognizes (const void *ptr) const
 
virtual void DoDeallocate (void *ptr)=0
 
virtual Result< Layout > DoGetInfo (InfoType, const void *) const
 
- Static Protected Member Functions inherited from pw::allocator::internal::GenericBlockAllocator
template<typename BlockType >
static constexpr Capabilities GetCapabilities ()
 
static void CrashOnAllocated (const void *allocated)
 
static void CrashOnOutOfRange (const void *freed)
 
static void CrashOnDoubleFree (const void *freed)
 Crashes with an informational message that a given block was freed twice.
 
- Static Protected Member Functions inherited from pw::Deallocator
static Result< Layout > GetInfo (const Deallocator &deallocator, InfoType info_type, const void *ptr)
 
static Result< Layout > GetRequestedLayout (const Deallocator &deallocator, const void *ptr)
 
static Result< Layout > GetUsableLayout (const Deallocator &deallocator, const void *ptr)
 
static Result< Layout > GetAllocatedLayout (const Deallocator &deallocator, const void *ptr)
 
static bool Recognizes (const Deallocator &deallocator, const void *ptr)
 
- Static Protected Attributes inherited from pw::Deallocator
template<typename T >
static constexpr bool is_bounded_array_v = ::pw::is_bounded_array_v<T>
 
template<typename T >
static constexpr bool is_unbounded_array_v = ::pw::is_unbounded_array_v<T>
 

Constructor & Destructor Documentation

◆ BestFitAllocator()

template<typename BlockType = BestFitBlock<uintptr_t>>
pw::allocator::BestFitAllocator< BlockType >::BestFitAllocator ( ByteSpan  region)
inline

Non-constexpr constructor that automatically calls Init.

Parameters
[in]regionRegion of memory to use when satisfying allocation requests. The region MUST be valid as an argument to BlockType::Init.
The documentation for this class was generated from the following file: