Games Task Scheduler (GTS): gts::ParallelVector< T, TSharedMutex, TAllocator > Class Template Reference

Games Task Scheduler (GTS)

A multi-processor scheduling framework for games engines

A obstruction-free parallel vector. Properties: More...

#include <ParallelVector.h>

Inherits gts::AlignedAllocator< GTS_NO_SHARING_CACHE_LINE_SIZE >.

Classes
class	const_iterator
	A constant forward iterator. Read-locks the referenced element until destruction. More...

class	iterator
	A forward iterator. Write-locks the referenced element until destruction. More...

struct	pop_back_result
	The result structure for pop_back_and_get. More...

Public Types
using	ticket_vec = internal::ParallelSubVector< T, TSharedMutex, TAllocator >

using	value_type = typename ticket_vec::value_type

using	mutex_type = typename ticket_vec::mutex_type

using	backoff_type = typename ticket_vec::backoff_type

using	size_type = typename ticket_vec::size_type

using	allocator_type = typename ticket_vec::allocator_type

using	read_guard = ReadGuard< value_type, mutex_type, mutex_type >

using	write_guard = WriteGuard< value_type, mutex_type, mutex_type >

Public Member Functions
	ParallelVector (const allocator_type &allocator=allocator_type())

	ParallelVector (size_type subVectorCountPow2, const allocator_type &allocator=allocator_type())

	~ParallelVector ()

	ParallelVector (ParallelVector const &other)

	ParallelVector (ParallelVector &&other)

ParallelVector &	operator= (ParallelVector const &other)

ParallelVector &	operator= (ParallelVector &&other)

const_iterator	cbegin () const

const_iterator	cend () const

iterator	begin ()

iterator	end ()

size_type	capacity () const

size_type	max_size () const

size_type	size () const

bool	empty () const

allocator_type	get_allocator () const

read_guard	cat (size_type index) const

write_guard	at (size_type index)

read_guard	operator[] (size_type index) const

write_guard	operator[] (size_type index)

read_guard	cfront () const

write_guard	front ()

read_guard	cback () const

write_guard	back ()

void	reserve (size_type size)

void	resize (size_type size)

void	resize (size_type size, value_type const &fill)

void	push_back (value_type const &val)

void	push_back (value_type &&val)

template<typename... TArgs>
void	emplace_back (TArgs &&... args)

void	pop_back ()

pop_back_result	pop_back_and_get ()

void	swap_out (size_type index)

void	swap_out (iterator &iter)

void	clear ()

template<typename... TArgs>
void	emplace_back (TArgs &&... args)

template<typename... TArgs>
void	_emplaceBack (TArgs &&... args)

Friends
class	base_const_iterator

class	const_iterator

class	iterator

Detailed Description

template<typename T, typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>
class gts::ParallelVector< T, TSharedMutex, TAllocator >

A obstruction-free parallel vector. Properties:

Unbound.
Reference stable.

Not linearizable.

Remarks: Iterators and guards contain spin-locks that are unlocked in the their destructors. Holding onto them may cause deadlocks.

Template Parameters

T	The element type stored in the container.
TAccessorSharedMutex	The shared mutex type to access individual elements.
TGrowSharedMutex	The shared mutex type used to grow the table.
TAllocator	The allocator used by the storage backing.

Implement insert()

Implement delete()

Make more methods thread-safe.

Constructor & Destructor Documentation

◆ ParallelVector() [1/4]

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

gts::ParallelVector< T, TSharedMutex, TAllocator >::ParallelVector ( const allocator_type & allocator = allocator_type() )

explicit

Constructs an empty container with the given 'allocator'. The number of sub vectors is equal to the number of HW threads on the machine.

Remarks: Thread-safe.

◆ ParallelVector() [2/4]

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

gts::ParallelVector< T, TSharedMutex, TAllocator >::ParallelVector	(	size_type	subVectorCountPow2,
		const allocator_type &	allocator = `allocator_type()`
	)

