dune-common
2.2.0
|
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