SG::ArenaHeapAllocator Class Reference

Heap-based allocator. More...

#include <ArenaHeapAllocator.h>

Inheritance diagram for SG::ArenaHeapAllocator:

Collaboration diagram for SG::ArenaHeapAllocator:

Classes
struct	initParams
	Helper to initialize a parameters structure. More...

Public Types
typedef void	iterator
typedef void	const_iterator
typedef char *	pointer
	Type for pointers to elements. More...
typedef const char *	const_pointer
	And a const version of the pointer. More...
typedef void	func_t(pointer)
	Type of functions for constructor, etc. More...

Public Member Functions
	ArenaHeapAllocator (const Params &params)
	Constructor. More...
virtual	~ArenaHeapAllocator ()
	Destructor. More...
	ArenaHeapAllocator (const ArenaHeapAllocator &)=delete
	Don't allow copy construction or assignment. More...
ArenaHeapAllocator &	operator= (const ArenaHeapAllocator &)=delete
	ArenaHeapAllocator (ArenaHeapAllocator &&other)
	Move constructor. More...
ArenaHeapAllocator &	operator= (ArenaHeapAllocator &&other)
	Move assignment. More...
void	swap (ArenaHeapAllocator &other)
	Swap. More...
pointer	allocate ()
	Allocate a new element. More...
void	free (pointer p)
	Free an element. More...
virtual void	reset () override
	Free all allocated elements. More...
virtual void	erase () override final
	Free all allocated elements and release memory back to the system. More...
void	swap (ArenaBlockAllocatorBase &other)
	Swap. More...
virtual void	reserve (size_t size) override
	Set the total number of elements cached by the allocator. More...
virtual Stats	stats () const override
	Return the statistics block for this allocator. More...
virtual const std::string &	name () const override
	Return the name of this allocator. More...
const Params &	params () const
	Return this Allocator's parameters. More...
void	protect ()
	Write-protect the memory managed by this allocator. More...
void	unprotect ()
	Write-enable the memory managed by this allocator. More...
virtual void	report (std::ostream &os) const
	Generate a report on the memory usage of this allocator. More...

Static Public Member Functions
template<class T >
static func_t *	makeConstructor (const std::false_type &)
	Make a constructor function pointer for a non-trivial constructor. More...
template<class T >
static func_t *	makeConstructor (const std::true_type &)
	Make a constructor function pointer for a trivial constructor. More...
template<class T >
static func_t *	makeDestructor (const std::false_type &)
	Make a constructor function pointer for a non-trivial destructor. More...
template<class T >
static func_t *	makeDestructor (const std::true_type &)
	Make a constructor function pointer for a trivial destructor. More...
template<class T >
static func_t *	makeClear (const std::false_type &)
	Make a function pointer for a clear function. More...
template<class T >
static func_t *	makeClear (const std::true_type &)
	Make a dummy clear function pointer. More...

Protected Member Functions
ArenaBlock *	getBlock ()
	Return an empty block, either newly-allocated or from the free list. More...

Protected Attributes
Params	m_params
	The parameters for this allocator. More...
ArenaBlock *	m_blocks
	The list of blocks currently in use. More...
ArenaBlock *	m_freeblocks
	The list of free blocks. More...
ArenaAllocatorBase::Stats	m_stats
	The statistics structure. More...
bool	m_protected
	Flag whether the arena has been protected. More...

Private Member Functions
void	slowClear ()
	Call clear() for all allocated elements. More...
pointer	refill ()
	Add more free elements to the pool, and allocate a new element. More...
pointer &	link (pointer p) const
	Return a reference to the link for an element. More...

Static Private Member Functions
template<typename T >
static void	construct_fcn (pointer p)
	Call T's default constructor on the object at p. More...
template<typename T >
static void	destroy_fcn (pointer p)
	Call T's destructor on the object at p. More...
template<typename T >
static void	clear_fcn (pointer p)
	Call T::clear on the object at p. More...

Private Attributes
pointer	m_freeptr
	Pointer to the next free element. More...

Detailed Description

Heap-based allocator.

See Arena.h for an overview of the arena-based memory allocators.

This is a block-based memory allocator, with heap-like behavior. This allows freeing individual elements, but we don't implement resetTo or an iterator.

There are some extra costs though.

• We need an additional pointer (‘link’) for each free element.

  By default, this is done by increasing the element size by a pointer, since we don't know whether there is data in the element itself that must be preserved across free/allocate. However, if you know that part of the element may be safely while it is free, then the allocator can be configured to use that as the link instead.