explicit

Constructs an empty container with 'subVectorCount' sub vectors and with the given 'allocator'.

Remarks: Thread-safe.

◆ ~ParallelVector()

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

ParallelVector::~ParallelVector ( )

Destructs the container. The destructors of the elements are called and the used storage is deallocated.

Remarks: Not thread-safe.

◆ ParallelVector() [3/4]

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

ParallelVector::ParallelVector ( ParallelVector< T, TSharedMutex, TAllocator > const & other )

Copy constructor. Constructs the container with the copy of the contents of 'other'.

Remarks: Not thread-safe.

◆ ParallelVector() [4/4]

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

ParallelVector::ParallelVector ( ParallelVector< T, TSharedMutex, TAllocator > && other )

Move constructor. Constructs the container with the contents of other using move semantics. After the move, other is invalid.

Remarks: Not thread-safe.

Member Function Documentation

◆ at()

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

ParallelVector< T, TSharedMutex, TAllocator >::write_guard ParallelVector::at ( size_type index )

Access specified element.

Returns: A reference to the element wrapped in a write_guard.

Remarks: Thread-safe.

◆ back()

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

ParallelVector< T, TSharedMutex, TAllocator >::write_guard ParallelVector::back ( )

Accesses the last element.

Returns: A reference to the element wrapped in a write_guard.

Remarks: Thread-safe.

◆ begin()

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

ParallelVector< T, TSharedMutex, TAllocator >::iterator ParallelVector::begin ( )

Returns: An iterator to the beginning of the current vector state.

Remarks: Thread-safe.

◆ capacity()

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

ParallelVector< T, TSharedMutex, TAllocator >::size_type ParallelVector::capacity ( ) const

Returns: The total number of slots in the table.

Remarks: Not thread-safe. May return old value during a resize.

◆ cat()

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

ParallelVector< T, TSharedMutex, TAllocator >::read_guard ParallelVector::cat ( size_type index ) const

Access specified element.

Returns: A reference to the element wrapped in a read_guard.

Remarks: Thread-safe.

◆ cback()

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

ParallelVector< T, TSharedMutex, TAllocator >::read_guard ParallelVector::cback ( ) const

Accesses the last element.

Returns: A reference to the element wrapped in a read_guard.

Remarks: Thread-safe.

◆ cbegin()

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

ParallelVector< T, TSharedMutex, TAllocator >::const_iterator ParallelVector::cbegin ( ) const

Returns: An iterator to the beginning of the current vector state.

Remarks: Thread-safe.

◆ cend()

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

ParallelVector< T, TSharedMutex, TAllocator >::const_iterator ParallelVector::cend ( ) const

Returns: An iterator to the end of the current vector state.

Remarks: Thread-safe.

◆ cfront()

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

ParallelVector< T, TSharedMutex, TAllocator >::read_guard ParallelVector::cfront ( ) const

Accesses the first element.

Returns: A reference to the element wrapped in a read_guard.

Remarks: Thread-safe.

◆ clear()

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

void ParallelVector::clear ( )

Clears the data from the table. Leaves the capacity of the vector unchanged.

Remarks: Thread-safe.

◆ emplace_back()

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

template<typename... TArgs>

void gts::ParallelVector< T, TSharedMutex, TAllocator >::emplace_back ( TArgs &&... args )

Removes the last element.

Remarks: Thread-safe.

◆ empty()

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

bool ParallelVector::empty ( ) const

Returns: True if there are no element in the vector, false otherwise.

Remarks: Thread-safe.

◆ end()

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

ParallelVector< T, TSharedMutex, TAllocator >::iterator ParallelVector::end ( )

Returns: An iterator to the end of the current vector state.

Remarks: Thread-safe.

◆ front()

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

ParallelVector< T, TSharedMutex, TAllocator >::write_guard ParallelVector::front ( )

Accesses the first element.

Returns: A reference to the element wrapped in a write_guard.

