Dune Core Modules (2.4.1)

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