pw::allocator::internal::BucketBase< Derived, BlockType_, ItemType_ > Class Template Reference

Overview

template<typename Derived, typename BlockType_, typename ItemType_>
class pw::allocator::internal::BucketBase< Derived, BlockType_, ItemType_ >

A container of free blocks.

Allocators can use buckets to manage their free blocks. This may include using buckets to sort free blocks based on their size, partitioning them into several buckets, etc., for faster searching when allocating. Each bucket may have a maximum block inner size set which indicates the largest free block allowable in the bucket, or be unbounded.

This class is a CRTP-style base class. The specific derived class includes an intrusive container type from pw_containers. The usable space of free blocks added to the bucket is used to store the intrusive item corresponding to the container.

This implies that a block must be large enough to hold the item type in order to be added to a bucket. Since intrusive items can be part of at most one container at any point in time, free blocks can be in at most ONE bucket at any time. However, a sufficiently large block may be sequentially added to more than one type of bucket. This can be useful for allocators that may track blocks in more than one way, e.g. an allocator that caches recently freed blocks.

Template Parameters

Derived	Bucket type derived from this base class.
BlockType	Type of free blocks that can be held in this bucket.
ItemType	Intrusive pw_containers type. The usable space of each free block in the bucket will hold an item of this type.

Inheritance diagram for pw::allocator::internal::BucketBase< Derived, BlockType_, ItemType_ >:

Public Types
using	BlockType = BlockType_
using	ItemType = ItemType_

Public Member Functions
constexpr bool	empty () const
	Returns whether this buckets contains any free blocks.
constexpr size_t	max_inner_size () const
	Returns the configured maximum inner size for blocks in this bucket.
constexpr void	set_max_inner_size (size_t max_inner_size)
bool	Add (BlockType &block)
const BlockType *	FindLargest () const
BlockType *	RemoveAny ()
bool	Remove (BlockType &block)
BlockType *	RemoveCompatible (Layout layout)
void	Clear ()
	Removes all blocks from this bucket.

Static Protected Member Functions
template<typename Iterator , typename Predicate >
static Iterator	FindPrevIf (Iterator before_first, Iterator last, Predicate predicate)
static auto	MakeCanAllocPredicate (Layout layout)
static bool	Compare (const ItemType &item1, const ItemType &item2)
template<typename Iterator >
static constexpr BlockType *	GetBlockFromIterator (Iterator iter, Iterator last)
template<typename Iterator >
static constexpr BlockType *	GetBlockFromPrev (Iterator prev, Iterator last)
static ItemType &	GetItemFrom (BlockType &block)

Member Function Documentation

Add()

template<typename Derived , typename BlockType_ , typename ItemType_ >

bool pw::allocator::internal::BucketBase< Derived, BlockType_, ItemType_ >::Add ( BlockType &  block )

inline

Adds a block to this bucket if the block can hold an item of the bucket's ItemType, otherwise does nothing.

Parameters

block

The block to be added.

Compare()

template<typename Derived , typename BlockType_ , typename ItemType_ >

static bool pw::allocator::internal::BucketBase< Derived, BlockType_, ItemType_ >::Compare ( const ItemType &  item1, const ItemType &  item2  )

inlinestaticprotected

Returns whether the first item represents a block with a smaller inner size than the block represented by the second item.

FindLargest()

template<typename Derived , typename BlockType_ , typename ItemType_ >

const BlockType * pw::allocator::internal::BucketBase< Derived, BlockType_, ItemType_ >::FindLargest ( ) const

inline

Returns the block of the largest inner size in the bucket, or null if the bucket is empty.

FindPrevIf()

template<typename Derived , typename BlockType_ , typename ItemType_ >

template<typename Iterator , typename Predicate >

static Iterator pw::allocator::internal::BucketBase< Derived, BlockType_, ItemType_ >::FindPrevIf ( Iterator  before_first, Iterator  last, Predicate  predicate  )

inlinestaticprotected

Returns an iterator the first element in a range whose successor satisfies a given predicate.

The returned iterator will be in the range [before_first, last), and will be the element before the first element that satisfies the predicate.

This is intended to act similar to std::find_if in order to return iterators that can be used with sorted forward lists like std::forward_list<T> or pw::IntrusiveForwardList<T>. In particular, methods likeinsert_afteranderase_after` need the iterator that precedes a desired item.

GetBlockFromIterator()

template<typename Derived , typename BlockType_ , typename ItemType_ >

template<typename Iterator >

static constexpr BlockType * pw::allocator::internal::BucketBase< Derived, BlockType_, ItemType_ >::GetBlockFromIterator ( Iterator  iter, Iterator  last  )

inlinestaticconstexprprotected

Returns the block storing the item pointed to by the provided iter, or null if the iterator is the last iterator.

GetBlockFromPrev()

template<typename Derived , typename BlockType_ , typename ItemType_ >

template<typename Iterator >

static constexpr BlockType * pw::allocator::internal::BucketBase< Derived, BlockType_, ItemType_ >::GetBlockFromPrev ( Iterator  prev, Iterator  last  )

inlinestaticconstexprprotected

Returns the block storing the item after the provided prev iterator, or null if the iterator points to the element before the last iterator.

GetItemFrom()

template<typename Derived , typename BlockType_ , typename ItemType_ >

static ItemType & pw::allocator::internal::BucketBase< Derived, BlockType_, ItemType_ >::GetItemFrom ( BlockType &  block )

inlinestaticprotected

Returns an existing item stored in a free block's usable space.

The item is created when adding a block to a bucket, that is, in the derived type's implementation of DoAdd.

Precondition

the block must have been added to a bucket of type Derived.

MakeCanAllocPredicate()

template<typename Derived , typename BlockType_ , typename ItemType_ >

static auto pw::allocator::internal::BucketBase< Derived, BlockType_, ItemType_ >::MakeCanAllocPredicate ( Layout  layout )

inlinestaticprotected

Returns a lambda that tests if the blocks storing an item can be allocated with the given layout.

This lambda can be used with std::find_if and FindPrevIf.

Remove()

template<typename Derived , typename BlockType_ , typename ItemType_ >

bool pw::allocator::internal::BucketBase< Derived, BlockType_, ItemType_ >::Remove ( BlockType &  block )

inline

If the given block is in this bucket, removes it and returns true; otherwise, returns false.

Parameters

block

The block to be removed.

RemoveAny()

template<typename Derived , typename BlockType_ , typename ItemType_ >

BlockType * pw::allocator::internal::BucketBase< Derived, BlockType_, ItemType_ >::RemoveAny ( )

inline

Removes and returns a block if the bucket is not empty; otherwise returns null. Exactly which block is returned depends on the specific bucket implementation.

RemoveCompatible()

template<typename Derived , typename BlockType_ , typename ItemType_ >

BlockType * pw::allocator::internal::BucketBase< Derived, BlockType_, ItemType_ >::RemoveCompatible ( Layout  layout )

inline

Removes and returns a block that can be allocated with the given layout, or null if no such block is present in the bucket.

Bucket implementations must only return a block if block->CanAlloc(layout) would succeed.

Parameters

layout

Allocatable layout of the block to be removed.

set_max_inner_size()

template<typename Derived , typename BlockType_ , typename ItemType_ >

constexpr void pw::allocator::internal::BucketBase< Derived, BlockType_, ItemType_ >::set_max_inner_size ( size_t  max_inner_size )

inlineconstexpr

Sets the maximum inner size for blocks in this bucket.

This can only be called when the bucket is empty.

---

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

• pw_allocator/bucket/public/pw_allocator/bucket/base.h