Remarks: Thread-safe.

◆ get_allocator()

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

ParallelVector< T, TSharedMutex, TAllocator >::allocator_type ParallelVector::get_allocator ( ) const

Returns: This vector's allocator.

Remarks: Thread-safe.

◆ max_size()

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

ParallelVector< T, TSharedMutex, TAllocator >::size_type ParallelVector::max_size ( ) const

Returns: Maximum number of slots the container can grow to.

Remarks: Thread-safe.

◆ operator=() [1/2]

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

ParallelVector< T, TSharedMutex, TAllocator > & ParallelVector::operator= ( ParallelVector< T, TSharedMutex, TAllocator > && other )

Move assignment operator. Replaces the contents with those of other using move semantics. After the move, other is invalid.

Remarks: Not thread-safe.

◆ operator=() [2/2]

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

ParallelVector< T, TSharedMutex, TAllocator > & ParallelVector::operator= ( ParallelVector< T, TSharedMutex, TAllocator > const & other )

Copy assignment operator. Replaces the contents with a copy of the contents of 'other'.

Remarks: Not thread-safe.

◆ operator[]() [1/2]

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

ParallelVector< T, TSharedMutex, TAllocator >::write_guard ParallelVector::operator[] ( size_type index )

Access specified element.

Returns: A reference to the element wrapped in a write_guard.

Remarks: It's likely more efficient to use cat() if the caller only needs read access.; Thread-safe.

◆ operator[]() [2/2]

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

ParallelVector< T, TSharedMutex, TAllocator >::read_guard ParallelVector::operator[] ( size_type index ) const

Access specified element.

Returns: A reference to the element wrapped in a read_guard.

Remarks: Thread-safe.

◆ pop_back()

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

void ParallelVector::pop_back ( )

Removes the last element.

Remarks: Thread-safe.; If the vector is empty. This function is undefined.

◆ pop_back_and_get()

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

ParallelVector< T, TSharedMutex, TAllocator >::pop_back_result ParallelVector::pop_back_and_get ( )

Removes the last element and returns it. Basically packages back() and and pop_back() into a single thread-safe transaction.

Remarks: Thread-safe.; If the vector is empty. This function is undefined.

◆ push_back() [1/2]

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

void gts::ParallelVector< T, TSharedMutex, TAllocator >::push_back ( value_type && val )

Moves the specified value into the back of the container.

Remarks: Thread-safe.

◆ push_back() [2/2]

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

void gts::ParallelVector< T, TSharedMutex, TAllocator >::push_back ( value_type const & val )

Copies the specified value into the back of the container.

Remarks: Thread-safe.

◆ reserve()

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

void ParallelVector::reserve ( size_type size )

Increases the capacity of the vector. Does nothing if 'size' < capacity.

Remarks: Not thread-safe.

◆ resize() [1/2]

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

void ParallelVector::resize ( size_type size )

Changes the number of elements in the vector to 'size'.

Remarks: Not thread-safe.

◆ resize() [2/2]

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

void ParallelVector::resize	(	size_type	size,
		value_type const &	fill
	)

Changes the number of elements in the vector to 'size'. New elements will have the value 'fill'.

Remarks: Not thread-safe.

◆ size()

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

ParallelVector< T, TSharedMutex, TAllocator >::size_type ParallelVector::size ( ) const

Returns: The number of elements in the vector.

Remarks: Thread-safe.

◆ swap_out() [1/2]

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

void ParallelVector::swap_out ( iterator & iter )

Removes the specified element and replaces it with the last element.

Remarks: Thread-safe.; If iter is out of range or the vector is empty, this function is undefined.

◆ swap_out() [2/2]

template<typename T , typename TSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>

void ParallelVector::swap_out ( size_type index )

Removes the specified element and replaces it with the last element.

Remarks: Thread-safe.; If index is out of range or the vector is empty, this function is undefined.

gts
ParallelVector
Generated by 1.9.1