GetFEM  5.4.3
dal_basic.h
Go to the documentation of this file.
1 /* -*- c++ -*- (enables emacs c++ mode) */
2 /*===========================================================================
3 
4  Copyright (C) 1995-2020 Yves Renard
5 
6  This file is a part of GetFEM
7 
8  GetFEM is free software; you can redistribute it and/or modify it
9  under the terms of the GNU Lesser General Public License as published
10  by the Free Software Foundation; either version 3 of the License, or
11  (at your option) any later version along with the GCC Runtime Library
12  Exception either version 3.1 or (at your option) any later version.
13  This program is distributed in the hope that it will be useful, but
14  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
16  License and GCC Runtime Library Exception for more details.
17  You should have received a copy of the GNU Lesser General Public License
18  along with this program; if not, write to the Free Software Foundation,
19  Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
20 
21  As a special exception, you may use this file as it is a part of a free
22  software library without restriction. Specifically, if other files
23  instantiate templates or use macros or inline functions from this file,
24  or you compile this file and link it with other files to produce an
25  executable, this file does not by itself cause the resulting executable
26  to be covered by the GNU Lesser General Public License. This exception
27  does not however invalidate any other reasons why the executable file
28  might be covered by the GNU Lesser General Public License.
29 
30 ===========================================================================*/
31 
32 /**@file dal_basic.h
33  @author Yves Renard <Yves.Renard@insa-lyon.fr>
34  @date June 01, 1995.
35  @brief Dynamic array class.
36 */
37 #ifndef DAL_BASIC_H__
38 #define DAL_BASIC_H__
39 
40 #include <vector>
41 #include "dal_config.h"
42 #include "getfem_omp.h"
43 
44 /// Dynamic Array Library
45 namespace dal
46 {
47  template<class T, unsigned char pks = 5> class dynamic_array;
48 
49  /// Iterator class for dynamic array.
50  template<class T, unsigned char pks> struct dna_iterator {
51  typedef T value_type;
52  typedef value_type* pointer;
53  typedef value_type& reference;
54  typedef size_t size_type;
55  typedef ptrdiff_t difference_type;
56  typedef std::random_access_iterator_tag iterator_category;
57 
58 # define DNAMPKS__ ((size_type(1) << pks) - 1)
59  dynamic_array<T,pks> *p;
60  size_type in;
61  pointer pT;
62 
63  dna_iterator(void) {}
64  dna_iterator(dynamic_array<T,pks> &da, size_type ii)
65  { p = &da; in = ii; pT = p->pt_to(in); }
66 
67  inline size_type index(void) const { return in; }
68  /// next element.
69  dna_iterator operator ++(int) {
70  dna_iterator tmp = *this;
71  if ((++in)&DNAMPKS__) pT++; else pT=p->pt_to(in); return tmp;
72  }
73  /// previous element.
74  dna_iterator operator --(int) {
75  dna_iterator tmp = *this;
76  if ((in--)&DNAMPKS__) pT--; else pT=p->pt_to(in); return tmp;
77  }
78  /// next element.
79  dna_iterator &operator ++()
80  { if ((++in)&DNAMPKS__) pT++; else pT=p->pt_to(in); return *this; }
81  /// previous element.
82  dna_iterator &operator --()
83  { if ((in--)&DNAMPKS__) pT--; else pT=p->pt_to(in); return *this; }
84  /// go i elements forward.
85  dna_iterator &operator +=(difference_type i)
86  { in += i; pT=p->pt_to(in); return *this; }
87  /// go i elements backward.
88  dna_iterator &operator -=(difference_type i)
89  { in -= i; pT=p->pt_to(in); return *this; }
90  /// gives an iterator pointing i elements forward.
91  dna_iterator operator +(difference_type i) const
92  { dna_iterator it = *this; return (it += i); }
93  /// gives an iterator pointing i elements backward.
94  dna_iterator operator -(difference_type i) const
95  { dna_iterator it = *this; return (it -= i); }
96  /// Gives the difference, in term of elements between two iterators.
97  difference_type operator -(const dna_iterator &i) const
98  { return difference_type(in - i.in); }
99 
100  reference operator *() const { return (*pT); }
101  pointer operator ->() const { return pT; }
102  reference operator [](size_type ii) const { return (*p)[in+ii]; }
103 
104  bool operator ==(const dna_iterator &i) const { return (i.in==in);}
105  bool operator !=(const dna_iterator &i) const { return (i.in!=in);}
106  bool operator < (const dna_iterator &i) const { return ( in<i.in);}
107  bool operator >=(const dna_iterator &i) const { return ( in>=i.in);}
108  bool operator > (const dna_iterator &i) const { return ( in>i.in);}
109  };
110 
111  /// Constant iterator class for dynamic array.
112  template<class T, unsigned char pks> struct dna_const_iterator {
113  typedef T value_type;
114  typedef const value_type* pointer;
115  typedef const value_type& reference;
116  typedef size_t size_type;
117  typedef ptrdiff_t difference_type;
118  typedef std::random_access_iterator_tag iterator_category;
119 
120 # define DNAMPKS__ ((size_type(1) << pks) - 1)
121  const dynamic_array<T,pks> *p;
122  size_type in;
123  pointer pT;
124 
125  dna_const_iterator(void) {}
126  dna_const_iterator(const dynamic_array<T,pks> &da, size_type ii)
127  { p = &da; in = ii; pT = p->pt_to(in); }
128  dna_const_iterator(const dna_iterator<T, pks> &it)
129  : p(it.p), in(it.in), pT(it.pT) {}
130 
131  inline size_type index(void) const { return in; }
132  dna_const_iterator operator ++(int) {
133  dna_const_iterator tmp = *this;
134  if ((++in)&DNAMPKS__) pT++; else pT=p->pt_to(in); return tmp;
135  }
136  dna_const_iterator operator --(int) {
137  dna_const_iterator tmp = *this;
138  if ((in--)&DNAMPKS__) pT--; else pT=p->pt_to(in); return tmp;
139  }
140  dna_const_iterator &operator ++()
141  { if ((++in)&DNAMPKS__) pT++; else pT=p->pt_to(in); return *this; }
142  dna_const_iterator &operator --()
143  { if ((in--)&DNAMPKS__) pT--; else pT=p->pt_to(in); return *this; }
144  dna_const_iterator &operator +=(difference_type i)
145  { in += i; pT=p->pt_to(in); return *this; }
146  dna_const_iterator &operator -=(difference_type i)
147  { in -= i; pT=p->pt_to(in); return *this; }
148  dna_const_iterator operator +(difference_type i) const
149  { dna_const_iterator it = *this; return (it += i); }
150  dna_const_iterator operator -(difference_type i) const
151  { dna_const_iterator it = *this; return (it -= i); }
152  difference_type operator -(const dna_const_iterator &i) const
153  { return difference_type(in - i.in); }
154 
155  reference operator *() const { return (*pT); }
156  pointer operator ->() const { return pT; }
157  reference operator [](size_type ii) const { return (*p)[in+ii]; }
158 
159  bool operator ==(const dna_const_iterator &i) const
160  { return (i.in == in); }
161  bool operator !=(const dna_const_iterator &i) const
162  { return (i.in != in); }
163  bool operator < (const dna_const_iterator &i) const
164  { return (in < i.in); }
165  bool operator >=(const dna_const_iterator &i) const
166  { return (i.in >= in); }
167  bool operator > (const dna_const_iterator &i) const
168  { return (in > i.in); }
169  };
170 
171  /** Dynamic Array. Defines the basic container of the library which is
172  * dal::dynamic_array<T, pks>. This container is virtually an
173  * infinite array of element of type T. When a random acces tab[i] is
174  * called, a control is made on i and an allocation is made if
175  * needed. The allocation is made by blocks of n elements, where
176  * @f$n = 2^{pks}@f$. @f$pks@f$ is an optional parameter assumed to be 5.
177  * The structure of this container is similar to the one of std::deque<T>
178  * but with a faster random access.
179  *
180  *
181  * <h3>Example of code</h3>
182  * If T is any type (with or without trivial constructor/destructor,
183  * and with constructor T(0) and T(1)), the
184  * following code is valid:
185  * @code
186  * #include<dal_basic.h>
187  * dal::dynamic_array<T> tab;
188  * tab[50] = T(0); // 51 elements in tab.
189  * std::fill(tab.begin(), tab.end(), T(0)); // 51 elements initialized
190  * dal::dynamic_array<T>::iterator it = tab.begin();
191  * dal::dynamic_array<T>::iterator ite = it + 50;
192  * for( ; it != ite; ++it)
193  * { *it = T(1); } // only the 50 first elements are changed.
194  * @endcode
195  */
196  template<class T, unsigned char pks> class dynamic_array {
197  public :
198 
199  typedef T value_type;
200  typedef value_type* pointer;
201  typedef const value_type* const_pointer;
202  typedef value_type& reference;
203  typedef const value_type& const_reference;
204  typedef size_t size_type;
205  typedef ptrdiff_t difference_type;
206  typedef unsigned char pack_size_type;
207  typedef std::vector<std::unique_ptr<T[]>> pointer_array;
208  typedef dna_iterator<T, pks> iterator;
209  typedef dna_const_iterator<T, pks> const_iterator;
210  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
211  typedef std::reverse_iterator<iterator> reverse_iterator;
212 
213  protected :
214 
215 # define DNAMPKS__ ((size_type(1) << pks) - 1)
216  pointer_array array;
217  pack_size_type ppks; /* size of pointer packs (2^ppks). */
218  size_type m_ppks; /* = (2^ppks) - 1. */
219  size_type last_ind; /* allocated = 0 .. last_ind-1. */
220  size_type last_accessed; /* valid = 0 .. last_accessed-1. */
221 
222  public :
223 
224  /// Number of allocated elements.
225  size_type size(void) const { return last_accessed; }
226  size_type capacity(void) const { return last_ind; }
227  size_type max_size(void) const { return (size_type(-1)) / 2; }
228  /// True if no space is allocated.
229  bool empty(void) const { return last_accessed == 0; }
230  /// Iterator on the first element.
231  iterator begin(void) { return iterator(*this, 0); }
232  /// Constant iterator on the first element.
233  const_iterator begin(void) const { return const_iterator(*this, 0); }
234  /// Iterator on the last + 1 element.
235  iterator end(void) { return iterator(*this, size()); }
236  /// Constant iterator on the last + 1 element.
237  const_iterator end(void) const
238  { return const_iterator(*this, size()); }
239  reverse_iterator rbegin(void) { return reverse_iterator(end()); }
240  const_reverse_iterator rbegin(void) const
241  { return const_reverse_iterator(end()); }
242  reverse_iterator rend(void) { return reverse_iterator(begin()); }
243  const_reverse_iterator rend(void) const
244  { return const_reverse_iterator(begin()); }
245 
246  reference front(void) { return *begin(); }
247  const_reference front(void) const { return *begin(); }
248  reference back(void) { return *(end() - 1); }
249  const_reference back(void) const { return *(end() - 1); }
250 
251  void swap(dynamic_array<T,pks> &da);
252  /// Clear and desallocate all the elements.
253  void clear(void);
254  dynamic_array<T,pks> &operator =(const dynamic_array<T,pks> &da);
255 
256  protected:
257 
258  void init(void)
259  { last_accessed = last_ind = 0; array.resize(8); ppks = 3; m_ppks = 7; }
260 
261 
262  public:
263 
264  dynamic_array(const dynamic_array<T,pks> &da) { init(); *this = da; }
265  dynamic_array(void) { init(); }
266  // ~dynamic_array(void) { clear(); }
267  inline pointer pt_to(size_type ii) /* used by iterators. */
268  { return (ii >=last_ind) ? NULL : &((array[ii>>pks])[ii&DNAMPKS__]); }
269  inline const_pointer pt_to(size_type ii) const
270  { return (ii >=last_ind) ? NULL : &((array[ii>>pks])[ii&DNAMPKS__]); }
271 
272  /// Gives a constant reference on element ii.
273  const_reference operator [](size_type ii) const;
274  /// Gives a reference on element ii.
275  reference operator [](size_type ii);
276  void resize(size_type i) { (*this)[i-1]; }
277 
278  /// Gives the total memory occupied by the array.
279  size_type memsize(void) const {
280  return sizeof(pointer) * array.capacity()
281  + last_ind*sizeof(T) + sizeof(dynamic_array<T,pks>);
282  }
283 
284  /// Swap element i1 and i2.
285  void swap(size_type i1, size_type i2)
286  { std::swap((*this)[i1], (*this)[i2]); }
287  };
288 
289 
290  /* ********************************************************************* */
291  /* Member functions */
292  /* ********************************************************************* */
293 
294 
295  template<class T, unsigned char pks>
296  void dynamic_array<T,pks>::swap(dynamic_array<T,pks> &da) {
297  array.swap(da.array);
298  std::swap(last_ind, da.last_ind);
299  std::swap(last_accessed, da.last_accessed);
300  std::swap(ppks, da.ppks); std::swap(m_ppks, da.m_ppks);
301  }
302 
303  template<class T, unsigned char pks>
304  void dynamic_array<T,pks>::clear(void) {
305  // typename pointer_array::iterator it = array.begin();
306  // typename pointer_array::iterator ite = it+ ((last_ind + DNAMPKS__) >> pks);
307  // while (it != ite) delete[] *it++;
308  array.clear(); init();
309  }
310 
311  template<class T, unsigned char pks> dynamic_array<T,pks>
312  &dynamic_array<T,pks>::operator = (const dynamic_array<T,pks> &da) {
313  array.resize(da.array.size());
314  last_ind = da.last_ind;
315  last_accessed = da.last_accessed;
316  ppks = da.ppks; m_ppks = da.m_ppks;
317  typename pointer_array::iterator it = array.begin();
318  typename pointer_array::const_iterator ita = da.array.begin();
319  typename pointer_array::iterator ite = it+ ((last_ind + DNAMPKS__) >> pks);
320  while (it != ite) {
321  *it = std::unique_ptr<T[]>(new T[DNAMPKS__+1]);// std::make_unique<T[]>(DNAMPKS__+1);
322  pointer p = it->get(); ++it;
323  pointer pe = p + (DNAMPKS__+1);
324  const_pointer pa = (ita++)->get();
325  while (p != pe) *p++ = *pa++;
326  }
327  return *this;
328  }
329 
330  template<class T, unsigned char pks>
331  typename dynamic_array<T,pks>::const_reference
332  dynamic_array<T,pks>::operator [](size_type ii) const {
333  THREAD_SAFE_STATIC T f;
334  return (ii<last_ind) ? (array[ii>>pks])[ii&DNAMPKS__] : f;
335  }
336 
337  template<class T, unsigned char pks> typename dynamic_array<T,pks>::reference
338  dynamic_array<T,pks>::operator [](size_type ii) {
339  if (ii >= last_accessed) {
340  GMM_ASSERT2(ii < INT_MAX, "out of range");
341 
342  last_accessed = ii + 1;
343  if (ii >= last_ind) {
344  if ((ii >> (pks+ppks)) > 0) {
345  while ((ii >> (pks+ppks)) > 0) ppks++;
346  array.resize(m_ppks = (size_type(1) << ppks)); m_ppks--;
347  }
348  for (size_type jj = (last_ind >> pks); ii >= last_ind;
349  jj++, last_ind += (DNAMPKS__ + 1)){
350  array[jj] = std::unique_ptr<T[]>(new T[DNAMPKS__+1]);
351  } // std::make_unique<T[]>(DNAMPKS__ + 1); }
352  }
353  }
354  return (array[ii >> pks])[ii & DNAMPKS__];
355  }
356 
357 
358  /* ********************************************************************* */
359  /* Templates functions */
360  /* ********************************************************************* */
361 
362  template<class T, unsigned char pks>
363  bool operator==(const dynamic_array<T,pks> &x,
364  const dynamic_array<T,pks> &y) {
365  typename dynamic_array<T,pks>::const_iterator itxb=x.begin(), itxe=x.end();
366  typename dynamic_array<T,pks>::const_iterator ityb=y.begin(), itye=y.end();
367  typename dynamic_array<T,pks>::size_type d = std::min(itxe-itxb,itye-ityb);
368  typename dynamic_array<T,pks>::const_iterator itxc = itxb+d, ityc = ityb+d;
369 
370  if (!std::equal(itxb, itxc, ityb)) return false;
371  for (; itxc != itxe; itxc++) if (*itxc != T()) return false;
372  for (; ityc != itye; ityc++) if (*ityc != T()) return false;
373  return true;
374  }
375 
376  template<class T, unsigned char pks>
377  bool operator < (const dynamic_array<T,pks> &x,
378  const dynamic_array<T,pks> &y)
379  { return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end()); }
380 
381  template<class T, unsigned char pks> inline
382  void swap(const dynamic_array<T,pks> &x, const dynamic_array<T,pks> &y)
383  { x.swap(y); }
384 
385 }
386 #endif /* DAL_BASIC_H__ */
dal::dynamic_array
Dynamic Array.
Definition: dal_basic.h:196
dal::dynamic_array::memsize
size_type memsize(void) const
Gives the total memory occupied by the array.
Definition: dal_basic.h:279
dal::dynamic_array::end
const_iterator end(void) const
Constant iterator on the last + 1 element.
Definition: dal_basic.h:237
dal::dynamic_array::begin
iterator begin(void)
Iterator on the first element.
Definition: dal_basic.h:231
dal::dynamic_array::empty
bool empty(void) const
True if no space is allocated.
Definition: dal_basic.h:229
dal::dynamic_array::size
size_type size(void) const
Number of allocated elements.
Definition: dal_basic.h:225
dal::dynamic_array::clear
void clear(void)
Clear and desallocate all the elements.
Definition: dal_basic.h:304
dal::dynamic_array::end
iterator end(void)
Iterator on the last + 1 element.
Definition: dal_basic.h:235
dal::dynamic_array::begin
const_iterator begin(void) const
Constant iterator on the first element.
Definition: dal_basic.h:233
dal::dynamic_array::swap
void swap(size_type i1, size_type i2)
Swap element i1 and i2.
Definition: dal_basic.h:285
dal::dynamic_array::operator[]
const_reference operator[](size_type ii) const
Gives a constant reference on element ii.
Definition: dal_basic.h:332
dal_config.h
defines and typedefs for namespace dal
getfem_omp.h
Tools for multithreaded, OpenMP and Boost based parallelization.
bgeot::size_type
size_t size_type
used as the common size type in the library
Definition: bgeot_poly.h:49
dal
Dynamic Array Library.
Definition: dal_backtrace.cc:29
dal::dna_const_iterator
Constant iterator class for dynamic array.
Definition: dal_basic.h:112
dal::dna_iterator
Iterator class for dynamic array.
Definition: dal_basic.h:50
dal::dna_iterator::operator++
dna_iterator & operator++()
next element.
Definition: dal_basic.h:79
dal::dna_iterator::operator+=
dna_iterator & operator+=(difference_type i)
go i elements forward.
Definition: dal_basic.h:85
dal::dna_iterator::operator-
dna_iterator operator-(difference_type i) const
gives an iterator pointing i elements backward.
Definition: dal_basic.h:94
dal::dna_iterator::operator--
dna_iterator & operator--()
previous element.
Definition: dal_basic.h:82
dal::dna_iterator::operator+
dna_iterator operator+(difference_type i) const
gives an iterator pointing i elements forward.
Definition: dal_basic.h:91
dal::dna_iterator::operator-=
dna_iterator & operator-=(difference_type i)
go i elements backward.
Definition: dal_basic.h:88