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

#include <lfVector.h>

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.
void	push_back (const T &item)
	Add an element to the vector.
void	pop_back ()
	Remove the last element (STL version).
bool	pop_back (T &element)
	Remove the last element (atomic version).
iterator	erase (iterator pos)
	Remove an element.
iterator	erase (const T &element)
	Remove the last occurence of the given element.
void	clear ()
	Clear the vector and all storage.
Public Types
typedef LFVectorIterator < LFVector< T >, T >	iterator
	Iterator over the vector elements.
typedef LFVectorIterator < const LFVector< T >, const T >	const_iterator
	Iterator over the const vector elements.

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.

Definition at line 57 of file lfVector.h.

Member Typedef Documentation

template<class T, int32_t nSlots = 32>

typedef LFVectorIterator< const LFVector< T >, const T > lunchbox::LFVector< T, nSlots >::const_iterator

Iterator over the const vector elements.

Version:: 1.3.2

Definition at line 213 of file lfVector.h.

template<class T, int32_t nSlots = 32>

typedef LFVectorIterator< LFVector< T >, T > lunchbox::LFVector< T, nSlots >::iterator

Iterator over the vector elements.

Version:: 1.3.2

Definition at line 211 of file lfVector.h.

Constructor & Destructor Documentation

template<class T, int32_t nSlots = 32>

lunchbox::LFVector< T, nSlots >::LFVector ( ) [inline]

Version:: 1.3.2

Definition at line 63 of file lfVector.h.

template<class T, int32_t nSlots = 32>

lunchbox::LFVector< T, nSlots >::LFVector ( const size_t n ) [inline, explicit]

Version:: 1.3.2

Definition at line 66 of file lfVector.h.

References lunchbox::getIndexOfLastBit().

Here is the call graph for this function:

template<class T, int32_t nSlots = 32>

lunchbox::LFVector< T, nSlots >::LFVector	(	const size_t	n,
		const T &	t
	)		`[inline, explicit]`

Version:: 1.3.2

Definition at line 76 of file lfVector.h.

References lunchbox::getIndexOfLastBit().

Here is the call graph for this function:

template<class T, int32_t nSlots = 32>

lunchbox::LFVector< T, nSlots >::LFVector ( const LFVector< T, nSlots > & from ) [inline, explicit]

Version:: 1.3.2

Definition at line 95 of file lfVector.h.

template<class T, int32_t nSlots = 32>

template<int32_t fromSlots>

lunchbox::LFVector< T, nSlots >::LFVector ( const LFVector< T, fromSlots > & from ) [inline, explicit]

Version:: 1.3.2

Definition at line 100 of file lfVector.h.

template<class T, int32_t nSlots = 32>

lunchbox::LFVector< T, nSlots >::~LFVector ( ) [inline]

Version:: 1.3.2

Definition at line 105 of file lfVector.h.

Member Function Documentation

template<class T, int32_t nSlots = 32>

T& lunchbox::LFVector< T, nSlots >::back ( ) [inline]

Version:: 1.3.2

Definition at line 204 of file lfVector.h.

References lunchbox::LFVector< T, nSlots >::empty().

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

Here is the call graph for this function:

Here is the caller graph for this function:

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 471 of file lfVector.h.

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 483 of file lfVector.h.

template<class T, int32_t nSlots = 32>

void lunchbox::LFVector< T, nSlots >::clear ( ) [inline]

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 375 of file lfVector.h.

template<class T, int32_t nSlots = 32>

bool lunchbox::LFVector< T, nSlots >::empty ( ) const [inline]

Version:: 1.3.2

Definition at line 168 of file lfVector.h.

Referenced by lunchbox::LFVector< T, nSlots >::back(), and lunchbox::LFVector< T, nSlots >::front().

Here is the caller graph for this function:

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 477 of file lfVector.h.

Referenced by lunchbox::LFVector< T, nSlots >::erase(), and 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 >::end ( ) [inline]

Version:: 1.3.2

Definition at line 489 of file lfVector.h.

template<class T, int32_t nSlots = 32>

iterator lunchbox::LFVector< T, nSlots >::erase ( iterator pos ) [inline]

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:

pos	the 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 317 of file lfVector.h.

References lunchbox::LFVector< T, nSlots >::end().

Here is the call graph for this function:

template<class T, int32_t nSlots = 32>

iterator lunchbox::LFVector< T, nSlots >::erase ( const T & element ) [inline]

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:

element the 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 346 of file lfVector.h.

References lunchbox::LFVector< T, nSlots >::end().

Here is the call graph for this function:

template<class T, int32_t nSlots = 32>

void lunchbox::LFVector< T, nSlots >::expand	(	const size_t	newSize,
		const T &	item = `T( )`
	)		`[inline]`

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:

newSize	the minimum new size.
item	the element to insert.

Version:: 1.3.2

Definition at line 236 of file lfVector.h.

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

Here is the call graph for this function:

template<class T, int32_t nSlots = 32>

T& lunchbox::LFVector< T, nSlots >::front ( ) [inline]

Version:: 1.3.2

Definition at line 197 of file lfVector.h.

References lunchbox::LFVector< T, nSlots >::empty().

Here is the call graph for this function:

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 166 of file lfVector.h.

template<class T, int32_t nSlots = 32>

LFVector& lunchbox::LFVector< T, nSlots >::operator= ( const LFVector< T, nSlots > & from ) [inline]

Version:: 1.3.2

Definition at line 112 of file lfVector.h.

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 146 of file lfVector.h.

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

Here is the call graph for this function:

template<class T, int32_t nSlots = 32>

T& lunchbox::LFVector< T, nSlots >::operator[] ( size_t i ) [inline]

Version:: 1.3.2

Definition at line 172 of file lfVector.h.

References lunchbox::getIndexOfLastBit().

Here is the call graph for this function:

template<class T, int32_t nSlots = 32>

const T& lunchbox::LFVector< T, nSlots >::operator[] ( size_t i ) const [inline]

Version:: 1.3.2

Definition at line 185 of file lfVector.h.

References lunchbox::getIndexOfLastBit().

Here is the call graph for this function:

template<class T, int32_t nSlots = 32>

void lunchbox::LFVector< T, nSlots >::pop_back ( ) [inline]

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 268 of file lfVector.h.

template<class T, int32_t nSlots = 32>

bool lunchbox::LFVector< T, nSlots >::pop_back ( T & element ) [inline]

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:

element the 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 291 of file lfVector.h.

References lunchbox::LFVector< T, nSlots >::back().

Here is the call graph for this function:

template<class T, int32_t nSlots = 32>

void lunchbox::LFVector< T, nSlots >::push_back ( const T & item ) [inline]

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: