Dune Core Modules (2.8.0)

poolallocator.hh
Go to the documentation of this file.
1// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2// vi: set et ts=4 sw=2 sts=2:
3#ifndef DUNE_COMMON_POOLALLOCATOR_HH
4#define DUNE_COMMON_POOLALLOCATOR_HH
5
10#include <numeric>
11#include <typeinfo>
12#include <iostream>
13#include <cassert>
14#include <new>
15
16#ifndef DOXYGEN
17// forward declarations.
18// we need to know the test function to declare it friend
19template<std::size_t size, typename T>
20struct testPoolMain;
21#endif
22
23namespace Dune
24{
25
26 template<typename T, std::size_t s>
27 class Pool;
28
29 template<typename T, std::size_t s>
30 class PoolAllocator;
31
32}
33
34namespace std
35{
36 /*
37 template<class T, std::size_t S>
38 inline ostream& operator<<(ostream& os, Dune::Pool<T,S>& pool)
39 {
40 os<<"pool="<<&pool<<" allocated_="<<pool.allocated_;
41 return os;
42 }
43
44 template<class T, std::size_t S>
45 inline ostream& operator<<(ostream& os, Dune::PoolAllocator<T,S>& pool)
46 {
47 os<<pool.memoryPool_<<std::endl;
48 return os;
49 }
50 */
51}
52
53
54namespace Dune
55{
86 template<class T, std::size_t s>
87 class Pool
88 {
89 // make the test function friend
90 friend struct ::testPoolMain<s,T>;
91
92 //friend std::ostream& std::operator<<<>(std::ostream&,Pool<T,s>&);
93 template< class, std::size_t > friend class PoolAllocator;
94
95 private:
96
98 struct Reference
99 {
100 Reference *next_;
101 };
102
103 public:
104
106 typedef T MemberType;
107 enum
108 {
112 unionSize = ((sizeof(MemberType) < sizeof(Reference)) ?
113 sizeof(Reference) : sizeof(MemberType)),
114
119 size = ((sizeof(MemberType) <= s && sizeof(Reference) <= s) ?
121
126 alignment = std::lcm(alignof(MemberType), alignof(Reference)),
127
134 alignedSize = ((unionSize % alignment == 0) ?
135 unionSize :
137
143 chunkSize = ((size % alignment == 0) ?
145
150 };
151
152 private:
154 struct Chunk
155 {
156
157 //friend int testPool<s,T>();
158
160 alignas(alignment) char chunk_[chunkSize];
161
163 Chunk *next_;
164 };
165
166 public:
168 inline Pool();
170 inline ~Pool();
175 inline void* allocate();
180 inline void free(void* o);
181
185 inline void print(std::ostream& os);
186
187 private:
188
189 // Prevent Copying!
190 Pool(const Pool<MemberType,s>&);
191
192 void operator=(const Pool<MemberType,s>& pool) const;
194 inline void grow();
196 Reference *head_;
198 Chunk *chunks_;
199 /* @brief The number of currently allocated elements. */
200 //size_t allocated_;
201
202 };
203
221 template<class T, std::size_t s>
223 {
224 //friend std::ostream& std::operator<<<>(std::ostream&,PoolAllocator<T,s>&);
225
226 public:
230 typedef T value_type;
231
232 enum
233 {
238 size=s*sizeof(value_type)
239 };
240
244 typedef T* pointer;
245
249 typedef const T* const_pointer;
250
254 typedef T& reference;
255
259 typedef const T& const_reference;
260
264 typedef std::size_t size_type;
265
269 typedef std::ptrdiff_t difference_type;
270
274 inline PoolAllocator();
275
279 template<typename U, std::size_t u>
281 {
282 // we allow copying but never copy the pool
283 // to have a clear ownership of allocated pointers.
284 }
285
288 {
289 // we allow copying but never copy the pool
290 // to have a clear ownership of allocated pointers.
291 // For this behaviour we have to implement
292 // the copy constructor, because the default
293 // one would copy the pool and deallocation
294 // of it would break.
295 }
302 inline pointer allocate(std::size_t n, const_pointer hint=0);
303
311 inline void deallocate(pointer p, std::size_t n);
312
318 inline void construct(pointer p, const_reference value);
319
324 inline void destroy(pointer p);
325
329 inline pointer address(reference x) const { return &x; }
330
331
335 inline const_pointer address(const_reference x) const { return &x; }
336
340 inline int max_size() const noexcept { return 1; }
341
345 template<class U>
346 struct rebind
347 {
349 };
350
353
354 private:
358 PoolType memoryPool_;
359 };
360
361 // specialization for void
362 template <std::size_t s>
363 class PoolAllocator<void,s>
364 {
365 public:
366 typedef void* pointer;
367 typedef const void* const_pointer;
368 // reference to void members are impossible.
369 typedef void value_type;
370 template <class U> struct rebind
371 {
372 typedef PoolAllocator<U,s> other;
373 };
374 };
375
376
377 template<typename T1, std::size_t t1, typename T2, std::size_t t2>
378 bool operator==(const PoolAllocator<T1,t1>&, const PoolAllocator<T2,t2>&)
379 {
380 return false;
381 }
382
383
384 template<typename T1, std::size_t t1, typename T2, std::size_t t2>
385 bool operator!=(const PoolAllocator<T1,t1>&, const PoolAllocator<T2,t2>&)
386 {
387 return true;
388 }
389
390 template<typename T, std::size_t t1, std::size_t t2>
391 bool operator==(const PoolAllocator<T,t1>& p1, const PoolAllocator<T,t2>& p2)
392 {
393 return &p1==&p2;
394 }
395
396
397 template<typename T, std::size_t t1, std::size_t t2>
398 bool operator!=(const PoolAllocator<T,t1>& p1, const PoolAllocator<T,t2>& p2)
399 {
400 return &p1 != &p2;
401 }
402
403 template<typename T, std::size_t t1, std::size_t t2>
404 bool operator==(const PoolAllocator<void,t1>&, const PoolAllocator<T,t2>&)
405 {
406 return false;
407 }
408
409
410 template<typename T, std::size_t t1, std::size_t t2>
411 bool operator!=(const PoolAllocator<void,t1>&, const PoolAllocator<T,t2>&)
412 {
413 return true;
414 }
415
416 template<std::size_t t1, std::size_t t2>
417 bool operator==(const PoolAllocator<void,t1>& p1, const PoolAllocator<void,t2>& p2)
418 {
419 return &p1==&p2;
420 }
421
422 template<std::size_t t1, std::size_t t2>
423 bool operator!=(const PoolAllocator<void,t1>& p1, const PoolAllocator<void,t2>& p2)
424 {
425 return &p1!=&p2;
426 }
427
428 template<class T, std::size_t S>
430 : head_(0), chunks_(0) //, allocated_(0)
431 {
432 static_assert(sizeof(T)<=unionSize, "Library Error: type T is too big");
433 static_assert(sizeof(Reference)<=unionSize, "Library Error: type of referene is too big");
434 static_assert(unionSize<=alignedSize, "Library Error: alignedSize too small");
435 static_assert(sizeof(T)<=chunkSize, "Library Error: chunkSize must be able to hold at least one value");
436 static_assert(sizeof(Reference)<=chunkSize, "Library Error: chunkSize must be able to hold at least one reference");
437 static_assert(chunkSize % alignment == 0, "Library Error: compiler cannot calculate!");
438 static_assert(elements>=1, "Library Error: we need to hold at least one element!");
439 static_assert(elements*alignedSize<=chunkSize, "Library Error: aligned elements must fit into chuck!");
440 }
441
442 template<class T, std::size_t S>
444 {
445 /*
446 if(allocated_!=0)
447 std::cerr<<"There are still "<<allocated_<<" allocated elements by the Pool<"<<typeid(T).name()<<","<<S<<"> "
448 <<static_cast<void*>(this)<<"! This is a memory leak and might result in segfaults"
449 <<std::endl;
450 */
451 // delete the allocated chunks.
452 Chunk *current=chunks_;
453
454 while(current!=0)
455 {
456 Chunk *tmp = current;
457 current = current->next_;
458 delete tmp;
459 }
460 }
461
462 template<class T, std::size_t S>
463 inline void Pool<T,S>::print(std::ostream& os)
464 {
465 Chunk* current=chunks_;
466 while(current) {
467 os<<current<<" ";
468 current=current->next_;
469 }
470 os<<current<<" ";
471 }
472
473 template<class T, std::size_t S>
474 inline void Pool<T,S>::grow()
475 {
476 Chunk *newChunk = new Chunk;
477 newChunk->next_ = chunks_;
478 chunks_ = newChunk;
479
480 char* start = chunks_->chunk_;
481 char* last = &start[elements*alignedSize];
482 Reference* ref = new (start) (Reference);
483
484 // grow is only called if head==0,
485 assert(!head_);
486
487 head_ = ref;
488
489 for(char* element=start+alignedSize; element<last; element=element+alignedSize) {
490 Reference* next = new (element) (Reference);
491 ref->next_ = next;
492 ref = next;
493 }
494 ref->next_=0;
495 }
496
497 template<class T, std::size_t S>
498 inline void Pool<T,S>::free(void* b)
499 {
500 if(b) {
501#ifndef NDEBUG
502 Chunk* current=chunks_;
503 while(current) {
504 if(static_cast<void*>(current->chunk_)<=b &&
505 static_cast<void*>(current->chunk_+chunkSize)>b)
506 break;
507 current=current->next_;
508 }
509 if(!current)
510 throw std::bad_alloc();
511#endif
512 Reference* freed = static_cast<Reference*>(b);
513 freed->next_ = head_;
514 head_ = freed;
515 //--allocated_;
516 }
517 else
518 {
519 std::cerr<< "Tried to free null pointer! "<<b<<std::endl;
520 throw std::bad_alloc();
521 }
522 }
523
524 template<class T, std::size_t S>
525 inline void* Pool<T,S>::allocate()
526 {
527 if(!head_)
528 grow();
529
530 Reference* p = head_;
531 head_ = p->next_;
532 //++allocated_;
533 return p;
534 }
535
536 template<class T, std::size_t s>
538 { }
539
540 template<class T, std::size_t s>
541 inline typename PoolAllocator<T,s>::pointer
543 {
544 if(n==1)
545 return static_cast<T*>(memoryPool_.allocate());
546 else
547 throw std::bad_alloc();
548 }
549
550 template<class T, std::size_t s>
551 inline void PoolAllocator<T,s>::deallocate(pointer p, std::size_t n)
552 {
553 for(size_t i=0; i<n; i++)
554 memoryPool_.free(p++);
555 }
556
557 template<class T, std::size_t s>
559 {
560 ::new (static_cast<void*>(p))T(value);
561 }
562
563 template<class T, std::size_t s>
565 {
566 p->~T();
567 }
568
570}
571#endif
An allocator managing a pool of objects for reuse.
Definition: poolallocator.hh:223
Pool< T, size > PoolType
The type of the memory pool we use.
Definition: poolallocator.hh:352
const_pointer address(const_reference x) const
Convert a reference to a pointer.
Definition: poolallocator.hh:335
const T & const_reference
The constant reference type.
Definition: poolallocator.hh:259
std::size_t size_type
The size type.
Definition: poolallocator.hh:264
T value_type
Type of the values we construct and allocate.
Definition: poolallocator.hh:230
@ size
The number of objects to fit into one memory chunk allocated.
Definition: poolallocator.hh:238
T & reference
The reference type.
Definition: poolallocator.hh:254
PoolAllocator(const PoolAllocator &)
Copy constructor that does not copy the memory pool.
Definition: poolallocator.hh:287
const T * const_pointer
The constant pointer type.
Definition: poolallocator.hh:249
pointer address(reference x) const
Convert a reference to a pointer.
Definition: poolallocator.hh:329
T * pointer
The pointer type.
Definition: poolallocator.hh:244
PoolAllocator(const PoolAllocator< U, u > &)
Copy Constructor that does not copy the memory pool.
Definition: poolallocator.hh:280
std::ptrdiff_t difference_type
The difference_type.
Definition: poolallocator.hh:269
int max_size() const noexcept
Not correctly implemented, yet!
Definition: poolallocator.hh:340
A memory pool of objects.
Definition: poolallocator.hh:88
@ elements
The number of element each chunk can hold.
Definition: poolallocator.hh:149
@ chunkSize
The size of each chunk memory chunk.
Definition: poolallocator.hh:143
@ unionSize
The size of a union of Reference and MemberType.
Definition: poolallocator.hh:112
@ alignment
The alignment that suits both the MemberType and the Reference (i.e. their least common multiple).
Definition: poolallocator.hh:126
@ size
Size requirement. At least one object has to stored.
Definition: poolallocator.hh:119
@ alignedSize
The aligned size of the type.
Definition: poolallocator.hh:134
T MemberType
The type of object we allocate memory for.
Definition: poolallocator.hh:106
void construct(pointer p, const_reference value)
Construct an object.
Definition: poolallocator.hh:558
void free(void *o)
Free an object.
Definition: poolallocator.hh:498
~Pool()
Destructor.
Definition: poolallocator.hh:443
void * allocate()
Get a new or recycled object.
Definition: poolallocator.hh:525
void print(std::ostream &os)
Print elements in pool for debugging.
Definition: poolallocator.hh:463
pointer allocate(std::size_t n, const_pointer hint=0)
Allocates objects.
Definition: poolallocator.hh:542
Pool()
Constructor.
Definition: poolallocator.hh:429
void deallocate(pointer p, std::size_t n)
Free objects.
Definition: poolallocator.hh:551
void destroy(pointer p)
Destroy an object without freeing memory.
Definition: poolallocator.hh:564
PoolAllocator()
Constructor.
Definition: poolallocator.hh:537
EnableIfInterOperable< T1, T2, bool >::type operator==(const ForwardIteratorFacade< T1, V1, R1, D > &lhs, const ForwardIteratorFacade< T2, V2, R2, D > &rhs)
Checks for equality.
Definition: iteratorfacades.hh:235
EnableIfInterOperable< T1, T2, bool >::type operator!=(const ForwardIteratorFacade< T1, V1, R1, D > &lhs, const ForwardIteratorFacade< T2, V2, R2, D > &rhs)
Checks for inequality.
Definition: iteratorfacades.hh:257
Dune namespace.
Definition: alignedallocator.hh:11
STL namespace.
Rebind the allocator to another type.
Definition: poolallocator.hh:347
Get the 'const' version of a reference to a mutable object.
Definition: genericiterator.hh:85
Creative Commons License   |  Legal Statements / Impressum  |  Hosted by TU Dresden  |  generated with Hugo v0.111.3 (Nov 21, 23:30, 2024)