Frobby 0.10.0
Loading...
Searching...
No Matches
Arena.h
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
140 void discardPreviousBlock();
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
157 char* _blockBegin;
158 char* _freeBegin;
159 char* _blockEnd;
160 Block* _previousBlock;
161 } _block;
162
163 static Arena _scratchArena;
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());
200 ASSERT(alignNoOverflow(size) <= _block.getFreeCapacity());
201
202 void* ptr = _block._freeBegin;
203 _block._freeBegin += alignNoOverflow(size);
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
221 freeTopFromOldBlock(ptr);
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
238 freeAndAllAfterFromOldBlock(ptr);
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
261template<class T>
262pair<T*, T*> Arena::allocArray(size_t elementCount) {
263 pair<T*, T*> p = allocArrayNoCon<T>(elementCount);
264 T* it = p.first;
265 try {
266 for (; it != p.second; ++it)
267 new (it) T();
268 } catch (...) {
269 freeTopArray<T>(p.first, it);
270 throw;
271 }
272 return p;
273}
274
275template<class T>
276void Arena::freeTopArray(T* array, T* arrayEnd) {
277 ASSERT(array != 0);
278 ASSERT(array <= arrayEnd);
279
280 while (arrayEnd != array) {
281 --arrayEnd;
282 arrayEnd->~T();
283 }
284 freeTop(array);
285}
286
287template<class T>
288void Arena::freeArrayAndAllAfter(T* array, T* arrayEnd) {
289 ASSERT(array != 0);
290 ASSERT(array <= arrayEnd);
291
292 while (arrayEnd != array) {
293 --arrayEnd;
294 arrayEnd->~T();
295 }
296 freeAndAllAfter(array);
297}
298
299#endif
void freeArrayAndAllAfter(T *array, T *arrayEnd)
Definition Arena.h:288
void * alloc(size_t size)
Definition Arena.h:180
bool isEmpty() const
Definition Arena.h:117
pair< T *, T * > allocArrayNoCon(size_t elementCount)
Definition Arena.h:250
void freeTop(void *ptr)
Definition Arena.h:209
void freeTopArray(T *array, T *arrayEnd)
Definition Arena.h:276
void freeArrayAndAllAfter(pair< T *, T * > p)
Definition Arena.h:110
void freeTopArray(pair< T *, T * > p)
Definition Arena.h:100
static Arena & getArena()
Definition Arena.h:126
void freeAndAllAfter(void *ptr)
Definition Arena.h:224
pair< T *, T * > allocArray(size_t elementCount)
Definition Arena.h:262