Arena.h
Go to the documentation of this file.
/* Frobby: Software for monomial ideal computations.
Copyright (C) 2011 University of Aarhus
Contact Bjarke Hammersholt Roune for license information (www.broune.com)
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see http://www.gnu.org/licenses/.
*/
#ifndef ARENA_GUARD
#define ARENA_GUARD
#include <utility>
#ifdef DEBUG
#include <stack>
#endif
class Arena {
public:
Arena();
~Arena();
// ***** Basic void* interface *****
void* alloc(size_t size);
void freeTop(void* ptr);
void freeAndAllAfter(void* ptr);
// ***** Array interface *****
template<class T>
pair<T*, T*> allocArrayNoCon(size_t elementCount);
template<class T>
pair<T*, T*> allocArray(size_t elementCount);
template<class T>
void freeTopArray(T* array, T* arrayEnd);
template<class T>
void freeTopArray(pair<T*, T*> p) {freeTopArray(p.first, p.second);}
template<class T>
void freeArrayAndAllAfter(T* array, T* arrayEnd);
template<class T>
void freeArrayAndAllAfter(pair<T*, T*> p) {
freeArrayAndAllAfter(p.first, p.second);
}
// ***** Miscellaneous *****
bool isEmpty() const {return !_block.hasPreviousBlock() && _block.isEmpty();}
static Arena& getArena() {return _scratchArena;}
private:
void growCapacity(size_t needed);
void freeTopFromOldBlock(void* ptr);
void freeAndAllAfterFromOldBlock(void* ptr);
void discardPreviousBlock();
static size_t alignNoOverflow(size_t value);
struct Block {
Block();
inline bool isInBlock(const void* ptr) const;
size_t getSize() const {return _blockEnd - _blockBegin;}
size_t getFreeCapacity() const {return _blockEnd - _freeBegin;}
bool isEmpty() const {return _blockBegin == _freeBegin;}
bool isNull() const {return _blockBegin == 0;}
bool hasPreviousBlock() const {return _previousBlock != 0;}
IF_DEBUG(bool debugIsValid(const void* ptr) const;)
char* _blockBegin;
char* _freeBegin;
char* _blockEnd;
Block* _previousBlock;
} _block;
static Arena _scratchArena;
IF_DEBUG(stack<void*> _debugAllocs;)
};
inline size_t Arena::alignNoOverflow(const size_t value) {
const size_t decAlign = MemoryAlignment - 1; // compile time constant
// This works because MemoryAlignment is a power of 2.
const size_t aligned = (value + decAlign) & (~decAlign);
ASSERT(aligned % MemoryAlignment == 0); // alignment
ASSERT(aligned >= value); // no overflow
ASSERT(aligned - value < MemoryAlignment); // adjustment minimal
return aligned;
}
inline void* Arena::alloc(size_t size) {
// It is OK to check capacity before aligning size as capacity is aligned.
// This single if checks for three different special circumstances:
// * size is 0 (size - 1 will overflow)
// * there is not enough capacity (size > capacity)
// * aligning size would cause an overflow (capacity is aligned)
const size_t capacity = _block.getFreeCapacity();
ASSERT(capacity % MemoryAlignment == 0);
if (size - 1 >= capacity) {
ASSERT(size == 0 || size > capacity);
if (size == 0) {
size = 1;
if (capacity > 0)
goto capacityOK;
}
growCapacity(size);
}
capacityOK:
ASSERT(0 < size);
ASSERT(size <= _block.getFreeCapacity());
ASSERT(alignNoOverflow(size) <= _block.getFreeCapacity());
void* ptr = _block._freeBegin;
_block._freeBegin += alignNoOverflow(size);
IF_DEBUG(_debugAllocs.push(ptr));
return ptr;
}
inline void Arena::freeTop(void* ptr) {
ASSERT(ptr != 0);
#ifdef DEBUG
ASSERT(!_debugAllocs.empty());
ASSERT(_debugAllocs.top() == ptr);
_debugAllocs.pop();
#endif
if (!_block.isEmpty()) {
ASSERT(_block.debugIsValid(ptr));
_block._freeBegin = static_cast<char*>(ptr);
} else
freeTopFromOldBlock(ptr);
}
inline void Arena::freeAndAllAfter(void* ptr) {
ASSERT(ptr != 0);
#ifdef DEBUG
while (!_debugAllocs.empty() && ptr != _debugAllocs.top())
_debugAllocs.pop();
ASSERT(!_debugAllocs.empty());
ASSERT(_debugAllocs.top() == ptr);
_debugAllocs.pop();
#endif
if (_block.isInBlock(ptr)) {
ASSERT(_block.debugIsValid(ptr));
_block._freeBegin = static_cast<char*>(ptr);
} else
freeAndAllAfterFromOldBlock(ptr);
}
inline bool Arena::Block::isInBlock(const void* ptr) const {
const char* p = static_cast<const char*>(ptr);
const size_t offset = static_cast<size_t>(p - _blockBegin);
// if _blockBegin > ptr then offset overflows to a large integer
ASSERT((offset < getSize()) == (_blockBegin <= p && p < _blockEnd));
return offset < getSize();
}
template<class T>
pair<T*, T*> Arena::allocArrayNoCon(size_t elementCount) {
if (elementCount > static_cast<size_t>(-1) / sizeof(T))
throw bad_alloc();
const size_t size = elementCount * sizeof(T);
ASSERT(size / sizeof(T) == elementCount);
char* buffer = static_cast<char*>(alloc(size));
T* array = reinterpret_cast<T*>(buffer);
T* arrayEnd = reinterpret_cast<T*>(buffer + size);
return make_pair(array, arrayEnd);
}
#undef new
template<class T>
pair<T*, T*> Arena::allocArray(size_t elementCount) {
pair<T*, T*> p = allocArrayNoCon<T>(elementCount);
T* it = p.first;
try {
for (; it != p.second; ++it)
new (it) T();
} catch (...) {
freeTopArray<T>(p.first, it);
throw;
}
return p;
}
#ifdef NEW_MACRO
#define new NEW_MACRO
#endif
template<class T>
void Arena::freeTopArray(T* array, T* arrayEnd) {
ASSERT(array != 0);
ASSERT(array <= arrayEnd);
while (arrayEnd != array) {
--arrayEnd;
arrayEnd->~T();
}
freeTop(array);
}
template<class T>
void Arena::freeArrayAndAllAfter(T* array, T* arrayEnd) {
ASSERT(array != 0);
ASSERT(array <= arrayEnd);
while (arrayEnd != array) {
--arrayEnd;
arrayEnd->~T();
}
freeAndAllAfter(array);
}
#endif
Arena::_block
struct Arena::Block _block
Arena::freeArrayAndAllAfter
void freeArrayAndAllAfter(T *array, T *arrayEnd)
As freeAndAllAfter(array) except that the elements of the array in the range (array,...
Definition Arena.h:292
Arena::freeAndAllAfterFromOldBlock
void freeAndAllAfterFromOldBlock(void *ptr)
As Arena::freeAndAllAfter where ptr was allocated from an old block.
Definition Arena.cpp:82
Arena::_scratchArena
static Arena _scratchArena
Definition Arena.h:163
Arena::alloc
void * alloc(size_t size)
Returns a pointer to a buffer of size bytes.
Definition Arena.h:180
Arena::discardPreviousBlock
void discardPreviousBlock()
Free the memory for the previous block.
Definition Arena.cpp:98
Arena::isEmpty
bool isEmpty() const
Returns true if there are no live allocations for this Arena.
Definition Arena.h:117
Arena::allocArrayNoCon
pair< T *, T * > allocArrayNoCon(size_t elementCount)
As alloc(elementCount * sizeof(T)).
Definition Arena.h:250
Arena::Arena
Arena()
Definition Arena.cpp:26
Arena::freeTop
void freeTop(void *ptr)
Frees the buffer pointed to by ptr.
Definition Arena.h:209
Arena::freeTopArray
void freeTopArray(T *array, T *arrayEnd)
As freeTop(array) except that the elements of the array in the range (array, arrayEnd] are deconstruc...
Definition Arena.h:280
Arena::alignNoOverflow
static size_t alignNoOverflow(size_t value)
Rounds value up to the nearest multiple of MemoryAlignment.
Definition Arena.h:168
Arena::freeTopFromOldBlock
void freeTopFromOldBlock(void *ptr)
As Arena::freeTop where ptr was allocated from an old block.
Definition Arena.cpp:71
Arena::freeArrayAndAllAfter
void freeArrayAndAllAfter(pair< T *, T * > p)
As freeTopArrayAndAllAfter(p.first, p.second).
Definition Arena.h:110
Arena::freeTopArray
void freeTopArray(pair< T *, T * > p)
As freeTopArray(p.first, p.second).
Definition Arena.h:100
Arena::growCapacity
void growCapacity(size_t needed)
Allocate a new block with at least needed bytes.
Definition Arena.cpp:42
Arena::getArena
static Arena & getArena()
Returns an arena object that can be used for non-thread safe scratch memory after static objects have...
Definition Arena.h:126
Arena::freeAndAllAfter
void freeAndAllAfter(void *ptr)
Frees the buffer pointed to by ptr and all not yet freed allocations that have happened since that bu...
Definition Arena.h:224
Arena::~Arena
~Arena()
Definition Arena.cpp:29
Arena::allocArray
pair< T *, T * > allocArray(size_t elementCount)
As allocArrayNoCon except that constructors for the elements of the array are called.
Definition Arena.h:263
MemoryAlignment
static const size_t MemoryAlignment
The alignment that memory allocators must ensure.
Definition stdinc.h:99
IF_DEBUG
#define IF_DEBUG(X)
Definition stdinc.h:85
ASSERT
#define ASSERT(X)
Definition stdinc.h:86
Arena::Block::getSize
size_t getSize() const
Definition Arena.h:150
Arena::Block::getFreeCapacity
size_t getFreeCapacity() const
Definition Arena.h:151
Arena::Block::hasPreviousBlock
bool hasPreviousBlock() const
Definition Arena.h:154
Arena::Block::_previousBlock
Block * _previousBlock
one past last byte (aligned)
Definition Arena.h:160
Arena::Block::_blockBegin
char * _blockBegin
Definition Arena.h:157
Arena::Block::isNull
bool isNull() const
Definition Arena.h:153
Arena::Block::_blockEnd
char * _blockEnd
pointer to first free byte (aligned)
Definition Arena.h:159
Arena::Block::Block
Block()
Definition Arena.cpp:35
Arena::Block::isEmpty
bool isEmpty() const
Definition Arena.h:152
Arena::Block::_freeBegin
char * _freeBegin
beginning of current block (aligned)
Definition Arena.h:158
Arena::Block::isInBlock
bool isInBlock(const void *ptr) const
Definition Arena.h:241