Frobby 0.9.5
Arena.h
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#ifndef ARENA_GUARD
19#define ARENA_GUARD
20
21#include <utility>
22
23#ifdef DEBUG
24#include <stack>
25#endif
26
53class Arena {
54 public:
55 Arena();
56 ~Arena();
57
58 // ***** Basic void* interface *****
59
63 void* alloc(size_t size);
64
68 void freeTop(void* ptr);
69
73 void freeAndAllAfter(void* ptr);
74
75
76 // ***** Array interface *****
77
80 template<class T>
81 pair<T*, T*> allocArrayNoCon(size_t elementCount);
82
87 template<class T>
88 pair<T*, T*> allocArray(size_t elementCount);
89
95 template<class T>
96 void freeTopArray(T* array, T* arrayEnd);
97
99 template<class T>
100 void freeTopArray(pair<T*, T*> p) {freeTopArray(p.first, p.second);}
101
105 template<class T>
106 void freeArrayAndAllAfter(T* array, T* arrayEnd);
107
109 template<class T>
110 void freeArrayAndAllAfter(pair<T*, T*> p) {
111 freeArrayAndAllAfter(p.first, p.second);
112 }
113
114 // ***** Miscellaneous *****
115
117 bool isEmpty() const {return !_block.hasPreviousBlock() && _block.isEmpty();}
118
126 static Arena& getArena() {return _scratchArena;}
127
128 private:
130 void growCapacity(size_t needed);
131
133 void freeTopFromOldBlock(void* ptr);
134
137 void freeAndAllAfterFromOldBlock(void* ptr);
138
141
144 static size_t alignNoOverflow(size_t value);
145
146 struct Block {
147 Block();
148
149 inline bool isInBlock(const void* ptr) const;
150 size_t getSize() const {return _blockEnd - _blockBegin;}
151 size_t getFreeCapacity() const {return _blockEnd - _freeBegin;}
152 bool isEmpty() const {return _blockBegin == _freeBegin;}
153 bool isNull() const {return _blockBegin == 0;}
154 bool hasPreviousBlock() const {return _previousBlock != 0;}
155 IF_DEBUG(bool debugIsValid(const void* ptr) const;)
156
159 char* _blockEnd;
162
164
165 IF_DEBUG(stack<void*> _debugAllocs;)
166};
167
168inline size_t Arena::alignNoOverflow(const size_t value) {
169 const size_t decAlign = MemoryAlignment - 1; // compile time constant
170
171 // This works because MemoryAlignment is a power of 2.
172 const size_t aligned = (value + decAlign) & (~decAlign);
173
174 ASSERT(aligned % MemoryAlignment == 0); // alignment
175 ASSERT(aligned >= value); // no overflow
176 ASSERT(aligned - value < MemoryAlignment); // adjustment minimal
177 return aligned;
178}
179
180inline void* Arena::alloc(size_t size) {
181 // It is OK to check capacity before aligning size as capacity is aligned.
182 // This single if checks for three different special circumstances:
183 // * size is 0 (size - 1 will overflow)
184 // * there is not enough capacity (size > capacity)
185 // * aligning size would cause an overflow (capacity is aligned)
186 const size_t capacity = _block.getFreeCapacity();
187 ASSERT(capacity % MemoryAlignment == 0);
188 if (size - 1 >= capacity) {
189 ASSERT(size == 0 || size > capacity);
190 if (size == 0) {
191 size = 1;
192 if (capacity > 0)
193 goto capacityOK;
194 }
195 growCapacity(size);
196 }
197 capacityOK:
198 ASSERT(0 < size);
199 ASSERT(size <= _block.getFreeCapacity());
201
202 void* ptr = _block._freeBegin;
204
205 IF_DEBUG(_debugAllocs.push(ptr));
206 return ptr;
207}
208
209inline void Arena::freeTop(void* ptr) {
210 ASSERT(ptr != 0);
211#ifdef DEBUG
212 ASSERT(!_debugAllocs.empty());
213 ASSERT(_debugAllocs.top() == ptr);
214 _debugAllocs.pop();
215#endif
216
217 if (!_block.isEmpty()) {
218 ASSERT(_block.debugIsValid(ptr));
219 _block._freeBegin = static_cast<char*>(ptr);
220 } else
222}
223
224inline void Arena::freeAndAllAfter(void* ptr) {
225 ASSERT(ptr != 0);
226#ifdef DEBUG
227 while (!_debugAllocs.empty() && ptr != _debugAllocs.top())
228 _debugAllocs.pop();
229 ASSERT(!_debugAllocs.empty());
230 ASSERT(_debugAllocs.top() == ptr);
231 _debugAllocs.pop();
232#endif
233
234 if (_block.isInBlock(ptr)) {
235 ASSERT(_block.debugIsValid(ptr));
236 _block._freeBegin = static_cast<char*>(ptr);
237 } else
239}
240
241inline bool Arena::Block::isInBlock(const void* ptr) const {
242 const char* p = static_cast<const char*>(ptr);
243 const size_t offset = static_cast<size_t>(p - _blockBegin);
244 // if _blockBegin > ptr then offset overflows to a large integer
245 ASSERT((offset < getSize()) == (_blockBegin <= p && p < _blockEnd));
246 return offset < getSize();
247}
248
249template<class T>
250pair<T*, T*> Arena::allocArrayNoCon(size_t elementCount) {
251 if (elementCount > static_cast<size_t>(-1) / sizeof(T))
252 throw bad_alloc();
253 const size_t size = elementCount * sizeof(T);
254 ASSERT(size / sizeof(T) == elementCount);
255 char* buffer = static_cast<char*>(alloc(size));
256 T* array = reinterpret_cast<T*>(buffer);
257 T* arrayEnd = reinterpret_cast<T*>(buffer + size);
258 return make_pair(array, arrayEnd);
259}
260
261#undef new
262template<class T>
263pair<T*, T*> Arena::allocArray(size_t elementCount) {
264 pair<T*, T*> p = allocArrayNoCon<T>(elementCount);
265 T* it = p.first;
266 try {
267 for (; it != p.second; ++it)
268 new (it) T();
269 } catch (...) {
270 freeTopArray<T>(p.first, it);
271 throw;
272 }
273 return p;
274}
275#ifdef NEW_MACRO
276#define new NEW_MACRO
277#endif
278
279template<class T>
280void Arena::freeTopArray(T* array, T* arrayEnd) {
281 ASSERT(array != 0);
282 ASSERT(array <= arrayEnd);
283
284 while (arrayEnd != array) {
285 --arrayEnd;
286 arrayEnd->~T();
287 }
288 freeTop(array);
289}
290
291template<class T>
292void Arena::freeArrayAndAllAfter(T* array, T* arrayEnd) {
293 ASSERT(array != 0);
294 ASSERT(array <= arrayEnd);
295
296 while (arrayEnd != array) {
297 --arrayEnd;
298 arrayEnd->~T();
299 }
300 freeAndAllAfter(array);
301}
302
303#endif
This is an arena allocator.
Definition Arena.h:53
struct Arena::Block _block
void freeArrayAndAllAfter(T *array, T *arrayEnd)
As freeAndAllAfter(array) except that the elements of the array in the range (array,...
Definition Arena.h:292
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 * alloc(size_t size)
Returns a pointer to a buffer of size bytes.
Definition Arena.h:180
void discardPreviousBlock()
Free the memory for the previous block.
Definition Arena.cpp:98
bool isEmpty() const
Returns true if there are no live allocations for this Arena.
Definition Arena.h:117
pair< T *, T * > allocArrayNoCon(size_t elementCount)
As alloc(elementCount * sizeof(T)).
Definition Arena.h:250
Arena()
Definition Arena.cpp:26
void freeTop(void *ptr)
Frees the buffer pointed to by ptr.
Definition Arena.h:209
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
static size_t alignNoOverflow(size_t value)
Rounds value up to the nearest multiple of MemoryAlignment.
Definition Arena.h:168
void freeTopFromOldBlock(void *ptr)
As Arena::freeTop where ptr was allocated from an old block.
Definition Arena.cpp:71
void freeArrayAndAllAfter(pair< T *, T * > p)
As freeTopArrayAndAllAfter(p.first, p.second).
Definition Arena.h:110
void freeTopArray(pair< T *, T * > p)
As freeTopArray(p.first, p.second).
Definition Arena.h:100
void growCapacity(size_t needed)
Allocate a new block with at least needed bytes.
Definition Arena.cpp:42
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
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()
Definition Arena.cpp:29
pair< T *, T * > allocArray(size_t elementCount)
As allocArrayNoCon except that constructors for the elements of the array are called.
Definition Arena.h:263
static const size_t MemoryAlignment
The alignment that memory allocators must ensure.
Definition stdinc.h:99
#define IF_DEBUG(X)
Definition stdinc.h:85
#define ASSERT(X)
Definition stdinc.h:86
size_t getSize() const
Definition Arena.h:150
size_t getFreeCapacity() const
Definition Arena.h:151
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