Lunchbox  1.11.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Types | Public Member Functions | List of all members
lunchbox::LFVector< T, nSlots > Class Template Reference

STL-like vector implementation providing certain thread-safety guarantees. More...

#include <lfVector.h>

+ Collaboration diagram for lunchbox::LFVector< T, nSlots >:

Public Types

typedef ScopedFastWrite ScopedWrite
 
typedef T value_type
 
typedef LFVectorIterator
< LFVector< T, nSlots >, T > 		iterator
 Iterator over the vector elements. More...
 
typedef LFVectorIterator
< const LFVector< T, nSlots >
, const T > 		const_iterator
 Iterator over the const vector elements. More...
 

Public Member Functions

 LFVector ()
 
 LFVector (const size_t n)
 
 LFVector (const size_t n, const T &t)
 
 LFVector (const LFVector &from)
 
template<int32_t fromSlots>
 LFVector (const LFVector< T, fromSlots > &from)
 
 ~LFVector ()
 
LFVector & operator= (const LFVector &from)
 
bool operator== (const LFVector &rhs) const
 
bool operator!= (const LFVector &rhs) const
 
bool empty () const
 
size_t size () const
 
T & operator[] (size_t i)
 
const T & operator[] (size_t i) const
 
T & front ()
 
T & back ()
 
const_iterator begin () const
 
const_iterator end () const
 
iterator begin ()
 
iterator end ()
 
void expand (const size_t newSize, const T &item=T())
 Resize the vector to at least the given size. More...
 
void push_back (const T &item, bool lock=true)
 Add an element to the vector. More...
 
void pop_back ()
 Remove the last element (STL version). More...
 
bool pop_back (T &element)
 Remove the last element (atomic version). More...
 
iterator erase (typename LFVector< T, nSlots >::iterator pos)
 Remove an element. More...
 
iterator erase (const T &element)
 Remove the last occurence of the given element. More...
 
void resize (const size_t size, const T &value=T())
 Resize the vector. More...
 
void clear ()
 Clear the vector and all storage. More...
 
ScopedWrite getWriteLock ()
 

Detailed Description

template<class T, int32_t nSlots = 32>
class lunchbox::LFVector< T, nSlots >

STL-like vector implementation providing certain thread-safety guarantees.

All operations not modifying the vector size are lock-free and wait-free. All operations modifying the vector size are serialized using a spin lock. The interaction of operations is documented in the corresponding modify operation.

Undocumented methods behave like the STL implementation. The number of slots (default 32) sets the maximum elements the vector may hold to 2^nSlots-1. Each slot needs one pointer additional storage. Naturally it should never be set higher than 64.

Not all std::vector methods are implemented. Serializable using boost.serialization.

Example:

