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:

Generated on Tue Dec 9 13:39:39 2008 for Amino by  doxygen 1.5.6