this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Filip Konvicka <filip.konvicka@logis.cz>
5 *
6 * Copyright:
7 * LOGIS, s.r.o., 2009
8 *
9 * Bugfixes provided by:
10 * Gustavo Gutierrez
11 *
12 * This file is part of Gecode, the generic constraint
13 * development environment:
14 * http://www.gecode.org
15 *
16 * Permission is hereby granted, free of charge, to any person obtaining
17 * a copy of this software and associated documentation files (the
18 * "Software"), to deal in the Software without restriction, including
19 * without limitation the rights to use, copy, modify, merge, publish,
20 * distribute, sublicense, and/or sell copies of the Software, and to
21 * permit persons to whom the Software is furnished to do so, subject to
22 * the following conditions:
23 *
24 * The above copyright notice and this permission notice shall be
25 * included in all copies or substantial portions of the Software.
26 *
27 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
28 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
29 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
30 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
31 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
32 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
33 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
34 */
35
36#include <limits>
37
38namespace Gecode {
39
40 template<class T> struct space_allocator;
41
42/**
43
44\defgroup FuncMemAllocator Using allocators with Gecode
45\ingroup FuncMem
46
47%Gecode provides two allocator classes that can be used with
48generic data structures such as those of the STL
49(e.g. <tt>std::set</tt>). Memory can be allocated from the space heap
50(see Space) or from a region (see Region).
51
52\section FuncMemAllocatorA Using allocators with dynamic data structures
53
54There are two possible scenarios for allocator usage. One is to
55let the dynamic data structure allocate memory from the space or
56region:
57
58\code
59struct MySpace : public Space {
60 typedef std::set<int, std::less<int>, Gecode::space_allocator<int> > S;
61 S safe_set;
62
63 MySpace(void)
64 : safe_set(S::key_compare(), S::allocator_type(*this))
65 {}
66
67 MySpace(bool share, MySpace& other)
68 : Space(share, other),
69 safe_set(other.safe_set.begin(), other.safe_set.end(),
70 S::key_compare(), S::allocator_type(*this))
71 {}
72
73 ...
74};
75\endcode
76
77In this example, \a S is a set that allocates its nodes from the
78space heap. Note that we pass an instance of space_allocator
79bound to this space to the constructor of the set. A similar
80thing must be done in the copying constructor, where we must be
81sure to pass an allocator that allocates memory from the
82destination ("this") space, not "other". Note that the set
83itself is a member of \a MySpace, so it is destroyed within
84<i>MySpace::~MySpace</i> as usual. The set destructor destroys
85all contained items and deallocates all nodes in its destructors.
86
87\section FuncMemAllocatorB Preventing unnecessary destruction overhead
88
89In the above example, we know that the value type in \a S is a
90builtin type and does not have a destructor. So what happens
91during \a safe_set destruction is that it just deallocates all
92nodes. However, we know that all nodes were allocated from the
93space heap, which is going to disappear with the space anyway.
94If we prevent calling \a safe_set destructor, we may save a
95significant amount of time during space destruction. A safe way
96of doing this is to allocate the set object itself on the space
97heap, and keep only a reference to it as a member of the
98space. We can use the convenience helpers Space::construct for
99the construction.
100
101\code
102struct MySpace : public Space {
103 typedef std::set<int, std::less<int>, Gecode::space_allocator<int> > S;
104 S& fast_set;
105
106 MySpace(void)
107 : fast_set(construct<S>(S::key_compare(), S::allocator_type(*this)))
108 {}
109
110 MySpace(MySpace& other)
111 : Space(other),
112 fast_set(construct<S>(other.safe_set.begin(), other.safe_set.end(),
113 S::key_compare(), S::allocator_type(*this)))
114 {}
115
116 ...
117};
118\endcode
119
120\section FuncMemAllocatorC Region example
121
122The above examples were using a space_allocator. A region_allocator
123works similarly, one just should keep in mind that regions never
124really release any memory. Similar to Space, Region provides
125helper functions Region::construct to make non-stack allocation
126easy.
127
128\code
129Space& home = ...;
130typedef std::set<int, std::less<int>, Gecode::region_allocator<int> > SR;
131// Create a set with the region allocator. Note that the set destructor is still quite costly...
132{
133 Region r;
134 SR r_safe_set(SR::key_compare(), (SR::allocator_type(r)));
135 for(int i=0; i<10000; ++i)
136 r_safe_set.insert(i*75321%10000);
137}
138// Create a set directly in the region (not on the stack). No destructors will be called.
139{
140 Region r;
141 SR& r_fast_set=r.construct<SR>(SR::key_compare(), SR::allocator_type(r));
142 for(int i=0; i<10000; ++i)
143 r_fast_set.insert(i*75321%10000);
144}
145\endcode
146
147*/
148
149
150 /**
151 * \brief %Space allocator - specialization for \c void.
152 *
153 * The specialization is needed as the default instantiation fails
154 * for \c void.
155 */
156 template<>
157 struct space_allocator<void> {
158 typedef void* pointer;
159 typedef const void* const_pointer;
160 typedef void value_type;
161 /// Rebinding helper (returns the type of a similar allocator for type \a U)
162 template<class U> struct rebind {
163 typedef space_allocator<U> other;
164 };
165 };
166
167 /**
168 * \brief Allocator that allocates memory from a space heap
169 *
170 * Note that this allocator may be used to construct dynamic
171 * data structures that allocate memory from the space heap,
172 * or even reside in the space heap as a whole.
173 *
174 * \ingroup FuncMemAllocator
175 */
176 template<class T>
177 struct space_allocator {
178 /// Type of objects the allocator creates. This is identical to \a T.
179 typedef T value_type;
180 /// Type that can represent the size of the largest object.
181 typedef size_t size_type;
182 /// Type that can represent the difference between any two pointers.
183 typedef ptrdiff_t difference_type;
184 /// Type of pointers returned by the allocator.
185 typedef T* pointer;
186 /// Const version of pointer.
187 typedef T const* const_pointer;
188 /// Non-const reference to \a T.
189 typedef T& reference;
190 /// Const reference to \a T.
191 typedef T const& const_reference;
192 /// Rebinding helper (returns the type of a similar allocator for type \a U).
193 template<class U> struct rebind {
194 /// The allocator type for \a U
195 typedef space_allocator<U> other;
196 };
197
198 /// The space that we allocate objects from
199 Space& space;
200
201 /**
202 * \brief Construction
203 * @param space The space whose heap to allocate objects from.
204 */
205 space_allocator(Space& space) noexcept : space(space) {}
206 /**
207 * \brief Copy construction
208 * @param al The allocator to copy.
209 */
210 space_allocator(space_allocator const& al) noexcept : space(al.space) {}
211 /**
212 * \brief Assignment operator
213 * @param al The allocator to assign.
214 */
215 space_allocator& operator =(space_allocator const& al) {
216 (void) al;
217 assert(&space == &al.space);
218 return *this;
219 }
220 /**
221 * \brief Copy from other instantiation
222 * @param al The source allocator.
223 */
224 template<class U>
225 space_allocator(space_allocator<U> const& al) noexcept : space(al.space) {}
226
227 /// Convert a reference \a x to a pointer
228 pointer address(reference x) const { return &x; }
229 /// Convert a const reference \a x to a const pointer
230 const_pointer address(const_reference x) const { return &x; }
231 /// Returns the largest size for which a call to allocate might succeed.
232 size_type max_size(void) const noexcept {
233 return std::numeric_limits<size_type>::max() /
234 (sizeof(T)>0 ? sizeof(T) : 1);
235 }
236 /**
237 * \brief Allocates storage
238 *
239 * Returns a pointer to the first element in a block of storage
240 * <tt>count*sizeof(T)</tt> bytes in size. The block is aligned
241 * appropriately for objects of type \a T. Throws the exception
242 * \a bad_alloc if the storage is unavailable.
243 */
244 pointer allocate(size_type count) {
245 return static_cast<pointer>(space.ralloc(sizeof(T)*count));
246 }
247
248 /**
249 * \brief Allocates storage
250 *
251 * Returns a pointer to the first element in a block of storage
252 * <tt>count*sizeof(T)</tt> bytes in size. The block is aligned
253 * appropriately for objects of type \a T. Throws the exception
254 * \a bad_alloc if the storage is unavailable.
255 * The (unused) parameter could be used as an allocation hint,
256 * but this allocator ignores it.
257 */
258 pointer allocate(size_type count, const void * const hint) {
259 (void) hint;
260 return allocate(count);
261 }
262
263 /// Deallocates the storage obtained by a call to allocate() with arguments \a count and \a p.
264 void deallocate(pointer p, size_type count) {
265 space.rfree(static_cast<void*>(p), count);
266 }
267
268 /*
269 * \brief Constructs an object
270 *
271 * Constructs an object of type \a T with the initial value of \a t
272 * at the location specified by \a element. This function calls
273 * the <i>placement new()</i> operator.
274 */
275 void construct(pointer element, const_reference t) {
276 new (element) T(t);
277 }
278
279 /// Calls the destructor on the object pointed to by \a element.
280 void destroy(pointer element) {
281 element->~T();
282 }
283 };
284
285 /**
286 * \brief Tests two space allocators for equality
287 *
288 * Two allocators are equal when each can release storage allocated
289 * from the other.
290 */
291 template<class T1, class T2>
292 bool operator==(space_allocator<T1> const& al1,
293 space_allocator<T2> const& al2) noexcept {
294 return &al1.space == &al2.space;
295 }
296
297 /**
298 * \brief Tests two space allocators for inequality
299 *
300 * Two allocators are equal when each can release storage allocated
301 * from the other.
302 */
303 template<class T1, class T2>
304 bool operator!=(space_allocator<T1> const& al1,
305 space_allocator<T2> const& al2) noexcept {
306 return &al1.space != &al2.space;
307 }
308
309
310 template<class T> struct region_allocator;
311
312 /**
313 * \brief %Region allocator - specialization for \c void.
314 *
315 * The specialization is needed as the default instantiation fails
316 * for \c void.
317 */
318 template<>
319 struct region_allocator<void> {
320 typedef void* pointer;
321 typedef const void* const_pointer;
322 typedef void value_type;
323 /// Rebinding helper (returns the type of a similar allocator for type \a U)
324 template<class U> struct rebind {
325 typedef region_allocator<U> other;
326 };
327 };
328
329 /**
330 * \brief Allocator that allocates memory from a region
331 *
332 * Note that this allocator may be used to construct dynamic data structures
333 * that allocate memory from the region, or even reside in the region as a whole.
334 *
335 * \ingroup FuncMemAllocator
336 */
337 template<class T>
338 struct region_allocator {
339 /// Type of objects the allocator creates. This is identical to \a T.
340 typedef T value_type;
341 /// Type that can represent the size of the largest object.
342 typedef size_t size_type;
343 /// Type that can represent the difference between any two pointers.
344 typedef ptrdiff_t difference_type;
345 /// Type of pointers returned by the allocator.
346 typedef T* pointer;
347 /// Const version of pointer.
348 typedef T const* const_pointer;
349 /// Non-const reference to \a T.
350 typedef T& reference;
351 /// Const reference to \a T.
352 typedef T const& const_reference;
353
354 /// Rebinding helper (returns the type of a similar allocator for type \a U).
355 template<class U> struct rebind {
356 /// The allocator type for \a U
357 typedef region_allocator<U> other;
358 };
359
360 /// The region that we allocate objects from
361 Region& region;
362
363 /**
364 * \brief Construction
365 * @param region The region to allocate objects from.
366 */
367 region_allocator(Region& region) noexcept
368 : region(region) {}
369 /**
370 * \brief Copy construction
371 * @param al The allocator to copy.
372 */
373 region_allocator(region_allocator const& al) noexcept
374 : region(al.region) {}
375 /**
376 * \brief Copy from other instantiation.
377 * @param al The source allocator.
378 */
379 template<class U>
380 region_allocator(region_allocator<U> const& al) noexcept
381 : region(al.region) {}
382
383 /// Convert a reference \a x to a pointer
384 pointer address(reference x) const { return &x; }
385 /// Convert a const reference \a x to a const pointer
386 const_pointer address(const_reference x) const { return &x; }
387 /// Returns the largest size for which a call to allocate might succeed.
388 size_type max_size(void) const noexcept {
389 return std::numeric_limits<size_type>::max()
390 / (sizeof(T)>0 ? sizeof(T) : 1);
391 }
392
393 /**
394 * \brief Allocates storage
395 *
396 * Returns a pointer to the first element in a block of storage
397 * <tt>count*sizeof(T)</tt> bytes in size. The block is aligned
398 * appropriately for objects of type \a T. Throws the exception
399 * \a bad_alloc if the storage is unavailable.
400 */
401 pointer allocate(size_type count) {
402 return static_cast<pointer>(region.ralloc(sizeof(T)*count));
403 }
404
405 /**
406 * \brief Allocates storage
407 *
408 * Returns a pointer to the first element in a block of storage
409 * <tt>count*sizeof(T)</tt> bytes in size. The block is aligned
410 * appropriately for objects of type \a T. Throws the exception
411 * \a bad_alloc if the storage is unavailable.
412 *
413 * The (unused) parameter could be used as an allocation hint,
414 * but this allocator ignores it.
415 */
416 pointer allocate(size_type count, const void * const hint) {
417 (void) hint;
418 return allocate(count);
419 }
420
421 /**
422 * \brief Deallocates storage
423 *
424 * Deallocates storage obtained by a call to allocate() with
425 * arguments \a count and \a p. Note that region allocator never
426 * actually deallocates memory (so this function does nothing);
427 * the memory is released when the region is destroyed.
428 */
429 void deallocate(pointer p, size_type count) {
430 region.rfree(static_cast<void*>(p), count);
431 }
432
433 /**
434 * \brief Constructs an object
435 *
436 * Constructs an object of type \a T with the initial value
437 * of \a t at the location specified by \a element. This function
438 * calls the <i>placement new()</i> operator.
439 */
440 void construct(pointer element, const_reference t) {
441 new (element) T(t);
442 }
443
444 /// Calls the destructor on the object pointed to by \a element.
445 void destroy(pointer element) {
446 element->~T();
447 }
448 };
449
450 /*
451 * \brief Tests two region allocators for equality
452 *
453 * Two allocators are equal when each can release storage allocated
454 * from the other.
455 */
456 template<class T1, class T2>
457 bool operator==(region_allocator<T1> const& al1,
458 region_allocator<T2> const& al2) noexcept {
459 return &al1.region == &al2.region;
460 }
461
462 /*
463 * \brief Tests two region allocators for inequality
464 *
465 * Two allocators are equal when each can release storage allocated
466 * from the other.
467 */
468 template<class T1, class T2>
469 bool operator!=(region_allocator<T1> const& al1,
470 region_allocator<T2> const& al2) noexcept {
471 return &al1.region != &al2.region;
472 }
473
474}
475
476// STATISTICS: kernel-memory