GetFEM++  5.3
dal_basic.h
Go to the documentation of this file.
1 /* -*- c++ -*- (enables emacs c++ mode) */
2 /*===========================================================================
3 
4  Copyright (C) 1995-2017 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  };
108 
109  /// Constant iterator class for dynamic array.
110  template<class T, unsigned char pks> struct dna_const_iterator {
111  typedef T value_type;
112  typedef const value_type* pointer;
113  typedef const value_type& reference;
114  typedef size_t size_type;
115  typedef ptrdiff_t difference_type;
116  typedef std::random_access_iterator_tag iterator_category;
117 
118 # define DNAMPKS__ ((size_type(1) << pks) - 1)
119  const dynamic_array<T,pks> *p;
120  size_type in;
121  pointer pT;
122 
123  dna_const_iterator(void) {}
124  dna_const_iterator(const dynamic_array<T,pks> &da, size_type ii)
125  { p = &da; in = ii; pT = p->pt_to(in); }
126  dna_const_iterator(const dna_iterator<T, pks> &it)
127  : p(it.p), in(it.in), pT(it.pT) {}
128 
129  inline size_type index(void) const { return in; }
130  dna_const_iterator operator ++(int) {
131  dna_const_iterator tmp = *this;
132  if ((++in)&DNAMPKS__) pT++; else pT=p->pt_to(in); return tmp;
133  }
134  dna_const_iterator operator --(int) {
135  dna_const_iterator tmp = *this;
136  if ((in--)&DNAMPKS__) pT--; else pT=p->pt_to(in); return tmp;
137  }
138  dna_const_iterator &operator ++()
139  { if ((++in)&DNAMPKS__) pT++; else pT=p->pt_to(in); return *this; }
140  dna_const_iterator &operator --()
141  { if ((in--)&DNAMPKS__) pT--; else pT=p->pt_to(in); return *this; }
142  dna_const_iterator &operator +=(difference_type i)
143  { in += i; 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) const
147  { dna_const_iterator it = *this; return (it += i); }
148  dna_const_iterator operator -(difference_type i) const
149  { dna_const_iterator it = *this; return (it -= i); }
150  difference_type operator -(const dna_const_iterator &i) const
151  { return difference_type(in - i.in); }
152 
153  reference operator *() const { return (*pT); }
154  pointer operator ->() const { return pT; }
155  reference operator [](size_type ii) const { return (*p)[in+ii]; }
156 
157  bool operator ==(const dna_const_iterator &i) const
158  { return (i.in == in); }
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 (in < i.in); }
163  };
164 
165  /** Dynamic Array. Defines the basic container of the library which is
166  * dal::dynamic_array<T, pks>. This container is virtually an
167  * infinite array of element of type T. When a random acces tab[i] is
168  * called, a control is made on i and an allocation is made if
169  * needed. The allocation is made by blocks of n elements, where
170  * @f$n = 2^{pks}@f$. @f$pks@f$ is an optional parameter assumed to be 5.
171  * The structure of this container is similar to the one of std::deque<T>
172  * but with a faster random access.
173  *
174  *
175  * <h3>Example of code</h3>
176  * If T is any type (with or without trivial constructor/destructor,
177  * and with constructor T(0) and T(1)), the
178  * following code is valid:
179  * @code
180  * #include<dal_basic.h>
181  * dal::dynamic_array<T> tab;
182  * tab[50] = T(0); // 51 elements in tab.
183  * std::fill(tab.begin(), tab.end(), T(0)); // 51 elements initialized
184  * dal::dynamic_array<T>::iterator it = tab.begin();
185  * dal::dynamic_array<T>::iterator ite = it + 50;
186  * for( ; it != ite; ++it)
187  * { *it = T(1); } // only the 50 first elements are changed.
188  * @endcode
189  */
190  template<class T, unsigned char pks> class dynamic_array {
191  public :
192 
193  typedef T value_type;
194  typedef value_type* pointer;
195  typedef const value_type* const_pointer;
196  typedef value_type& reference;
197  typedef const value_type& const_reference;
198  typedef size_t size_type;
199  typedef ptrdiff_t difference_type;
200  typedef unsigned char pack_size_type;
201  typedef std::vector<std::unique_ptr<T[]>> pointer_array;
202  typedef dna_iterator<T, pks> iterator;
203  typedef dna_const_iterator<T, pks> const_iterator;
204  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
205  typedef std::reverse_iterator<iterator> reverse_iterator;
206 
207  protected :
208 
209 # define DNAMPKS__ ((size_type(1) << pks) - 1)
210  pointer_array array;
211  pack_size_type ppks; /* size of pointer packs (2^ppks). */
212  size_type m_ppks; /* = (2^ppks) - 1. */
213  size_type last_ind; /* allocated = 0 .. last_ind-1. */
214  size_type last_accessed; /* valid = 0 .. last_accessed-1. */
215 
216  public :
217 
218  /// Number of allocated elements.
219  size_type size(void) const { return last_accessed; }
220  size_type capacity(void) const { return last_ind; }
221  size_type max_size(void) const { return (size_type(-1)) / 2; }
222  /// True if no space is allocated.
223  bool empty(void) const { return last_accessed == 0; }
224  /// Iterator on the first element.
225  iterator begin(void) { return iterator(*this, 0); }
226  /// Constant iterator on the first element.
227  const_iterator begin(void) const { return const_iterator(*this, 0); }
228  /// Iterator on the last + 1 element.
229  iterator end(void) { return iterator(*this, size()); }
230  /// Constant iterator on the last + 1 element.
231  const_iterator end(void) const
232  { return const_iterator(*this, size()); }
233  reverse_iterator rbegin(void) { return reverse_iterator(end()); }
234  const_reverse_iterator rbegin(void) const
235  { return const_reverse_iterator(end()); }
236  reverse_iterator rend(void) { return reverse_iterator(begin()); }
237  const_reverse_iterator rend(void) const
238  { return const_reverse_iterator(begin()); }
239 
240  reference front(void) { return *begin(); }
241  const_reference front(void) const { return *begin(); }
242  reference back(void) { return *(end() - 1); }
243  const_reference back(void) const { return *(end() - 1); }
244 
245  void swap(dynamic_array<T,pks> &da);
246  /// Clear and desallocate all the elements.
247  void clear(void);
248  dynamic_array<T,pks> &operator =(const dynamic_array<T,pks> &da);
249 
250  protected:
251 
252  void init(void)
253  { last_accessed = last_ind = 0; array.resize(8); ppks = 3; m_ppks = 7; }
254 
255 
256  public:
257 
258  dynamic_array(const dynamic_array<T,pks> &da) { init(); *this = da; }
259  dynamic_array(void) { init(); }
260  // ~dynamic_array(void) { clear(); }
261  inline pointer pt_to(size_type ii) /* used by iterators. */
262  { return (ii >=last_ind) ? NULL : &((array[ii>>pks])[ii&DNAMPKS__]); }
263  inline const_pointer pt_to(size_type ii) const
264  { return (ii >=last_ind) ? NULL : &((array[ii>>pks])[ii&DNAMPKS__]); }
265 
266  /// Gives a constant reference on element ii.
267  const_reference operator [](size_type ii) const;
268  /// Gives a reference on element ii.
269  reference operator [](size_type ii);
270  void resize(size_type i) { (*this)[i-1]; }
271 
272  /// Gives the total memory occupied by the array.
273  size_type memsize(void) const {
274  return sizeof(pointer) * array.capacity()
275  + last_ind*sizeof(T) + sizeof(dynamic_array<T,pks>);
276  }
277 
278  /// Swap element i1 and i2.
279  void swap(size_type i1, size_type i2)
280  { std::swap((*this)[i1], (*this)[i2]); }
281  };
282 
283 
284  /* ********************************************************************* */
285  /* Menbers functions */
286  /* ********************************************************************* */
287 
288 
289  template<class T, unsigned char pks>
290  void dynamic_array<T,pks>::swap(dynamic_array<T,pks> &da) {
291  array.swap(da.array);
292  std::swap(last_ind, da.last_ind);
293  std::swap(last_accessed, da.last_accessed);
294  std::swap(ppks, da.ppks); std::swap(m_ppks, da.m_ppks);
295  }
296 
297  template<class T, unsigned char pks>
298  void dynamic_array<T,pks>::clear(void) {
299  // typename pointer_array::iterator it = array.begin();
300  // typename pointer_array::iterator ite = it+ ((last_ind + DNAMPKS__) >> pks);
301  // while (it != ite) delete[] *it++;
302  array.clear(); init();
303  }
304 
305  template<class T, unsigned char pks> dynamic_array<T,pks>
306  &dynamic_array<T,pks>::operator = (const dynamic_array<T,pks> &da) {
307  array.resize(da.array.size());
308  last_ind = da.last_ind;
309  last_accessed = da.last_accessed;
310  ppks = da.ppks; m_ppks = da.m_ppks;
311  typename pointer_array::iterator it = array.begin();
312  typename pointer_array::const_iterator ita = da.array.begin();
313  typename pointer_array::iterator ite = it+ ((last_ind + DNAMPKS__) >> pks);
314  while (it != ite) {
315  *it = std::unique_ptr<T[]>(new T[DNAMPKS__+1]);// std::make_unique<T[]>(DNAMPKS__+1);
316  register pointer p = it->get(); ++it;
317  register pointer pe = p + (DNAMPKS__+1);
318  register const_pointer pa = (ita++)->get();
319  while (p != pe) *p++ = *pa++;
320  }
321  return *this;
322  }
323 
324  template<class T, unsigned char pks>
325  typename dynamic_array<T,pks>::const_reference
326  dynamic_array<T,pks>::operator [](size_type ii) const {
327  DEFINE_STATIC_THREAD_LOCAL_INITIALIZED(std::shared_ptr<T>,pf,NULL);
328  if (pf.get() == NULL) { pf = std::make_shared<T>(); }
329  return (ii<last_ind) ? (array[ii>>pks])[ii&DNAMPKS__] : *pf;
330  }
331 
332  template<class T, unsigned char pks> typename dynamic_array<T,pks>::reference
333  dynamic_array<T,pks>::operator [](size_type ii) {
334  if (ii >= last_accessed) {
335  GMM_ASSERT2(ii < INT_MAX, "out of range");
336 
337  last_accessed = ii + 1;
338  if (ii >= last_ind) {
339  if ((ii >> (pks+ppks)) > 0) {
340  while ((ii >> (pks+ppks)) > 0) ppks++;
341  array.resize(m_ppks = (size_type(1) << ppks)); m_ppks--;
342  }
343  for (size_type jj = (last_ind >> pks); ii >= last_ind;
344  jj++, last_ind += (DNAMPKS__ + 1))
345  { array[jj] = std::unique_ptr<T[]>(new T[DNAMPKS__+1]); } // std::make_unique<T[]>(DNAMPKS__ + 1); }
346  }
347  }
348  return (array[ii >> pks])[ii & DNAMPKS__];
349  }
350 
351 
352  /* ********************************************************************* */
353  /* Templates functions */
354  /* ********************************************************************* */
355 
356  template<class T, unsigned char pks>
357  bool operator==(const dynamic_array<T,pks> &x,
358  const dynamic_array<T,pks> &y) {
359  typename dynamic_array<T,pks>::const_iterator itxb=x.begin(), itxe=x.end();
360  typename dynamic_array<T,pks>::const_iterator ityb=y.begin(), itye=y.end();
361  typename dynamic_array<T,pks>::size_type d = std::min(itxe-itxb,itye-ityb);
362  typename dynamic_array<T,pks>::const_iterator itxc = itxb+d, ityc = ityb+d;
363 
364  if (!std::equal(itxb, itxc, ityb)) return false;
365  for (; itxc != itxe; itxc++) if (*itxc != T()) return false;
366  for (; ityc != itye; ityc++) if (*ityc != T()) return false;
367  return true;
368  }
369 
370  template<class T, unsigned char pks>
371  bool operator < (const dynamic_array<T,pks> &x,
372  const dynamic_array<T,pks> &y)
373  { return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end()); }
374 
375  template<class T, unsigned char pks> inline
376  void swap(const dynamic_array<T,pks> &x, const dynamic_array<T,pks> &y)
377  { x.swap(y); }
378 
379 }
380 #endif /* DAL_BASIC_H__ */
dal::dynamic_array::empty
bool empty(void) const
True if no space is allocated.
Definition: dal_basic.h:223
dal::dynamic_array::operator[]
const_reference operator[](size_type ii) const
Gives a constant reference on element ii.
Definition: dal_basic.h:326
dal::dna_iterator::operator-=
dna_iterator & operator-=(difference_type i)
go i elements backward.
Definition: dal_basic.h:88
dal::dna_const_iterator
Constant iterator class for dynamic array.
Definition: dal_basic.h:110
dal::dna_iterator
Iterator class for dynamic array.
Definition: dal_basic.h:50
dal::dna_iterator::operator+
dna_iterator operator+(difference_type i) const
gives an iterator pointing i elements forward.
Definition: dal_basic.h:91
getfem_omp.h
Tools for multithreaded, OpenMP and Boost based parallelization.
dal::dynamic_array::swap
void swap(size_type i1, size_type i2)
Swap element i1 and i2.
Definition: dal_basic.h:279
dal_config.h
defines and typedefs for namespace dal
dal::dynamic_array
Dynamic Array.
Definition: dal_basic.h:47
dal::dna_iterator::operator-
dna_iterator operator-(difference_type i) const
gives an iterator pointing i elements backward.
Definition: dal_basic.h:94
dal::dynamic_array::memsize
size_type memsize(void) const
Gives the total memory occupied by the array.
Definition: dal_basic.h:273
dal
Dynamic Array Library.
Definition: dal_backtrace.cc:29
dal::dna_iterator::operator--
dna_iterator & operator--()
previous element.
Definition: dal_basic.h:82
dal::dynamic_array::size
size_type size(void) const
Number of allocated elements.
Definition: dal_basic.h:219
dal::dynamic_array::end
const_iterator end(void) const
Constant iterator on the last + 1 element.
Definition: dal_basic.h:231
dal::dynamic_array::end
iterator end(void)
Iterator on the last + 1 element.
Definition: dal_basic.h:229
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++()
next element.
Definition: dal_basic.h:79
dal::dynamic_array::begin
iterator begin(void)
Iterator on the first element.
Definition: dal_basic.h:225
dal::dynamic_array::clear
void clear(void)
Clear and desallocate all the elements.
Definition: dal_basic.h:298
dal::dynamic_array::begin
const_iterator begin(void) const
Constant iterator on the first element.
Definition: dal_basic.h:227