00001
00002
00003 #ifndef DUNE_COMMON_POOLALLOCATOR_HH
00004 #define DUNE_COMMON_POOLALLOCATOR_HH
00005
00010 #include "lcm.hh"
00011 #include <typeinfo>
00012 #include <iostream>
00013 #include <cassert>
00014 #include <new>
00015
00016 #ifndef DOXYGEN
00017
00018
00019 template<std::size_t size, typename T>
00020 struct testPoolMain;
00021 #endif
00022
00023 namespace Dune
00024 {
00025
00026 template<typename T, std::size_t s>
00027 class Pool;
00028
00029 template<typename T, std::size_t s>
00030 class PoolAllocator;
00031
00032 }
00033
00034 namespace std
00035 {
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051 }
00052
00053
00054 namespace Dune
00055 {
00086 template<class T, std::size_t s>
00087 class Pool
00088 {
00089
00090 friend struct ::testPoolMain<s,T>;
00091
00092
00093 template< class, std::size_t > friend class PoolAllocator;
00094
00095 private:
00096
00098 struct Reference
00099 {
00100 Reference *next_;
00101 };
00102
00103 public:
00104
00106 typedef T MemberType;
00107 enum
00108 {
00112 unionSize = ((sizeof(MemberType) < sizeof(Reference)) ?
00113 sizeof(Reference) : sizeof(MemberType)),
00114
00119 size = ((sizeof(MemberType) <= s && sizeof(Reference) <= s) ?
00120 s : unionSize),
00121
00126 alignment = Lcm<alignof(MemberType), alignof(Reference)>::value,
00127
00134 alignedSize = ((unionSize % alignment == 0) ?
00135 unionSize :
00136 ((unionSize / alignment + 1) * alignment)),
00137
00145 chunkSize = ((size % alignment == 0) ?
00146 size : ((size / alignment + 1)* alignment))
00147 + alignment - 1,
00148
00152 elements = ((chunkSize - alignment + 1)/ alignedSize)
00153 };
00154
00155 private:
00157 struct Chunk
00158 {
00159
00160
00161
00163 char chunk_[chunkSize];
00164
00169 char* memory_;
00170
00172 Chunk *next_;
00173
00177 Chunk()
00178 {
00179
00180
00181 unsigned long long lmemory = reinterpret_cast<unsigned long long>(chunk_);
00182 if(lmemory % alignment != 0)
00183 lmemory = (lmemory / alignment + 1)
00184 * alignment;
00185
00186 memory_ = reinterpret_cast<char *>(lmemory);
00187 }
00188 };
00189
00190 public:
00192 inline Pool();
00194 inline ~Pool();
00199 inline void* allocate();
00204 inline void free(void* o);
00205
00209 inline void print(std::ostream& os);
00210
00211 private:
00212
00213
00214 Pool(const Pool<MemberType,s>&);
00215
00216 void operator=(const Pool<MemberType,s>& pool) const;
00218 inline void grow();
00220 Reference *head_;
00222 Chunk *chunks_;
00223
00224
00225
00226 };
00227
00245 template<class T, std::size_t s>
00246 class PoolAllocator
00247 {
00248
00249
00250 public:
00254 typedef T value_type;
00255
00256 enum
00257 {
00262 size=s*sizeof(value_type)
00263 };
00264
00268 typedef T* pointer;
00269
00273 typedef const T* const_pointer;
00274
00278 typedef T& reference;
00279
00283 typedef const T& const_reference;
00284
00288 typedef std::size_t size_type;
00289
00293 typedef std::ptrdiff_t difference_type;
00294
00298 inline PoolAllocator();
00299
00303 template<typename U, std::size_t u>
00304 inline PoolAllocator(const PoolAllocator<U,u>&)
00305 {
00306
00307
00308 }
00309
00311 PoolAllocator(const PoolAllocator&)
00312 {
00313
00314
00315
00316
00317
00318
00319 }
00326 inline pointer allocate(std::size_t n, const_pointer hint=0);
00327
00335 inline void deallocate(pointer p, std::size_t n);
00336
00342 inline void construct(pointer p, const_reference value);
00343
00348 inline void destroy(pointer p);
00349
00353 inline pointer address(reference x) const { return &x; }
00354
00355
00359 inline const_pointer address(const_reference x) const { return &x; }
00360
00364 inline int max_size() const throw(){ return 1;}
00365
00369 template<class U>
00370 struct rebind
00371 {
00372 typedef PoolAllocator<U,s> other;
00373 };
00374
00376 typedef Pool<T,size> PoolType;
00377
00378 private:
00382 PoolType memoryPool_;
00383 };
00384
00385
00386 template <std::size_t s>
00387 class PoolAllocator<void,s>
00388 {
00389 public:
00390 typedef void* pointer;
00391 typedef const void* const_pointer;
00392
00393 typedef void value_type;
00394 template <class U> struct rebind
00395 {
00396 typedef PoolAllocator<U,s> other;
00397 };
00398 };
00399
00400
00401 template<typename T1, std::size_t t1, typename T2, std::size_t t2>
00402 bool operator==(const PoolAllocator<T1,t1>&, const PoolAllocator<T2,t2>&)
00403 {
00404 return false;
00405 }
00406
00407
00408 template<typename T1, std::size_t t1, typename T2, std::size_t t2>
00409 bool operator!=(const PoolAllocator<T1,t1>&, const PoolAllocator<T2,t2>&)
00410 {
00411 return true;
00412 }
00413
00414 template<typename T, std::size_t t1, std::size_t t2>
00415 bool operator==(const PoolAllocator<T,t1>& p1, const PoolAllocator<T,t2>& p2)
00416 {
00417 return &p1==&p2;
00418 }
00419
00420
00421 template<typename T, std::size_t t1, std::size_t t2>
00422 bool operator!=(const PoolAllocator<T,t1>& p1, const PoolAllocator<T,t2>& p2)
00423 {
00424 return &p1 != &p2;
00425 }
00426
00427 template<typename T, std::size_t t1, std::size_t t2>
00428 bool operator==(const PoolAllocator<void,t1>&, const PoolAllocator<T,t2>&)
00429 {
00430 return false;
00431 }
00432
00433
00434 template<typename T, std::size_t t1, std::size_t t2>
00435 bool operator!=(const PoolAllocator<void,t1>&, const PoolAllocator<T,t2>&)
00436 {
00437 return true;
00438 }
00439
00440 template<std::size_t t1, std::size_t t2>
00441 bool operator==(const PoolAllocator<void,t1>& p1, const PoolAllocator<void,t2>& p2)
00442 {
00443 return &p1==&p2;
00444 }
00445
00446 template<std::size_t t1, std::size_t t2>
00447 bool operator!=(const PoolAllocator<void,t1>& p1, const PoolAllocator<void,t2>& p2)
00448 {
00449 return &p1!=&p2;
00450 }
00451
00452 template<class T, std::size_t S>
00453 inline Pool<T,S>::Pool()
00454 : head_(0), chunks_(0)
00455 {
00456 static_assert(sizeof(T)<=unionSize, "Library Error: type T is too big");
00457 static_assert(sizeof(Reference)<=unionSize, "Library Error: type of referene is too big");
00458 static_assert(unionSize<=alignedSize, "Library Error: alignedSize too small");
00459 static_assert(sizeof(T)<=chunkSize, "Library Error: chunkSize must be able to hold at least one value");
00460 static_assert(sizeof(Reference)<=chunkSize, "Library Error: chunkSize must be able to hold at least one reference");
00461 static_assert((chunkSize - (alignment - 1)) % alignment == 0, "Library Error: compiler cannot calculate!");
00462 static_assert(elements>=1, "Library Error: we need to hold at least one element!");
00463 static_assert(elements*alignedSize<=chunkSize, "Library Error: aligned elements must fit into chuck!");
00464 }
00465
00466 template<class T, std::size_t S>
00467 inline Pool<T,S>::~Pool()
00468 {
00469
00470
00471
00472
00473
00474
00475
00476 Chunk *current=chunks_;
00477
00478 while(current!=0)
00479 {
00480 Chunk *tmp = current;
00481 current = current->next_;
00482 delete tmp;
00483 }
00484 }
00485
00486 template<class T, std::size_t S>
00487 inline void Pool<T,S>::print(std::ostream& os)
00488 {
00489 Chunk* current=chunks_;
00490 while(current) {
00491 os<<current<<" ";
00492 current=current->next_;
00493 }
00494 os<<current<<" ";
00495 }
00496
00497 template<class T, std::size_t S>
00498 inline void Pool<T,S>::grow()
00499 {
00500 Chunk *newChunk = new Chunk;
00501 newChunk->next_ = chunks_;
00502 chunks_ = newChunk;
00503
00504 char* start = chunks_->memory_;
00505 char* last = &start[elements*alignedSize];
00506 Reference* ref = new (start) (Reference);
00507
00508
00509 assert(!head_);
00510
00511 head_ = ref;
00512
00513 for(char* element=start+alignedSize; element<last; element=element+alignedSize) {
00514 Reference* next = new (element) (Reference);
00515 ref->next_ = next;
00516 ref = next;
00517 }
00518 ref->next_=0;
00519 }
00520
00521 template<class T, std::size_t S>
00522 inline void Pool<T,S>::free(void* b)
00523 {
00524 if(b) {
00525 #ifndef NDEBUG
00526 Chunk* current=chunks_;
00527 while(current) {
00528 if(static_cast<void*>(current->chunk_)<=b &&
00529 static_cast<void*>(current->chunk_+chunkSize)>b)
00530 break;
00531 current=current->next_;
00532 }
00533 if(!current)
00534 throw std::bad_alloc();
00535 #endif
00536 Reference* freed = static_cast<Reference*>(b);
00537 freed->next_ = head_;
00538 head_ = freed;
00539
00540 }
00541 else
00542 {
00543 std::cerr<< "Tried to free null pointer! "<<b<<std::endl;
00544 throw std::bad_alloc();
00545 }
00546 }
00547
00548 template<class T, std::size_t S>
00549 inline void* Pool<T,S>::allocate()
00550 {
00551 if(!head_)
00552 grow();
00553
00554 Reference* p = head_;
00555 head_ = p->next_;
00556
00557 return p;
00558 }
00559
00560 template<class T, std::size_t s>
00561 inline PoolAllocator<T,s>::PoolAllocator()
00562 { }
00563
00564 template<class T, std::size_t s>
00565 inline typename PoolAllocator<T,s>::pointer
00566 PoolAllocator<T,s>::allocate(std::size_t n, const_pointer)
00567 {
00568 if(n==1)
00569 return static_cast<T*>(memoryPool_.allocate());
00570 else
00571 throw std::bad_alloc();
00572 }
00573
00574 template<class T, std::size_t s>
00575 inline void PoolAllocator<T,s>::deallocate(pointer p, std::size_t n)
00576 {
00577 for(size_t i=0; i<n; i++)
00578 memoryPool_.free(p++);
00579 }
00580
00581 template<class T, std::size_t s>
00582 inline void PoolAllocator<T,s>::construct(pointer p, const_reference value)
00583 {
00584 ::new (static_cast<void*>(p))T(value);
00585 }
00586
00587 template<class T, std::size_t s>
00588 inline void PoolAllocator<T,s>::destroy(pointer p)
00589 {
00590 p->~T();
00591 }
00592
00594 }
00595 #endif