GetFEM  5.4.2
bgeot_small_vector.h
Go to the documentation of this file.
1 /* -*- c++ -*- (enables emacs c++ mode) */
2 /*===========================================================================
3 
4  Copyright (C) 2000-2020 Julien Pommier
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 bgeot_small_vector.h
33  @author Julien Pommier <Julien.Pommier@insa-toulouse.fr>
34  @date January 2004.
35  @brief Small (dim < 8) vectors.
36 */
37 #ifndef BGEOT_SMALL_VECTOR_H
38 #define BGEOT_SMALL_VECTOR_H
39 
40 #include "dal_singleton.h"
41 #include "bgeot_config.h"
42 #ifdef DEBUG_SMALL_VECTOR
43 # include <cassert>
44 # define SVEC_ASSERT(x) assert(x)
45 #else
46 # define SVEC_ASSERT(x)
47 #endif
48 
49 namespace bgeot {
50 
51  class APIDECL block_allocator {
52  public:
53  typedef gmm::uint16_type uint16_type;
54  typedef gmm::uint32_type node_id;
55  typedef gmm::uint32_type size_type;
56  /* number of objects stored in a same block, power of 2 */
57  enum { p2_BLOCKSZ = 8, BLOCKSZ = 1<<p2_BLOCKSZ };
58  enum { OBJ_SIZE_LIMIT = 129 }; /* object size limit */
59  enum { MAXREF = 256 }; /* reference count limit before copying is used */
60  protected:
61  /* definition of a block (container of BLOCKSZ chunks) */
62  struct block {
63  /* effective data + reference count (stored in the BLOCKSZ first bytes) */
64  unsigned char * data;
65  /* keep track of unused chunks */
66  uint16_type first_unused_chunk, count_unused_chunk;
67  /* "pointers" for the list of free (or partially filled) blocks */
68  size_type prev_unfilled, next_unfilled;
69  size_type objsz; /* size (in bytes) of the chunks stored in this block */
70  block() : data(0) {}
71  block(size_type objsz_) : data(0),
72  prev_unfilled(size_type(-1)),
73  next_unfilled(size_type(-1)),
74  objsz(objsz_) {}
75  ~block() {} /* no cleanup of data, no copy constructor : it's on purpose
76  since the block will be moved a lot when the vector container
77  will be resized (cleanup done by ~block_allocator) */
78  void init() {
79  clear();
80  data = static_cast<unsigned char*>(::operator new(BLOCKSZ*objsz + BLOCKSZ));
81  /* first BLOCKSZ bytes are used for reference counting */
82  memset(data, 0, BLOCKSZ);
83  //cout << "init block&" << this << " allocated data: " << (void*)data << "\n";
84  }
85  void clear() {
86  //cout << "clear block&" << this << " frees data: " << (void*)data << "\n";
87  if (data) { ::operator delete(data); };
88  data = 0; first_unused_chunk = 0; count_unused_chunk = BLOCKSZ;
89  }
90  unsigned char& refcnt(size_type pos) { return data[pos]; }
91  bool empty() const { return data == 0; }
92  /* could be smarter .. */
93  };
94  /* container of all blocks .. a vector ensures fast access to
95  any element (better than deque) */
96  std::vector<block> blocks;
97  /* pointers to free (or partially free) blocks for each object size */
98  size_type first_unfilled[OBJ_SIZE_LIMIT];
99  public:
100  block_allocator();
101  ~block_allocator();
102  /* gets the data pointer for an object given its "id" */
103  void * obj_data(node_id id) {
104  return blocks[id/BLOCKSZ].data + BLOCKSZ + (id%BLOCKSZ)*blocks[id/BLOCKSZ].objsz;
105  }
106  dim_type obj_sz(node_id id) {
107  return dim_type(blocks[id/BLOCKSZ].objsz);
108  }
109  /* reference counting */
110  unsigned char& refcnt(node_id id) {
111  return blocks[id/BLOCKSZ].refcnt(id%BLOCKSZ);
112  }
113  node_id inc_ref(node_id id) {
114  if (id && ++refcnt(id) == 0) {
115  --refcnt(id);
116  id = duplicate(id);
117  }
118  return id;
119  }
120  void dec_ref(node_id id) {
121  SVEC_ASSERT(id==0 || refcnt(id));
122  if (id && --refcnt(id) == 0) {
123  ++refcnt(id);
124  deallocate(id);
125  }
126  }
127  void duplicate_if_aliased(node_id& id) {
128  if (refcnt(id) != 1) {
129  --refcnt(id);
130  id = duplicate(id); SVEC_ASSERT(id == 0 || refcnt(id)==1);
131  }
132  }
133  /* allocation of a chunk */
134  node_id allocate(block_allocator::size_type n);
135  /* deallocation of a chunk */
136  void deallocate(node_id nid);
137  void memstats();
138  protected:
139  /* won't work for non-POD types ... */
140  node_id duplicate(node_id id) {
141  node_id id2 = allocate(obj_sz(id));
142  memcpy(obj_data(id2),obj_data(id),obj_sz(id));
143  return id2;
144  }
145  void insert_block_into_unfilled(block_allocator::size_type bid);
146  void remove_block_from_unfilled(block_allocator::size_type bid);
147  };
148 
149  /* common class for all mini_vec, provides access to the common static allocator */
150  struct APIDECL static_block_allocator {
151  /* must be a pointer ... sgi CC is not able to order correctly the
152  destructors of static variables */
153  static block_allocator *palloc;
154  static_block_allocator() { if (!palloc) palloc=&dal::singleton<block_allocator,1000>::instance(); } //new block_allocator(); }
155  };
156 
157 #ifdef GETFEM_HAS_OPENMP
158  /**In case of multi-threaded assembly with OpenMP using std::vector derived
159  class for it's thread safety*/
160  template<typename T> class small_vector : public std::vector<T>
161  {
162  public:
163  using typename std::vector<T>::const_iterator;
164  using typename std::vector<T>::iterator;
165  const_iterator begin() const { return std::vector<T>::begin(); }
166  iterator begin() { return std::vector<T>::begin(); }
167  const_iterator end() const { return std::vector<T>::end(); }
168  iterator end() { return std::vector<T>::end(); }
169 
170  const_iterator const_begin() const { return std::vector<T>::cbegin(); }
171  const_iterator const_end() const { return std::vector<T>::cend(); }
172  dim_type size() const { return dim_type(std::vector<T>::size()); }
173 
174  const small_vector<T>& operator=(const small_vector<T>& other) {
175  std::vector<T>::operator=(other);
176  return *this;
177  }
178 
179  small_vector() : std::vector<T>() {}
180 
181  explicit small_vector(size_type n) : std::vector<T>(n) {}
182 
183  small_vector(const small_vector<T>& v) : std::vector<T>(v) {}
184 
185  small_vector(const std::vector<T>& v) : std::vector<T>(v) {}
186 
187  small_vector(T v1, T v2) : std::vector<T>(2)
188  { (*this)[0] = v1; (*this)[1] = v2; }
189 
190  small_vector(T v1, T v2, T v3) : std::vector<T>(3)
191  { (*this)[0] = v1; (*this)[1] = v2; (*this)[2] = v3; }
192 
193  template<class UNOP> small_vector(const small_vector<T>& a, UNOP op)
194  : std::vector<T>(a.size())
195  { std::transform(a.begin(), a.end(), begin(), op); }
196 
197  template<class BINOP> small_vector(const small_vector<T>& a, const small_vector<T>& b, BINOP op)
198  : std::vector<T>(a.size())
199  { std::transform(a.begin(), a.end(), b.begin(), begin(), op); }
200 #else
201  /** container for small vectors of POD (Plain Old Data) types. Should be as fast as
202  std::vector<T> while beeing smaller and uses copy-on-write. The gain is especially
203  valuable on 64 bits architectures.
204  */
205  template<typename T> class small_vector : public static_block_allocator {
206  typedef block_allocator::node_id node_id;
207  node_id id;
208  public:
209  typedef small_vector<T> this_type;
210  typedef this_type vector_type;
211  typedef T value_type;
212  typedef T * pointer;
213  typedef const T * const_pointer;
214  typedef T& reference;
215  typedef const T & const_reference;
216  typedef T *iterator;
217  typedef const T * const_iterator;
218 
219  reference operator[](size_type l)
220  { GMM_ASSERT2(l <=size(), "out of range, l="<<l<<"size="<<size()); return base()[l]; }
221  value_type operator[](size_type l) const
222  { GMM_ASSERT2(l <= size(), "out of range, l="<<l<<"size="<<size()); return const_base()[l]; }
223  value_type at(size_type l) const { return const_base()[l]; }
224  iterator begin() { return base(); }
225  const_iterator begin() const { return const_base(); }
226  const_iterator const_begin() const { return const_base(); }
227  iterator end() { return base()+size(); }
228  const_iterator end() const { return const_base()+size(); }
229  const_iterator const_end() const { return const_base()+size(); }
230  void resize(size_type n) {
231  if (n == size()) return;
232  if (n) {
233  small_vector<T> other(n); SVEC_ASSERT(other.refcnt() == 1);
234  memcpy(other.base(), const_base(), std::min(size(),other.size())*sizeof(value_type));
235  SVEC_ASSERT(id==0 || refcnt());
236  swap(other);
237  SVEC_ASSERT(refcnt()); SVEC_ASSERT(other.id == 0 || other.refcnt());
238  } else { allocator().dec_ref(id); id=0; }
239  }
240  const small_vector<T>& operator=(const small_vector<T>& other) {
241  /* order very important when &other == this */
242  node_id id2 = allocator().inc_ref(other.id);
243  allocator().dec_ref(id); id = id2;
244  SVEC_ASSERT(id == 0 || refcnt()); SVEC_ASSERT(other.id == 0 || other.refcnt());
245  return *this;
246  }
247  void swap(small_vector<T> &v) { std::swap(id,v.id); }
248  small_vector() : id(0) {}
249  explicit small_vector(size_type n) : id(allocate(n)) {}
250  small_vector(const small_vector<T>& v) : static_block_allocator(), id(allocator().inc_ref(v.id)) {}
251  explicit small_vector(const std::vector<T>& v) : id(allocate(v.size())) {
252  std::copy(v.begin(),v.end(),begin());
253  }
254  ~small_vector() {
255  // in the wonderful world of static objects, the order of destruction
256  // can be really important when the memory allocator is destroyed
257  // before , for ex. a global variable of type small_vector...
258  // that's why there is a check on the state of the allocator..
259  if (!allocator_destroyed())
260  allocator().dec_ref(id);
261  }
262 
263  small_vector(T v1, T v2) : id(allocate(2))
264  { begin()[0] = v1; begin()[1] = v2; }
265  small_vector(T v1, T v2, T v3) : id(allocate(3))
266  { begin()[0] = v1; begin()[1] = v2; begin()[2] = v3; }
267  template<class UNOP> small_vector(const small_vector<T>& a, UNOP op)
268  : id(allocate(a.size())) { std::transform(a.begin(), a.end(), begin(), op); }
269  template<class BINOP> small_vector(const small_vector<T>& a, const small_vector<T>& b, BINOP op)
270  : id(allocate(a.size())) { std::transform(a.begin(), a.end(), b.begin(), begin(), op); }
271  bool empty() const { return id==0; }
272  unsigned char refcnt() const { return allocator().refcnt(id); }
273  dim_type size() const
274  { return dim_type(allocator().obj_sz(id)/sizeof(value_type)); }
275 #endif
276 
277  small_vector<T> operator+(const small_vector<T>& other) const
278  { return small_vector<T>(*this,other,std::plus<T>()); }
279 
280  small_vector<T> operator-(const small_vector<T>& other) const
281  { return small_vector<T>(*this,other,std::minus<T>()); }
282 
283  small_vector<T> operator-() const
284  { return -1.*(*this); }
285 
286  small_vector<T> operator*(T v) const
287  {return small_vector<T>(*this, [&v](const auto &x) {return v * x;});}
288 
289  small_vector<T> operator/(T v) const { return (*this)*(T(1)/v); }
290  small_vector<T>& operator+=(const small_vector<T>& other) {
291  const_iterator b = other.begin(); iterator it = begin();
292  for (size_type i=0; i < size(); ++i) *it++ += *b++;
293  return *this;
294  }
295 
296  small_vector<T>& addmul(T v, const small_vector<T>& other) IS_DEPRECATED;
297  //{ std::transform(begin(), end(), other.begin(), begin(), std::plus<T>()); return *this; }
298  small_vector<T>& operator-=(const small_vector<T>& other) {
299  const_iterator b = other.begin(); iterator it = begin();
300  for (size_type i=0; i < size(); ++i) *it++ -= *b++;
301  return *this;
302  }
303 
304  small_vector<T> operator*=(T v) {
305  iterator it = begin(), ite=end();
306  while(it < ite) *it++ *= v;
307  return *this;
308  }
309  small_vector<T> operator/=(T v) { return operator*=(T(1)/v); }
310  inline bool operator<(const small_vector<T>& other) const
311  {
312  return std::lexicographical_compare(begin(), end(), other.begin(), other.end());
313  }
314  void fill(T v) { for (iterator it=begin(); it != end(); ++it) *it = v; }
315  small_vector<T>& operator<<(T x) { push_back(x); return *this; }
316 #ifdef GETFEM_HAS_OPENMP
317  size_type memsize() const { return (size()*sizeof(T)) + sizeof(*this); }
318 #else
319  size_type memsize() const { return (size()*sizeof(T) / refcnt()) + sizeof(*this); }
320  small_vector<T>& clear() { resize(0); return *this; }
321  void push_back(T x) { resize(size()+1); begin()[size()-1] = x; }
322  protected:
323  /* read-write access (ensures the refcount is 1) */
324  pointer base() {
325  allocator().duplicate_if_aliased(id);
326  return static_cast<pointer>(allocator().obj_data(id));
327  }
328  /* read-only access */
329  const_pointer const_base() const {
330  SVEC_ASSERT(id == 0 || refcnt()); return static_cast<pointer>(allocator().obj_data(id));
331  }
332  block_allocator& allocator() const { return *palloc; }
333  bool allocator_destroyed() const { return palloc == 0; }
334  node_id allocate(size_type n) {
335  return node_id(allocator().allocate(gmm::uint32_type(n*sizeof(value_type)))); SVEC_ASSERT(refcnt() == 1);
336  }
337 #endif
338  };
339 
340  template<class T> inline small_vector<T>& small_vector<T>::addmul(T v, const small_vector<T>& other)
341  {
342  const_iterator b = other.begin(); iterator it = begin();
343  for (size_type i=0; i < size(); ++i) *it++ += v * *b++;
344  return *this;
345  }
346 
347 
348  template<class T> std::ostream& operator<<(std::ostream& os, const small_vector<T>& v) {
349  os << "["; for (size_type i=0; i < v.size(); ++i) { if (i) os << ", "; os << v[i]; }
350  os << "]"; return os;
351  }
352 
353  template<class T> inline small_vector<T> operator *(T x, const small_vector<T>& m)
354  { return m*x; }
355 
356 
357  template <class VEC_CONT>
358  void vectors_to_base_matrix(base_matrix &G, const VEC_CONT &a) {
359  size_type P = (*(a.begin())).size(), NP = a.end() - a.begin();
360  G.base_resize(P, NP);
361  typename VEC_CONT::const_iterator it = a.begin(), ite = a.end();
362  base_matrix::iterator itm = G.begin();
363  for (; it != ite; ++it, itm += P)
364  std::copy((*it).begin(), (*it).end(), itm);
365  }
366 
367  typedef small_vector<scalar_type> base_small_vector;
368  typedef base_small_vector base_node;
369 
370 }
371 
372 
373 namespace std {
374  inline void swap(bgeot::base_node& a, bgeot::base_node& b) { a.swap(b); }
375 }
376 
377 #include "gmm/gmm_interface_bgeot.h"
378 
379 #endif
dal::singleton::instance
static T & instance()
Instance from the current thread.
Definition: dal_singleton.h:165
bgeot::operator<<
std::ostream & operator<<(std::ostream &o, const convex_structure &cv)
Print the details of the convex structure cvs to the output stream o.
Definition: bgeot_convex_structure.cc:71
bgeot::size_type
size_t size_type
used as the common size type in the library
Definition: bgeot_poly.h:49
gmm::clear
void clear(L &l)
clear (fill with zeros) a vector or matrix.
Definition: gmm_blas.h:59
dal_singleton.h
A simple singleton implementation.
gmm_interface_bgeot.h
interface for bgeot::small_vector
bgeot::operator+
rational_fraction< T > operator+(const polynomial< T > &P, const rational_fraction< T > &Q)
Add Q to P.
Definition: bgeot_poly.h:749
bgeot::small_vector
container for small vectors of POD (Plain Old Data) types.
Definition: bgeot_small_vector.h:205
bgeot
Basic Geometric Tools.
Definition: bgeot_convex_ref.cc:27
bgeot_config.h
defines and typedefs for namespace bgeot
bgeot::operator-
rational_fraction< T > operator-(const polynomial< T > &P, const rational_fraction< T > &Q)
Subtract Q from P.
Definition: bgeot_poly.h:756