Honeycomb: honey::lockfree::List< T, Alloc_, Backoff, iterMax > Class Template Reference

Honeycomb 0.1

Component-Model Framework

Lock-free doubly-linked list. More...

#include <List.h>

Inheritance diagram for honey::lockfree::List< T, Alloc_, Backoff, iterMax >:

Inheritance graph

[legend]

Collaboration diagram for honey::lockfree::List< T, Alloc_, Backoff, iterMax >:

Collaboration graph

[legend]

Classes
class	Iter_
	Iterator. More...

class	IterR_
	Reverse iterator. More...

Public Types
typedef T	value_type

typedef Alloc_	Alloc

typedef Iter_< T >	Iter

typedef Iter_< const T >	ConstIter

typedef IterR_< T >	IterR

typedef IterR_< const T >	ConstIterR

Public Member Functions
	List (const Alloc &alloc=Alloc(), int threadMax=10)

	~List ()

template<class T_ >
void	push_front (T_ &&val)
	Insert new element constructed with `val` at the beginning of the list. More...

template<class T_ >
void	push_back (T_ &&val)
	Add new element constructed with `val` onto the end of the list. More...

bool	pop_front (optional< T & > val=optnull)
	Remove element from the beginning of the list and move it into `val`. Returns true on success, false if there is no element to pop. More...

bool	pop_back (optional< T & > val=optnull)
	Remove element from the end of the list and move it into `val`. Returns true on success, false if there is no element to pop. More...

ConstIter	begin () const
	Get iterator to the beginning of the list. More...

Iter	begin ()

ConstIter	end () const
	Get iterator to the end of the list. More...

Iter	end ()

ConstIterR	rbegin () const
	Get reverse iterator to the end of the list. More...

IterR	rbegin ()

ConstIterR	rend () const
	Get reverse iterator to the beginning of the list. More...

IterR	rend ()

bool	front (T &val)
	Get a copy of the element at the beginning of the list. Returns true on success, false if there is no element. More...

bool	back (T &val)
	Get a copy of the element the end of the list. Returns true on success, false if there is no element. More...

template<class T_ >
Iter	insert (const Iter &it, T_ &&val)
	Insert new element constructed with `val` before iterator position. Returns iterator pointing to new element. More...

bool	erase (Iter &it, optional< T & > val=optnull)
	Erase element at iterator position and move it into `val`, and advance iterator. Returns true if this thread erased the element, false if already erased. More...

void	clear ()
	Remove all elements. More...

bool	empty () const
	Check whether the list does not contain any elements. More...

szt	size () const
	Number of elements in list. More...

Friends
template<class >
class	HazardMem

Detailed Description

template<class T, class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>
class honey::lockfree::List< T, Alloc_, Backoff, iterMax >

Lock-free doubly-linked list.

Based on the paper: "Lock-free deques and doubly linked lists", Sundell, et al. - 2008

Template Parameters

T	Container element type
Alloc_	Allocator for elements, should be lock-free. If using MemPool then ensure it has a bucket large enough to hold List<T>::Node.
Backoff	Backoff algorithm to reduce contention
iterMax	Max number of iterator instances per thread

Member Typedef Documentation

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

typedef Alloc_ honey::lockfree::List< T, Alloc_, Backoff, iterMax >::Alloc

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

typedef Iter_<const T> honey::lockfree::List< T, Alloc_, Backoff, iterMax >::ConstIter

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

typedef IterR_<const T> honey::lockfree::List< T, Alloc_, Backoff, iterMax >::ConstIterR

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

typedef Iter_<T> honey::lockfree::List< T, Alloc_, Backoff, iterMax >::Iter

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

typedef IterR_<T> honey::lockfree::List< T, Alloc_, Backoff, iterMax >::IterR

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

typedef T honey::lockfree::List< T, Alloc_, Backoff, iterMax >::value_type

Constructor & Destructor Documentation

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

