amino::OrderedList< KeyType > Class Template Reference

This is a lock-free list, based on:. More...

#include <ordered_list.h>

List of all members.

Public Types
typedef __list_iterator< KeyType >	iterator
typedef __list_const_iterator < KeyType >	const_iterator
Public Member Functions
	OrderedList ()
	constructor. constructs a empty with head is NULL
	~OrderedList ()
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	push_front (const KeyType &e)
	Add a specified element in to the list.(the same to the insert method.).
bool	insert (int index, const KeyType &e)
	Add the specified element into the list.
bool	empty ()
	Judge if the list is empty.
iterator	begin ()
iterator	end ()
bool	remove (const KeyType &e)
	Remove a specified element by value.
bool	remove (const KeyType &e, atomic< NodeType< KeyType > * > *start)
	Remove a specified element by value.
bool	search (const KeyType &e)
	Judge if the element is in the list.
bool	search (const KeyType &e, atomic< NodeType< KeyType > * > *start)
	Judge if the element is in the list.
Friends
class	Set

---

Detailed Description

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

This is a lock-free list, based on:.

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

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. All method related to index is not thread safe. Add() will add the element to the head of the list which is different with the normal list.

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::OrderedList< KeyType >::iterator

template<typename KeyType>

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

---

Constructor & Destructor Documentation

template<typename KeyType>

amino::OrderedList< KeyType >::OrderedList

(

)

[inline]

constructor. constructs a empty with head is NULL

template<typename KeyType>

amino::OrderedList< KeyType >::~OrderedList

(

)

[inline]

---

Member Function Documentation

template<typename KeyType>

bool amino::OrderedList< 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::OrderedList< KeyType >::push_front

(

const KeyType &

e

)

[inline]

Add a specified element in to the list.(the same to the insert method.).

Parameters:

e

The element to be added

Returns:

True for success and false for failed

template<typename KeyType>

bool amino::OrderedList< 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>

bool amino::OrderedList< KeyType >::empty

(

)

[inline]

Judge if the list is empty.

Returns:

True is the list is empty, else return false

template<typename KeyType>

iterator amino::OrderedList< KeyType >::begin

(

)

[inline]

template<typename KeyType>

iterator amino::OrderedList< KeyType >::end

(

)

[inline]

template<typename KeyType>

bool amino::OrderedList< 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::OrderedList< KeyType >::remove	(	const KeyType &	e,
		atomic< NodeType< KeyType > * > *	start
	)			[inline]

Remove a specified element by value.

Parameters:

	e	The element to be removed
	start	address of the begin position

Returns:

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

CAS operation, mark holder.cur as deleted. if successful, the thread attempts to remove it next step. else, it implies that one or more of three events must have taken place since the snapshot in Find method was taken. Then goto the start of this while loop

CAS operation, set the next pointer of prew to the next pointer of cur. If successful, delete holder.cur by delNode of SMR. If failed, ,it implies that another thread must have removed the node from the list after the success of the MARK CAS before. and a new Find is invoked in order to guarantee that the number of deleted nodes not yet removed never exceeds the maximum number of concurrent threads operating on the object

template<typename KeyType>

bool amino::OrderedList< 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

template<typename KeyType>

bool amino::OrderedList< KeyType >::search	(	const KeyType &	e,
		atomic< NodeType< KeyType > * > *	start
	)			[inline]

Judge if the element is in the list.

Parameters:

	e	The element to be searched
	start	Address of the begin position

Returns:

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

---

Friends And Related Function Documentation

template<typename KeyType>

friend class Set [friend]

---

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

• include/amino/ordered_list.h