• When reset() is called, we need to call clear() on all allocated elements (if it is defined). If canReclear is set, then we just call clear() on all elements in allocated blocks on reset(), regardless of whether or not the individual elements are allocated or not. Otherwise, we make two passes over the elements, first to build a list of those that are allocated and second to actually call clear().

  An intermediate strategy, not currently implemented, could be used if the link does not overlap the element: set the link to a magic value when an element is allocated.

Definition at line 62 of file ArenaHeapAllocator.h.

Member Typedef Documentation

const_iterator

typedef void SG::ArenaHeapAllocator::const_iterator

Definition at line 190 of file ArenaHeapAllocator.h.

const_pointer

typedef const char* SG::ArenaAllocatorBase::const_pointer

inherited

And a const version of the pointer.

Definition at line 140 of file ArenaAllocatorBase.h.

func_t

typedef void SG::ArenaAllocatorBase::func_t(pointer)

inherited

Type of functions for constructor, etc.

Definition at line 143 of file ArenaAllocatorBase.h.

iterator

typedef void SG::ArenaHeapAllocator::iterator

Definition at line 189 of file ArenaHeapAllocator.h.

pointer

typedef char* SG::ArenaAllocatorBase::pointer

inherited

Type for pointers to elements.

Definition at line 137 of file ArenaAllocatorBase.h.

Constructor & Destructor Documentation

ArenaHeapAllocator() [1/3]

SG::ArenaHeapAllocator::ArenaHeapAllocator

(

const Params &

params

)

Constructor.

Parameters

params

The parameters structure for this allocator. See ArenaAllocatorBase.h for the contents.

Definition at line 27 of file ArenaHeapAllocator.cxx.

  : ArenaBlockAllocatorBase (params),
    m_freeptr (nullptr)
{
  // Consistency check.
  assert (params.linkOffset + sizeof (pointer) <= params.eltSize);
}

~ArenaHeapAllocator()

SG::ArenaHeapAllocator::~ArenaHeapAllocator ( )

virtual

Destructor.

This will free all the Allocator's storage.

Definition at line 39 of file ArenaHeapAllocator.cxx.

{
  erase();
}

ArenaHeapAllocator() [2/3]

SG::ArenaHeapAllocator::ArenaHeapAllocator ( const ArenaHeapAllocator &  )

delete

Don't allow copy construction or assignment.

ArenaHeapAllocator() [3/3]

SG::ArenaHeapAllocator::ArenaHeapAllocator

(

ArenaHeapAllocator &&

other

)

Move constructor.

Definition at line 48 of file ArenaHeapAllocator.cxx.

    : ArenaBlockAllocatorBase (std::move (other)),
      m_freeptr (other.m_freeptr)
{
  // False positives
  // cppcheck-suppress useInitializationList
  other.m_freeptr = nullptr;
}

Member Function Documentation

allocate()

pointer SG::ArenaHeapAllocator::allocate

(

)

Allocate a new element.

The fast path of this will be completely inlined.

clear_fcn()

template<typename T >

static void SG::ArenaAllocatorBase::clear_fcn ( pointer  p )

staticprivateinherited

Call T::clear on the object at p.

Parameters

p	The object on which to run the clear.

construct_fcn()

template<typename T >

static void SG::ArenaAllocatorBase::construct_fcn ( pointer  p )

staticprivateinherited

Call T's default constructor on the object at p.

Parameters

p	The object on which to run the constructor.

destroy_fcn()

template<typename T >

static void SG::ArenaAllocatorBase::destroy_fcn ( pointer  p )

staticprivateinherited

Call T's destructor on the object at p.

Parameters

p	The object on which to run the destructor.

erase()

void SG::ArenaHeapAllocator::erase ( )

finaloverridevirtual

Free all allocated elements and release memory back to the system.

All elements allocated are freed, and all allocated blocks of memory are released back to the system. destructor should be called on them if it was provided (preceded by clear if provided and mustClear was set).

Reimplemented from SG::ArenaBlockAllocatorBase.

Definition at line 129 of file ArenaHeapAllocator.cxx.

{
  ArenaBlockAllocatorBase::erase();
  m_freeptr = nullptr;
}

free()

void SG::ArenaHeapAllocator::free

(

pointer

p

)

Free an element.

Parameters

p	The element to be freed.

clear() will be called on the element at this point, if it has been defined.

getBlock()

