cds::container::SkipListSet< gc::nogc, T, Traits > Class Template Reference

Lock-free skip-list set (template specialization for gc::nogc) More...

#include <cds/container/skip_list_set_nogc.h>

Inheritance diagram for cds::container::SkipListSet< gc::nogc, T, Traits >:

Public Types
typedef base_class::gc	gc
	Garbage collector used.
typedef T	value_type
	Value type stored in the set.
typedef Traits	options
	Options specified.
typedef base_class::back_off	back_off
	Back-off strategy used.
typedef options::allocator	allocator_type
	Allocator type used for allocate/deallocate the skip-list nodes.
typedef base_class::item_counter	item_counter
	Item counting policy used.
typedef maker::key_comparator	key_comparator
	key compare functor
typedef base_class::memory_model	memory_model
	Memory ordering. See cds::opt::memory_model option.
typedef options::stat	stat
	internal statistics type
typedef base_class::random_level_generator	random_level_generator
	random level generator

Public Member Functions
	SkipListSet ()
	Default ctor.
	~SkipListSet ()
	Destructor destroys the set object.
template<typename Q >
iterator	insert (const Q &val)
	Inserts new node. More...
template<typename... Args>
iterator	emplace (Args &&...args)
	Inserts data of type value_type constructed with std::forward<Args>(args)... More...
template<typename Q >
std::pair< iterator, bool >	update (const Q &val, bool bInsert=true)
	Updates the item. More...
template<typename Q >
iterator	contains (Q const &key) const
	Checks whether the set contains key. More...
value_type *	get_min () const
value_type *	get_max () const
	Gets maximum key from the set. More...
void	clear ()
	Clears the set (non-atomic) More...
bool	empty () const
	Checks if the set is empty.
size_t	size () const
	Returns item count in the set. More...
stat const &	statistics () const
	Returns const reference to internal statistics.

Static Public Member Functions
static constexpr unsigned int	max_height () noexcept
	Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.

Forward iterators
typedef skip_list::details::iterator< typename base_class::iterator >	iterator
	Forward ordered iterator. More...
typedef skip_list::details::iterator< typename base_class::const_iterator >	const_iterator
	Const iterator type.
iterator	begin ()
	Returns a forward iterator addressing the first element in a set.
const_iterator	begin () const
	Returns a forward const iterator addressing the first element in a set.
const_iterator	cbegin () const
	Returns a forward const iterator addressing the first element in a set.
iterator	end ()
	Returns a forward iterator that addresses the location succeeding the last element in a set.
const_iterator	end () const
	Returns a forward const iterator that addresses the location succeeding the last element in a set.
const_iterator	cend () const
	Returns a forward const iterator that addresses the location succeeding the last element in a set.

Additional Inherited Members
Protected Types inherited from cds::intrusive::SkipListSet< cds::gc::nogc, T, Traits >
typedef node_type::atomic_ptr	atomic_node_ptr
	Atomic node pointer.
typedef cds::gc::nogc	gc
	No garbage collector is used.
typedef T	value_type
	type of value stored in the skip-list
typedef Traits	traits
	Traits template parameter.
typedef traits::hook	hook
	hook type
typedef hook::node_type	node_type
	node type
typedef implementation_defined	key_comparator
	key comparison functor based on Traits::compare and Traits::less
typedef get_node_traits< value_type, node_type, hook >::type	node_traits
	node traits
typedef traits::item_counter	item_counter
	Item counting policy.
typedef traits::memory_model	memory_model
	Memory ordering. See cds::opt::memory_model option.
typedef traits::random_level_generator	random_level_generator
	random level generator
typedef traits::allocator	allocator_type
	allocator for maintaining array of next pointers of the node
typedef traits::back_off	back_off
	Back-off strategy.
typedef traits::stat	stat
	internal statistics type
typedef traits::disposer	disposer
	disposer
typedef skip_list::details::iterator< gc, node_traits, back_off, false >	iterator
	Forward iterator. More...
typedef skip_list::details::iterator< gc, node_traits, back_off, true >	const_iterator
	Const iterator type.
Protected Member Functions inherited from cds::intrusive::SkipListSet< cds::gc::nogc, T, Traits >
	SkipListSet ()
	Default constructor. More...
	~SkipListSet ()
	Clears and destructs the skip-list.
bool	insert (value_type &val)
	Inserts new node. More...
template<typename Func >
std::pair< bool, bool >	update (value_type &val, Func func, bool bInsert=true)
	Updates the node. More...
template<typename Q , typename Func >
bool	find (Q &key, Func f) const
	Finds key. More...
template<typename Q , typename Less , typename Func >
bool	find_with (Q &key, Less pred, Func f) const
	Finds the key key using pred predicate for comparing. More...
template<typename Q >
value_type *	contains (Q const &key) const
	Checks whether the set contains key. More...
template<typename Q , typename Less >
value_type *	contains (Q const &key, Less pred) const
	Checks whether the set contains key using pred predicate for searching. More...
value_type *	get_min () const
	Gets minimum key from the set. More...
value_type *	get_max () const
	Gets maximum key from the set. More...
void	clear ()
	Clears the set (non-atomic) More...
size_t	size () const
	Returns item count in the set. More...
bool	empty () const
	Checks if the set is empty.
stat const &	statistics () const
	Returns const reference to internal statistics.
iterator	begin ()
	Returns a forward iterator addressing the first element in a set.
const_iterator	begin () const
	Returns a forward const iterator addressing the first element in a set.
const_iterator	cbegin () const
	Returns a forward const iterator addressing the first element in a set.
