amino::List< KeyType > Class Template Reference

This is an implementation of a lock-free linked list data structure. The implementation is according to the paper High Performance Dynamic Lock-Free Hash Tables and List-Based Sets by Maged M. Michael, 2002. To gain a complete understanding of this data structure, please first read this paper, available at: http://www.research.ibm.com/people/m/michael/spaa-2002.pdf. More...

#include <list.h>

List of all members.

Public Types
typedef __list_iterator< KeyType >	iterator
typedef __list_const_iterator < KeyType >	const_iterator
Public Member Functions
	List ()
	constructor. constructs a empty with head is dummy
	~List ()
	Destructor, supposed to be called when its associated data structure is to be deleted.
bool	front (KeyType &ret)
	Get the first element in the list. If the list is empty, it will return false. else return true and assign the first element to the parameter.
bool	insert (int index, const KeyType &e)
	Add the specified element into the list.
iterator	begin ()
iterator	end ()
const_iterator	begin () const
const_iterator	end () const
int	size ()
	Get the size of list.
bool	push_front (const KeyType &e)
	Add a specified element in to the list's first position.
bool	empty ()
	Judge if the list is empty.
bool	remove (const KeyType &e)
	Remove a specified element by value.
bool	search (const KeyType &e)
	Judge if the element is in the list.
Protected Types
typedef SMR< NodeType< KeyType > , NHPOINTER >::HP_Rec	HazardP
Protected Member Functions
	List (const List &s)
List &	operator= (const List &st)
Protected Attributes
atomic< NodeType< KeyType > * >	head
NodeType< KeyType > *	dummy
SMR< NodeType< KeyType > , NHPOINTER > *	mm

---

Detailed Description

template<typename KeyType>
class amino::List< KeyType >

This is an implementation of a lock-free linked list data structure. The implementation is according to the paper High Performance Dynamic Lock-Free Hash Tables and List-Based Sets by Maged M. Michael, 2002. To gain a complete understanding of this data structure, please first read this paper, available at: http://www.research.ibm.com/people/m/michael/spaa-2002.pdf.

This lock-free linked list is an unbounded thread-safe linked list. A LockFreeList is an appropriate choice when many threads will share access to a common collection. This list does not permit null elements.

This is a lock-free implementation intended for highly scalable add, remove and contains which is thread safe. Add() will add the element to the head of the list which is different with the normal list.

Iterator is not thread-safe and only used when debugging.

ABA prevention method is based on Maged M. Michael's: Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects

Author:

Xiao Jun Dai

Template Parameters:

KeyType

The type of the element which is stored in the list

---

Member Typedef Documentation

template<typename KeyType>

typedef __list_iterator<KeyType> amino::List< KeyType >::iterator

template<typename KeyType>

typedef __list_const_iterator<KeyType> amino::List< KeyType >::const_iterator

template<typename KeyType>

typedef SMR<NodeType<KeyType>, NHPOINTER>::HP_Rec amino::List< KeyType >::HazardP [protected]

---

Constructor & Destructor Documentation

template<typename KeyType>

amino::List< KeyType >::List

(

const List< KeyType > &

s

)

[inline, protected]

template<typename KeyType>

amino::List< KeyType >::List

(

)

[inline]

constructor. constructs a empty with head is dummy

template<typename KeyType>

amino::List< KeyType >::~List

(

)

[inline]

Destructor, supposed to be called when its associated data structure is to be deleted.

---

Member Function Documentation

template<typename KeyType>

List& amino::List< KeyType >::operator=

(

const List< KeyType > &

st

)

[inline, protected]

template<typename KeyType>

bool amino::List< KeyType >::front

(

KeyType &

ret

)

[inline]

Get the first element in the list. If the list is empty, it will return false. else return true and assign the first element to the parameter.

Parameters:

ret

The first element in the list. It is valid if the return value is true.

Returns:

If the list is empty return false, else return true.

template<typename KeyType>

bool amino::List< KeyType >::insert	(	int	index,
		const KeyType &	e
	)			[inline]

Add the specified element into the list.

Parameters:

	index	Not work in this function now.
	e	The element to be added

Returns:

If the element inserted successful return true, else return false

template<typename KeyType>

iterator amino::List< KeyType >::begin

(

)

[inline]

template<typename KeyType>

iterator amino::List< KeyType >::end

(

)

[inline]

template<typename KeyType>

const_iterator amino::List< KeyType >::begin

(

)

const [inline]

template<typename KeyType>

const_iterator amino::List< KeyType >::end

(

)

const [inline]

template<typename KeyType>

int amino::List< KeyType >::size

(

)

[inline]

Get the size of list.

Returns:

The size of list

template<typename KeyType>

bool amino::List< KeyType >::push_front

(

const KeyType &

e

)

[inline]

Add a specified element in to the list's first position.

Parameters:

e

The element to be added

Returns:

True for success and false for failed

template<typename KeyType>

bool amino::List< KeyType >::empty

(

)

[inline]

Judge if the list is empty.

Returns:

True is the list is empty, else return false

template<typename KeyType>

bool amino::List< KeyType >::remove

(

const KeyType &

e

)

[inline]

Remove a specified element by value.

Parameters:

e

The element to be removed

Returns:

If the value exists in the list, remove it and return true. else return false.

template<typename KeyType>

bool amino::List< KeyType >::search

(

const KeyType &

e

)

[inline]

Judge if the element is in the list.

Parameters:

e

The element to be searched

Returns:

If the element exists in the list, return true. else return false

---

Member Data Documentation

template<typename KeyType>

atomic<NodeType<KeyType>*> amino::List< KeyType >::head [protected]

Pointer to header node, initialized by a dummy node.

template<typename KeyType>

NodeType<KeyType>* amino::List< KeyType >::dummy [protected]

a pointer created for initializing of head pointer, for the performance reason

template<typename KeyType>

SMR<NodeType<KeyType>, NHPOINTER>* amino::List< KeyType >::mm [protected]

for memory management

---

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

• include/amino/list.h