Line data Source code
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 >
28 425 : LFVector< T, nSlots >::LFVector()
29 425 : : size_( 0 )
30 : {
31 425 : setZero( slots_, nSlots * sizeof( T* ));
32 425 : }
33 :
34 : template< class T, int32_t nSlots >
35 : LFVector< T, nSlots >::LFVector( const size_t n )
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( int32_t i = 0; i <= 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 >
66 : LFVector< T, nSlots >::LFVector( const LFVector& from )
67 : : size_( 0 )
68 : , lock_()
69 : {
70 : assign_( from );
71 : }
72 :
73 : template< class T, int32_t nSlots >
74 : template< int32_t fromSlots >
75 : LFVector< T, nSlots >::LFVector( const LFVector< T, fromSlots >& from )
76 : : size_( 0 )
77 : , lock_()
78 : {
79 : assign_( from );
80 : }
81 :
82 : template< class T, int32_t nSlots >
83 425 : LFVector< T, nSlots >::~LFVector()
84 : {
85 14025 : for( size_t i=0; i < nSlots; ++i )
86 13600 : delete [] slots_[i];
87 425 : }
88 :
89 : template< class T, int32_t nSlots > LFVector< T, nSlots >&
90 776 : LFVector< T, nSlots >::operator = ( const LFVector< T, nSlots >& from )
91 : {
92 776 : if( &from == this )
93 0 : return *this;
94 :
95 776 : ScopedWrite mutex1( lock_ ); // DEADLOCK when doing a=b and b=a
96 1552 : ScopedWrite mutex2( from.lock_ ); // consider trySet/yield approach
97 776 : size_ = 0;
98 25608 : for( int32_t i = 0; i < nSlots; ++i )
99 : {
100 24832 : if( from.slots_[i] )
101 : {
102 14028 : const size_t sz = 1<<i;
103 14028 : if( !slots_[ i ] )
104 7014 : slots_[ i ] = new T[ sz ];
105 :
106 191229652 : for( size_t j = 0; size_ < from.size_ && j < sz ; ++j )
107 : {
108 191215624 : slots_[ i ][ j ] = from.slots_[ i ][ j ];
109 191215624 : ++size_;
110 : }
111 : }
112 10804 : else if( slots_[ i ] ) // done copying, free unneeded slots
113 : {
114 0 : delete [] slots_[ i ];
115 0 : slots_[ i ] = 0;
116 : }
117 : }
118 :
119 776 : LBASSERTINFO( size_ == from.size_, size_ << " != " << from.size_ );
120 1552 : return *this;
121 : }
122 :
123 : template< class T, int32_t nSlots >
124 : bool LFVector< T, nSlots >::operator == ( const LFVector& rhs ) const
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 >
151 134735578 : T& LFVector< T, nSlots >::operator[]( size_t i )
152 : {
153 : // one beyond end is possible when called by erase
154 134735578 : LBASSERTINFO( size_ >= i, size_ << " < " << i );
155 137791002 : ++i;
156 137791002 : const int32_t slot = getIndexOfLastBit( i );
157 138641811 : const size_t index = i ^ ( size_t( 1 )<<slot );
158 :
159 138641811 : LBASSERTINFO( slot >=0 && slot < nSlots, slot );
160 136068919 : LBASSERT( slots_[ slot ] );
161 132132818 : LBASSERT( index < (1ull<<slot) );
162 126381042 : return slots_[ slot ][ index ];
163 : }
164 :
165 : template< class T, int32_t nSlots >
166 2000000 : const T& LFVector< T, nSlots >::operator[]( size_t i ) const
167 : {
168 2000000 : LBASSERTINFO( size_ > i, size_ << " <= " << i );
169 2000000 : ++i;
170 2000000 : const int32_t slot = getIndexOfLastBit( i );
171 2000000 : const size_t index = i ^ ( size_t( 1 )<<slot );
172 :
173 2000000 : LBASSERTINFO( slot >=0 && slot < nSlots, slot );
174 2000000 : LBASSERT( slots_[ slot ] );
175 2000000 : LBASSERT( index < (1ull<<slot) );
176 2000000 : 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 >
186 : T& LFVector< T, nSlots >::front()
187 : {
188 : LBASSERT( !empty( ));
189 : return slots_[ 0 ][ 0 ];
190 : }
191 :
192 : template< class T, int32_t nSlots >
193 7199964 : T& LFVector< T, nSlots >::back()
194 : {
195 7199964 : LBASSERT( !empty( ));
196 7199964 : 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 9200202 : void LFVector< T, nSlots >::push_back( const T& item, bool lock )
209 : {
210 9200202 : ScopedWrite mutex( lock ? &lock_ : 0 );
211 9200345 : push_back_unlocked_( item );
212 9200340 : }
213 :
214 : template< class T, int32_t nSlots >
215 1999999 : void LFVector< T, nSlots >::pop_back()
216 : {
217 1999999 : ScopedWrite mutex( lock_ );
218 1999999 : if( size_ == 0 )
219 1999999 : return;
220 1999999 : --size_;
221 1999999 : (*this)[size_] = T(); // not correct for all T? Needed to reset RefPtr
222 1999999 : trim_();
223 : }
224 :
225 : template< class T, int32_t nSlots >
226 7200313 : bool LFVector< T, nSlots >::pop_back( T& element )
227 : {
228 7200313 : ScopedWrite mutex( lock_ );
229 7200342 : if( size_ == 0 )
230 378 : return false;
231 :
232 7199964 : element = back();
233 7199964 : --size_;
234 7199964 : (*this)[size_] = T(); // not correct for all T? Needed to reset RefPtr
235 7199964 : trim_();
236 7199964 : return true;
237 : }
238 :
239 : template< class T, int32_t nSlots > typename LFVector< T, nSlots >::iterator
240 380 : LFVector< T, nSlots >::erase( typename LFVector< T, nSlots >::iterator pos )
241 : {
242 380 : LBASSERT( pos.container_ == this );
243 380 : if( pos.container_ != this || pos.i_ >= size_ )
244 0 : return end();
245 :
246 380 : ScopedWrite mutex( lock_ );
247 380 : --size_;
248 : #pragma warning (push)
249 : #pragma warning (disable: 4996) // unchecked iterators
250 380 : std::copy( pos+1, end()+1, pos );
251 : #pragma warning (pop)
252 380 : (*this)[size_] = T(); // correct for all T? Needed to reset RefPtr
253 380 : trim_();
254 380 : 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 2 : void LFVector< T, nSlots >::resize( const size_t newSize, const T& value )
281 : {
282 2 : ScopedWrite mutex( lock_ );
283 5 : while( size_ > newSize )
284 : {
285 1 : --size_;
286 1 : (*this)[size_] = T(); // not correct for all T? Needed to reset RefPtr
287 : }
288 2 : trim_();
289 :
290 13 : while( size_ < newSize )
291 11 : push_back_unlocked_( value );
292 2 : }
293 :
294 : template< class T, int32_t nSlots >
295 : void LFVector< T, nSlots >::clear()
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
311 : LFVector< T, nSlots >::getWriteLock()
312 : {
313 : return ScopedWrite( lock_ );
314 : }
315 :
316 : template< class T, int32_t nSlots >
317 : template< int32_t fromSlots >
318 : void LFVector< T, nSlots >::assign_( const LFVector< T, fromSlots >& from )
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 size_t sz = 1<<i;
333 : slots_[ i ] = new T[ sz ];
334 : for( size_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 9200354 : void LFVector< T, nSlots >::push_back_unlocked_( const T& item )
344 : {
345 9200354 : const size_t i = size_ + 1;
346 9200354 : const int32_t slot = getIndexOfLastBit( i );
347 9200354 : if( slot < 0 || slot >= nSlots )
348 : {
349 0 : LBASSERTINFO( slot >= 0 && slot < nSlots, slot );
350 0 : LBTHROW( std::runtime_error( "LFVector full" ));
351 : }
352 :
353 9200354 : const size_t sz = ( size_t( 1 ) << slot );
354 :
355 9200354 : if( !slots_[ slot ] )
356 672 : slots_[ slot ] = new T[ sz ];
357 :
358 9200354 : const ssize_t index = i ^ sz;
359 9200354 : slots_[ slot ][ index ] = item;
360 9200354 : ++size_;
361 9200354 : }
362 :
363 : template< class T, int32_t nSlots >
364 9200345 : void LFVector< T, nSlots >::trim_()
365 : {
366 9200345 : const int32_t nextSlot = getIndexOfLastBit( size_+1 ) + 1;
367 9200345 : if( nextSlot < nSlots && slots_[ nextSlot ] )
368 : {
369 632 : delete [] slots_[ nextSlot ]; // delete next slot (keep a spare)
370 632 : slots_[ nextSlot ] = 0;
371 : }
372 9200345 : }
373 :
374 : template< class T, int32_t nSlots > inline typename
375 0 : LFVector< T, nSlots >::const_iterator LFVector< T, nSlots >::begin() const
376 : {
377 0 : return const_iterator( this, 0 );
378 : }
379 :
380 : template< class T, int32_t nSlots > inline typename
381 0 : LFVector< T, nSlots >::const_iterator LFVector< T, nSlots >::end() const
382 : {
383 0 : return const_iterator( this, size_ );
384 : }
385 :
386 : template< class T, int32_t nSlots > inline typename
387 383 : LFVector< T, nSlots >::iterator LFVector< T, nSlots >::begin()
388 : {
389 383 : return iterator( this, 0 );
390 : }
391 :
392 : template< class T, int32_t nSlots > inline typename
393 2000759 : LFVector< T, nSlots >::iterator LFVector< T, nSlots >::end()
394 : {
395 2000759 : return iterator( this, size_ );
396 : }
397 :
398 : /** @cond IGNORE */
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 : }
420 : /** @endcond */
421 :
422 : template< class T >
423 0 : std::ostream& operator << ( std::ostream& os, const LFVector< T >& v )
424 : {
425 0 : os << className( &v ) << " size " << v.size() << " [ ";
426 0 : for(typename LFVector< T >::const_iterator i = v.begin(); i != v.end(); ++i)
427 : {
428 0 : if( i.getPosition() > 255 )
429 : {
430 0 : os << "... ";
431 0 : break;
432 : }
433 0 : os << (*i) << ' ';
434 : }
435 0 : return os << ']' << std::endl;
436 : }
437 :
438 : }
|
