tiny_dlna::ListLockFree< T, Alloc > Class Template Reference

Lock-free double linked list using atomic operations. More...

#include <ListLockFree.h>

Classes
class	Iterator
	Bidirectional iterator for ListLockFree. More...
struct	Node

Public Types
using	NodeAlloc = typename std::allocator_traits< Alloc >::template rebind_alloc< Node >

Public Member Functions
	ListLockFree (const Alloc &alloc=Alloc())
	Default constructor.
	ListLockFree (const ListLockFree &ref)
	Copy constructor (not thread-safe for the source list)
template<size_t N>
	ListLockFree (const T(&a)[N], const Alloc &alloc=Alloc())
	Constructor using array.
	~ListLockFree ()
bool	swap (ListLockFree< T > &ref)
	Swap contents with another list. Not implemented (returns false).
bool	push_back (const T &data)
bool	push_front (const T &data)
bool	insert (Iterator it, const T &data)
bool	pop_front ()
bool	pop_back ()
bool	pop_front (T &data)
bool	pop_back (T &data)
bool	erase (Iterator it)
Iterator	begin ()
Iterator	end ()
Iterator	rbegin ()
Iterator	rend ()
size_t	size ()
bool	empty ()
bool	clear ()
T &	operator[] (int index)
	Access element at index (O(n)). Not thread-safe under concurrency. Make sure that no other thread modifies the list while using this.
T &	back ()
	Provides the last element.
T &	front ()
	Provides the first element.

Protected Member Functions
Node *	createNode ()
void	deleteNode (Node *p_delete)
void	link ()

Protected Attributes
Node	first
Node	last
std::atomic< size_t >	record_count {0}
NodeAlloc	node_alloc_ {}

Friends
class	Iterator
	Iterator is a friend for access to internals.

Detailed Description

template<class T, class Alloc = DLNA_ALLOCATOR<T>>
class tiny_dlna::ListLockFree< T, Alloc >

Lock-free double linked list using atomic operations.

Author

Phil Schatzmann

Copyright

GPLv3

Template Parameters

T

This implementation provides thread-safe operations without using locks. It uses atomic pointers and compare-and-swap operations for synchronization.

Note

Thread-safety caveats:

• Some operations like size() and operator[] may not be perfectly consistent in highly concurrent scenarios but will be eventually consistent.
• The copy constructor is not thread-safe for the source list.
• Iterators are invalidated if the list is modified.
• The allocator (if used) must be thread-safe for concurrent use.

Member Typedef Documentation

NodeAlloc

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

using tiny_dlna::ListLockFree< T, Alloc >::NodeAlloc = typename std::allocator_traits<Alloc>::template rebind_alloc<Node>

Constructor & Destructor Documentation

ListLockFree() [1/3]

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

tiny_dlna::ListLockFree< T, Alloc >::ListLockFree ( const Alloc &  alloc = Alloc() )

inline

Default constructor.

ListLockFree() [2/3]

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

tiny_dlna::ListLockFree< T, Alloc >::ListLockFree ( const ListLockFree< T, Alloc > &  ref )

inline

Copy constructor (not thread-safe for the source list)

ListLockFree() [3/3]

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

template<size_t N>

tiny_dlna::ListLockFree< T, Alloc >::ListLockFree ( const T(&)  a[N], const Alloc &  alloc = Alloc()  )

inline

Constructor using array.

~ListLockFree()

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

tiny_dlna::ListLockFree< T, Alloc >::~ListLockFree ( )

inline

Member Function Documentation

back()

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

T & tiny_dlna::ListLockFree< T, Alloc >::back ( )

inline

Provides the last element.

begin()

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

Iterator tiny_dlna::ListLockFree< T, Alloc >::begin ( )

inline

clear()

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

bool tiny_dlna::ListLockFree< T, Alloc >::clear ( )

inline

createNode()

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

Node * tiny_dlna::ListLockFree< T, Alloc >::createNode ( )

inlineprotected

deleteNode()

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

void tiny_dlna::ListLockFree< T, Alloc >::deleteNode ( Node *  p_delete )

inlineprotected

empty()

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

bool tiny_dlna::ListLockFree< T, Alloc >::empty ( )

inline

end()

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

Iterator tiny_dlna::ListLockFree< T, Alloc >::end ( )

inline

erase()

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

bool tiny_dlna::ListLockFree< T, Alloc >::erase ( Iterator  it )

inline

front()

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

T & tiny_dlna::ListLockFree< T, Alloc >::front ( )

inline

Provides the first element.

insert()

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

bool tiny_dlna::ListLockFree< T, Alloc >::insert ( Iterator  it, const T &  data  )

inline

link()

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

void tiny_dlna::ListLockFree< T, Alloc >::link ( )

inlineprotected

operator[]()

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

T & tiny_dlna::ListLockFree< T, Alloc >::operator[] ( int  index )

inline

Access element at index (O(n)). Not thread-safe under concurrency. Make sure that no other thread modifies the list while using this.

Parameters

index

Index of element

Returns

Reference to element, or a static dummy value if out of bounds (no exceptions)

Warning

If index is out of bounds, returns a reference to a static dummy value.

pop_back() [1/2]

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

bool tiny_dlna::ListLockFree< T, Alloc >::pop_back ( )

inline

pop_back() [2/2]

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

bool tiny_dlna::ListLockFree< T, Alloc >::pop_back ( T &  data )

inline

pop_front() [1/2]

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

bool tiny_dlna::ListLockFree< T, Alloc >::pop_front ( )

inline

pop_front() [2/2]

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

bool tiny_dlna::ListLockFree< T, Alloc >::pop_front ( T &  data )

inline

push_back()

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

bool tiny_dlna::ListLockFree< T, Alloc >::push_back ( const T &  data )

inline

push_front()

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

bool tiny_dlna::ListLockFree< T, Alloc >::push_front ( const T &  data )

inline

rbegin()

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

Iterator tiny_dlna::ListLockFree< T, Alloc >::rbegin ( )

inline

rend()

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

Iterator tiny_dlna::ListLockFree< T, Alloc >::rend ( )

inline

size()

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

size_t tiny_dlna::ListLockFree< T, Alloc >::size ( )

inline

swap()

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

bool tiny_dlna::ListLockFree< T, Alloc >::swap ( ListLockFree< T > &  ref )

inline

Swap contents with another list. Not implemented (returns false).

Returns

Always false. Not lock-free.

Friends And Related Function Documentation

Iterator

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

friend class Iterator

friend

Iterator is a friend for access to internals.

Member Data Documentation

first

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

Node tiny_dlna::ListLockFree< T, Alloc >::first

protected

last

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

Node tiny_dlna::ListLockFree< T, Alloc >::last

protected

node_alloc_

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

NodeAlloc tiny_dlna::ListLockFree< T, Alloc >::node_alloc_ {}

protected

record_count

template<class T , class Alloc = DLNA_ALLOCATOR<T>>

std::atomic<size_t> tiny_dlna::ListLockFree< T, Alloc >::record_count {0}

protected

---

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

• src/concurrency/ListLockFree.h