honey::lockfree::List< T, Alloc_, Backoff, iterMax >::List	(	const Alloc &	alloc = `Alloc()`,
		int	threadMax = `10`
	)

inline

Parameters

alloc
threadMax	Max number of threads that can access this container. Use a thread pool so the threads have a longer life cycle than this container.

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

honey::lockfree::List< T, Alloc_, Backoff, iterMax >::~List ( )

inline

Member Function Documentation

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

bool honey::lockfree::List< T, Alloc_, Backoff, iterMax >::back ( T & val )

inline

Get a copy of the element the end of the list. Returns true on success, false if there is no element.

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

ConstIter honey::lockfree::List< T, Alloc_, Backoff, iterMax >::begin ( ) const

inline

Get iterator to the beginning of the list.

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

Iter honey::lockfree::List< T, Alloc_, Backoff, iterMax >::begin ( )

inline

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

void honey::lockfree::List< T, Alloc_, Backoff, iterMax >::clear ( )

inline

Remove all elements.

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

bool honey::lockfree::List< T, Alloc_, Backoff, iterMax >::empty ( ) const

inline

Check whether the list does not contain any elements.

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

ConstIter honey::lockfree::List< T, Alloc_, Backoff, iterMax >::end ( ) const

inline

Get iterator to the end of the list.

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

Iter honey::lockfree::List< T, Alloc_, Backoff, iterMax >::end ( )

inline

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

bool honey::lockfree::List< T, Alloc_, Backoff, iterMax >::erase	(	Iter &	it,
		optional< T & >	val = `optnull`
	)

inline

Erase element at iterator position and move it into val, and advance iterator. Returns true if this thread erased the element, false if already erased.

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

bool honey::lockfree::List< T, Alloc_, Backoff, iterMax >::front ( T & val )

inline

Get a copy of the element at the beginning of the list. Returns true on success, false if there is no element.

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

template<class T_ >

Iter honey::lockfree::List< T, Alloc_, Backoff, iterMax >::insert	(	const Iter &	it,
		T_ &&	val
	)

inline

Insert new element constructed with val before iterator position. Returns iterator pointing to new element.

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

bool honey::lockfree::List< T, Alloc_, Backoff, iterMax >::pop_back ( optional< T & > val = optnull )

inline

Remove element from the end of the list and move it into val. Returns true on success, false if there is no element to pop.

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

bool honey::lockfree::List< T, Alloc_, Backoff, iterMax >::pop_front ( optional< T & > val = optnull )

inline

Remove element from the beginning of the list and move it into val. Returns true on success, false if there is no element to pop.

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

template<class T_ >

void honey::lockfree::List< T, Alloc_, Backoff, iterMax >::push_back ( T_ && val )

inline

Add new element constructed with val onto the end of the list.

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

template<class T_ >

void honey::lockfree::List< T, Alloc_, Backoff, iterMax >::push_front ( T_ && val )

inline

Insert new element constructed with val at the beginning of the list.

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

ConstIterR honey::lockfree::List< T, Alloc_, Backoff, iterMax >::rbegin ( ) const

inline

Get reverse iterator to the end of the list.

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

IterR honey::lockfree::List< T, Alloc_, Backoff, iterMax >::rbegin ( )

inline

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

ConstIterR honey::lockfree::List< T, Alloc_, Backoff, iterMax >::rend ( ) const

inline

Get reverse iterator to the beginning of the list.

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

IterR honey::lockfree::List< T, Alloc_, Backoff, iterMax >::rend ( )

inline

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

szt honey::lockfree::List< T, Alloc_, Backoff, iterMax >::size ( ) const

inline

Number of elements in list.

Friends And Related Function Documentation

template<class T , class Alloc_ = SmallAllocator<T>, class Backoff = Backoff, uint8 iterMax = 2>

template<class >

friend class HazardMem

friend

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

src/common/Honey/Thread/LockFree/List.h