internal::SMR< T, K > Class Template Reference

SMR way to prevent ABA for lock-free data structrue based on the following paper:. More...

#include <smr.h>

List of all members.

Public Types
typedef T	NodeType
typedef HPRecType< NodeType, K >	HP_Rec
typedef SMRListNode< NodeType * >	SMR_Node
Public Member Functions
	~SMR ()
void	delNode (NodeType *node)
	Lock-free program should call this function whenever a shared node should be deleted. This function delays the deletion of nodes until no other threads need it.
void	delNode (HP_Rec *my_hprec, NodeType *node)
	Lock-free program should call this function whenever a shared node should be deleted. This function delays the deletion of nodes until no other threads need it.
HP_Rec *	getHPRec ()
	Get the thread local hazard pointer record.
void	retire (HP_Rec *my_hprec, int index)
	Assign NULL to one hazard pointer so that the original pointer is not marked as "in-use" any more.
void	retire (HP_Rec *my_hprec, NodeType *p)
void	retire (int index)
	Assign NULL to one hazard pointer so that the original pointer is not marked as "in-use" any more.
void	retire (NodeType *p)
NodeType *	newNode ()
	allocate a new node. This function will reuse nodes from freelist if the macro FREELIST is defined.
NodeType *	newNode (HP_Rec *my_hprec)
	allocate a new node. This function will reuse nodes from freelist if the macro FREELIST is defined.
void	employ (int index, NodeType *pointer)
	Lock-free program should call this method to mark one node as in-use.
void	employ (HP_Rec *my_hprec, int index, NodeType *pointer)
	Lock-free program should call this method to mark one node as in-use.
Friends
SMR< NodeType, K > *	getSMR ()
	Factory method to return instance of SMR<T, K>.

---

Detailed Description

template<typename T, int K>
class internal::SMR< T, K >

SMR way to prevent ABA for lock-free data structrue based on the following paper:.

Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects

MM Michael - IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2004

This class is used to managed memory for lock free algorithm. For C program, we only need one SMR for the whole program. But For C++ program, we need type information so delete can work correctly. For each composition of template parameter, we will have one SMR instance.

Author:

Mo Jiong Qiu, Zhi Gan (ganzhi@gmail.com)

Template Parameters:

	T	The type of node stored in SMR.
	K	Number of hazard pointers for one thread

---

Member Typedef Documentation

template<typename T, int K>

typedef T internal::SMR< T, K >::NodeType

template<typename T, int K>

typedef HPRecType<NodeType, K> internal::SMR< T, K >::HP_Rec

template<typename T, int K>

typedef SMRListNode<NodeType*> internal::SMR< T, K >::SMR_Node

---

Constructor & Destructor Documentation

template<typename T, int K>

internal::SMR< T, K >::~SMR

(

)

[inline]

---

Member Function Documentation

template<typename T, int K>

void internal::SMR< T, K >::delNode

(

NodeType *

node

)

[inline]

Lock-free program should call this function whenever a shared node should be deleted. This function delays the deletion of nodes until no other threads need it.

Parameters:

node

The node which should be deleted after all reference to it has expired

template<typename T, int K>

void internal::SMR< T, K >::delNode	(	HP_Rec *	my_hprec,
		NodeType *	node
	)			[inline]

Lock-free program should call this function whenever a shared node should be deleted. This function delays the deletion of nodes until no other threads need it.

Parameters:

	my_hprec	A thread local hazard pointer record which can be got by calling getHPRec();
	node	The node which should be deleted after all reference to it has expired

template<typename T, int K>

HP_Rec* internal::SMR< T, K >::getHPRec

(

)

[inline]

Get the thread local hazard pointer record.

Returns:

hazard pointer record for current thread

template<typename T, int K>

void internal::SMR< T, K >::retire	(	HP_Rec *	my_hprec,
		int	index
	)			[inline]

Assign NULL to one hazard pointer so that the original pointer is not marked as "in-use" any more.

If a node was emplyed by one thread, and it's not needed after a while, this thread can call this method to explicitly remove this node from SMR from hazard pointer list. After this method is called, this thread won't prevent deletion of targeting pointer any more.

Parameters:

	my_hprec	A thread local hazard pointer record which can be got by calling getHPRec();
	index	Index of removing nodes. The removing pointer is inserted into SMR with this index by calling employ(int, NodeType *) method.

template<typename T, int K>

void internal::SMR< T, K >::retire	(	HP_Rec *	my_hprec,
		NodeType *	p
	)			[inline]

template<typename T, int K>

void internal::SMR< T, K >::retire

(

int

index

)

[inline]

Assign NULL to one hazard pointer so that the original pointer is not marked as "in-use" any more.

If a node was emplyed by one thread, and it's not needed after a while, this thread can call this method to explicitly remove this node from SMR from hazard pointer list. After this method is called, this thread won't prevent deletion of targeting pointer any more.

Parameters:

index

Index of removing nodes. The removing pointer is inserted into SMR with this index by calling employ(int, NodeType *) method.

template<typename T, int K>

void internal::SMR< T, K >::retire

(

NodeType *

p

)

[inline]

template<typename T, int K>

NodeType* internal::SMR< T, K >::newNode

(

)

[inline]

allocate a new node. This function will reuse nodes from freelist if the macro FREELIST is defined.

template<typename T, int K>

NodeType* internal::SMR< T, K >::newNode

(

HP_Rec *

my_hprec

)

[inline]

allocate a new node. This function will reuse nodes from freelist if the macro FREELIST is defined.

Parameters:

my_hprec

A thread local hazard pointer record which can be got by calling getHPRec();

template<typename T, int K>

void internal::SMR< T, K >::employ	(	int	index,
		NodeType *	pointer
	)			[inline]

Lock-free program should call this method to mark one node as in-use.

Parameters:

	my_hprec	A thread local hazard pointer record which can be got by calling getHPRec();
	index	index of inserting node. It should be less than template paramete K.
	pointer	pointer to the inserting node.

template<typename T, int K>

void internal::SMR< T, K >::employ	(	HP_Rec *	my_hprec,
		int	index,
		NodeType *	pointer
	)			[inline]

Lock-free program should call this method to mark one node as in-use.

Parameters:

	my_hprec	A thread local hazard pointer record which can be got by calling getHPRec();
	index	index of inserting node. It should be less than template paramete K.
	pointer	pointer to the inserting node.

---

Friends And Related Function Documentation

template<typename T, int K>

SMR<NodeType, K>* getSMR

(

)

[friend]

Factory method to return instance of SMR<T, K>.

Template Parameters:

	Type	of node stored inside SMR.
	Number	of hazard pointers for one thread.

Returns:

A SMR instance with the specified template parameter.

---

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

• include/amino/smr.h