dune-common  2.2.0
poolallocator.hh
Go to the documentation of this file.
00001 // -*- tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
00002 // vi: set et ts=8 sw=2 sts=2:
00003 // $Id: poolallocator.hh 6785 2012-05-31 22:07:47Z sander $
00004 #ifndef DUNE_COMMON_POOLALLOCATOR_HH
00005 #define DUNE_COMMON_POOLALLOCATOR_HH
00006 
00011 #include"alignment.hh"
00012 #include"static_assert.hh"
00013 #include"lcm.hh"
00014 #include<typeinfo>
00015 #include<iostream>
00016 #include<cassert>
00017 #include<new>
00018 
00019 //forward declarations.
00020 
00021 // we need to know the test function to declare it friend
00022 template<std::size_t size, typename T>
00023 struct testPoolMain;
00024 
00025 namespace Dune
00026 {
00027   
00028 template<typename T, std::size_t s>
00029 class Pool;
00030 
00031 template<typename T, std::size_t s>
00032 class PoolAllocator;
00033 
00034 }
00035 
00036 namespace std
00037 {
00038   /*
00039   template<class T, std::size_t S>
00040   inline ostream& operator<<(ostream& os, Dune::Pool<T,S>& pool)
00041   {
00042     os<<"pool="<<&pool<<" allocated_="<<pool.allocated_;
00043     return os;
00044   }
00045   
00046   template<class T, std::size_t S>
00047   inline ostream& operator<<(ostream& os, Dune::PoolAllocator<T,S>& pool)
00048   {
00049     os<<pool.memoryPool_<<std::endl;
00050     return os;
00051   }
00052   */
00053 }
00054 
00055 
00056 namespace Dune
00057 {  
00088   template<class T, std::size_t s>
00089   class Pool
00090   {
00091     // make the test function friend
00092     friend struct ::testPoolMain<s,T>;
00093     
00094     //friend std::ostream& std::operator<<<>(std::ostream&,Pool<T,s>&);
00095     template< class, std::size_t > friend class PoolAllocator;
00096 
00097   private:
00098     
00100     struct Reference
00101     {
00102       Reference *next_;
00103     };
00104 
00105   public:
00106 
00108     typedef T MemberType;
00109     enum 
00110     {
00114       unionSize = ((sizeof(MemberType) < sizeof(Reference)) ? 
00115         sizeof(Reference) : sizeof(MemberType)),
00116       
00121       size = ((sizeof(MemberType) <= s && sizeof(Reference) <= s)? 
00122         s : unionSize),
00123       
00128       alignment = Lcm<AlignmentOf<MemberType>::value,AlignmentOf<Reference>::value>::value,
00129       
00136       alignedSize = ((unionSize % alignment == 0) ?
00137         unionSize : 
00138         ((unionSize / alignment + 1) * alignment)),
00139       
00147       chunkSize = ((size % alignment == 0)? 
00148         size : ((size / alignment + 1)* alignment)) 
00149       + alignment - 1,
00150       
00154       elements = ((chunkSize - alignment + 1)/ alignedSize)
00155     };
00156     
00157   private:
00159     struct Chunk
00160     {
00161 
00162       //friend int testPool<s,T>();
00163 
00165       char chunk_[chunkSize];
00166 
00171       char* memory_;
00172       
00174       Chunk *next_;
00175       
00179       Chunk()
00180       {
00181         // Make sure the alignment is correct!
00182         // long long should be 64bit safe!
00183         unsigned long long lmemory = reinterpret_cast<unsigned long long>(chunk_);
00184         if(lmemory % alignment != 0)
00185           lmemory = (lmemory / alignment + 1)
00186             * alignment;
00187         
00188         memory_ = reinterpret_cast<char *>(lmemory);
00189       }
00190     };
00191   
00192   public:
00194     inline Pool();
00196     inline ~Pool();
00201     inline void* allocate();
00206     inline void free(void* o);
00207 
00211     inline void print(std::ostream& os);
00212 
00213   private:
00214   
00215     // Prevent Copying!
00216     Pool(const Pool<MemberType,s>&);
00217 
00218     void operator=(const Pool<MemberType,s>& pool) const;
00220     inline void grow();
00222     Reference *head_;
00224     Chunk *chunks_;
00225     /* @brief The number of currently allocated elements. */
00226     //size_t allocated_;
00227 
00228   };
00229 
00247   template<class T, std::size_t s>
00248   class PoolAllocator
00249   {
00250     //friend std::ostream& std::operator<<<>(std::ostream&,PoolAllocator<T,s>&);
00251     
00252   public:
00256     typedef T value_type;
00257 
00258     enum
00259     {
00264       size=s*sizeof(value_type)
00265     };
00266     
00270     typedef T* pointer;
00271 
00275     typedef const T* const_pointer;
00276 
00280     typedef T& reference;
00281 
00285     typedef const T& const_reference;
00286 
00290     typedef std::size_t size_type;
00291     
00295     typedef std::ptrdiff_t difference_type;
00296     
00300     inline PoolAllocator();
00301 
00305     template<typename U, std::size_t u>
00306     inline PoolAllocator(const PoolAllocator<U,u>&)
00307     {}
00308     
00315     inline pointer allocate(std::size_t n, const_pointer hint=0);
00316     
00324     inline void deallocate(pointer p, std::size_t n);
00325 
00331     inline void construct(pointer p, const_reference value);
00332 
00337     inline void destroy(pointer p);
00338 
00342     inline pointer  address(reference x) const { return &x; }
00343 
00344     
00348     inline const_pointer address(const_reference x) const { return &x; }
00349 
00353     inline int max_size() const throw(){ return 1;}
00354     
00358     template<class U>
00359     struct rebind
00360     {
00361       typedef PoolAllocator<U,s> other;
00362     };
00363 
00365     typedef Pool<T,size> PoolType;
00366 
00367   private:
00371     static PoolType memoryPool_;
00372   };
00373 
00374   // specialization for void
00375   template <std::size_t s> 
00376   class PoolAllocator<void,s> 
00377   {
00378   public:
00379     typedef void*       pointer;
00380     typedef const void* const_pointer;
00381     // reference to void members are impossible.
00382     typedef void value_type;
00383     template <class U> struct rebind 
00384     { 
00385       typedef PoolAllocator<U,s> other; 
00386     };
00387 
00388     template<typename T, std::size_t t>
00389     PoolAllocator(const PoolAllocator<T,t>&)
00390     {}
00391     
00392   };
00393 
00394 
00395   template<typename T1, std::size_t t1, typename T2, std::size_t t2>
00396   bool operator==(const PoolAllocator<T1,t1>&, const PoolAllocator<T2,t2>&)
00397   {
00398     return false;
00399   }
00400   
00401 
00402   template<typename T1, std::size_t t1, typename T2, std::size_t t2>
00403   bool operator!=(const PoolAllocator<T1,t1>&, const PoolAllocator<T2,t2>&)
00404   {
00405     return true;
00406   }
00407 
00408   template<typename T, std::size_t t1, std::size_t t2>
00409   bool operator==(const PoolAllocator<T,t1>&, const PoolAllocator<T,t2>&)
00410   {
00411     return Pool<T,t1>::chunkSize == Pool<T,t2>::chunkSize;
00412   }
00413   
00414 
00415   template<typename T, std::size_t t1, std::size_t t2>
00416   bool operator!=(const PoolAllocator<T,t1>&, const PoolAllocator<T,t2>&)
00417   {
00418     return Pool<T,t1>::chunkSize != Pool<T,t2>::chunkSize;
00419   }
00420 
00421 
00422   template<typename T, std::size_t t1, std::size_t t2>
00423   bool operator==(const PoolAllocator<T,t1>&, const PoolAllocator<void,t2>&)
00424   {
00425     return false;
00426   }
00427   
00428 
00429   template<typename T, std::size_t t1, std::size_t t2>
00430   bool operator!=(const PoolAllocator<T,t1>&, const PoolAllocator<void,t2>&)
00431   {
00432     return true;
00433   }
00434 
00435   template<typename T, std::size_t t1, std::size_t t2>
00436   bool operator==(const PoolAllocator<void,t1>&, const PoolAllocator<T,t2>&)
00437   {
00438     return false;
00439   }
00440   
00441 
00442   template<typename T, std::size_t t1, std::size_t t2>
00443   bool operator!=(const PoolAllocator<void,t1>&, const PoolAllocator<T,t2>&)
00444   {
00445     return true;
00446   }
00447   template<std::size_t t1, std::size_t t2>
00448   bool operator==(const PoolAllocator<void,t1>&, const PoolAllocator<void,t2>&)
00449   {
00450     return true;
00451   }
00452 
00453   template<std::size_t t1, std::size_t t2>
00454   bool operator!=(const PoolAllocator<void,t1>&, const PoolAllocator<void,t2>&)
00455   {
00456     return false;
00457   }
00458 
00459   template<class T, std::size_t S>
00460   inline Pool<T,S>::Pool()
00461     :head_(0), chunks_(0)//, allocated_(0)
00462   {
00463     dune_static_assert(sizeof(T)<=unionSize, "Library Error: type T is too big");
00464     dune_static_assert(sizeof(Reference)<=unionSize, "Library Error: type of referene is too big");
00465     dune_static_assert(unionSize<=alignedSize, "Library Error: alignedSize too small");
00466     dune_static_assert(sizeof(T)<=chunkSize, "Library Error: chunkSize must be able to hold at least one value");
00467     dune_static_assert(sizeof(Reference)<=chunkSize, "Library Error: chunkSize must be able to hold at least one reference");
00468     dune_static_assert((chunkSize - (alignment - 1)) % alignment == 0, "Library Error: compiler cannot calculate!");
00469     dune_static_assert(elements>=1, "Library Error: we need to hold at least one element!");
00470     dune_static_assert(elements*alignedSize<=chunkSize, "Library Error: aligned elements must fit into chuck!");
00471     /*    std::cout<<"s= "<<S<<" : T: "<<sizeof(T)<<" Reference: "<<sizeof(Reference)<<" union: "<<unionSize<<" alignment: "<<alignment<<
00472           "aligned: "<<alignedSize<<" chunk: "<< chunkSize<<" elements: "<<elements<<std::endl;*/
00473   }
00474   
00475   template<class T, std::size_t S>
00476   inline Pool<T,S>::~Pool()
00477   {
00478     /*
00479     if(allocated_!=0)
00480       std::cerr<<"There are still "<<allocated_<<" allocated elements by the Pool<"<<typeid(T).name()<<","<<S<<"> "
00481                <<static_cast<void*>(this)<<"! This is a memory leak and might result in segfaults"
00482                <<std::endl;
00483     */
00484     // delete the allocated chunks.
00485     Chunk *current=chunks_;
00486     
00487     while(current!=0)
00488     {
00489       Chunk *tmp = current;
00490       current = current->next_;
00491       delete tmp;
00492     }
00493   }
00494 
00495   template<class T, std::size_t S>
00496   inline void Pool<T,S>::print(std::ostream& os)
00497   {
00498     Chunk* current=chunks_;
00499     while(current){
00500       os<<current<<" ";
00501       current=current->next_;
00502     }
00503     os<<current<<" ";
00504   }
00505   
00506   template<class T, std::size_t S>
00507   inline void Pool<T,S>::grow()
00508   {
00509     Chunk *newChunk = new Chunk;
00510     newChunk->next_ = chunks_;
00511     chunks_ = newChunk;
00512     
00513     char* start = chunks_->memory_;
00514     char* last  = &start[elements*alignedSize];
00515     Reference* ref = new (start) (Reference);
00516 
00517     // grow is only called if head==0, 
00518     assert(!head_);
00519 
00520     head_ = ref;
00521       
00522     for(char* element=start+alignedSize; element<last; element=element+alignedSize){
00523       Reference* next = new (element) (Reference);
00524       ref->next_ = next;
00525       ref = next;
00526     }
00527     ref->next_=0;
00528   }
00529 
00530   template<class T, std::size_t S>
00531   inline void Pool<T,S>::free(void* b)
00532   {
00533     if(b){
00534     Reference* freed = static_cast<Reference*>(b);
00535     freed->next_ = head_;
00536     head_ = freed;
00537     //--allocated_;
00538     }else
00539       std::cerr<< "Tried to free null pointer! "<<b<<std::endl;
00540   }
00541 
00542   template<class T, std::size_t S>
00543   inline void* Pool<T,S>::allocate()
00544   {
00545     if(!head_)
00546       grow();
00547       
00548     Reference* p = head_;
00549     head_ = p->next_;
00550     //++allocated_;
00551     return p;
00552   }
00553 
00554   template<class T, std::size_t s> 
00555   typename PoolAllocator<T,s>::PoolType PoolAllocator<T,s>::memoryPool_;
00556 
00557   template<class T, std::size_t s> 
00558   inline PoolAllocator<T,s>::PoolAllocator()
00559   { }
00560 
00561   template<class T, std::size_t s>
00562   inline typename PoolAllocator<T,s>::pointer
00563   PoolAllocator<T,s>::allocate(std::size_t n, const_pointer hint)
00564   {
00565     if(n==1)
00566       return static_cast<T*>(memoryPool_.allocate());
00567     else
00568       throw std::bad_alloc();
00569   }
00570 
00571   template<class T, std::size_t s>
00572   inline void PoolAllocator<T,s>::deallocate(pointer p, std::size_t n)
00573   {
00574     for(size_t i=0; i<n; i++)
00575       memoryPool_.free(p++);
00576   }
00577   
00578   template<class T, std::size_t s>
00579   inline void PoolAllocator<T,s>::construct(pointer p, const_reference value)
00580   {
00581     ::new (static_cast<void*>(p)) T(value);
00582   }
00583 
00584   template<class T, std::size_t s>
00585   inline void PoolAllocator<T,s>::destroy(pointer p)
00586   {
00587     p->~T();
00588   }
00589 
00591 }
00592 #endif