Frobby  0.9.5
Arena.cpp
Go to the documentation of this file.
1 /* Frobby: Software for monomial ideal computations.
2  Copyright (C) 2011 University of Aarhus
3  Contact Bjarke Hammersholt Roune for license information (www.broune.com)
4 
5  This program is free software; you can redistribute it and/or modify
6  it under the terms of the GNU General Public License as published by
7  the Free Software Foundation; either version 2 of the License, or
8  (at your option) any later version.
9 
10  This program is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  GNU General Public License for more details.
14 
15  You should have received a copy of the GNU General Public License
16  along with this program. If not, see http://www.gnu.org/licenses/.
17 */
18 #include "stdinc.h"
19 #include "Arena.h"
20 
21 #include <new>
22 #include <limits>
23 
25 
27 }
28 
30  while (_block.hasPreviousBlock())
32  delete[] _block._blockBegin;
33 }
34 
36  _blockBegin(0),
37  _freeBegin(0),
38  _blockEnd(0),
39  _previousBlock(0) {
40 }
41 
42 void Arena::growCapacity(const size_t needed) {
43  // ** Calcuate size of block (doubles capacity)
44  size_t size = std::max(needed, _block.getSize());
45  if (size > std::numeric_limits<size_t>::max() / 2)
46  throw bad_alloc(); // size * 2 overflows
47  size *= 2;
48  const size_t minimumAlloc = 16 * 1024 - sizeof(Block) - 16;
49  size = std::max(size, minimumAlloc); // avoid many small blocks
50  // align size by rounding down
51  size = size & ~(MemoryAlignment - 1); // works because m.a. is a power of 2
52  ASSERT(size >= needed); // is satisfied because we multiplied by 2
53  ASSERT(size % MemoryAlignment == 0);
54  if (size > std::numeric_limits<size_t>::max() - sizeof(Block))
55  throw bad_alloc(); // size + sizeof(block) overflows
56 
57  // ** Save current block information at end of memory area
58  if (!_block.isNull()) {
59  Block* previousBlock = reinterpret_cast<Block*>(_block._blockEnd);
60  *previousBlock = _block;
61  _block._previousBlock = previousBlock;
62  }
63 
64  // ** Allocate buffer and update _block
65  char* buffer = new char[size + sizeof(Block)];
66  _block._blockBegin = buffer;
67  _block._freeBegin = buffer;
68  _block._blockEnd = buffer + size;
69 }
70 
71 void Arena::freeTopFromOldBlock(void* ptr) {
72  ASSERT(ptr != 0);
75 
76  ASSERT(_block._previousBlock->debugIsValid(ptr));
77  _block._previousBlock->_freeBegin = static_cast<char*>(ptr);
80 }
81 
83  ASSERT(!_block.isInBlock(ptr));
85 
87  while (!(_block._previousBlock->isInBlock(ptr))) {
90  }
91 
92  ASSERT(_block._previousBlock->debugIsValid(ptr));
93  _block._previousBlock->_freeBegin = static_cast<char*>(ptr);
96 }
97 
102  _block._previousBlock = before;
103 }
104 
105 #ifdef DEBUG
106 bool Arena::Block::debugIsValid(const void* ptr) const {
107  return _blockBegin <= ptr && ptr < _freeBegin;
108 }
109 #endif
This is an arena allocator.
Definition: Arena.h:53
struct Arena::Block _block
void freeAndAllAfterFromOldBlock(void *ptr)
As Arena::freeAndAllAfter where ptr was allocated from an old block.
Definition: Arena.cpp:82
static Arena _scratchArena
Definition: Arena.h:163
void discardPreviousBlock()
Free the memory for the previous block.
Definition: Arena.cpp:98
Arena()
Definition: Arena.cpp:26
void freeTopFromOldBlock(void *ptr)
As Arena::freeTop where ptr was allocated from an old block.
Definition: Arena.cpp:71
void growCapacity(size_t needed)
Allocate a new block with at least needed bytes.
Definition: Arena.cpp:42
~Arena()
Definition: Arena.cpp:29
static const size_t MemoryAlignment
The alignment that memory allocators must ensure.
Definition: stdinc.h:99
#define ASSERT(X)
Definition: stdinc.h:86
size_t getSize() const
Definition: Arena.h:150
bool hasPreviousBlock() const
Definition: Arena.h:154
Block * _previousBlock
one past last byte (aligned)
Definition: Arena.h:160
char * _blockBegin
Definition: Arena.h:157
bool isNull() const
Definition: Arena.h:153
char * _blockEnd
pointer to first free byte (aligned)
Definition: Arena.h:159
bool isEmpty() const
Definition: Arena.h:152
char * _freeBegin
beginning of current block (aligned)
Definition: Arena.h:158
bool isInBlock(const void *ptr) const
Definition: Arena.h:241