dune-fem  2.8-git
dynamicarray.hh
Go to the documentation of this file.
1 #ifndef DUNE_FEM_DYNAMICARRAY_HH
2 #define DUNE_FEM_DYNAMICARRAY_HH
3 
4 #include <algorithm>
5 #include <cassert>
6 #include <cmath>
7 #include <cstdlib>
8 #include <cstring>
9 #include <iostream>
10 #include <memory>
11 #include <type_traits>
12 
13 #include <dune/common/densevector.hh>
14 #include <dune/common/ftraits.hh>
16 
17 namespace Dune
18 {
19 
20  namespace Fem
21  {
22  // forward declaration
23  template< class K > class StaticArray;
24 
26  template <typename T>
28  : public std::allocator< T >
29  {
30  typedef std::allocator< T > BaseType;
31  public:
32 #if __cplusplus <= 201703L
33  typedef typename BaseType :: pointer pointer ;
34 #else
35  typedef T* pointer;
36 #endif
37  typedef typename BaseType :: size_type size_type;
38 
40  {
41  return new T[ n ];
42  }
43 
45  {
46  delete [] p;
47  }
48 
49  pointer reallocate ( pointer oldMem, size_type oldSize, size_type n )
50  {
51  assert(oldMem);
52  pointer p = allocate( n );
53  const size_type copySize = std::min( oldSize, n );
54  std::copy( oldMem, oldMem+copySize, p );
55  deallocate( oldMem, oldSize );
56  return p;
57  }
58  };
59 
62  template <typename T>
63  class PODArrayAllocator : public std::allocator< T >
64  {
65  static_assert( Std::is_pod< T > :: value, "T is not POD" );
66  typedef std::allocator< T > BaseType;
67  public:
68  PODArrayAllocator() = default;
69 
70 #if __cplusplus <= 201703L
71  typedef typename BaseType :: pointer pointer ;
72 #else
73  typedef T* pointer;
74 #endif
75  typedef typename BaseType :: size_type size_type;
76  typedef typename BaseType :: value_type value_type;
77 
80  {
81  pointer p = static_cast< pointer > (std::malloc(n * sizeof(value_type)));
82  assert(p);
83  return p;
84  }
85 
88  {
89  assert(p);
90  std::free(p);
91  }
92 
95  {
96  assert(oldMem);
97  pointer p = static_cast< pointer > (std::realloc(oldMem , n*sizeof(value_type)));
98  assert(p);
99  return p;
100  }
101  };
102 
103  template <class T, class AllocatorType = typename std::conditional< Std::is_pod< T > :: value,
104  PODArrayAllocator< T >,
105  StandardArrayAllocator< T > > :: type >
106  class DynamicArray;
107 
108  } // end namespace Fem
109 
110  // specialization of DenseMatVecTraits for StaticArray
111  template< class K >
112  struct DenseMatVecTraits< Fem::StaticArray< K > >
113  {
115  typedef K* container_type;
116  typedef K value_type;
117  typedef std::size_t size_type;
118  };
119 
120  template< class K >
121  struct FieldTraits< Fem::StaticArray< K > >
122  {
123  typedef typename FieldTraits< K >::field_type field_type;
124  typedef typename FieldTraits< K >::real_type real_type;
125  };
126 
127  // specialization of DenseMatVecTraits for DynamicArray
128  template< class K >
129  struct DenseMatVecTraits< Fem::DynamicArray< K > > : public DenseMatVecTraits< Fem::StaticArray< K > >
130  {
131  };
132 
133  template< class K >
134  struct FieldTraits< Fem::DynamicArray< K > > : public FieldTraits< Fem::StaticArray< K > >
135  {
136  };
137 
138  namespace Fem
139  {
140 
141 
146  template <class T>
147  class StaticArray : public DenseVector< StaticArray< T > >
148  {
149  typedef StaticArray< T > ThisType;
150  typedef DenseVector< ThisType > BaseType;
151 
152  public:
153  typedef typename BaseType::size_type size_type;
154 
155  typedef typename BaseType::value_type value_type;
157 
158  typedef typename DenseMatVecTraits< ThisType >::container_type DofStorageType;
159 
160  StaticArray(const ThisType&) = delete;
161 
163  explicit StaticArray(size_type size, const value_type* vec)
164  : vec_( const_cast< DofStorageType > (vec) )
165  , size_(size)
166  {
167  }
168 
170  size_type size () const
171  {
172  return size_;
173  }
174 
177  {
178  assert( i < size_ );
179  return vec_[i];
180  }
181 
184  {
185  assert( i < size_ );
186  return vec_[i];
187  }
188 
191  {
192  assert(org.size_ >= size() );
193  assert( ( size_ > 0 ) ? vec_ != nullptr : true );
194  std::copy(org.vec_, org.vec_ + size_, vec_ );
195  return *this;
196  }
197 
199  void clear ()
200  {
201  std::fill( vec_, vec_+size_, value_type(0) );
202  }
203 
205  void memmove(size_type length, size_type oldStartIdx, size_type newStartIdx)
206  {
207  void * dest = ((void *) (&vec_[newStartIdx]));
208  const void * src = ((const void *) (&vec_[oldStartIdx]));
209  std::memmove(dest, src, length * sizeof(value_type));
210  }
211 
214  bool operator==(const ThisType& other) const
215  {
216  return vec_ == other.vec_;
217  }
218 
221  {
222  return vec_;
223  }
224 
226  const value_type* data() const
227  {
228  return vec_;
229  }
230 
231  protected:
234  };
235 
236 
242  template <class T, class Allocator>
243  class DynamicArray : public StaticArray<T>
244  {
245  public:
246  typedef Allocator AllocatorType;
247  protected:
250 
251  using BaseType :: size_ ;
252  using BaseType :: vec_ ;
253 
254  public:
255  using BaseType :: size ;
256 
257  typedef typename BaseType::size_type size_type;
259 
261  DynamicArray(const ThisType& other)
262  : BaseType(0, nullptr)
263  , memoryFactor_(1.0)
264  , memSize_(0)
265  , allocator_( other.allocator_ )
266  {
267  assign( other );
268  }
269 
272  const value_type& value,
273  AllocatorType allocator = AllocatorType() )
274  : BaseType(size, (size == 0) ? nullptr : allocator.allocate(size) )
275  , memoryFactor_(1.0)
276  , memSize_(size)
277  , allocator_( allocator )
278  {
279  if( size_ > 0 )
280  {
281  std::fill( vec_, vec_+size_, value );
282  }
283  }
284 
287  AllocatorType allocator = AllocatorType() )
288  : BaseType(size, (size == 0) ? nullptr : allocator.allocate(size) )
289  , memoryFactor_(1.0)
290  , memSize_(size)
291  , allocator_( allocator )
292  {
293  }
294 
296  void setMemoryFactor(double memFactor)
297  {
298  memoryFactor_ = memFactor;
299  assert( memoryFactor_ >= 1.0 );
300  }
301 
304  {
305  freeMemory();
306  }
307 
310  {
311  return memSize_;
312  }
313 
315  void assign (const ThisType & org)
316  {
317  memoryFactor_ = org.memoryFactor_;
318  assert( memoryFactor_ >= 1.0 );
319 
320  resize( org.size_ );
321  assert( ( size_ > 0 ) ? vec_ != nullptr : true );
322  std::copy(org.vec_, org.vec_ + size_, vec_ );
323  }
324 
327  {
328  assign( org );
329  return *this;
330  }
331 
334  void resize ( size_type nsize )
335  {
336  // only initialize value if we are not using a POD type
338  }
339 
342  void resize ( size_type nsize, const value_type& value )
343  {
344  doResize( nsize, true, value );
345  }
346 
347  void doResize( size_type nsize, bool initializeNewValues, const value_type& value = value_type() )
348  {
349  // just set size if nsize is smaller than memSize but larger the half of memSize
350  if( (nsize <= memSize_) && (nsize >= (memSize_/2)) )
351  {
352  size_ = nsize;
353  return ;
354  }
355 
356  // if nsize == 0 freeMemory
357  if( nsize == 0 )
358  {
359  freeMemory();
360  return ;
361  }
362 
363  // reserve or shrink to memory + overestimate
364  adjustMemory( nsize, initializeNewValues, value );
365  // set new size
366  size_ = nsize;
367  }
368 
371  void reserve ( size_type mSize )
372  {
373  // check whether we already have the mem size and if just do nothing
374  if( mSize <= memSize_ )
375  {
376  return ;
377  }
378 
379  // adjust memory accordingly
380  adjustMemory( mSize, false );
381  }
382 
385  {
386  return memSize_ * sizeof(value_type) + sizeof(ThisType);
387  }
388 
389  protected:
391  void adjustMemory( size_type mSize, bool initializeNewValues, const value_type& value = value_type() )
392  {
393  assert( memoryFactor_ >= 1.0 );
394  const double overEstimate = memoryFactor_ * mSize;
395  const size_type nMemSize = (size_type) std::ceil( overEstimate );
396  assert( nMemSize >= mSize );
397 
398  if( vec_ == nullptr )
399  {
400  // allocate new memory
401  vec_ = allocator_.allocate( nMemSize );
402  if( initializeNewValues )
403  {
404  std::fill( vec_, vec_+nMemSize, value );
405  }
406  }
407  else
408  {
409  assert( nMemSize > 0 );
410  assert( vec_ );
411 
412  // reallocate memory
413  vec_ = allocator_.reallocate (vec_, memSize_, nMemSize);
414  if( nMemSize > memSize_ && initializeNewValues )
415  {
416  std::fill( vec_+memSize_, vec_+nMemSize, value );
417  }
418  }
419 
420  // set new mem size
421  memSize_ = nMemSize;
422  }
423 
424  // free memory and reset sizes
425  void freeMemory()
426  {
427  if( vec_ != nullptr )
428  {
429  allocator_.deallocate( vec_, memSize_ );
430  vec_ = nullptr;
431  }
432  size_ = 0;
433  memSize_ = 0;
434  }
435 
439  };
440 
441  } // namespace Fem
442 
443 } // namespace Dune
444 #endif // #ifndef DUNE_FEM_DYNAMICARRAY_HH
Definition: bindguard.hh:11
static constexpr T min(T a)
Definition: utility.hh:93
Definition: utility.hh:162
An implementation of DenseVector which uses a C-array of fixed size as storage.
Definition: dynamicarray.hh:148
size_type size() const
return size of array
Definition: dynamicarray.hh:170
ThisType & operator=(const ThisType &org)
copy assignament
Definition: dynamicarray.hh:190
BaseType::size_type size_type
Definition: dynamicarray.hh:153
bool operator==(const ThisType &other) const
Definition: dynamicarray.hh:214
size_type size_
Definition: dynamicarray.hh:233
StaticArray(const ThisType &)=delete
DofStorageType vec_
Definition: dynamicarray.hh:232
value_type & operator[](size_type i)
random access operator
Definition: dynamicarray.hh:176
void clear()
set all entries to 0
Definition: dynamicarray.hh:199
const value_type * data() const
return pointer to data
Definition: dynamicarray.hh:226
value_type * data()
return pointer to data
Definition: dynamicarray.hh:220
DenseMatVecTraits< ThisType >::container_type DofStorageType
Definition: dynamicarray.hh:158
StaticArray(size_type size, const value_type *vec)
create array of length size and store vec as pointer to memory
Definition: dynamicarray.hh:163
void memmove(size_type length, size_type oldStartIdx, size_type newStartIdx)
move memory from old to new destination
Definition: dynamicarray.hh:205
BaseType::value_type value_type
Definition: dynamicarray.hh:155
value_type FieldType
Definition: dynamicarray.hh:156
oriented to the STL Allocator funtionality
Definition: dynamicarray.hh:29
pointer reallocate(pointer oldMem, size_type oldSize, size_type n)
Definition: dynamicarray.hh:49
BaseType ::size_type size_type
Definition: dynamicarray.hh:37
pointer allocate(size_type n)
Definition: dynamicarray.hh:39
void deallocate(pointer p, size_type n)
Definition: dynamicarray.hh:44
BaseType ::pointer pointer
Definition: dynamicarray.hh:33
Definition: dynamicarray.hh:64
void deallocate(pointer p, size_type n)
release memory previously allocated with malloc member
Definition: dynamicarray.hh:87
BaseType ::size_type size_type
Definition: dynamicarray.hh:75
pointer reallocate(pointer oldMem, size_type oldSize, size_type n)
allocate array of nmemb objects of type T
Definition: dynamicarray.hh:94
BaseType ::value_type value_type
Definition: dynamicarray.hh:76
BaseType ::pointer pointer
Definition: dynamicarray.hh:71
pointer allocate(size_type n)
allocate array of nmemb objects of type T
Definition: dynamicarray.hh:79
An implementation of DenseVector which uses a C-array of dynamic size as storage.
Definition: dynamicarray.hh:244
void setMemoryFactor(double memFactor)
set memory factor
Definition: dynamicarray.hh:296
void adjustMemory(size_type mSize, bool initializeNewValues, const value_type &value=value_type())
adjust the memory
Definition: dynamicarray.hh:391
void assign(const ThisType &org)
assign arrays
Definition: dynamicarray.hh:315
void reserve(size_type mSize)
Definition: dynamicarray.hh:371
size_type capacity() const
return number of total enties of array
Definition: dynamicarray.hh:309
AllocatorType allocator_
Definition: dynamicarray.hh:438
BaseType::value_type value_type
Definition: dynamicarray.hh:258
DynamicArray< T, AllocatorType > ThisType
Definition: dynamicarray.hh:248
void resize(size_type nsize)
Definition: dynamicarray.hh:334
void resize(size_type nsize, const value_type &value)
Definition: dynamicarray.hh:342
void freeMemory()
Definition: dynamicarray.hh:425
double memoryFactor_
Definition: dynamicarray.hh:436
DynamicArray(const ThisType &other)
copy constructor
Definition: dynamicarray.hh:261
DynamicArray(size_type size=0, AllocatorType allocator=AllocatorType())
create array of length size without initializing the values
Definition: dynamicarray.hh:286
~DynamicArray()
destructor
Definition: dynamicarray.hh:303
size_type usedMemorySize() const
return size of vector in bytes
Definition: dynamicarray.hh:384
BaseType::size_type size_type
Definition: dynamicarray.hh:257
void doResize(size_type nsize, bool initializeNewValues, const value_type &value=value_type())
Definition: dynamicarray.hh:347
DynamicArray(size_type size, const value_type &value, AllocatorType allocator=AllocatorType())
create array of length size with initialized values
Definition: dynamicarray.hh:271
StaticArray< T > BaseType
Definition: dynamicarray.hh:249
ThisType & operator=(const ThisType &org)
assign arrays
Definition: dynamicarray.hh:326
Allocator AllocatorType
Definition: dynamicarray.hh:246
size_type memSize_
Definition: dynamicarray.hh:437
K * container_type
Definition: dynamicarray.hh:115
std::size_t size_type
Definition: dynamicarray.hh:117
Fem::StaticArray< K > derived_type
Definition: dynamicarray.hh:114
K value_type
Definition: dynamicarray.hh:116
FieldTraits< K >::real_type real_type
Definition: dynamicarray.hh:124
FieldTraits< K >::field_type field_type
Definition: dynamicarray.hh:123