LCOV - code coverage report
Current view: top level - lunchbox - lfVector.ipp (source / functions) Hit Total Coverage
Test: lcov2.info Lines: 104 122 85.2 %
Date: 2014-10-01 Functions: 15 18 83.3 %

          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             : }

Generated by: LCOV version 1.10