Lunchbox  1.15.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 
27 template< class T, int32_t nSlots >
29  : size_( 0 )
30 {
31  setZero( slots_, nSlots * sizeof( T* ));
32 }
33 
34 template< class T, int32_t nSlots >
36  : size_( n )
37 {
38  LBASSERT( n != 0 );
39  setZero( slots_, nSlots * sizeof( T* ));
40  const int32_t s = getIndexOfLastBit( uint64_t( n ));
41  for( int32_t i = 0; i <= s; ++i )
42  slots_[ i ] = new T[ 1<<i ];
43 }
44 
45 template< class T, int32_t nSlots >
46 LFVector< T, nSlots >::LFVector( const size_t n, const T& t )
47  : size_( 0 )
48 {
49  LBASSERT( n != 0 );
50  setZero( slots_, nSlots * sizeof( T* ));
51  const int32_t s = getIndexOfLastBit( uint64_t( n ));
52  for( size_t i = 0; i <= size_t(s); ++i )
53  {
54  const size_t sz = 1<<i;
55  slots_[ i ] = new T[ sz ];
56  for( size_t j = 0; size_ < n && j < sz ; ++j )
57  {
58  slots_[ i ][ j ] = t;
59  ++size_;
60  }
61  }
62  LBASSERTINFO( size_ == n, size_ << " != " << n );
63 }
64 
65 template< class T, int32_t nSlots >
67  : size_( 0 )
68  , lock_()
69 {
70  assign_( from );
71 }
72 
73 template< class T, int32_t nSlots >
74 template< int32_t fromSlots >
76  : size_( 0 )
77  , lock_()
78 {
79  assign_( from );
80 }
81 
82 template< class T, int32_t nSlots >
84 {
85  for( size_t i=0; i < nSlots; ++i )
86  delete [] slots_[i];
87 }
88 
89 template< class T, int32_t nSlots > LFVector< T, nSlots >&
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 = 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  ScopedWrite mutex( lock ? &lock_ : 0 );
211  push_back_unlocked_( item );
212 }
213 
214 template< class T, int32_t nSlots >
216 {
217  ScopedWrite mutex( lock_ );
218  if( size_ == 0 )
219  return;
220  --size_;
221  (*this)[size_] = T(); // not correct for all T? Needed to reset RefPtr
222  trim_();
223 }
224 
225 template< class T, int32_t nSlots >
227 {
228  ScopedWrite mutex( lock_ );
229  if( size_ == 0 )
230  return false;
231 
232  element = back();
233  --size_;
234  (*this)[size_] = T(); // not correct for all T? Needed to reset RefPtr
235  trim_();
236  return true;
237 }
238 
239 template< class T, int32_t nSlots > typename LFVector< T, nSlots >::iterator
241 {
242  LBASSERT( pos.container_ == this );
243  if( pos.container_ != this || pos.i_ >= size_ )
244  return end();
245 
246  ScopedWrite mutex( lock_ );
247  --size_;
248 #pragma warning (push)
249 #pragma warning (disable: 4996) // unchecked iterators
250  std::copy( pos+1, end()+1, pos );
251 #pragma warning (pop)
252  (*this)[size_] = T(); // correct for all T? Needed to reset RefPtr
253  trim_();
254  return pos;
255 }
256 
257 template< class T, int32_t nSlots > typename LFVector< T, nSlots >::iterator
258 LFVector< T, nSlots >::erase( const T& element )
259 {
260  ScopedWrite mutex( lock_ );
261  for( size_t i = size_; i != 0 ; --i )
262  {
263  if( (*this)[i-1] == element )
264  {
265  --size_;
266  iterator pos( this, i-1 );
267 #pragma warning (push)
268 #pragma warning (disable: 4996) // unchecked iterators
269  std::copy( pos+1, end()+1, pos );
270 #pragma warning (pop)
271  (*this)[size_] = 0; // see comment in other erase
272  trim_();
273  return pos;
274  }
275  }
276  return end();
277 }
278 
279 template< class T, int32_t nSlots >
280 void LFVector< T, nSlots >::resize( const size_t newSize, const T& value )
281 {
282  ScopedWrite mutex( lock_ );
283  while( size_ > newSize )
284  {
285  --size_;
286  (*this)[size_] = T(); // not correct for all T? Needed to reset RefPtr
287  }
288  trim_();
289 
290  while( size_ < newSize )
291  push_back_unlocked_( value );
292 }
293 
294 template< class T, int32_t nSlots >
296 {
297  ScopedWrite mutex( lock_ );
298  while( size_ > 0 )
299  {
300  --size_;
301  (*this)[size_] = T(); // Needed to reset RefPtr
302  }
303  for( int32_t i = 0; i < nSlots; ++i )
304  {
305  delete [] slots_[ i ];
306  slots_[ i ] = 0;
307  }
308 }
309 
310 template< class T, int32_t nSlots > typename LFVector< T, nSlots >::ScopedWrite
312 {
313  return ScopedWrite( lock_ );
314 }
315 
316 template< class T, int32_t nSlots >
317 template< int32_t fromSlots >
319 {
320  setZero( slots_, nSlots * sizeof( T* ));
321 
322  ScopedWrite mutex( from.lock_ );
323  for( int32_t i = 0; i < nSlots; ++i )
324  {
325  if( i >= fromSlots || !from.slots_[i] ) // done copying
326  {
327  LBASSERTINFO( size_ == from.size_,
328  size_ << " != " << from.size_ );
329  return;
330  }
331 
332  const int32_t sz = 1<<i;
333  slots_[ i ] = new T[ sz ];
334  for( int32_t j = 0; size_ < from.size_ && j < sz ; ++j )
335  {
336  slots_[ i ][ j ] = from.slots_[ i ][ j ];
337  ++size_;
338  }
339  }
340 }
341 
342 template< class T, int32_t nSlots >
343 void LFVector< T, nSlots >::push_back_unlocked_( const T& item )
344 {
345  const size_t i = size_ + 1;
346  const int32_t slot = getIndexOfLastBit( i );
347  if( slot < 0 || slot >= nSlots )
348  {
349  LBASSERTINFO( slot >= 0 && slot < nSlots, slot );
350  LBTHROW( std::runtime_error( "LFVector full" ));
351  }
352 
353  const size_t sz = ( size_t( 1 ) << slot );
354 
355  if( !slots_[ slot ] )
356  slots_[ slot ] = new T[ sz ];
357 
358  const ssize_t index = i ^ sz;
359  slots_[ slot ][ index ] = item;
360  ++size_;
361 }
362 
363 template< class T, int32_t nSlots >
365 {
366  const int32_t nextSlot = getIndexOfLastBit( size_+1 ) + 1;
367  if( nextSlot < nSlots && slots_[ nextSlot ] )
368  {
369  delete [] slots_[ nextSlot ]; // delete next slot (keep a spare)
370  slots_[ nextSlot ] = 0;
371  }
372 }
373 
374 template< class T, int32_t nSlots > inline typename
376 {
377  return const_iterator( this, 0 );
378 }
379 
380 template< class T, int32_t nSlots > inline typename
382 {
383  return const_iterator( this, size_ );
384 }
385 
386 template< class T, int32_t nSlots > inline typename
388 {
389  return iterator( this, 0 );
390 }
391 
392 template< class T, int32_t nSlots > inline typename
394 {
395  return iterator( this, size_ );
396 }
397 
399 template< class T, int32_t nSlots > template< class Archive >
400 inline void LFVector< T, nSlots >::save( Archive& ar,
401  const unsigned int /*version*/ ) const
402 {
403  ar << size_;
404  for( size_t i = 0; i < size_; ++i )
405  ar << operator[](i);
406 }
407 
408 template< class T, int32_t nSlots > template< class Archive >
409 inline void LFVector< T, nSlots >::load( Archive& ar,
410  const unsigned int /*version*/ )
411 {
412  size_t newSize = 0;
413  ar >> newSize;
414  expand( newSize );
415  LBASSERT( size_ == newSize );
416 
417  for( size_t i = 0; i < size_; ++i )
418  ar >> operator[](i);
419 }
422 template< class T >
423 std::ostream& operator << ( std::ostream& os, const LFVector< T >& v )
424 {
425  os << className( &v ) << " size " << v.size() << " [ ";
426  for(typename LFVector< T >::const_iterator i = v.begin(); i != v.end(); ++i)
427  {
428  if( i.getPosition() > 255 )
429  {
430  os << "... ";
431  break;
432  }
433  os << (*i) << ' ';
434  }
435  return os << ']' << std::endl;
436 }
437 
438 }
std::string className(const T &object)
Print the RTTI name of the given class.
Definition: debug.h:74
An iterator for LFVector.
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:53
int32_t getIndexOfLastBit(T value)
LFVector & operator=(const LFVector &from)
Definition: lfVector.ipp:90
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:311
static void setZero(void *ptr, const size_t size)
OS-independent call to bzero(3).
Definition: os.h:74
LFVectorIterator< const LFVector< T, nSlots >, const T > const_iterator
Iterator over the const vector elements.
Definition: lfVector.h:106
bool operator==(const LFVector &rhs) const
Definition: lfVector.ipp:124
#define LBTHROW(exc)
Log a std::exception if topic LOG_EXCEPTION is set before throwing exception.
Definition: log.h:218
void pop_back()
Remove the last element (STL version).
Definition: lfVector.ipp:215
void clear()
Clear the vector and all storage.
Definition: lfVector.ipp:295
const_iterator end() const
Definition: lfVector.ipp:381
Abstraction layer and common utilities for multi-threaded programming.
Definition: algorithm.h:32
void resize(const size_t size, const T &value=T())
Resize the vector.
Definition: lfVector.ipp:280
void expand(const size_t newSize, const T &item=T())
Resize the vector to at least the given size.
Definition: lfVector.ipp:200
A scoped mutex.
Definition: scopedMutex.h:59
const_iterator begin() const
Definition: lfVector.ipp:375
LFVectorIterator< LFVector< T, nSlots >, T > iterator
Iterator over the vector elements.
Definition: lfVector.h:103
iterator erase(typename LFVector< T, nSlots >::iterator pos)
Remove an element.
Definition: lfVector.ipp:240