Frobby
0.10.0
Toggle main menu visibility
Loading...
Searching...
No Matches
src
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
53
class
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
168
inline
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
180
inline
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
209
inline
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
224
inline
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
241
inline
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
249
template
<
class
T>
250
pair<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
template
<
class
T>
262
pair<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
275
template
<
class
T>
276
void
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
287
template
<
class
T>
288
void
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
Arena::freeArrayAndAllAfter
void freeArrayAndAllAfter(T *array, T *arrayEnd)
Definition
Arena.h:288
Arena::alloc
void * alloc(size_t size)
Definition
Arena.h:180
Arena::isEmpty
bool isEmpty() const
Definition
Arena.h:117
Arena::allocArrayNoCon
pair< T *, T * > allocArrayNoCon(size_t elementCount)
Definition
Arena.h:250
Arena::freeTop
void freeTop(void *ptr)
Definition
Arena.h:209
Arena::freeTopArray
void freeTopArray(T *array, T *arrayEnd)
Definition
Arena.h:276
Arena::freeArrayAndAllAfter
void freeArrayAndAllAfter(pair< T *, T * > p)
Definition
Arena.h:110
Arena::freeTopArray
void freeTopArray(pair< T *, T * > p)
Definition
Arena.h:100
Arena::getArena
static Arena & getArena()
Definition
Arena.h:126
Arena::freeAndAllAfter
void freeAndAllAfter(void *ptr)
Definition
Arena.h:224
Arena::allocArray
pair< T *, T * > allocArray(size_t elementCount)
Definition
Arena.h:262
Generated by
1.17.0