Line data Source code
1 :
2 : /* Copyright (c) 2011-2013, 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 191229644 : for( size_t j = 0; size_ < from.size_ && j < sz ; ++j )
107 : {
108 191215616 : slots_[ i ][ j ] = from.slots_[ i ][ j ];
109 191215616 : ++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 142218825 : T& LFVector< T, nSlots >::operator[]( size_t i )
152 : {
153 : // one beyond end is possible when called by erase
154 142218825 : LBASSERTINFO( size_ >= i, size_ << " < " << i );
155 146164805 : ++i;
156 146164805 : const int32_t slot = getIndexOfLastBit( i );
157 145396625 : const size_t index = i ^ ( size_t( 1 )<<slot );
158 :
159 145396625 : LBASSERTINFO( slot >=0 && slot < nSlots, slot );
160 145601790 : LBASSERT( slots_[ slot ] );
161 141955449 : LBASSERT( index < (1ull<<slot) );
162 138045413 : 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 7199963 : T& LFVector< T, nSlots >::back()
194 : {
195 7199963 : LBASSERT( !empty( ));
196 7199963 : 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 9200332 : void LFVector< T, nSlots >::push_back( const T& item, bool lock )
209 : {
210 9200332 : ScopedWrite mutex( lock ? &lock_ : 0 );
211 9200344 : push_back_unlocked_( item );
212 9200344 : }
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 7200336 : bool LFVector< T, nSlots >::pop_back( T& element )
227 : {
228 7200336 : ScopedWrite mutex( lock_ );
229 7200341 : if( size_ == 0 )
230 378 : return false;
231 :
232 7199963 : element = back();
233 7199963 : --size_;
234 7199963 : (*this)[size_] = T(); // not correct for all T? Needed to reset RefPtr
235 7199963 : trim_();
236 7199963 : 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 9200353 : void LFVector< T, nSlots >::push_back_unlocked_( const T& item )
344 : {
345 9200353 : const size_t i = size_ + 1;
346 9200353 : const int32_t slot = getIndexOfLastBit( i );
347 9200353 : const size_t sz = ( size_t( 1 ) << slot );
348 :
349 9200353 : LBASSERTINFO( slot >= 0 && slot < nSlots, slot );
350 9200353 : if( !slots_[ slot ] )
351 672 : slots_[ slot ] = new T[ sz ];
352 :
353 9200353 : const ssize_t index = i ^ sz;
354 9200353 : slots_[ slot ][ index ] = item;
355 9200353 : ++size_;
356 9200353 : }
357 :
358 : template< class T, int32_t nSlots >
359 9200344 : void LFVector< T, nSlots >::trim_()
360 : {
361 9200344 : const int32_t nextSlot = getIndexOfLastBit( size_+1 ) + 1;
362 9200344 : if( nextSlot < nSlots && slots_[ nextSlot ] )
363 : {
364 632 : delete [] slots_[ nextSlot ]; // delete next slot (keep a spare)
365 632 : slots_[ nextSlot ] = 0;
366 : }
367 9200344 : }
368 :
369 : template< class T, int32_t nSlots > inline typename
370 0 : LFVector< T, nSlots >::const_iterator LFVector< T, nSlots >::begin() const
371 : {
372 0 : return const_iterator( this, 0 );
373 : }
374 :
375 : template< class T, int32_t nSlots > inline typename
376 0 : LFVector< T, nSlots >::const_iterator LFVector< T, nSlots >::end() const
377 : {
378 0 : return const_iterator( this, size_ );
379 : }
380 :
381 : template< class T, int32_t nSlots > inline typename
382 383 : LFVector< T, nSlots >::iterator LFVector< T, nSlots >::begin()
383 : {
384 383 : return iterator( this, 0 );
385 : }
386 :
387 : template< class T, int32_t nSlots > inline typename
388 2000759 : LFVector< T, nSlots >::iterator LFVector< T, nSlots >::end()
389 : {
390 2000759 : return iterator( this, size_ );
391 : }
392 :
393 : /** @cond IGNORE */
394 : template< class T, int32_t nSlots > template< class Archive >
395 : inline void LFVector< T, nSlots >::save( Archive& ar,
396 : const unsigned int /*version*/ ) const
397 : {
398 : ar << size_;
399 : for( size_t i = 0; i < size_; ++i )
400 : ar << operator[](i);
401 : }
402 :
403 : template< class T, int32_t nSlots > template< class Archive >
404 : inline void LFVector< T, nSlots >::load( Archive& ar,
405 : const unsigned int /*version*/ )
406 : {
407 : size_t newSize = 0;
408 : ar >> newSize;
409 : expand( newSize );
410 : LBASSERT( size_ == newSize );
411 :
412 : for( size_t i = 0; i < size_; ++i )
413 : ar >> operator[](i);
414 : }
415 : /** @endcond */
416 :
417 : template< class T >
418 0 : std::ostream& operator << ( std::ostream& os, const LFVector< T >& v )
419 : {
420 0 : os << className( &v ) << " size " << v.size() << " [ ";
421 0 : for(typename LFVector< T >::const_iterator i = v.begin(); i != v.end(); ++i)
422 : {
423 0 : if( i.getPosition() > 255 )
424 : {
425 0 : os << "... ";
426 0 : break;
427 : }
428 0 : os << (*i) << ' ';
429 : }
430 0 : return os << ']' << std::endl;
431 : }
432 :
433 : }
|
