OgreHaptics::ConcurrentQueue< T > Class Template Reference

ConcurrentQueue is an unbounded FIFO (First-In First-Out) data structure that permits producers and consumers on multiple threads of execution to concurrently push and pop elements. More...

#include <OgreHapticsConcurrentQueue.h>

Inheritance diagram for OgreHaptics::ConcurrentQueue< T >:

List of all members.

Public Member Functions
	ConcurrentQueue ()
	Standard constructor.
	~ConcurrentQueue ()
	Standard destructor.
HazardPtr *	allocateHazardPtr (void)
	Allocates a HazardPtr for the queue instance to be used by the calling thread.
void	retireHazardPtr (HazardPtr *ptr)
	Marks the given HazardPtr to be available for reuse by other threads.
void	push (HazardPtr *ptr, const T &value)
	Inserts the given value at the back of the queue in a thread-safe manner.
bool	pop (HazardPtr *ptr, T &destination)
	Pops an entry from the queue in a thread-safe manner.
Classes
class	HazardPtr
	HazardPtr provides a safe mechanism for threads to advertise to all other threads making use of the same data structure about their memory usage. More...
struct	Node

---

Detailed Description

template<typename T>
class OgreHaptics::ConcurrentQueue< T >

ConcurrentQueue is an unbounded FIFO (First-In First-Out) data structure that permits producers and consumers on multiple threads of execution to concurrently push and pop elements.

The implementation is lock-free if the atomic primitive compare-and-swap is lock-free.

Remarks:

The implementation provides safe memory reclamation of added nodes using hazard pointers. Every thread must manage its own hazard pointer, which needs to be allocated before the thread uses the structure its pop and/or push operations.

There is not choosen to use thread local storage per instance of the queue class, since this would incurr a performance overhead, and would make memory management of hazard pointers unclear.

The ConcurrentQueue does not provide methods for iterating over the elements it contains, since this would need additional mechanisms providing concurrent access to the elements of the queue.

This class is based on the article 'Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects' by Maged. M. Michael, which can be found at http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf and the article 'Lock-Free Algorithms' in Game Programming Gems 6 by Toby Jones.

Todo:

The ConcurrentQueue class could be extended with an allocation and a deallocation policy for the creation of internally used nodes. This would allow the use of thread local node pooles to improve performance.

Definition at line 62 of file OgreHapticsConcurrentQueue.h.

---

Constructor & Destructor Documentation

template<typename T>

OgreHaptics::ConcurrentQueue< T >::ConcurrentQueue

(

)

Standard constructor.

Definition at line 138 of file OgreHapticsConcurrentQueue.h.

template<typename T>

OgreHaptics::ConcurrentQueue< T >::~ConcurrentQueue

(

)

Standard destructor.

Note:

After cleaning up the queue any hazard pointers associated with the queue are invalid and must not be used.

Definition at line 154 of file OgreHapticsConcurrentQueue.h.

---

Member Function Documentation

template<typename T>

HazardPtr* OgreHaptics::ConcurrentQueue< T >::allocateHazardPtr

(

void

)

Allocates a HazardPtr for the queue instance to be used by the calling thread.

All allocated HazardPtrs must be retired if the thread wishes to no longer use the queue.

Remarks:

The queue will first try to use a retired HazardPtr. If no available pointers can be found a new instance is added.

See also:

ConcurrentQueue::retireHazardPtr

Definition at line 187 of file OgreHapticsConcurrentQueue.h.

template<typename T>

void OgreHaptics::ConcurrentQueue< T >::retireHazardPtr

(

HazardPtr *

ptr

)

Marks the given HazardPtr to be available for reuse by other threads.

Remarks:

Left over retired nodes to which the HazardPtr points will still eventually be freed.

Definition at line 229 of file OgreHapticsConcurrentQueue.h.

template<typename T>

void OgreHaptics::ConcurrentQueue< T >::push	(	HazardPtr *	ptr,
		const T &	value
	)

Inserts the given value at the back of the queue in a thread-safe manner.

Parameters:

	ptr	Pointer to the hazard pointer owned by the thread in which the operation is called.
	value	Reference of the value to insert.

Definition at line 247 of file OgreHapticsConcurrentQueue.h.

template<typename T>

bool OgreHaptics::ConcurrentQueue< T >::pop	(	HazardPtr *	ptr,
		T &	destination
	)

Pops an entry from the queue in a thread-safe manner.

Parameters:

	ptr	Pointer to the hazard pointer owned by the thread in which the operation is called.
	destination	Reference to the variable to which the entry will be assigned when popping was successful.

Returns:

true if the destination value has been set successfully (e.g. the queue was not empty), false otherwise.

Definition at line 302 of file OgreHapticsConcurrentQueue.h.

---

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

• OgreHapticsConcurrentQueue.h