ArenaBlock * SG::ArenaBlockAllocatorBase::getBlock ( )

protectedinherited

Return an empty block, either newly-allocated or from the free list.

Update statistics appropriately.

Definition at line 234 of file ArenaBlockAllocatorBase.cxx.

{
  if (m_protected) {
    throw SG::ExcProtected();
  }
 
  ArenaBlock* newblock = m_freeblocks;
  if (newblock) {
    // There's something on the free list.  Remove it and update statistics.
    m_freeblocks = newblock->link();
    --m_stats.blocks.free;
  }
  else {
    // Otherwise, we need to make a new block.
    newblock = ArenaBlock::newBlock (m_params.nblock, m_params.eltSize,
                                     m_params.constructor);
    m_stats.elts.total += newblock->size();
    ++m_stats.blocks.total;
  }
  // Finish updating statistics.
  // (Remaining ones are computed in stats().)
  ++m_stats.blocks.inuse;
 
  // Link it into the in-use list and return.
  newblock->link() = m_blocks;
  m_blocks = newblock;
  return newblock;
}

link()

pointer& SG::ArenaHeapAllocator::link ( pointer  p ) const

private

Return a reference to the link for an element.

Parameters

p	The element.

makeClear() [1/2]

template<class T >

static func_t* SG::ArenaAllocatorBase::makeClear ( const std::false_type &  )

staticinherited

Make a function pointer for a clear function.

makeClear() [2/2]

template<class T >

static func_t* SG::ArenaAllocatorBase::makeClear ( const std::true_type &  )

staticinherited

Make a dummy clear function pointer.

makeConstructor() [1/2]

template<class T >

static func_t* SG::ArenaAllocatorBase::makeConstructor ( const std::false_type &  )

staticinherited

Make a constructor function pointer for a non-trivial constructor.

makeConstructor() [2/2]

template<class T >

static func_t* SG::ArenaAllocatorBase::makeConstructor ( const std::true_type &  )

staticinherited

Make a constructor function pointer for a trivial constructor.

makeDestructor() [1/2]

template<class T >

static func_t* SG::ArenaAllocatorBase::makeDestructor ( const std::false_type &  )

staticinherited

Make a constructor function pointer for a non-trivial destructor.

makeDestructor() [2/2]

template<class T >

static func_t* SG::ArenaAllocatorBase::makeDestructor ( const std::true_type &  )

staticinherited

Make a constructor function pointer for a trivial destructor.

name()

const std::string & SG::ArenaBlockAllocatorBase::name ( ) const

overridevirtualinherited

Return the name of this allocator.

Implements SG::ArenaAllocatorBase.

Definition at line 214 of file ArenaBlockAllocatorBase.cxx.

{
  return m_params.name;
}

operator=() [1/2]

ArenaHeapAllocator & SG::ArenaHeapAllocator::operator=

(

ArenaHeapAllocator &&

other

)

Move assignment.

Definition at line 63 of file ArenaHeapAllocator.cxx.

{
  if (this != &other) {
    ArenaBlockAllocatorBase::operator= (std::move (other));
    m_freeptr = other.m_freeptr;
    other.m_freeptr = nullptr;
  }
  return *this;
}

operator=() [2/2]

ArenaHeapAllocator& SG::ArenaHeapAllocator::operator= ( const ArenaHeapAllocator &  )

delete

params()

const ArenaAllocatorBase::Params & SG::ArenaBlockAllocatorBase::params ( ) const

inherited

Return this Allocator's parameters.

Return this allocator's parameters.

Definition at line 224 of file ArenaBlockAllocatorBase.cxx.

{
  return m_params;
}

protect()

void SG::ArenaBlockAllocatorBase::protect ( )

inherited

Write-protect the memory managed by this allocator.

Adjust protection on the memory managed by this allocator to disallow writes.

Definition at line 270 of file ArenaBlockAllocatorBase.cxx.

{
  SG::ArenaBlock::protectList (m_blocks);
  m_protected = true;
}

refill()

ArenaHeapAllocator::pointer SG::ArenaHeapAllocator::refill ( )

private

Add more free elements to the pool, and allocate a new element.

Definition at line 139 of file ArenaHeapAllocator.cxx.

