Lunchbox  1.17.0
Multi-threaded C++ toolbox library for all application developers creating high-performance multi-threaded programs.
lfVector.ipp
1 
2 /* Copyright (c) 2011-2014, EPFL/Blue Brain Project
3  * Daniel Nachbaur <daniel.nachbaur@epfl.ch>
4  * Stefan.Eilemann@epfl.ch
5  *
6  * This file is part of Lunchbox <https://github.com/Eyescale/Lunchbox>
7  *
8  * This library is free software; you can redistribute it and/or modify it under
9  * the terms of the GNU Lesser General Public License version 3.0 as published
10  * by the Free Software Foundation.
11  *
12  * This library is distributed in the hope that it will be useful, but WITHOUT
13  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
14  * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
15  * details.
16  *
17  * You should have received a copy of the GNU Lesser General Public License
18  * along with this library; if not, write to the Free Software Foundation, Inc.,
19  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
20  */
21 
22 #include "lfVectorIterator.h"
23 
24 namespace lunchbox
25 {
26 template <class T, int32_t nSlots>
28  : size_(0)
29 {
30  setZero(slots_, nSlots * sizeof(T*));
31 }
32 
33 template <class T, int32_t nSlots>
35  : size_(n)
36 {
37  LBASSERT(n != 0);
38  setZero(slots_, nSlots * sizeof(T*));
39  const int32_t s = getIndexOfLastBit(uint64_t(n));
40  for (int32_t i = 0; i <= s; ++i)
41  slots_[i] = new T[1 << i];
42 }
43 
44 template <class T, int32_t nSlots>
45 LFVector<T, nSlots>::LFVector(const size_t n, const T& t)
46  : size_(0)
47 {
48  LBASSERT(n != 0);
49  setZero(slots_, nSlots * sizeof(T*));
50  const int32_t s = getIndexOfLastBit(uint64_t(n));
51  for (size_t i = 0; i <= size_t(s); ++i)
52  {
53  const size_t sz = 1 << i;
54  slots_[i] = new T[sz];
55  for (size_t j = 0; size_ < n && j < sz; ++j)
56  {
57  slots_[i][j] = t;
58  ++size_;
59  }
60  }
61  LBASSERTINFO(size_ == n, size_ << " != " << n);
62 }
63 
64 template <class T, int32_t nSlots>
66  : size_(0)
67  , lock_()
68 {
69  assign_(from);
70 }
71 
72 template <class T, int32_t nSlots>
73 template <int32_t fromSlots>
75  : size_(0)
76  , lock_()
77 {
78  assign_(from);
79 }
80 
81 template <class T, int32_t nSlots>
83 {
84  for (size_t i = 0; i < nSlots; ++i)
85  delete[] slots_[i];
86 }
87 
88 template <class T, int32_t nSlots>
90  const LFVector<T, nSlots>& from)
91 {
92  if (&from == this)
93  return *this;
94 
95  ScopedWrite mutex1(lock_); // DEADLOCK when doing a=b and b=a
96  ScopedWrite mutex2(from.lock_); // consider trySet/yield approach
97  size_ = 0;
98  for (size_t i = 0; i < size_t(nSlots); ++i)
99  {
100  if (from.slots_[i])
101  {
102  const size_t sz = size_t(1) << i;
103  if (!slots_[i])
104  slots_[i] = new T[sz];
105 
106  for (size_t j = 0; size_ < from.size_ && j < sz; ++j)
107  {
108  slots_[i][j] = from.slots_[i][j];
109  ++size_;
110  }
111  }
112  else if (slots_[i]) // done copying, free unneeded slots
113  {
114  delete[] slots_[i];
115  slots_[i] = 0;
116  }
117  }
118 
119  LBASSERTINFO(size_ == from.size_, size_ << " != " << from.size_);
120  return *this;
121 }
122 
123 template <class T, int32_t nSlots>
125 {
126  if (&rhs == this)
127  return true;
128 
129  if (size() != rhs.size())
130  return false;
131 
132  const_iterator it = begin();
133  const_iterator rhsIt = rhs.begin();
134  for (; it != end() && rhsIt != end(); ++it, ++rhsIt)
135  {
136  if (*it != *rhsIt)
137  return false;
138  }
139 
140  return true;
141 }
142 
143 #ifdef LB_GCC_4_6_OR_LATER // http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51721
144 #ifndef LB_GCC_4_8 // http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56824
145 #pragma GCC diagnostic push
146 #endif
147 #pragma GCC diagnostic ignored "-Warray-bounds"
148 #endif
149 
150 template <class T, int32_t nSlots>
152 {
153  // one beyond end is possible when called by erase
154  LBASSERTINFO(size_ >= i, size_ << " < " << i);
155  ++i;
156  const int32_t slot = getIndexOfLastBit(i);
157  const size_t index = i ^ (size_t(1) << slot);
158 
159  LBASSERTINFO(slot >= 0 && slot < nSlots, slot);
160  LBASSERT(slots_[slot]);
161  LBASSERT(index < (1ull << slot));
162  return slots_[slot][index];
163 }
164 
165 template <class T, int32_t nSlots>
166 const T& LFVector<T, nSlots>::operator[](size_t i) const
167 {
168  LBASSERTINFO(size_ > i, size_ << " <= " << i);
169  ++i;
170  const int32_t slot = getIndexOfLastBit(i);
171  const size_t index = i ^ (size_t(1) << slot);
172 
173  LBASSERTINFO(slot >= 0 && slot < nSlots, slot);
174  LBASSERT(slots_[slot]);
175  LBASSERT(index < (1ull << slot));
176  return slots_[slot][index];
177 }
178 
179 #ifdef LB_GCC_4_6_OR_LATER
180 #ifndef LB_GCC_4_8
181 #pragma GCC diagnostic pop
182 #endif
183 #endif
184 
185 template <class T, int32_t nSlots>
187 {
188  LBASSERT(!empty());
189  return slots_[0][0];
190 }
191 
192 template <class T, int32_t nSlots>
194 {
195  LBASSERT(!empty());
196  return (*this)[size_ - 1];
197 }
198 
199 template <class T, int32_t nSlots>
200 void LFVector<T, nSlots>::expand(const size_t newSize, const T& item)
201 {
202  ScopedWrite mutex(lock_);
203  while (newSize > size())
204  push_back_unlocked_(item);
205 }
206 
207 template <class T, int32_t nSlots>
208 void LFVector<T, nSlots>::push_back(const T& item, bool lock)
209 {
210  if (lock)
211  {
212  ScopedWrite mutex(lock_);
213  push_back_unlocked_(item);
214  }
215  else
216  push_back_unlocked_(item);
217 }
218 
219 template <class T, int32_t nSlots>
221 {
222  ScopedWrite mutex(lock_);
223  if (size_ == 0)
224  return;
225  --size_;
226  (*this)[size_] = T(); // not correct for all T? Needed to reset RefPtr
227  trim_();
228 }
229 
230 template <class T, int32_t nSlots>
232 {
233  ScopedWrite mutex(lock_);
234  if (size_ == 0)
235  return false;
236 
237  element = back();
238  --size_;
239  (*this)[size_] = T(); // not correct for all T? Needed to reset RefPtr
240  trim_();
241  return true;
242 }
243 
244 template <class T, int32_t nSlots>
246  typename LFVector<T, nSlots>::iterator pos)
247 {
248  LBASSERT(pos.container_ == this);
249  if (pos.container_ != this || pos.i_ >= size_)
250  return end();
251 
252  ScopedWrite mutex(lock_);
253  --size_;
254 #pragma warning(push)
255 #pragma warning(disable : 4996) // unchecked iterators
256  std::copy(pos + 1, end() + 1, pos);
257 #pragma warning(pop)
258  (*this)[size_] = T(); // correct for all T? Needed to reset RefPtr
259  trim_();
260  return pos;
261 }
262 
263 template <class T, int32_t nSlots>
265  const T& element)
266 {
267  ScopedWrite mutex(lock_);
268  for (size_t i = size_; i != 0; --i)
269  {
270  if ((*this)[i - 1] == element)
271  {
272  --size_;
273  iterator pos(this, i - 1);
274 #pragma warning(push)
275 #pragma warning(disable : 4996) // unchecked iterators
276  std::copy(pos + 1, end() + 1, pos);
277 #pragma warning(pop)
278  (*this)[size_] = 0; // see comment in other erase
279  trim_();
280  return pos;
281  }
282  }
283  return end();
284 }
285 
286 template <class T, int32_t nSlots>
287 void LFVector<T, nSlots>::resize(const size_t newSize, const T& value)
288 {
289  ScopedWrite mutex(lock_);
290  while (size_ > newSize)
291  {
292  --size_;
293  (*this)[size_] = T(); // not correct for all T? Needed to reset RefPtr
294  }
295  trim_();
296 
297  while (size_ < newSize)
298  push_back_unlocked_(value);
299 }
300 
301 template <class T, int32_t nSlots>
303 {
304  ScopedWrite mutex(lock_);
305  while (size_ > 0)
306  {
307  --size_;
308  (*this)[size_] = T(); // Needed to reset RefPtr
309  }
310  for (int32_t i = 0; i < nSlots; ++i)
311  {
312  delete[] slots_[i];
313  slots_[i] = 0;
314  }
315 }
316 
317 template <class T, int32_t nSlots>
318 typename LFVector<T, nSlots>::ScopedWrite LFVector<T, nSlots>::getWriteLock()
319 {
320  lock_.set();
321  return {lock_, std::adopt_lock};
322 }
323 
324 template <class T, int32_t nSlots>
325 template <int32_t fromSlots>
327 {
328  setZero(slots_, nSlots * sizeof(T*));
329 
330  ScopedWrite mutex(from.lock_);
331  for (int32_t i = 0; i < nSlots; ++i)
332  {
333  if (i >= fromSlots || !from.slots_[i]) // done copying
334  {
335  LBASSERTINFO(size_ == from.size_, size_ << " != " << from.size_);
336  return;
337  }
338 
339  const int32_t sz = 1 << i;
340  slots_[i] = new T[sz];
341  for (int32_t j = 0; size_ < from.size_ && j < sz; ++j)
342  {
343  slots_[i][j] = from.slots_[i][j];
344  ++size_;
345  }
346  }
347 }
348 
349 template <class T, int32_t nSlots>
351 {
352  const size_t i = size_ + 1;
353  const int32_t slot = getIndexOfLastBit(i);
354  if (slot < 0 || slot >= nSlots)
355  {
356  LBASSERTINFO(slot >= 0 && slot < nSlots, slot);
357  LBTHROW(std::runtime_error("LFVector full"));
358  }
359 
360  const size_t sz = (size_t(1) << slot);
361 
362  if (!slots_[slot])
363  slots_[slot] = new T[sz];
364 
365  const ssize_t index = i ^ sz;
366  slots_[slot][index] = item;
367  ++size_;
368 }
369 
370 template <class T, int32_t nSlots>
372 {
373  const int32_t nextSlot = getIndexOfLastBit(size_ + 1) + 1;
374  if (nextSlot < nSlots && slots_[nextSlot])
375  {
376  delete[] slots_[nextSlot]; // delete next slot (keep a spare)
377  slots_[nextSlot] = 0;
378  }
379 }
380 
381 template <class T, int32_t nSlots>
383  const
384 {
385  return const_iterator(this, 0);
386 }
387 
388 template <class T, int32_t nSlots>
390  const
391 {
392  return const_iterator(this, size_);
393 }
394 
395 template <class T, int32_t nSlots>
397 {
398  return iterator(this, 0);
399 }
400 
401 template <class T, int32_t nSlots>
403 {
404  return iterator(this, size_);
405 }
406 
408 template <class T, int32_t nSlots>
409 template <class Archive>
410 inline void LFVector<T, nSlots>::save(Archive& ar,
411  const unsigned int /*version*/) const
412 {
413  ar << size_;
414  for (size_t i = 0; i < size_; ++i)
415  ar << operator[](i);
416 }
417 
418 template <class T, int32_t nSlots>
419 template <class Archive>
420 inline void LFVector<T, nSlots>::load(Archive& ar,
421  const unsigned int /*version*/)
422 {
423  size_t newSize = 0;
424  ar >> newSize;
425  expand(newSize);
426  LBASSERT(size_ == newSize);
427 
428  for (size_t i = 0; i < size_; ++i)
429  ar >> operator[](i);
430 }
433 template <class T>
434 std::ostream& operator<<(std::ostream& os, const LFVector<T>& v)
435 {
436  os << className(&v) << " size " << v.size() << " [ ";
437  for (typename LFVector<T>::const_iterator i = v.begin(); i != v.end(); ++i)
438  {
439  if (i.getPosition() > 255)
440  {
441  os << "... ";
442  break;
443  }
444  os << (*i) << ' ';
445  }
446  return os << ']' << std::endl;
447 }
448 }
std::string className(const T &object)
Print the RTTI name of the given class.
Definition: debug.h:75
An iterator for LFVector.
void set()
Acquire the lock exclusively.
bool empty() const
Definition: lfVector.h:87
size_t size() const
Definition: lfVector.h:88
STL-like vector implementation providing certain thread-safety guarantees.
Definition: lfVector.h:54
int32_t getIndexOfLastBit(T value)
LFVector & operator=(const LFVector &from)
Definition: lfVector.ipp:89
T & operator[](size_t i)
Definition: lfVector.ipp:151
void push_back(const T &item, bool lock=true)
Add an element to the vector.
Definition: lfVector.ipp:208
ScopedWrite getWriteLock()
Definition: lfVector.ipp:318
LFVectorIterator< LFVector< T, nSlots >, T > iterator
Iterator over the vector elements.
Definition: lfVector.h:102
static void setZero(void *ptr, const size_t size)
OS-independent call to bzero(3).
Definition: os.h:73
LFVectorIterator< const LFVector< T, nSlots >, const T > const_iterator
Iterator over the const vector elements.
Definition: lfVector.h:105
bool operator==(const LFVector &rhs) const
Definition: lfVector.ipp:124
void pop_back()
Remove the last element (STL version).
Definition: lfVector.ipp:220
void clear()
Clear the vector and all storage.
Definition: lfVector.ipp:302
const_iterator end() const
Definition: lfVector.ipp:389
Abstraction layer and common utilities for multi-threaded programming.
Definition: algorithm.h:29
void resize(const size_t size, const T &value=T())
Resize the vector.
Definition: lfVector.ipp:287
#define LBTHROW(exc)
Log a std::exception if topic LOG_EXCEPTION is set before throwing exception.
Definition: log.h:230
void expand(const size_t newSize, const T &item=T())
Resize the vector to at least the given size.
Definition: lfVector.ipp:200
const_iterator begin() const
Definition: lfVector.ipp:382
iterator erase(typename LFVector< T, nSlots >::iterator pos)
Remove an element.
Definition: lfVector.ipp:245