Lunchbox  1.4.0
lfVector.h
00001 
00002 /* Copyright (c) 2011-2012, EPFL/Blue Brain Project
00003  *                          Stefan Eilemann <stefan.eilemann@epfl.ch> 
00004  *
00005  * This file is part of Lunchbox <https://github.com/BlueBrain/Lunchbox>
00006  *
00007  * This library is free software; you can redistribute it and/or modify it under
00008  * the terms of the GNU Lesser General Public License version 3.0 as published
00009  * by the Free Software Foundation.
00010  *  
00011  * This library is distributed in the hope that it will be useful, but WITHOUT
00012  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
00013  * FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more
00014  * details.
00015  * 
00016  * You should have received a copy of the GNU Lesser General Public License
00017  * along with this library; if not, write to the Free Software Foundation, Inc.,
00018  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
00019  */
00020 
00021 #ifndef LUNCHBOX_LFVECTOR_H
00022 #define LUNCHBOX_LFVECTOR_H
00023 
00024 #include <lunchbox/bitOperation.h> // used inline
00025 #include <lunchbox/debug.h> // used inline
00026 #include <lunchbox/scopedMutex.h> // member
00027 #include <lunchbox/serializable.h>
00028 #include <lunchbox/spinLock.h> // member
00029 #include <algorithm> // used inline
00030 
00031 
00032 #ifdef _WIN32
00033 #  define lb_bzero( ptr, size ) memset( ptr, 0, size )
00034 #else
00035 #  include <strings.h>
00036 #  define lb_bzero bzero
00037 #endif
00038 
00039 namespace lunchbox
00040 {
00041 
00057 template< class T, int32_t nSlots = 32 > class LFVector
00058 {
00059     typedef ScopedFastWrite ScopedWrite;
00060 
00061 public:
00063     LFVector() : size_( 0 ) { lb_bzero( slots_, nSlots * sizeof( T* )); }
00064 
00066     explicit LFVector( const size_t n ) : size_( n )
00067         {
00068             LBASSERT( n != 0 );
00069             lb_bzero( slots_, nSlots * sizeof( T* ));
00070             const int32_t s = getIndexOfLastBit( uint64_t( n ));
00071             for( int32_t i = 0; i <= s; ++i )
00072                 slots_[ i ] = new T[ 1<<i ];
00073         }
00074 
00076     explicit LFVector( const size_t n, const T& t ) : size_( 0 )
00077         {
00078             LBASSERT( n != 0 );
00079             lb_bzero( slots_, nSlots * sizeof( T* ));
00080             const int32_t s = getIndexOfLastBit( uint64_t( n ));
00081             for( int32_t i = 0; i <= s; ++i )
00082             {
00083                 const size_t sz = 1<<i;
00084                 slots_[ i ] = new T[ sz ];
00085                 for( size_t j = 0; size_ < n && j < sz ; ++j )
00086                 {
00087                     slots_[ i ][ j ] = t;
00088                     ++size_;
00089                 }
00090             }
00091             LBASSERTINFO( size_ == n, size_ << " != " << n );
00092         }
00093 
00095     explicit LFVector( const LFVector& from ) : size_( 0 ), lock_()
00096         { assign_( from ); }
00097 
00099     template< int32_t fromSlots >
00100     explicit LFVector( const LFVector< T, fromSlots >& from )
00101             : size_( 0 ), lock_()
00102         { assign_( from ); }
00103 
00105     ~LFVector()
00106         {
00107             for( size_t i=0; i < nSlots; ++i )
00108                 delete [] slots_[i];
00109         }
00110 
00112     LFVector& operator = ( const LFVector& from )
00113         {
00114             if( &from == this )
00115                 return *this;
00116 
00117             ScopedWrite mutex1( lock_ ); // DEADLOCK when doing a=b and b=a
00118             ScopedWrite mutex2( from.lock_ ); // consider trySet/yield approach
00119             size_ = 0;
00120             for( int32_t i = 0; i < nSlots; ++i )
00121             {
00122                 if( from.slots_[i] )
00123                 {
00124                     const size_t sz = 1<<i;
00125                     if( !slots_[ i ] )
00126                         slots_[ i ] = new T[ sz ];
00127 
00128                     for( size_t j = 0; size_ < from.size_ && j < sz ; ++j )
00129                     {
00130                         slots_[ i ][ j ] = from.slots_[ i ][ j ];
00131                         ++size_;
00132                     }
00133                 }
00134                 else if( slots_[ i ] ) // done copying, free unneeded slots
00135                 {
00136                     delete [] slots_[ i ];
00137                     slots_[ i ] = 0;
00138                 }
00139             }
00140 
00141             LBASSERTINFO( size_ == from.size_, size_ << " != " << from.size_ );
00142             return *this;
00143         }
00144 
00146     bool operator == ( const LFVector& rhs ) const
00147     {
00148         if( &rhs == this )
00149             return true;
00150 
00151         if( size() != rhs.size() )
00152             return false;
00153 
00154         const_iterator it = begin();
00155         const_iterator rhsIt = rhs.begin();
00156         for( ; it != end() && rhsIt != end(); ++it, ++rhsIt )
00157         {
00158             if( *it != *rhsIt )
00159                 return false;
00160         }
00161 
00162         return true;
00163     }
00164 
00166     bool operator != ( const LFVector& rhs ) const { return !(*this == rhs); }
00167 
00168     bool empty() const { return size_ == 0; } 
00169     size_t size() const { return size_; } 
00170 
00172     T& operator[]( size_t i )
00173         {
00174             // one beyond end is possible when called by erase
00175             LBASSERTINFO( size_ >= i, size_ << " < " << i );
00176             ++i;
00177             const int32_t slot = getIndexOfLastBit( i );
00178             const size_t index = i ^ ( size_t( 1 )<<slot );
00179 
00180             LBASSERT( slots_[ slot ] );
00181             return slots_[ slot ][ index ];
00182         }
00183 
00185     const T& operator[]( size_t i ) const
00186         {
00187             LBASSERTINFO( size_ > i, size_ << " <= " << i );
00188             ++i;
00189             const int32_t slot = getIndexOfLastBit( i );
00190             const size_t index = i ^ ( size_t( 1 )<<slot );
00191 
00192             LBASSERT( slots_[ slot ] );
00193             return slots_[ slot ][ index ];
00194         }
00195 
00197     T& front()
00198         {
00199             LBASSERT( !empty( ));
00200             return slots_[ 0 ][ 0 ];
00201         }
00202 
00204     T& back()
00205         {
00206             LBASSERT( !empty( ));
00207             return (*this)[ size_ - 1 ];
00208         }
00209 
00211     typedef LFVectorIterator< LFVector< T >, T > iterator;
00213     typedef LFVectorIterator< const LFVector< T >, const T > const_iterator;
00214 
00215     const_iterator begin() const; 
00216     const_iterator end() const; 
00217     iterator begin(); 
00218     iterator end(); 
00219 
00236     void expand( const size_t newSize, const T& item = T( ))
00237         {
00238             ScopedWrite mutex( lock_ );
00239             while( newSize > size( ))
00240                 push_back_unlocked_( item );
00241         }
00242 
00254     void push_back( const T& item )
00255         {
00256             ScopedWrite mutex( lock_ );
00257             push_back_unlocked_( item );
00258         }
00259 
00268     void pop_back()
00269         {
00270             ScopedWrite mutex( lock_ );
00271             if( size_ == 0 )
00272                 return;
00273             --size_;
00274             (*this)[size_] = 0; // not correct for all T? Needed to reset RefPtr
00275             trim_();
00276         }
00277 
00291     bool pop_back( T& element )
00292         {
00293             ScopedWrite mutex( lock_ );
00294             if( size_ == 0 )
00295                 return false;
00296 
00297             element = back();
00298             --size_;
00299             (*this)[size_] = 0; // not correct for all T? Needed to reset RefPtr
00300             trim_();
00301             return true;
00302         }
00303 
00317     iterator erase( iterator pos )
00318         {
00319             LBASSERT( pos.container_ == this );
00320             if( pos.container_ != this || pos.i_ >= size_ )
00321                 return end();
00322 
00323             ScopedWrite mutex( lock_ );
00324             --size_;
00325 #pragma warning (push)
00326 #pragma warning (disable: 4996) // unchecked iterators
00327             std::copy( pos+1, end()+1, pos );
00328 #pragma warning (pop)
00329             (*this)[size_] = T(); // correct for all T? Needed to reset RefPtr
00330             trim_();
00331             return pos;
00332         }
00333 
00346     iterator erase( const T& element )
00347         {
00348             ScopedWrite mutex( lock_ );
00349             for( size_t i = size_; i != 0 ; --i )
00350             {
00351                 if( (*this)[i-1] == element )
00352                 {
00353                     --size_;
00354                     iterator pos( this, i-1 );
00355 #pragma warning (push)
00356 #pragma warning (disable: 4996) // unchecked iterators
00357                     std::copy( pos+1, end()+1, pos );
00358 #pragma warning (pop)
00359                     (*this)[size_] = 0; // see comment in other erase
00360                     trim_();
00361                     return pos;
00362                 }
00363             }
00364             return end();
00365         }
00366 
00375     void clear()
00376         {
00377             ScopedWrite mutex( lock_ );
00378             while( size_ > 0 )
00379             {
00380                 --size_;
00381                 (*this)[size_] = 0; // Needed to reset RefPtr
00382             }
00383             for( int32_t i = 0; i < nSlots; ++i )
00384             {
00385                 delete [] slots_[ i ];
00386                 slots_[ i ] = 0;
00387             }
00388         }
00389 
00390 private:
00391     LB_SERIALIZABLE
00392 
00393     T* slots_[ nSlots ];
00394     size_t size_;
00395     mutable SpinLock lock_;
00396 
00397     template< int32_t fromSlots >
00398     void assign_( const LFVector< T, fromSlots >& from )
00399         {
00400             lb_bzero( slots_, nSlots * sizeof( T* ));
00401 
00402             ScopedWrite mutex( from.lock_ );
00403             for( int32_t i = 0; i < nSlots; ++i )
00404             {
00405                 if( i >= fromSlots || !from.slots_[i] ) // done copying
00406                 {
00407                     LBASSERTINFO( size_ == from.size_,
00408                                   size_ << " != " << from.size_ );
00409                     return;
00410                 }
00411 
00412                 const size_t sz = 1<<i;
00413                 slots_[ i ] = new T[ sz ];
00414                 for( size_t j = 0; size_ < from.size_ && j < sz ; ++j )
00415                 {
00416                     slots_[ i ][ j ] = from.slots_[ i ][ j ];
00417                     ++size_;
00418                 }
00419             }
00420         }
00421 
00422     void trim_()
00423         {
00424             const int32_t nextSlot = getIndexOfLastBit( size_+1 ) + 1;
00425             if( nextSlot < nSlots && slots_[ nextSlot ] )
00426             {
00427                 delete [] slots_[ nextSlot ]; // delete next slot (keep a spare)
00428                 slots_[ nextSlot ] = 0;
00429             }
00430         }
00431 
00432     void push_back_unlocked_( const T& item )
00433         {
00434             const size_t i = size_ + 1;
00435             const int32_t slot = getIndexOfLastBit( i );
00436             const size_t sz = ( size_t( 1 )<<slot );
00437             if( !slots_[ slot ] )
00438                 slots_[ slot ] = new T[ sz ];
00439 
00440             const ssize_t index = i ^ sz;
00441             slots_[ slot ][ index ] = item;
00442             ++size_;
00443         }
00444 };
00445 
00447 template< class T > inline
00448 std::ostream& operator << ( std::ostream& os, const LFVector< T >& v )
00449 {
00450     os << className( &v ) << " size " << v.size() << " [ ";
00451     for(typename LFVector< T >::const_iterator i = v.begin(); i != v.end(); ++i)
00452     {
00453         if( i.getPosition() > 255 )
00454         {
00455             os << "... ";
00456             break;
00457         }
00458         os << (*i) << ' ';
00459     }
00460     return os << ']' << std::endl;
00461 }
00462 
00463 }
00464 
00465 #include "lfVectorIterator.h"
00466 
00467 namespace lunchbox
00468 {
00469 
00470 template< class T, int32_t nSlots > inline typename 
00471 LFVector< T, nSlots >::const_iterator LFVector< T, nSlots >::begin() const
00472 { 
00473     return const_iterator( this, 0 );
00474 }
00475        
00476 template< class T, int32_t nSlots > inline typename
00477 LFVector< T, nSlots >::const_iterator LFVector< T, nSlots >::end() const
00478 { 
00479     return const_iterator( this, size_ );
00480 }
00481 
00482 template< class T, int32_t nSlots > inline typename
00483 LFVector< T, nSlots >::iterator LFVector< T, nSlots >::begin()
00484 { 
00485     return iterator( this, 0 );
00486 }
00487        
00488 template< class T, int32_t nSlots > inline typename
00489 LFVector< T, nSlots >::iterator LFVector< T, nSlots >::end()
00490 { 
00491     return iterator( this, size_ );
00492 }
00493 
00494 #ifdef LUNCHBOX_USE_BOOST
00495 template< class T, int32_t nSlots > template< class Archive >
00496 inline void LFVector< T, nSlots >::save( Archive& ar,
00497                                          const unsigned int version ) const
00498 {
00499     ar << size_;
00500     for( size_t i = 0; i < size_; ++i )
00501         ar << operator[](i);
00502 }
00503 
00504 template< class T, int32_t nSlots > template< class Archive >
00505 inline void LFVector< T, nSlots >::load( Archive& ar,
00506                                          const unsigned int version )
00507 {
00508     size_t newSize;
00509     ar >> newSize;
00510     expand( newSize );
00511     LBASSERT( size_ == newSize );
00512 
00513     for( size_t i = 0; i < size_; ++i )
00514         ar >> operator[](i);
00515 }
00516 #endif
00517 
00518 }
00519 
00520 #endif // LUNCHBOX_LFVECTOR_H