amino::Set< KeyType > Class Template Reference

This is an implementation of lock-free hash set data structure, based on algorithm described in two paper "Split-Ordered Lists - Lock-free Resizable Hash Tables" by Ori Shalev Tel Aviv University and Nir Shavit Tel-Aviv University and Sun Microsystems Laboratories "High Performance Dynamic Lock-Free Hash Tables and List-Based Set" by Maged M. Michael. More...

#include <lockfree_set.h>

List of all members.

Public Member Functions
	Set (int expectedSetSize=DEFAULT_SEGMENT_SIZE *DEFAULT_ARRAY_SIZE, float expectedLoadFactor=MAX_LOAD)
	Create a new set with explicitly specified expected size and load factor. The number of dummy nodes has a maximum of expectedSize This isn't a limitation of actual elements stored in set. But the average search number will increase if number of elements is bigger than expectedSize.
	~Set ()
	Destructor, supposed to be called when its associated data structure is to be deleted.
bool	empty ()
	Judge if the set is empty.
unsigned int	size ()
	Get the size of set.
bool	insert (KeyType element)
	Add the specified element into the set.
bool	remove (KeyType element)
	Remove a specified element by value.
bool	search (const KeyType &element)
	Judge if a specified element is in the set.

---

Detailed Description

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

This is an implementation of lock-free hash set data structure, based on algorithm described in two paper "Split-Ordered Lists - Lock-free Resizable Hash Tables" by Ori Shalev Tel Aviv University and Nir Shavit Tel-Aviv University and Sun Microsystems Laboratories "High Performance Dynamic Lock-Free Hash Tables and List-Based Set" by Maged M. Michael.

The internal data structure is a single linked LockFreeOrderedList. Elements are sorted by "binary reversal" of hash key of elements. Additionally, an array of dummy nodes is stored for allowing quick access to elements in the middle of lock-free ordered list. Elements are wrapped by SetNode before stored into set.

Author:

Hui Rui

Template Parameters:

KeyType

Type of elements stored in the set

---

Constructor & Destructor Documentation

template<typename KeyType>

amino::Set< KeyType >::Set	(	int	expectedSetSize = DEFAULT_SEGMENT_SIZE * DEFAULT_ARRAY_SIZE,
		float	expectedLoadFactor = MAX_LOAD
	)			[inline, explicit]

Create a new set with explicitly specified expected size and load factor. The number of dummy nodes has a maximum of expectedSize This isn't a limitation of actual elements stored in set. But the average search number will increase if number of elements is bigger than expectedSize.

Parameters:

	expectedSetSize	The expected size of set
	expectedLoadFactor	Average load factor. Number of dummy nodes will expand 2X if the actual load factor is higher than this parameter.

template<typename KeyType>

amino::Set< KeyType >::~Set

(

)

[inline]

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

---

Member Function Documentation

template<typename KeyType>

bool amino::Set< KeyType >::empty

(

)

[inline]

Judge if the set is empty.

Returns:

If the ordered list not stores the regular node, return true. else return false.

template<typename KeyType>

unsigned int amino::Set< KeyType >::size

(

)

[inline]

Get the size of set.

Returns:

The size of set

template<typename KeyType>

bool amino::Set< KeyType >::insert

(

KeyType

element

)

[inline]

Add the specified element into the set.

Parameters:

element

The element to be added

Returns:

If the element inserted successful return true, else return false

template<typename KeyType>

bool amino::Set< KeyType >::remove

(

KeyType

element

)

[inline]

Remove a specified element by value.

Parameters:

element

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::Set< KeyType >::search

(

const KeyType &

element

)

[inline]

Judge if a specified element is in the set.

Parameters:

element

The element to be searched

Returns:

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

---

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

• include/amino/lockfree_set.h