dune-common  2.2.1
poolallocator.hh
Go to the documentation of this file.
1 // -*- tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 // vi: set et ts=8 sw=2 sts=2:
3 // $Id: poolallocator.hh 6785 2012-05-31 22:07:47Z sander $
4 #ifndef DUNE_COMMON_POOLALLOCATOR_HH
5 #define DUNE_COMMON_POOLALLOCATOR_HH
6 
11 #include"alignment.hh"
12 #include"static_assert.hh"
13 #include"lcm.hh"
14 #include<typeinfo>
15 #include<iostream>
16 #include<cassert>
17 #include<new>
18 
19 //forward declarations.
20 
21 // we need to know the test function to declare it friend
22 template<std::size_t size, typename T>
23 struct testPoolMain;
24 
25 namespace Dune
26 {
27 
28 template<typename T, std::size_t s>
29 class Pool;
30 
31 template<typename T, std::size_t s>
33 
34 }
35 
36 namespace 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 
56 namespace 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  enum
110  {
114  unionSize = ((sizeof(MemberType) < sizeof(Reference)) ?
115  sizeof(Reference) : sizeof(MemberType)),
116 
121  size = ((sizeof(MemberType) <= s && sizeof(Reference) <= s)?
122  s : unionSize),
123 
129 
136  alignedSize = ((unionSize % alignment == 0) ?
137  unionSize :
138  ((unionSize / alignment + 1) * alignment)),
139 
147  chunkSize = ((size % alignment == 0)?
148  size : ((size / alignment + 1)* alignment))
149  + alignment - 1,
150 
155  };
156 
157  private:
159  struct Chunk
160  {
161 
162  //friend int testPool<s,T>();
163 
165  char chunk_[chunkSize];
166 
171  char* memory_;
172 
174  Chunk *next_;
175 
179  Chunk()
180  {
181  // Make sure the alignment is correct!
182  // long long should be 64bit safe!
183  unsigned long long lmemory = reinterpret_cast<unsigned long long>(chunk_);
184  if(lmemory % alignment != 0)
185  lmemory = (lmemory / alignment + 1)
186  * alignment;
187 
188  memory_ = reinterpret_cast<char *>(lmemory);
189  }
190  };
191 
192  public:
194  inline Pool();
196  inline ~Pool();
201  inline void* allocate();
206  inline void free(void* o);
207 
211  inline void print(std::ostream& os);
212 
213  private:
214 
215  // Prevent Copying!
216  Pool(const Pool<MemberType,s>&);
217 
218  void operator=(const Pool<MemberType,s>& pool) const;
220  inline void grow();
222  Reference *head_;
224  Chunk *chunks_;
225  /* @brief The number of currently allocated elements. */
226  //size_t allocated_;
227 
228  };
229 
247  template<class T, std::size_t s>
248  class PoolAllocator
249  {
250  //friend std::ostream& std::operator<<<>(std::ostream&,PoolAllocator<T,s>&);
251 
252  public:
256  typedef T value_type;
257 
258  enum
259  {
264  size=s*sizeof(value_type)
265  };
266 
270  typedef T* pointer;
271 
275  typedef const T* const_pointer;
276 
280  typedef T& reference;
281 
285  typedef const T& const_reference;
286 
290  typedef std::size_t size_type;
291 
295  typedef std::ptrdiff_t difference_type;
296 
300  inline PoolAllocator();
301 
305  template<typename U, std::size_t u>
307  {}
308 
315  inline pointer allocate(std::size_t n, const_pointer hint=0);
316 
324  inline void deallocate(pointer p, std::size_t n);
325 
331  inline void construct(pointer p, const_reference value);
332 
337  inline void destroy(pointer p);
338 
342  inline pointer address(reference x) const { return &x; }
343 
344 
348  inline const_pointer address(const_reference x) const { return &x; }
349 
353  inline int max_size() const throw(){ return 1;}
354 
358  template<class U>
359  struct rebind
360  {
362  };
363 
366 
367  private:
371  static PoolType memoryPool_;
372  };
373 
374  // specialization for void
375  template <std::size_t s>
376  class PoolAllocator<void,s>
377  {
378  public:
379  typedef void* pointer;
380  typedef const void* const_pointer;
381  // reference to void members are impossible.
382  typedef void value_type;
383  template <class U> struct rebind
384  {
386  };
387 
388  template<typename T, std::size_t t>
390  {}
391 
392  };
393 
394 
395  template<typename T1, std::size_t t1, typename T2, std::size_t t2>
397  {
398  return false;
399  }
400 
401 
402  template<typename T1, std::size_t t1, typename T2, std::size_t t2>
404  {
405  return true;
406  }
407 
408  template<typename T, std::size_t t1, std::size_t t2>
410  {
412  }
413 
414 
415  template<typename T, std::size_t t1, std::size_t t2>
417  {
419  }
420 
421 
422  template<typename T, std::size_t t1, std::size_t t2>
424  {
425  return false;
426  }
427 
428 
429  template<typename T, std::size_t t1, std::size_t t2>
431  {
432  return true;
433  }
434 
435  template<typename T, std::size_t t1, std::size_t t2>
437  {
438  return false;
439  }
440 
441 
442  template<typename T, std::size_t t1, std::size_t t2>
444  {
445  return true;
446  }
447  template<std::size_t t1, std::size_t t2>
449  {
450  return true;
451  }
452 
453  template<std::size_t t1, std::size_t t2>
455  {
456  return false;
457  }
458 
459  template<class T, std::size_t S>
461  :head_(0), chunks_(0)//, allocated_(0)
462  {
463  dune_static_assert(sizeof(T)<=unionSize, "Library Error: type T is too big");
464  dune_static_assert(sizeof(Reference)<=unionSize, "Library Error: type of referene is too big");
465  dune_static_assert(unionSize<=alignedSize, "Library Error: alignedSize too small");
466  dune_static_assert(sizeof(T)<=chunkSize, "Library Error: chunkSize must be able to hold at least one value");
467  dune_static_assert(sizeof(Reference)<=chunkSize, "Library Error: chunkSize must be able to hold at least one reference");
468  dune_static_assert((chunkSize - (alignment - 1)) % alignment == 0, "Library Error: compiler cannot calculate!");
469  dune_static_assert(elements>=1, "Library Error: we need to hold at least one element!");
470  dune_static_assert(elements*alignedSize<=chunkSize, "Library Error: aligned elements must fit into chuck!");
471  /* std::cout<<"s= "<<S<<" : T: "<<sizeof(T)<<" Reference: "<<sizeof(Reference)<<" union: "<<unionSize<<" alignment: "<<alignment<<
472  "aligned: "<<alignedSize<<" chunk: "<< chunkSize<<" elements: "<<elements<<std::endl;*/
473  }
474 
475  template<class T, std::size_t S>
477  {
478  /*
479  if(allocated_!=0)
480  std::cerr<<"There are still "<<allocated_<<" allocated elements by the Pool<"<<typeid(T).name()<<","<<S<<"> "
481  <<static_cast<void*>(this)<<"! This is a memory leak and might result in segfaults"
482  <<std::endl;
483  */
484  // delete the allocated chunks.
485  Chunk *current=chunks_;
486 
487  while(current!=0)
488  {
489  Chunk *tmp = current;
490  current = current->next_;
491  delete tmp;
492  }
493  }
494 
495  template<class T, std::size_t S>
496  inline void Pool<T,S>::print(std::ostream& os)
497  {
498  Chunk* current=chunks_;
499  while(current){
500  os<<current<<" ";
501  current=current->next_;
502  }
503  os<<current<<" ";
504  }
505 
506  template<class T, std::size_t S>
507  inline void Pool<T,S>::grow()
508  {
509  Chunk *newChunk = new Chunk;
510  newChunk->next_ = chunks_;
511  chunks_ = newChunk;
512 
513  char* start = chunks_->memory_;
514  char* last = &start[elements*alignedSize];
515  Reference* ref = new (start) (Reference);
516 
517  // grow is only called if head==0,
518  assert(!head_);
519 
520  head_ = ref;
521 
522  for(char* element=start+alignedSize; element<last; element=element+alignedSize){
523  Reference* next = new (element) (Reference);
524  ref->next_ = next;
525  ref = next;
526  }
527  ref->next_=0;
528  }
529 
530  template<class T, std::size_t S>
531  inline void Pool<T,S>::free(void* b)
532  {
533  if(b){
534  Reference* freed = static_cast<Reference*>(b);
535  freed->next_ = head_;
536  head_ = freed;
537  //--allocated_;
538  }else
539  std::cerr<< "Tried to free null pointer! "<<b<<std::endl;
540  }
541 
542  template<class T, std::size_t S>
543  inline void* Pool<T,S>::allocate()
544  {
545  if(!head_)
546  grow();
547 
548  Reference* p = head_;
549  head_ = p->next_;
550  //++allocated_;
551  return p;
552  }
553 
554  template<class T, std::size_t s>
556 
557  template<class T, std::size_t s>
559  { }
560 
561  template<class T, std::size_t s>
562  inline typename PoolAllocator<T,s>::pointer
564  {
565  if(n==1)
566  return static_cast<T*>(memoryPool_.allocate());
567  else
568  throw std::bad_alloc();
569  }
570 
571  template<class T, std::size_t s>
572  inline void PoolAllocator<T,s>::deallocate(pointer p, std::size_t n)
573  {
574  for(size_t i=0; i<n; i++)
575  memoryPool_.free(p++);
576  }
577 
578  template<class T, std::size_t s>
580  {
581  ::new (static_cast<void*>(p)) T(value);
582  }
583 
584  template<class T, std::size_t s>
586  {
587  p->~T();
588  }
589 
591 }
592 #endif