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