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