lsst::ap::utils::Arena< T > Class Template Reference

#include <Arena.h>

Public Member Functions
	Arena (size_t blockCapacity=262144/sizeof(T))
	~Arena ()
void	destroy (T *ptr)
size_t	capacity () const
size_t	getNumBytes () const
size_t	getBlockCapacity () const

Private Member Functions
	BOOST_STATIC_ASSERT ((ALIGN &(ALIGN-1))==0)
	Arena (Arena const &)
Arena &	operator= (Arena const &)
void *	_alloc ()
void	_dealloc (void *ptr)
void	_grow ()
friend	void (::operator delete<>)(void *

Static Private Member Functions
static unsigned char *	_align (unsigned char *p)

Private Attributes
std::vector< unsigned char * >	_blocks
	List of memory blocks. More...
std::vector< std::vector< bool > >	_masks
size_t const	_blockCapacity
	Capacity of a memory block. More...
size_t	_nFree
	Number of free elements. More...
unsigned char *	_free
	Head of linked free-list, 0 if arena is full. More...

Static Private Attributes
static const size_t	ALIGN = 16
static const size_t	SIZE = (sizeof(T) + ALIGN - 1) & ~(ALIGN - 1)

Friends
void *	operator new) (size_t, lsst::ap::utils::Arena< T > &)

Detailed Description

template<typename T>
class lsst::ap::utils::Arena< T >

A free-list based single-threaded arena allocator for objects of class T.

The arena grows in blocks of a run-time specified capacity, and never shrinks during the lifetime of the arena. All blocks are allocated with malloc(), and are freed when the arena is destroyed. Note that destroying the arena will also call the destructors of any live objects in the arena.

This class is quite low-level and is intended for use in performance critical code only.

Definition at line 44 of file Arena.h.

Constructor & Destructor Documentation

template<typename T >

lsst::ap::utils::Arena< T >::Arena

(

size_t

blockCapacity = 262144/sizeof(T)

)

Creates a new Arena for objects of type T. The arena allocates memory from the system in blocks, each of which is large enough to contain blockCapacity objects.

Definition at line 41 of file Arena.cc.

                                    :
    _blocks(),
    _masks(),
    _blockCapacity(blockCapacity),
    _nFree(0), 
    _free(0)
{
    if (blockCapacity == 0) {
        throw LSST_EXCEPT(lsst::pex::exceptions::InvalidParameterError,
                          "Cannot create Arena with 0 capacity");
    }
    _grow();
}

template<typename T >

lsst::ap::utils::Arena< T >::~Arena

(

)

Definition at line 56 of file Arena.cc.

                 {
    typedef std::vector<unsigned char *>::iterator Iter;

    if (_nFree == 0) {
        assert(_free == 0 &&
               "No free elements, but free list head is non-null");
        // call destructor for every element of every block
        for (Iter i = _blocks.begin(), e = _blocks.end(); i != e; ++i) {
            unsigned char *block = _align(*i);
            unsigned char *blockEnd = block + _blockCapacity*SIZE;
            for (; block < blockEnd; block += SIZE) {
                reinterpret_cast<T *>(block)->~T();
            }
        }
    } else if (_nFree < _blocks.size()*_blockCapacity) {
       assert(_free != 0 &&
              "Free count is non zero, but free list head is null");
       // need to call destructor for each allocated entry -
       // first compute free bits for every block.
       std::sort(_blocks.begin(), _blocks.end());
       unsigned char *ptr = _free;
       while (ptr != 0) {
           // figure out which block ptr is from and mark the element free
           Iter b = std::upper_bound(_blocks.begin(), _blocks.end(), ptr);
           assert(b != _blocks.begin() &&
                  "Free list contains pointer not belonging to arena");
           --b;
           unsigned char *ab = _align(*b);
           assert((ptr - ab) % SIZE == 0 &&
                  "Free list contains unaligned pointer");
           _masks[b - _blocks.begin()][(ptr - ab)/SIZE] = true;
           --_nFree;
           ptr = *reinterpret_cast<unsigned char **>(ptr);
       }
       assert(_nFree == 0 && "Free list does not contain all free elements");
       // free any element not flagged as free in its occupancy mask
       for (size_t i = 0; i < _blocks.size(); ++i) {
           unsigned char *block = _align(_blocks[i]);
           std::vector<bool> const & free = _masks[i];
           for (size_t j = 0; j < _blocks.size(); block += SIZE, ++j) {
               if (!free[j]) {
                   reinterpret_cast<T *>(block)->~T();
               }
           }
       }
    } else {
       assert(_nFree == _blocks.size()*_blockCapacity &&
              "Number of free elements exceeds arena capacity");
    }
    // free the memory for each block
    for (Iter i = _blocks.begin(), e = _blocks.end(); i != e; ++i) {
        std::free(*i);
        *i = 0;
    }
}

template<typename T>

lsst::ap::utils::Arena< T >::Arena ( Arena< T > const &  )

private

Member Function Documentation

template<typename T >

unsigned char * lsst::ap::utils::Arena< T >::_align ( unsigned char *  p )

inlinestaticprivate

Definition at line 221 of file Arena.cc.

                                                          {
    return reinterpret_cast<unsigned char *>(
        reinterpret_cast<size_t>(ptr + ALIGN) & ~(ALIGN - 1));
}

template<typename T >

void * lsst::ap::utils::Arena< T >::_alloc ( )

inlineprivate

Allocates and returns a pointer to a memory region large enough to hold a single object of type T.