{
  // Get a new block.
  ArenaBlock* newblock = getBlock();
 
  // Set up the links for the new free elements.
  pointer lastelt = nullptr;
  size_t sz = newblock->size();
  size_t elt_size = newblock->eltSize();
  for (size_t i=1; i < sz; i++) {
    pointer elt = newblock->index (i, elt_size);
    link(elt) = lastelt;
    lastelt = elt;
  }
  // Set the free pointer to the next-to-last one.
  m_freeptr = newblock->index (sz-1, elt_size);
 
  // And return the last one.
  return newblock->index (0, elt_size);
}

report()

void SG::ArenaAllocatorBase::report ( std::ostream &  os ) const

virtualinherited

Generate a report on the memory usage of this allocator.

Parameters

os	Stream to which the report should be written.

Definition at line 130 of file ArenaAllocatorBase.cxx.

{
  os << " " << stats() << "  " << name() << std::endl;
}

reserve()

void SG::ArenaBlockAllocatorBase::reserve ( size_t  size )

overridevirtualinherited

Set the total number of elements cached by the allocator.

Parameters

size	The desired pool size.

This allows changing the number of elements that are currently free but cached. Any allocated elements are not affected by this call.

If size is greater than the total number of elements currently cached, then more will be allocated. This will preferably done with a single block, but that is not guaranteed; in addition, the allocator may allocate more elements than is requested.

If size is smaller than the total number of elements currently cached, as many blocks as possible will be released back to the system. It may not be possible to release the number of elements requested; this should be implemented on a best-effort basis.

Implements SG::ArenaAllocatorBase.

Definition at line 120 of file ArenaBlockAllocatorBase.cxx.

{
  if (m_protected) {
    throw SG::ExcProtected();
  }
  if (size > m_stats.elts.total) {
    // Growing the pool.
    // Make a new block of the required size.
    size_t sz = size - m_stats.elts.total;
    ArenaBlock* newblock = ArenaBlock::newBlock (sz, m_params.eltSize,
                                                 m_params.constructor);
 
    // Update statistics (others are derived in stats()).
    ++m_stats.blocks.free;
    ++m_stats.blocks.total;
    m_stats.elts.total += newblock->size();
 
    // Add to the free list.
    newblock->link() = m_freeblocks;
    m_freeblocks = newblock;
  }
  else {
    // Shrinking the pool.
    // Loop while we can get rid of the first free block.
    while (size < m_stats.elts.total &&
           m_freeblocks &&
           m_freeblocks->size() <= (m_stats.elts.total - size))
    {
      // Remove it from the free list.
      ArenaBlock* p = m_freeblocks;
      m_freeblocks = m_freeblocks->link();
 
      // Update statistics (others are derived in stats()).
      m_stats.elts.total -= p->size();
      --m_stats.blocks.free;
      --m_stats.blocks.total;
 
      // Free the block.
      ArenaBlock::destroy (p, m_params.destructor);
    }
  }
}

reset()

void SG::ArenaHeapAllocator::reset ( )

overridevirtual

Free all allocated elements.

All elements allocated are returned to the free state. clear should be called on them if it was provided. The elements may continue to be cached internally, without returning to the system.

Implements SG::ArenaAllocatorBase.

Definition at line 95 of file ArenaHeapAllocator.cxx.

{
  if (!m_blocks) return;
  if (m_params.clear) {
    if (m_params.canReclear || m_freeptr == nullptr) {
      // Just call clear() on all blocks --- allocated or not.
      ArenaBlock::applyList (m_blocks, m_params.clear, m_blocks->size());
    }
    else {
      // We can only call clear() on allocated blocks.
      slowClear();
    }
  }
 
  // Move all blocks back to the free list.
  ArenaBlock::appendList (&m_freeblocks, m_blocks);
 
  // Reset state.
  m_blocks = nullptr;
  m_freeptr = nullptr;
  m_stats.elts.inuse = 0;
  m_stats.blocks.free += m_stats.blocks.inuse;
  m_stats.blocks.inuse = 0;
}

slowClear()

void SG::ArenaHeapAllocator::slowClear ( )

private

Call clear() for all allocated elements.

Definition at line 164 of file ArenaHeapAllocator.cxx.