/* Copyright (c) 2011-2014, Stefan Eilemann <stefan.eilemann@epfl.ch>
* 2012, Daniel Nachbaur <danielnachbaur@gmail.com>
*
* This library is free software; you can redistribute it and/or modify it under
* the terms of the GNU Lesser General Public License version 3.0 as published
* by the Free Software Foundation.
*
* This library is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
* FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
* details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with this library; if not, write to the Free Software Foundation, Inc.,
* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/
#define TEST_RUNTIME 600 // seconds
#include "test.h"
#pragma warning (push)
#pragma warning (disable: 4985) // http://www.softwareverify.com/blog/?p=671
# include <lunchbox/lfVector.h>
#pragma warning (pop)
#include <lunchbox/clock.h>
#include <lunchbox/init.h>
#include <lunchbox/monitor.h>
#include <lunchbox/omp.h>
#include <lunchbox/thread.h>
#include <limits>
#define LOOPSIZE 200000
lunchbox::Clock _clock;
typedef lunchbox::LFVector< size_t > Vector_t;
float rTime_;
float wTime_;
float eTime_;
float cTime_;
float pTime_;
lunchbox::Monitor< size_t > stage_;
#define STAGESIZE 10000;
class Reader : public lunchbox::Thread
{
public:
Reader() : vector( 0 ) {}
virtual ~Reader() {}
virtual void run()
{
size_t stage = 0;
while( true )
{
stage += STAGESIZE;
stage_.waitGE( stage );
if( stage_ == std::numeric_limits< size_t >::max( ))
return;
if( vector )
{
for( size_t i = 0; i < LOOPSIZE; ++i )
{
if( i < vector->size( ))
{
const size_t value = (*vector)[ i ];
TESTINFO( i == value || value == 0,
i << " - " << value << " - " << (*vector)[i]<<
": " << *vector );
}
}
rTime_ = _clock.getTimef();
}
++stage_;
}
}
Vector_t* vector;
// cppcheck-suppress operatorEqVarError
Reader& operator=( const Reader& ) { return *this; }
};
class Writer : public lunchbox::Thread
{
public:
Writer() : vector( 0 ) {}
virtual ~Writer() {}
virtual void run()
{
size_t stage = 0;
while( true )
{
stage += STAGESIZE;
stage_.waitGE( stage );
if( stage_ == std::numeric_limits< size_t >::max( ))
return;
if( vector )
{
for( size_t i = 0; i < LOOPSIZE; ++i )
{
if( i < vector->size( ))
(*vector)[ i ] = i;
}
wTime_ = _clock.getTimef();
}
++stage_;
}
}
Vector_t* vector;
// cppcheck-suppress operatorEqVarError
Writer& operator=( const Writer& ) { return *this; }
};
class Pusher : public lunchbox::Thread
{
public:
Pusher() : vector( 0 ) {}
virtual ~Pusher() {}
virtual void run()
{
size_t stage = 0;
while( true )
{
stage += STAGESIZE;
stage_.waitGE( stage );
if( stage_ == std::numeric_limits< size_t >::max( ))
return;
if( vector )
{
while( vector->size() < LOOPSIZE )
vector->push_back( 0 );
pTime_ = _clock.getTimef();
}
++stage_;
}
}
Vector_t* vector;
// cppcheck-suppress operatorEqVarError
Pusher& operator=( const Pusher& ) { return *this; }
};
class Copier : public lunchbox::Thread
{
public:
Copier() : vector( 0 ) {}
virtual ~Copier() {}
virtual void run()
{
Vector_t copy;
copy = *vector;
*vector = copy;
TEST( copy.size() >= vector->size( ));
cTime_ = _clock.getTimef();
}
Vector_t* vector;
// cppcheck-suppress operatorEqVarError
Copier& operator=( const Copier& ) { return *this; }
};
class Eraser : public lunchbox::Thread
{
public:
Eraser() : vector( 0 ) {}
virtual ~Eraser() {}
virtual void run()
{
const size_t pos = vector->size() / 2;
Vector_t::iterator i = vector->begin() + pos;
Vector_t::iterator j = vector->erase( i );
TEST( j != vector->end( ));
TEST( i == j );
eTime_ = _clock.getTimef();
}
Vector_t* vector;
// cppcheck-suppress operatorEqVarError
Eraser& operator=( const Eraser& ) { return *this; }
};
class Flusher : public lunchbox::Thread
{
public:
Flusher() : vector( 0 ) {}
virtual ~Flusher() {}
virtual void run()
{
size_t i = 0xFFFFFFFFu;
while( vector->pop_back( i ))
{
TEST( i == 0 || i >= vector->size( ));
}
}
Vector_t* vector;
// cppcheck-suppress operatorEqVarError
Flusher& operator=( const Flusher& ) { return *this; }
};
template< class V, class T > void _runSerialTest()
{
V vector;
_clock.reset();
while( vector.size() < LOOPSIZE*10 )
vector.push_back( T( 0 ));
pTime_ = _clock.getTimef();
_clock.reset();
for( size_t i = 0; i < LOOPSIZE*10; ++i )
{
if( i < vector.size( ))
vector[ i ] = i;
}
wTime_ = _clock.getTimef();
_clock.reset();
typename V::const_iterator it = vector.begin();
for( size_t i = 0; i < LOOPSIZE*10; ++i )
{
const size_t value = *it;
TESTINFO( i == value || value == 0, i << ", " << value );
++it;
if( it == vector.end( ))
it = vector.begin();
}
rTime_ = _clock.getTimef();
_clock.reset();
for( size_t i = 0; i < 10; ++i )
{
V copy;
copy = vector;
vector = copy;
TEST( copy.size() >= vector.size( ));
}
cTime_ = _clock.getTimef();
_clock.reset();
const size_t pos = vector.size() / 2;
typename V::iterator i = vector.begin() + pos;
typename V::iterator j = vector.erase( i );
TEST( j != vector.end( ));
TEST( *j == 0 || *j >= pos );
eTime_ = _clock.getTimef();
_clock.reset();
while( !vector.empty( ))
vector.pop_back();
const float fTime = _clock.getTimef();
std::cerr << std::setw(11) << float(LOOPSIZE*10)/rTime_ << ", "
<< std::setw(11) << float(LOOPSIZE*10)/wTime_ << ", "
<< std::setw(11) << float(LOOPSIZE*10)/pTime_ << ", "
<< std::setw(9) << float(10)/cTime_ << ", "
<< std::setw(9) << float(10)/eTime_ << ", "
<< std::setw(9) << float(LOOPSIZE*10)/fTime << ", "
<< std::setw(3) << 0 << ", " << std::setw(3) << 0
<< std::endl;
vector.push_back( 42 );
i = vector.begin();
i = vector.erase( i );
TEST( i == vector.begin( ));
TEST( vector.empty( ));
vector.push_back( 42 );
vector.push_back( 17 );
vector.resize( 1 );
TEST( vector.size() == 1 );
TEST( vector[0] == 42 );
vector.resize( 10, 17 );
TEST( vector.size() == 10 );
TEST( vector[0] == 42 );
TEST( vector[1] == 17 );
TEST( vector[9] == 17 );
}
int main( int, char** )
{
#ifdef LUNCHBOX_USE_OPENMP
const size_t nThreads = lunchbox::OMP::getNThreads() * 3;
#else
const size_t nThreads = 16;
#endif
std::cout << " read, write, push, copy, erase, "
<< " flush/ms, rd, other #threads" << std::endl;
_runSerialTest< std::vector< size_t >, size_t >();
_runSerialTest< Vector_t, size_t >();
std::vector< Reader > readers(nThreads);
std::vector< Writer > writers(nThreads);
std::vector< Pusher > pushers(nThreads);
stage_ = 1;
size_t stage = 0;
for( size_t l = 0; l < nThreads; ++l )
{
readers[l].start();
writers[l].start();
pushers[l].start();
}
lunchbox::sleep( 10 );
for( size_t i = 1; i <= nThreads; i = i<<1 )
for( size_t j = 1; j <= nThreads; j = j<<1 )
{
// concurrent read, write, push
Vector_t vector;
for( size_t k = 0; k < nThreads; ++k )
{
readers[k].vector = k < i ? &vector : 0;
writers[k].vector = k < j ? &vector : 0;
pushers[k].vector = k < j ? &vector : 0;
}
const size_t nextStage = ++stage * STAGESIZE;
_clock.reset();
stage_ = nextStage;
stage_.waitEQ( nextStage + (3 * nThreads) );
TEST( vector.size() >= LOOPSIZE );
// multi-threaded copy
std::vector< Copier > copiers(j);
_clock.reset();
for( size_t k = 0; k < j; ++k )
{
copiers[k].vector = &vector;
copiers[k].start();
}
for( size_t k = 0; k < j; ++k )
copiers[k].join();
for( size_t k = 0; k < vector.size(); ++k )
TEST( vector[k] == k || vector[k] == 0 );
// multi-threaded erase
std::vector< Eraser > erasers(j);
_clock.reset();
for( size_t k = 0; k < j; ++k )
{
erasers[k].vector = &vector;
erasers[k].start();
}
for( size_t k = 0; k < j; ++k )
erasers[k].join();
for( size_t k = 0; k < vector.size(); ++k )
{
if( vector[k] == 0 )
break;
if( k > vector.size() / 2 )
{
TEST( vector[k] > vector[k-1] );
}
else
{
TEST( vector[k] == k );
}
}
// multi-threaded pop_back
const size_t fOps = vector.size();
std::vector< Flusher > flushers(j);
_clock.reset();
for( size_t k = 0; k < j; ++k )
{
flushers[k].vector = &vector;
flushers[k].start();
}
for( size_t k = 0; k < j; ++k )
flushers[k].join();
const float fTime = _clock.getTimef();
TEST( vector.empty( ));
std::cerr << std::setw(11) << float(i*LOOPSIZE)/rTime_ << ", "
<< std::setw(11) << float(j*LOOPSIZE)/wTime_ << ", "
<< std::setw(11) << float(LOOPSIZE)/pTime_ << ", "
<< std::setw(9) << float(j)/cTime_ << ", "
<< std::setw(9) << float(j)/eTime_ << ", "
<< std::setw(9) << float(fOps)/fTime << ", "
<< std::setw(3) << i << ", " << std::setw(3) << j
<< std::endl;
}
stage_ = std::numeric_limits< size_t >::max();
for( size_t k = 0; k < nThreads; ++k )
{
readers[k].join();
writers[k].join();
pushers[k].join();
}
return EXIT_SUCCESS;
}

Definition at line 53 of file lfVector.h.

Member Typedef Documentation

template<class T, int32_t nSlots = 32>
typedef LFVectorIterator<const LFVector<T, nSlots>, const T> lunchbox::LFVector< T, nSlots >::const_iterator

Iterator over the const vector elements.

Version
1.3.2

Definition at line 106 of file lfVector.h.

template<class T, int32_t nSlots = 32>
typedef LFVectorIterator< LFVector< T, nSlots >, T > lunchbox::LFVector< T, nSlots >::iterator

Iterator over the vector elements.

Version
1.3.2

Definition at line 103 of file lfVector.h.

Constructor & Destructor Documentation

template<class T , int32_t nSlots>
lunchbox::LFVector< T, nSlots >::LFVector ( )
Version
1.3.2

Definition at line 28 of file lfVector.ipp.

References lunchbox::setZero().

+ Here is the call graph for this function:

template<class T , int32_t nSlots>
lunchbox::LFVector< T, nSlots >::LFVector ( const size_t  n)
explicit
Version
1.3.2

Definition at line 35 of file lfVector.ipp.

References lunchbox::getIndexOfLastBit(), and lunchbox::setZero().

+ Here is the call graph for this function:

template<class T, int32_t nSlots>
lunchbox::LFVector< T, nSlots >::LFVector ( const size_t  n,
const T &  t 
)
Version
1.3.2

Definition at line 46 of file lfVector.ipp.

References lunchbox::getIndexOfLastBit(), and lunchbox::setZero().

+ Here is the call graph for this function:

template<class T, int32_t nSlots>
lunchbox::LFVector< T, nSlots >::LFVector ( const LFVector< T, nSlots > &  from)
explicit
Version
1.3.2

Definition at line 66 of file lfVector.ipp.

template<class T, int32_t nSlots>
template<int32_t fromSlots>
lunchbox::LFVector< T, nSlots >::LFVector ( const LFVector< T, fromSlots > &  from)
explicit
Version
1.3.2

Definition at line 75 of file lfVector.ipp.

template<class T , int32_t nSlots>
lunchbox::LFVector< T, nSlots >::~LFVector ( )
Version
1.3.2

Definition at line 83 of file lfVector.ipp.

Member Function Documentation

template<class T , int32_t nSlots>
T & lunchbox::LFVector< T, nSlots >::back ( )
Version
1.3.2

Definition at line 193 of file lfVector.ipp.

template<class T , int32_t nSlots>
LFVector< T, nSlots >::const_iterator lunchbox::LFVector< T, nSlots >::begin ( ) const
inline
Version
1.3.2

Definition at line 375 of file lfVector.ipp.

Referenced by lunchbox::LFVector< T, nSlots >::operator==().

+ Here is the caller graph for this function:

template<class T , int32_t nSlots>
LFVector< T, nSlots >::iterator lunchbox::LFVector< T, nSlots >::begin ( )
inline
Version
1.3.2

Definition at line 387 of file lfVector.ipp.

template<class T , int32_t nSlots>
void lunchbox::LFVector< T, nSlots >::clear ( )

Clear the vector and all storage.

Thread-safe with other write operations. By nature not thread-safe with read operations.

Version
1.3.2

Definition at line 295 of file lfVector.ipp.

template<class T, int32_t nSlots = 32>
bool lunchbox::LFVector< T, nSlots >::empty ( ) const
inline
Version
1.3.2

Definition at line 87 of file lfVector.h.

template<class T , int32_t nSlots>
LFVector< T, nSlots >::const_iterator lunchbox::LFVector< T, nSlots >::end ( ) const
inline
Version
1.3.2

Definition at line 381 of file lfVector.ipp.

template<class T , int32_t nSlots>
LFVector< T, nSlots >::iterator lunchbox::LFVector< T, nSlots >::end ( )
inline
Version
1.3.2

Definition at line 393 of file lfVector.ipp.

template<class T, int32_t nSlots>
LFVector< T, nSlots >::iterator lunchbox::LFVector< T, nSlots >::erase ( typename LFVector< T, nSlots >::iterator  pos)

Remove an element.

A concurrent read on the item or any following item is not thread save. The vector's size is decremented first. Returns end() if the element can't be removed, i.e., the iterator is past end() or not for this vector.

Parameters
posthe element to remove
Returns
an iterator pointing to the element after the removed element, or end() if nothing was erased.
Version
1.3.2

Definition at line 240 of file lfVector.ipp.

template<class T, int32_t nSlots>
LFVector< T, nSlots >::iterator lunchbox::LFVector< T, nSlots >::erase ( const T &  element)

Remove the last occurence of the given element.

A concurrent read on the item or any following item is not thread save. The vector's size is decremented first. Returns end() if the element can't be removed, i.e., the vector does not contain the element.

Parameters
elementthe element to remove
Returns
an iterator pointing to the element after the removed element, or end() if nothing was erased.
Version
1.3.2

Definition at line 258 of file lfVector.ipp.

template<class T, int32_t nSlots>
void lunchbox::LFVector< T, nSlots >::expand ( const size_t  newSize,
const T &  item = T( ) 
)

Resize the vector to at least the given size.

In contrast to resize(), expand() only increases the size of the vector, allowing concurrent resize operations on the same vector. Completely thread-save with read operations. Existing end() iterators will keep pointing to the old end of the vector. The size is updated after all elements have been inserted, so size() followed by a read is thread-safe. In contrast to while( vector.size() < newSize ) vector.insert( item ); this method's operation is atomic with other writes.

Parameters
newSizethe minimum new size.
itemthe element to insert.
Exceptions
std::runtime_errorif the vector is full
Version
1.3.2

Definition at line 200 of file lfVector.ipp.

template<class T , int32_t nSlots>
T & lunchbox::LFVector< T, nSlots >::front ( )
Version
1.3.2

Definition at line 186 of file lfVector.ipp.

template<class T , int32_t nSlots>
LFVector< T, nSlots >::ScopedWrite lunchbox::LFVector< T, nSlots >::getWriteLock ( )
Returns
the locked mutex for unlocked write operations.
Version
1.5

Definition at line 311 of file lfVector.ipp.

template<class T, int32_t nSlots = 32>
bool lunchbox::LFVector< T, nSlots >::operator!= ( const LFVector< T, nSlots > &  rhs) const
inline
Version
1.3.2

Definition at line 85 of file lfVector.h.

template<class T , int32_t nSlots>
LFVector< T, nSlots > & lunchbox::LFVector< T, nSlots >::operator= ( const LFVector< T, nSlots > &  from)
Version
1.3.2

Definition at line 90 of file lfVector.ipp.

template<class T , int32_t nSlots>
bool lunchbox::LFVector< T, nSlots >::operator== ( const LFVector< T, nSlots > &  rhs) const
Version
1.3.2

Definition at line 124 of file lfVector.ipp.

References lunchbox::LFVector< T, nSlots >::begin(), and lunchbox::LFVector< T, nSlots >::size().

+ Here is the call graph for this function:

template<class T , int32_t nSlots>
T & lunchbox::LFVector< T, nSlots >::operator[] ( size_t  i)
Version
1.3.2

Definition at line 151 of file lfVector.ipp.

References lunchbox::getIndexOfLastBit().

+ Here is the call graph for this function:

template<class T , int32_t nSlots>
const T & lunchbox::LFVector< T, nSlots >::operator[] ( size_t  i) const
Version
1.3.2

Definition at line 166 of file lfVector.ipp.

References lunchbox::getIndexOfLastBit().

+ Here is the call graph for this function:

template<class T , int32_t nSlots>
void lunchbox::LFVector< T, nSlots >::pop_back ( )

Remove the last element (STL version).

A concurrent read on the removed item produces undefined results, in particular end() and back().

Version
1.3.2

Definition at line 215 of file lfVector.ipp.

template<class T, int32_t nSlots>
bool lunchbox::LFVector< T, nSlots >::pop_back ( T &  element)

Remove the last element (atomic version).

A concurrent read on the removed item produces undefined results, in particular end() and back(). The last element is assigned to the given output element if the vector is not empty. If the vector is empty, element is not touched and false is returned. The whole operation is atomic with other operations changing the size of the vector.

Parameters
elementthe item receiving the value which was stored at the end.
Returns
true if the vector was not empty, false if no item was popped.
Version
1.3.2

Definition at line 226 of file lfVector.ipp.

template<class T, int32_t nSlots>
void lunchbox::LFVector< T, nSlots >::push_back ( const T &  item,
bool  lock = true 
)

Add an element to the vector.

Completely thread-save with read operations. Existing end() iterators will keep pointing to the old end of the vector. The size is updated after the element is inserted, so size() followed by a read is thread-safe.

Parameters
itemthe element to insert.
locktrue for internal lock, false if locked with getWriteLock()
Exceptions
std::runtime_errorif the vector is full
Version
1.3.2

Definition at line 208 of file lfVector.ipp.

template<class T, int32_t nSlots>
void lunchbox::LFVector< T, nSlots >::resize ( const size_t  size,
const T &  value = T( ) 
)

Resize the vector.

Thread-safe with other write operations. Shrinking is not thread-safe with concurrent reads on the removed elements and produces undefined results.

Exceptions
std::runtime_errorif the vector is full
Version
1.7.2

Definition at line 280 of file lfVector.ipp.

template<class T, int32_t nSlots = 32>
size_t lunchbox::LFVector< T, nSlots >::size ( ) const
inline
Version
1.3.2

Definition at line 88 of file lfVector.h.

Referenced by lunchbox::LFVector< T, nSlots >::operator==().

+ Here is the caller graph for this function:

The documentation for this class was generated from the following files: