DUNE PDELab (git)

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// SPDX-FileCopyrightInfo: Copyright © DUNE Project contributors, see file LICENSE.md in module root
4// SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception
5#ifndef DUNE_COMMON_POOLALLOCATOR_HH
6#define DUNE_COMMON_POOLALLOCATOR_HH
7
12#include <numeric>
13#include <typeinfo>
14#include <iostream>
15#include <cassert>
16#include <new>
17
18#ifndef DOXYGEN
19// forward declarations.
20// we need to know the test function to declare it friend
21template<std::size_t size, typename T>
22struct testPoolMain;
23#endif
24
25namespace Dune
26{
27
28 template<typename T, std::size_t s>
29 class Pool;
30
31 template<typename T, std::size_t s>
32 class PoolAllocator;
33
34}
35
36namespace std
37{
38 /*
39 template<class T, std::size_t S>
40 inline ostream& operator<<(ostream& os, Dune::Pool<T,S>& pool)
41 {
42 os<<"pool="<<&pool<<" allocated_="<<pool.allocated_;
43 return os;
44 }
45
46 template<class T, std::size_t S>
47 inline ostream& operator<<(ostream& os, Dune::PoolAllocator<T,S>& pool)
48 {
49 os<<pool.memoryPool_<<std::endl;
50 return os;
51 }
52 */
53}
54
55
56namespace Dune
57{
88 template<class T, std::size_t s>
89 class Pool
90 {
91 // make the test function friend
92 friend struct ::testPoolMain<s,T>;
93
94 //friend std::ostream& std::operator<<<>(std::ostream&,Pool<T,s>&);
95 template< class, std::size_t > friend class PoolAllocator;
96
97 private:
98
100 struct Reference
101 {
102 Reference *next_;
103 };
104
105 public:
106
108 typedef T MemberType;
109
113 constexpr static int unionSize = (sizeof(MemberType) < sizeof(Reference)) ?
114 sizeof(Reference) : sizeof(MemberType);
115
120 constexpr static int size = (sizeof(MemberType) <= s && sizeof(Reference) <= s) ?
121 s : unionSize;
122
127 constexpr static int alignment = std::lcm(alignof(MemberType), alignof(Reference));
128
135 constexpr static int alignedSize = (unionSize % alignment == 0) ?
136 unionSize :
137 ((unionSize / alignment + 1) * alignment);
138
144 constexpr static int chunkSize = (size % alignment == 0) ?
145 size : ((size / alignment + 1)* alignment);
146
150 constexpr static int elements = (chunkSize / alignedSize);
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
236 constexpr static int size = s * sizeof(value_type);
237
241 typedef T* pointer;
242
246 typedef const T* const_pointer;
247
251 typedef T& reference;
252
256 typedef const T& const_reference;
257
261 typedef std::size_t size_type;
262
266 typedef std::ptrdiff_t difference_type;
267
271 inline PoolAllocator();
272
276 template<typename U, std::size_t u>
278 {
279 // we allow copying but never copy the pool
280 // to have a clear ownership of allocated pointers.
281 }
282
285 {
286 // we allow copying but never copy the pool
287 // to have a clear ownership of allocated pointers.
288 // For this behaviour we have to implement
289 // the copy constructor, because the default
290 // one would copy the pool and deallocation
291 // of it would break.
292 }
299 inline pointer allocate(std::size_t n, const_pointer hint=0);
300
308 inline void deallocate(pointer p, std::size_t n);
309
315 inline void construct(pointer p, const_reference value);
316
321 inline void destroy(pointer p);
322
326 inline pointer address(reference x) const { return &x; }
327
328
332 inline const_pointer address(const_reference x) const { return &x; }
333
337 inline int max_size() const noexcept { return 1; }
338
342 template<class U>
343 struct rebind
344 {
346 };
347
350
351 private:
355 PoolType memoryPool_;
356 };
357
358 // specialization for void
359 template <std::size_t s>
360 class PoolAllocator<void,s>
361 {
362 public:
363 typedef void* pointer;
364 typedef const void* const_pointer;
365 // reference to void members are impossible.
366 typedef void value_type;
367 template <class U> struct rebind
368 {
369 typedef PoolAllocator<U,s> other;
370 };
371 };
372
373
374 template<typename T1, std::size_t t1, typename T2, std::size_t t2>
375 bool operator==(const PoolAllocator<T1,t1>&, const PoolAllocator<T2,t2>&)
376 {
377 return false;
378 }
379
380
381 template<typename T1, std::size_t t1, typename T2, std::size_t t2>
382 bool operator!=(const PoolAllocator<T1,t1>&, const PoolAllocator<T2,t2>&)
383 {
384 return true;
385 }
386
387 template<typename T, std::size_t t1, std::size_t t2>
388 bool operator==(const PoolAllocator<T,t1>& p1, const PoolAllocator<T,t2>& p2)
389 {
390 return &p1==&p2;
391 }
392
393
394 template<typename T, std::size_t t1, std::size_t t2>
395 bool operator!=(const PoolAllocator<T,t1>& p1, const PoolAllocator<T,t2>& p2)
396 {
397 return &p1 != &p2;
398 }
399
400 template<typename T, std::size_t t1, std::size_t t2>
401 bool operator==(const PoolAllocator<void,t1>&, const PoolAllocator<T,t2>&)
402 {
403 return false;
404 }
405
406
407 template<typename T, std::size_t t1, std::size_t t2>
408 bool operator!=(const PoolAllocator<void,t1>&, const PoolAllocator<T,t2>&)
409 {
410 return true;
411 }
412
413 template<std::size_t t1, std::size_t t2>
414 bool operator==(const PoolAllocator<void,t1>& p1, const PoolAllocator<void,t2>& p2)
415 {
416 return &p1==&p2;
417 }
418
419 template<std::size_t t1, std::size_t t2>
420 bool operator!=(const PoolAllocator<void,t1>& p1, const PoolAllocator<void,t2>& p2)
421 {
422 return &p1!=&p2;
423 }
424
425 template<class T, std::size_t S>
427 : head_(0), chunks_(0) //, allocated_(0)
428 {
429 static_assert(sizeof(T)<=unionSize, "Library Error: type T is too big");
430 static_assert(sizeof(Reference)<=unionSize, "Library Error: type of reference is too big");
431 static_assert(unionSize<=alignedSize, "Library Error: alignedSize too small");
432 static_assert(sizeof(T)<=chunkSize, "Library Error: chunkSize must be able to hold at least one value");
433 static_assert(sizeof(Reference)<=chunkSize, "Library Error: chunkSize must be able to hold at least one reference");
434 static_assert(chunkSize % alignment == 0, "Library Error: compiler cannot calculate!");
435 static_assert(elements>=1, "Library Error: we need to hold at least one element!");
436 static_assert(elements*alignedSize<=chunkSize, "Library Error: aligned elements must fit into chuck!");
437 }
438
439 template<class T, std::size_t S>
441 {
442 /*
443 if(allocated_!=0)
444 std::cerr<<"There are still "<<allocated_<<" allocated elements by the Pool<"<<typeid(T).name()<<","<<S<<"> "
445 <<static_cast<void*>(this)<<"! This is a memory leak and might result in segfaults"
446 <<std::endl;
447 */
448 // delete the allocated chunks.
449 Chunk *current=chunks_;
450
451 while(current!=0)
452 {
453 Chunk *tmp = current;
454 current = current->next_;
455 delete tmp;
456 }
457 }
458
459 template<class T, std::size_t S>
460 inline void Pool<T,S>::print(std::ostream& os)
461 {
462 Chunk* current=chunks_;
463 while(current) {
464 os<<current<<" ";
465 current=current->next_;
466 }
467 os<<current<<" ";
468 }
469
470 template<class T, std::size_t S>
471 inline void Pool<T,S>::grow()
472 {
473 Chunk *newChunk = new Chunk;
474 newChunk->next_ = chunks_;
475 chunks_ = newChunk;
476
477 char* start = chunks_->chunk_;
478 char* last = &start[elements*alignedSize];
479 Reference* ref = new (start) (Reference);
480
481 // grow is only called if head==0,
482 assert(!head_);
483
484 head_ = ref;
485
486 for(char* element=start+alignedSize; element<last; element=element+alignedSize) {
487 Reference* next = new (element) (Reference);
488 ref->next_ = next;
489 ref = next;
490 }
491 ref->next_=0;
492 }
493
494 template<class T, std::size_t S>
495 inline void Pool<T,S>::free(void* b)
496 {
497 if(b) {
498#ifndef NDEBUG
499 Chunk* current=chunks_;
500 while(current) {
501 if(static_cast<void*>(current->chunk_)<=b &&
502 static_cast<void*>(current->chunk_+chunkSize)>b)
503 break;
504 current=current->next_;
505 }
506 if(!current)
507 throw std::bad_alloc();
508#endif
509 Reference* freed = static_cast<Reference*>(b);
510 freed->next_ = head_;
511 head_ = freed;
512 //--allocated_;
513 }
514 else
515 {
516 std::cerr<< "Tried to free null pointer! "<<b<<std::endl;
517 throw std::bad_alloc();
518 }
519 }
520
521 template<class T, std::size_t S>
522 inline void* Pool<T,S>::allocate()
523 {
524 if(!head_)
525 grow();
526
527 Reference* p = head_;
528 head_ = p->next_;
529 //++allocated_;
530 return p;
531 }
532
533 template<class T, std::size_t s>
535 { }
536
537 template<class T, std::size_t s>
538 inline typename PoolAllocator<T,s>::pointer
540 {
541 if(n==1)
542 return static_cast<T*>(memoryPool_.allocate());
543 else
544 throw std::bad_alloc();
545 }
546
547 template<class T, std::size_t s>
548 inline void PoolAllocator<T,s>::deallocate(pointer p, std::size_t n)
549 {
550 for(size_t i=0; i<n; i++)
551 memoryPool_.free(p++);
552 }
553
554 template<class T, std::size_t s>
556 {
557 ::new (static_cast<void*>(p))T(value);
558 }
559
560 template<class T, std::size_t s>
562 {
563 p->~T();
564 }
565
567}
568#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:349
const_pointer address(const_reference x) const
Convert a reference to a pointer.
Definition: poolallocator.hh:332
const T & const_reference
The constant reference type.
Definition: poolallocator.hh:256
std::size_t size_type
The size type.
Definition: poolallocator.hh:261
T value_type
Type of the values we construct and allocate.
Definition: poolallocator.hh:230
T & reference
The reference type.
Definition: poolallocator.hh:251
PoolAllocator(const PoolAllocator &)
Copy constructor that does not copy the memory pool.
Definition: poolallocator.hh:284
const T * const_pointer
The constant pointer type.
Definition: poolallocator.hh:246
pointer address(reference x) const
Convert a reference to a pointer.
Definition: poolallocator.hh:326
T * pointer
The pointer type.
Definition: poolallocator.hh:241
PoolAllocator(const PoolAllocator< U, u > &)
Copy Constructor that does not copy the memory pool.
Definition: poolallocator.hh:277
std::ptrdiff_t difference_type
The difference_type.
Definition: poolallocator.hh:266
int max_size() const noexcept
Not correctly implemented, yet!
Definition: poolallocator.hh:337
static constexpr int size
The number of objects to fit into one memory chunk allocated.
Definition: poolallocator.hh:236
A memory pool of objects.
Definition: poolallocator.hh:90
static constexpr int alignment
The alignment that suits both the MemberType and the Reference (i.e. their least common multiple).
Definition: poolallocator.hh:127
static constexpr int alignedSize
The aligned size of the type.
Definition: poolallocator.hh:135
static constexpr int chunkSize
The size of each chunk memory chunk.
Definition: poolallocator.hh:144
static constexpr int size
Size requirement. At least one object has to stored.
Definition: poolallocator.hh:120
static constexpr int unionSize
The size of a union of Reference and MemberType.
Definition: poolallocator.hh:113
T MemberType
The type of object we allocate memory for.
Definition: poolallocator.hh:108
static constexpr int elements
The number of element each chunk can hold.
Definition: poolallocator.hh:150
void construct(pointer p, const_reference value)
Construct an object.
Definition: poolallocator.hh:555
void free(void *o)
Free an object.
Definition: poolallocator.hh:495
~Pool()
Destructor.
Definition: poolallocator.hh:440
void * allocate()
Get a new or recycled object.
Definition: poolallocator.hh:522
void print(std::ostream &os)
Print elements in pool for debugging.
Definition: poolallocator.hh:460
pointer allocate(std::size_t n, const_pointer hint=0)
Allocates objects.
Definition: poolallocator.hh:539
Pool()
Constructor.
Definition: poolallocator.hh:426
void deallocate(pointer p, std::size_t n)
Free objects.
Definition: poolallocator.hh:548
void destroy(pointer p)
Destroy an object without freeing memory.
Definition: poolallocator.hh:561
PoolAllocator()
Constructor.
Definition: poolallocator.hh:534
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:238
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:260
Dune namespace.
Definition: alignedallocator.hh:13
STL namespace.
Rebind the allocator to another type.
Definition: poolallocator.hh:344
Get the 'const' version of a reference to a mutable object.
Definition: genericiterator.hh:87
Creative Commons License   |  Legal Statements / Impressum  |  Hosted by TU Dresden  |  generated with Hugo v0.111.3 (Nov 23, 23:29, 2024)