{
  // Make a list of all free elements, in sorted order.
  std::vector<pointer> free_ptrs;
  free_ptrs.reserve (m_stats.elts.total - m_stats.elts.inuse);
  for (pointer p = m_freeptr; p; p = link(p)) {
    free_ptrs.push_back (p);
  }
  std::sort (free_ptrs.begin(), free_ptrs.end());
 
  // Make a list of all used blocks, in sorted order.
  std::vector<ArenaBlock*> blocks;
  for (ArenaBlock* p = m_blocks; p; p = p->link()) {
    blocks.push_back (p);
  }
  std::sort (blocks.begin(), blocks.end());
 
  // Walk through both of these lists.
  // For each block, walk through its elements, and call @c clear
  // for those not on the free list.
  std::vector<pointer>::iterator pi = free_ptrs.begin();
  std::vector<pointer>::iterator pi_end = free_ptrs.end();
  std::vector<ArenaBlock*>::iterator bi = blocks.begin();
  std::vector<ArenaBlock*>::iterator bi_end = blocks.end();
  func_t* clear = m_params.clear;
  for (; bi != bi_end; ++bi) {
    ArenaBlock& bl = **bi;
    size_t sz = bl.size();
    size_t elt_size = bl.eltSize();
    for (size_t i = 0; i < sz; i++) {
      pointer ptr = bl.index (i, elt_size);
      if (pi != pi_end && ptr == *pi) {
        ++pi;
      }
      else {
        clear (ptr);
      }
    }
  }
}

stats()

ArenaAllocatorBase::Stats SG::ArenaBlockAllocatorBase::stats ( ) const

overridevirtualinherited

Return the statistics block for this allocator.

Implements SG::ArenaAllocatorBase.

Definition at line 196 of file ArenaBlockAllocatorBase.cxx.

{
  // Calculate derived statistics.
  Stats stats = m_stats;
  stats.elts.free = stats.elts.total - stats.elts.inuse;
  stats.bytes.inuse = stats.elts.inuse   * m_params.eltSize +
                      stats.blocks.inuse * ArenaBlock::overhead();
  stats.bytes.total = stats.elts.total   * m_params.eltSize +
                      stats.blocks.total * ArenaBlock::overhead();
  stats.bytes.free  = stats.elts.free   * m_params.eltSize +
                      stats.blocks.free * ArenaBlock::overhead();
  return stats;
}

swap() [1/2]

void SG::ArenaBlockAllocatorBase::swap ( ArenaBlockAllocatorBase &  other )

inherited

Swap.

Definition at line 91 of file ArenaBlockAllocatorBase.cxx.

{
  if (this != &other) {
    std::swap (m_params, other.m_params);
    std::swap (m_blocks, other.m_blocks);
    std::swap (m_freeblocks, other.m_freeblocks);
    std::swap (m_stats, other.m_stats);
    std::swap (m_protected, other.m_protected);
  }
}

swap() [2/2]

void SG::ArenaHeapAllocator::swap

(

ArenaHeapAllocator &

other

)

Swap.

Definition at line 78 of file ArenaHeapAllocator.cxx.

{
  if (this != &other) {
    ArenaBlockAllocatorBase::swap (other);
    std::swap (m_freeptr, other.m_freeptr);
  }
}

unprotect()

void SG::ArenaBlockAllocatorBase::unprotect ( )

inherited

Write-enable the memory managed by this allocator.

Adjust protection on the memory managed by this allocator to allow writes.

Definition at line 283 of file ArenaBlockAllocatorBase.cxx.

{
  if (m_protected) {
    SG::ArenaBlock::unprotectList (m_blocks);
    m_protected = false;
  }
}

Member Data Documentation

m_blocks

ArenaBlock* SG::ArenaBlockAllocatorBase::m_blocks

protectedinherited

The list of blocks currently in use.

Definition at line 153 of file ArenaBlockAllocatorBase.h.

m_freeblocks

ArenaBlock* SG::ArenaBlockAllocatorBase::m_freeblocks

protectedinherited

The list of free blocks.

Definition at line 156 of file ArenaBlockAllocatorBase.h.

m_freeptr

pointer SG::ArenaHeapAllocator::m_freeptr

private

Pointer to the next free element.

Definition at line 213 of file ArenaHeapAllocator.h.

m_params

Params SG::ArenaBlockAllocatorBase::m_params

protectedinherited

The parameters for this allocator.

Definition at line 150 of file ArenaBlockAllocatorBase.h.

m_protected

bool SG::ArenaBlockAllocatorBase::m_protected

protectedinherited

Flag whether the arena has been protected.

Definition at line 162 of file ArenaBlockAllocatorBase.h.

m_stats

ArenaAllocatorBase::Stats SG::ArenaBlockAllocatorBase::m_stats

protectedinherited

The statistics structure.

Definition at line 159 of file ArenaBlockAllocatorBase.h.

---

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

• ArenaHeapAllocator.h
• ArenaHeapAllocator.cxx