Definition at line 116 of file Arena.cc.

                              {
    if (_free == 0) {
        _grow();
    }
    unsigned char *next = _free;
    _free = *reinterpret_cast<unsigned char **>(next);
    --_nFree;
    return next;
}

template<typename T >

void lsst::ap::utils::Arena< T >::_dealloc ( void *  ptr )

inlineprivate

Frees the memory at the given address.

Definition at line 129 of file Arena.cc.

                                        {
    unsigned char *next = static_cast<unsigned char *>(ptr);
    *reinterpret_cast<unsigned char **>(next) = _free;
    _free = next;
    ++_nFree;
}

template<typename T >

void lsst::ap::utils::Arena< T >::_grow ( )

private

Definition at line 167 of file Arena.cc.

                     {
    // pre-allocate space in block and block mask list
    if (_blocks.size() == _blocks.capacity()) {
        if (_blocks.size() == _blocks.max_size()) {
            throw std::length_error("cannot expand vector: "
                                    "max_size() would be exceeded");
        }
        std::vector<unsigned char *>::size_type c = 2*_blocks.capacity();
        if (c == 0) {
            ++ c;
        }
        if (c < _blocks.capacity() || c > _blocks.max_size()) {
            c = _blocks.max_size();
        }
        _blocks.reserve(c);
    }
    if (_masks.size() == _masks.capacity()) {
        if (_masks.size() == _masks.max_size()) {
            throw std::length_error("cannot expand vector: "
                                    "max_size() would be exceeded");
        }
        std::vector<std::vector<bool> >::size_type c = 2*_masks.capacity();
        if (c == 0) {
            ++c;
        }
        if (c < _masks.capacity() || c > _masks.max_size()) {
            c = _masks.max_size();
        }
        _masks.reserve(c);
    }
    std::vector<bool> mask(_blockCapacity, false);
    // allocate another block
    unsigned char *block = static_cast<unsigned char *>(
        std::malloc(_blockCapacity*SIZE + ALIGN));
    if (block == 0) {
        throw std::bad_alloc();
    }
    // what follows will not throw so long as the std::vector default
    // constructor does not throw
    _masks.push_back(std::vector<bool>());
    std::swap(_masks.back(), mask);
    // initialize free-list
    unsigned char *item = _align(block);
    for (size_t i = 0; i < _blockCapacity - 1; ++i, item += SIZE) {
        *reinterpret_cast<unsigned char **>(item) = item + SIZE;
    }
    *reinterpret_cast<unsigned char **>(item) = 0;
    // set _free to head of free-list and store new block pointer
    _free = _align(block);
    _nFree += _blockCapacity;
    _blocks.push_back(block);
}

template<typename T>

lsst::ap::utils::Arena< T >::BOOST_STATIC_ASSERT ( (ALIGN &(ALIGN-1))  = =0 )

private

template<typename T >

size_t lsst::ap::utils::Arena< T >::capacity ( ) const

inline

Returns the total number of objects that can fit in the arena.

Definition at line 147 of file Arena.cc.

                                       {
    return _blockCapacity*_blocks.size();
}

template<typename T>

void lsst::ap::utils::Arena< T >::destroy ( T *  ptr )

inline

Destroys and frees the object at the given address.

Definition at line 139 of file Arena.cc.

                                    {
    ptr->~T();
    _dealloc(ptr);
}

template<typename T >

size_t lsst::ap::utils::Arena< T >::getBlockCapacity ( ) const

inline

Returns the number of objects that fit in a single arena block.

Definition at line 161 of file Arena.cc.

                                               {
    return _blockCapacity;
}

template<typename T >

size_t lsst::ap::utils::Arena< T >::getNumBytes ( ) const

inline

Returns the number of bytes in the arena.

Definition at line 154 of file Arena.cc.

                                          {
    return capacity()*SIZE;
}

template<typename T>

Arena& lsst::ap::utils::Arena< T >::operator= ( Arena< T > const &  )

private

template<typename T>

lsst::ap::utils::Arena< T >::void ( ::operator delete<>  )

private

Friends And Related Function Documentation

template<typename T>

void* operator new) ( size_t  , lsst::ap::utils::Arena< T > &    )

friend

Member Data Documentation

template<typename T>

size_t const lsst::ap::utils::Arena< T >::_blockCapacity

private

Capacity of a memory block.

Definition at line 100 of file Arena.h.

template<typename T>

std::vector<unsigned char *> lsst::ap::utils::Arena< T >::_blocks

private

List of memory blocks.

Definition at line 95 of file Arena.h.

template<typename T>

unsigned char* lsst::ap::utils::Arena< T >::_free

private

Head of linked free-list, 0 if arena is full.

Definition at line 102 of file Arena.h.

template<typename T>

std::vector<std::vector<bool> > lsst::ap::utils::Arena< T >::_masks

private

Per-block free bits - used only in the arena destructor, but is pre-allocated to avoid std::bad_alloc therein.

Definition at line 96 of file Arena.h.

template<typename T>

size_t lsst::ap::utils::Arena< T >::_nFree

private

Number of free elements.

Definition at line 101 of file Arena.h.

template<typename T>

const size_t lsst::ap::utils::Arena< T >::ALIGN = 16

staticprivate

Definition at line 80 of file Arena.h.

template<typename T>

const size_t lsst::ap::utils::Arena< T >::SIZE = (sizeof(T) + ALIGN - 1) & ~(ALIGN - 1)

staticprivate

Definition at line 81 of file Arena.h.

---

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

• /home/lsstsw/stack/Linux64/ap/10.0+224/include/lsst/ap/utils/Arena.h
• /home/lsstsw/stack/Linux64/ap/10.0+224/include/lsst/ap/utils/Arena.cc