Dune Core Modules (2.4.2)

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 "alignment.hh"
11 #include "lcm.hh"
12 #include <typeinfo>
13 #include <iostream>
14 #include <cassert>
15 #include <new>
16 
17 #ifndef DOXYGEN
18 // forward declarations.
19 // we need to know the test function to declare it friend
20 template<std::size_t size, typename T>
21 struct testPoolMain;
22 #endif
23 
24 namespace Dune
25 {
26 
27  template<typename T, std::size_t s>
28  class Pool;
29 
30  template<typename T, std::size_t s>
31  class PoolAllocator;
32 
33 }
34 
35 namespace std
36 {
37  /*
38  template<class T, std::size_t S>
39  inline ostream& operator<<(ostream& os, Dune::Pool<T,S>& pool)
40  {
41  os<<"pool="<<&pool<<" allocated_="<<pool.allocated_;
42  return os;
43  }
44 
45  template<class T, std::size_t S>
46  inline ostream& operator<<(ostream& os, Dune::PoolAllocator<T,S>& pool)
47  {
48  os<<pool.memoryPool_<<std::endl;
49  return os;
50  }
51  */
52 }
53 
54 
55 namespace Dune
56 {
87  template<class T, std::size_t s>
88  class Pool
89  {
90  // make the test function friend
91  friend struct ::testPoolMain<s,T>;
92 
93  //friend std::ostream& std::operator<<<>(std::ostream&,Pool<T,s>&);
94  template< class, std::size_t > friend class PoolAllocator;
95 
96  private:
97 
99  struct Reference
100  {
101  Reference *next_;
102  };
103 
104  public:
105 
107  typedef T MemberType;
108  enum
109  {
113  unionSize = ((sizeof(MemberType) < sizeof(Reference)) ?
114  sizeof(Reference) : sizeof(MemberType)),
115 
120  size = ((sizeof(MemberType) <= s && sizeof(Reference) <= s) ?
121  s : unionSize),
122 
128 
135  alignedSize = ((unionSize % alignment == 0) ?
136  unionSize :
138 
146  chunkSize = ((size % alignment == 0) ?
147  size : ((size / alignment + 1)* alignment))
148  + alignment - 1,
149 
154  };
155 
156  private:
158  struct Chunk
159  {
160 
161  //friend int testPool<s,T>();
162 
164  char chunk_[chunkSize];
165 
170  char* memory_;
171 
173  Chunk *next_;
174 
178  Chunk()
179  {
180  // Make sure the alignment is correct!
181  // long long should be 64bit safe!
182  unsigned long long lmemory = reinterpret_cast<unsigned long long>(chunk_);
183  if(lmemory % alignment != 0)
184  lmemory = (lmemory / alignment + 1)
185  * alignment;
186 
187  memory_ = reinterpret_cast<char *>(lmemory);
188  }
189  };
190 
191  public:
193  inline Pool();
195  inline ~Pool();
200  inline void* allocate();
205  inline void free(void* o);
206 
210  inline void print(std::ostream& os);
211 
212  private:
213 
214  // Prevent Copying!
215  Pool(const Pool<MemberType,s>&);
216 
217  void operator=(const Pool<MemberType,s>& pool) const;
219  inline void grow();
221  Reference *head_;
223  Chunk *chunks_;
224  /* @brief The number of currently allocated elements. */
225  //size_t allocated_;
226 
227  };
228 
246  template<class T, std::size_t s>
248  {
249  //friend std::ostream& std::operator<<<>(std::ostream&,PoolAllocator<T,s>&);
250 
251  public:
255  typedef T value_type;
256 
257  enum
258  {
263  size=s*sizeof(value_type)
264  };
265 
269  typedef T* pointer;
270 
274  typedef const T* const_pointer;
275 
279  typedef T& reference;
280 
284  typedef const T& const_reference;
285 
289  typedef std::size_t size_type;
290 
294  typedef std::ptrdiff_t difference_type;
295 
299  inline PoolAllocator();
300 
304  template<typename U, std::size_t u>
306  {
307  // we allow copying but never copy the pool
308  // to have a clear ownership of allocated pointers.
309  }
310 
313  {
314  // we allow copying but never copy the pool
315  // to have a clear ownership of allocated pointers.
316  // For this behaviour we have to implement
317  // the copy constructor, because the default
318  // one would copy the pool and deallocation
319  // of it would break.
320  }
327  inline pointer allocate(std::size_t n, const_pointer hint=0);
328 
336  inline void deallocate(pointer p, std::size_t n);
337 
343  inline void construct(pointer p, const_reference value);
344 
349  inline void destroy(pointer p);
350 
354  inline pointer address(reference x) const { return &x; }
355 
356 
360  inline const_pointer address(const_reference x) const { return &x; }
361 
365  inline int max_size() const throw(){ return 1;}
366 
370  template<class U>
371  struct rebind
372  {
373  typedef PoolAllocator<U,s> other;
374  };
375 
378 
379  private:
383  PoolType memoryPool_;
384  };
385 
386  // specialization for void
387  template <std::size_t s>
388  class PoolAllocator<void,s>
389  {
390  public:
391  typedef void* pointer;
392  typedef const void* const_pointer;
393  // reference to void members are impossible.
394  typedef void value_type;
395  template <class U> struct rebind
396  {
397  typedef PoolAllocator<U,s> other;
398  };
399  };
400 
401 
402  template<typename T1, std::size_t t1, typename T2, std::size_t t2>
403  bool operator==(const PoolAllocator<T1,t1>&, const PoolAllocator<T2,t2>&)
404  {
405  return false;
406  }
407 
408 
409  template<typename T1, std::size_t t1, typename T2, std::size_t t2>
410  bool operator!=(const PoolAllocator<T1,t1>&, const PoolAllocator<T2,t2>&)
411  {
412  return true;
413  }
414 
415  template<typename T, std::size_t t1, std::size_t t2>
416  bool operator==(const PoolAllocator<T,t1>& p1, const PoolAllocator<T,t2>& p2)
417  {
418  return &p1==&p2;
419  }
420 
421 
422  template<typename T, std::size_t t1, std::size_t t2>
423  bool operator!=(const PoolAllocator<T,t1>& p1, const PoolAllocator<T,t2>& p2)
424  {
425  return &p1 != &p2;
426  }
427 
428  template<typename T, std::size_t t1, std::size_t t2>
429  bool operator==(const PoolAllocator<void,t1>&, const PoolAllocator<T,t2>&)
430  {
431  return false;
432  }
433 
434 
435  template<typename T, std::size_t t1, std::size_t t2>
436  bool operator!=(const PoolAllocator<void,t1>&, const PoolAllocator<T,t2>&)
437  {
438  return true;
439  }
440 
441  template<std::size_t t1, std::size_t t2>
442  bool operator==(const PoolAllocator<void,t1>& p1, const PoolAllocator<void,t2>& p2)
443  {
444  return &p1==&p2;
445  }
446 
447  template<std::size_t t1, std::size_t t2>
448  bool operator!=(const PoolAllocator<void,t1>& p1, const PoolAllocator<void,t2>& p2)
449  {
450  return &p1!=&p2;
451  }
452 
453  template<class T, std::size_t S>
455  : head_(0), chunks_(0) //, allocated_(0)
456  {
457  static_assert(sizeof(T)<=unionSize, "Library Error: type T is too big");
458  static_assert(sizeof(Reference)<=unionSize, "Library Error: type of referene is too big");
459  static_assert(unionSize<=alignedSize, "Library Error: alignedSize too small");
460  static_assert(sizeof(T)<=chunkSize, "Library Error: chunkSize must be able to hold at least one value");
461  static_assert(sizeof(Reference)<=chunkSize, "Library Error: chunkSize must be able to hold at least one reference");
462  static_assert((chunkSize - (alignment - 1)) % alignment == 0, "Library Error: compiler cannot calculate!");
463  static_assert(elements>=1, "Library Error: we need to hold at least one element!");
464  static_assert(elements*alignedSize<=chunkSize, "Library Error: aligned elements must fit into chuck!");
465  }
466 
467  template<class T, std::size_t S>
469  {
470  /*
471  if(allocated_!=0)
472  std::cerr<<"There are still "<<allocated_<<" allocated elements by the Pool<"<<typeid(T).name()<<","<<S<<"> "
473  <<static_cast<void*>(this)<<"! This is a memory leak and might result in segfaults"
474  <<std::endl;
475  */
476  // delete the allocated chunks.
477  Chunk *current=chunks_;
478 
479  while(current!=0)
480  {
481  Chunk *tmp = current;
482  current = current->next_;
483  delete tmp;
484  }
485  }
486 
487  template<class T, std::size_t S>
488  inline void Pool<T,S>::print(std::ostream& os)
489  {
490  Chunk* current=chunks_;
491  while(current) {
492  os<<current<<" ";
493  current=current->next_;
494  }
495  os<<current<<" ";
496  }
497 
498  template<class T, std::size_t S>
499  inline void Pool<T,S>::grow()
500  {
501  Chunk *newChunk = new Chunk;
502  newChunk->next_ = chunks_;
503  chunks_ = newChunk;
504 
505  char* start = chunks_->memory_;
506  char* last = &start[elements*alignedSize];
507  Reference* ref = new (start) (Reference);
508 
509  // grow is only called if head==0,
510  assert(!head_);
511 
512  head_ = ref;
513 
514  for(char* element=start+alignedSize; element<last; element=element+alignedSize) {
515  Reference* next = new (element) (Reference);
516  ref->next_ = next;
517  ref = next;
518  }
519  ref->next_=0;
520  }
521 
522  template<class T, std::size_t S>
523  inline void Pool<T,S>::free(void* b)
524  {
525  if(b) {
526 #ifndef NDEBUG
527  Chunk* current=chunks_;
528  while(current) {
529  if(static_cast<void*>(&current->chunk_)<=b &&
530  static_cast<void*>((&current->chunk_)+chunkSize)>b)
531  break;
532  current=current->next_;
533  }
534  if(!current)
535  throw std::bad_alloc();
536 #endif
537  Reference* freed = static_cast<Reference*>(b);
538  freed->next_ = head_;
539  head_ = freed;
540  //--allocated_;
541  }
542  else
543  {
544  std::cerr<< "Tried to free null pointer! "<<b<<std::endl;
545  throw std::bad_alloc();
546  }
547  }
548 
549  template<class T, std::size_t S>
550  inline void* Pool<T,S>::allocate()
551  {
552  if(!head_)
553  grow();
554 
555  Reference* p = head_;
556  head_ = p->next_;
557  //++allocated_;
558  return p;
559  }
560 
561  template<class T, std::size_t s>
563  { }
564 
565  template<class T, std::size_t s>
566  inline typename PoolAllocator<T,s>::pointer
568  {
569  if(n==1)
570  return static_cast<T*>(memoryPool_.allocate());
571  else
572  throw std::bad_alloc();
573  }
574 
575  template<class T, std::size_t s>
576  inline void PoolAllocator<T,s>::deallocate(pointer p, std::size_t n)
577  {
578  for(size_t i=0; i<n; i++)
579  memoryPool_.free(p++);
580  }
581 
582  template<class T, std::size_t s>
584  {
585  ::new (static_cast<void*>(p))T(value);
586  }
587 
588  template<class T, std::size_t s>
590  {
591  p->~T();
592  }
593 
595 }
596 #endif
This file implements a template class to determine alignment requirements of types at compile time.
An allocator managing a pool of objects for reuse.
Definition: poolallocator.hh:248
Pool< T, size > PoolType
The type of the memory pool we use.
Definition: poolallocator.hh:377
const_pointer address(const_reference x) const
Convert a reference to a pointer.
Definition: poolallocator.hh:360
int max_size() const
Not correctly implemented, yet!
Definition: poolallocator.hh:365
const T & const_reference
The constant reference type.
Definition: poolallocator.hh:284
std::size_t size_type
The size type.
Definition: poolallocator.hh:289
T value_type
Type of the values we construct and allocate.
Definition: poolallocator.hh:255
@ size
The number of objects to fit into one memory chunk allocated.
Definition: poolallocator.hh:263
T & reference
The reference type.
Definition: poolallocator.hh:279
PoolAllocator(const PoolAllocator &)
Copy constructor that does not copy the memory pool.
Definition: poolallocator.hh:312
const T * const_pointer
The constant pointer type.
Definition: poolallocator.hh:274
pointer address(reference x) const
Convert a reference to a pointer.
Definition: poolallocator.hh:354
T * pointer
The pointer type.
Definition: poolallocator.hh:269
PoolAllocator(const PoolAllocator< U, u > &)
Copy Constructor that does not copy the memory pool.
Definition: poolallocator.hh:305
std::ptrdiff_t difference_type
The difference_type.
Definition: poolallocator.hh:294
A memory pool of objects.
Definition: poolallocator.hh:89
@ elements
The number of element each chunk can hold.
Definition: poolallocator.hh:153
@ chunkSize
The size of each chunk memory chunk.
Definition: poolallocator.hh:146
@ unionSize
The size of a union of Reference and MemberType.
Definition: poolallocator.hh:113
@ alignment
The alignment that suits both the MemberType and the Reference (i.e. their least common multiple).
Definition: poolallocator.hh:127
@ size
Size requirement. At least one object has to stored.
Definition: poolallocator.hh:120
@ alignedSize
The aligned size of the type.
Definition: poolallocator.hh:135
T MemberType
The type of object we allocate memory for.
Definition: poolallocator.hh:107
void construct(pointer p, const_reference value)
Construct an object.
Definition: poolallocator.hh:583
void free(void *o)
Free an object.
Definition: poolallocator.hh:523
~Pool()
Destructor.
Definition: poolallocator.hh:468
void * allocate()
Get a new or recycled object.
Definition: poolallocator.hh:550
void print(std::ostream &os)
Print elements in pool for debugging.
Definition: poolallocator.hh:488
pointer allocate(std::size_t n, const_pointer hint=0)
Allocates objects.
Definition: poolallocator.hh:567
Pool()
Constructor.
Definition: poolallocator.hh:454
void deallocate(pointer p, std::size_t n)
Free objects.
Definition: poolallocator.hh:576
void destroy(pointer p)
Destroy an object without freeing memory.
Definition: poolallocator.hh:589
PoolAllocator()
Constructor.
Definition: poolallocator.hh:562
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:252
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:230
Statically compute the least common multiple of two integers.
Dune namespace.
Definition: alignment.hh:10
Calculates the alignment requirement of a type.
Definition: alignment.hh:96
Calculate the least common multiple of two numbers.
Definition: lcm.hh:30
Rebind the allocator to another type.
Definition: poolallocator.hh:372
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.80.0 (May 14, 22:30, 2024)