iterator	end ()
	Returns a forward iterator that addresses the location succeeding the last element in a set.
const_iterator	end () const
	Returns a forward const iterator that addresses the location succeeding the last element in a set.
const_iterator	cend () const
	Returns a forward const iterator that addresses the location succeeding the last element in a set.
Static Protected Member Functions inherited from cds::intrusive::SkipListSet< cds::gc::nogc, T, Traits >
static constexpr unsigned int	max_height () noexcept
	Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
Protected Attributes inherited from cds::intrusive::SkipListSet< cds::gc::nogc, T, Traits >
head_node	m_Head
	head tower (max height)
random_level_generator	m_RandomLevelGen
	random level generator instance
atomics::atomic< unsigned int >	m_nHeight
	estimated high level
item_counter	m_ItemCounter
	item counter
stat	m_Stat
	internal statistics
Static Protected Attributes inherited from cds::intrusive::SkipListSet< cds::gc::nogc, T, Traits >
static unsigned int const	c_nMaxHeight
	Max node height. The actual node height should be in range [0 .. c_nMaxHeight) More...

Detailed Description

template<typename T, class Traits = skip_list::traits>
class cds::container::SkipListSet< gc::nogc, T, Traits >

Lock-free skip-list set (template specialization for gc::nogc)

This specialization is intended for so-called persistent usage when no item reclamation may be performed. The class does not support deleting of list item. See SkipListSet for detailed description.

Template arguments:

• T - type to be stored in the list.
• Traits - type traits. See skip_list::traits for explanation.

It is possible to declare option-based list with cds::container::skip_list::make_traits metafunction istead of Traits template argument. Options template arguments of cds::container::skip_list::make_traits metafunction are:

• opt::compare - key comparison functor. No default functor is provided. If the option is not specified, the opt::less is used.
• opt::less - specifies binary predicate used for key comparison. Default is std::less<T>.
• opt::item_counter - the type of item counting feature. Default is atomicity::empty_item_counter that is no item counting.
• opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default) or opt::v::sequential_consistent (sequentially consisnent memory model).
• skip_list::random_level_generator - random level generator. Can be skip_list::xor_shift, skip_list::turbo or user-provided one. See skip_list::random_level_generator option description for explanation. Default is skip_list::turbo32.
• opt::allocator - allocator for skip-list node. Default is CDS_DEFAULT_ALLOCATOR.
• opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
• opt::stat - internal statistics. Available types: skip_list::stat, skip_list::empty_stat (the default)

Member Typedef Documentation

template<typename T , class Traits = skip_list::traits>

typedef skip_list::details::iterator< typename base_class::iterator > cds::container::SkipListSet< gc::nogc, T, Traits >::iterator

Forward ordered iterator.

The forward iterator for a split-list has some features:

• it has no post-increment operator
• it depends on iterator of underlying OrderedList

Member Function Documentation

template<typename T , class Traits = skip_list::traits>

void cds::container::SkipListSet< gc::nogc, T, Traits >::clear ( )

inline

Clears the set (non-atomic)

The function is not atomic. Finding and/or inserting is prohibited while clearing. Otherwise an unpredictable result may be encountered. Thus, clear() may be used only for debugging purposes.

template<typename T , class Traits = skip_list::traits>

template<typename Q >

iterator cds::container::SkipListSet< gc::nogc, T, Traits >::contains ( Q const &  key ) const

inline

Checks whether the set contains key.

The function searches the item with key equal to key and returns an iterator to item found or end() if the key is not fund

template<typename T , class Traits = skip_list::traits>

template<typename... Args>

iterator cds::container::SkipListSet< gc::nogc, T, Traits >::emplace ( Args &&...  args )

inline

Inserts data of type value_type constructed with std::forward<Args>(args)...

Return an iterator pointing to inserted item if success end() otherwise

template<typename T , class Traits = skip_list::traits>

value_type* cds::container::SkipListSet< gc::nogc, T, Traits >::get_max ( ) const

inline

Gets maximum key from the set.

The function returns nullptr if the set is empty

template<typename T , class Traits = skip_list::traits>

value_type* cds::container::SkipListSet< gc::nogc, T, Traits >::get_min ( ) const

inline

/ Gets minimum key from the set /** If the set is empty the function returns nullptr

template<typename T , class Traits = skip_list::traits>

template<typename Q >

iterator cds::container::SkipListSet< gc::nogc, T, Traits >::insert ( const Q &  val )

inline

Inserts new node.

The function inserts val in the set if it does not contain an item with key equal to val.

Return an iterator pointing to inserted item if success, otherwise end()

template<typename T , class Traits = skip_list::traits>

size_t cds::container::SkipListSet< gc::nogc, T, Traits >::size ( ) const

inline

Returns item count in the set.

The value returned depends on item counter type provided by Traits template parameter. If it is atomicity::empty_item_counter this function always returns 0. The function is not suitable for checking the set emptiness, use empty member function for this purpose.

template<typename T , class Traits = skip_list::traits>

template<typename Q >

std::pair<iterator, bool> cds::container::SkipListSet< gc::nogc, T, Traits >::update ( const Q &  val, bool  bInsert = true  )

inline

Updates the item.

The operation inserts new item if val is not found in the set and bInsert is true. Otherwise, if that key exists, the function returns an iterator that points to item found.

Returns std::pair<iterator, bool> where first is an iterator pointing to item found or inserted or end() if val is not found and bInsert is false, second is true if new item has been added or false if the item already is in the set.

---

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

• cds/container/skip_list_set_nogc.h