Dune Core Modules (2.5.0)

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