cds  2.2.0
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 >:
cds::intrusive::SkipListSet< cds::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_typeget_min () const
 
value_typeget_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_typecontains (Q const &key) const
 Checks whether the set contains key. More...
 
template<typename Q , typename Less >
value_typecontains (Q const &key, Less pred) const
 Checks whether the set contains key using pred predicate for searching. More...
 
value_typeget_min () const
 Gets minimum key from the set. More...
 
value_typeget_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)
 
item_counter m_ItemCounter
 item counter
 
random_level_generator m_RandomLevelGen
 random level generator instance
 
atomics::atomic< unsigned int > m_nHeight
 estimated high level
 
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:

Member Typedef Documentation

§ iterator

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

§ clear()

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.

§ contains()

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

§ emplace()

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

§ get_max()

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

§ get_min()

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

§ insert()

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()

§ size()

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.

§ update()

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 2.2.0 Developed by Maxim Khizhinsky aka khizmax 2007 - 2017
Autogenerated Wed Jan 4 2017 08:49:41 by Doxygen 1.8.12