--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
+
+ Source code repo: http://github.com/khizmax/libcds/
+ Download: http://sourceforge.net/projects/libcds/files/
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions are met:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef CDSLIB_INTRUSIVE_SKIP_LIST_NOGC_H
+#define CDSLIB_INTRUSIVE_SKIP_LIST_NOGC_H
+
+#include <type_traits>
+#include <memory>
+#include <cds/gc/nogc.h>
+#include <cds/intrusive/details/skip_list_base.h>
+#include <cds/opt/compare.h>
+#include <cds/details/binary_functor_wrapper.h>
+
+namespace cds { namespace intrusive {
+
+ //@cond
+ namespace skip_list {
+ template <typename Tag>
+ class node< cds::gc::nogc, Tag >
+ {
+ public:
+ typedef cds::gc::nogc gc; ///< Garbage collector
+ typedef Tag tag; ///< tag
+
+ typedef atomics::atomic<node * > atomic_ptr;
+ typedef atomic_ptr tower_item_type;
+
+ protected:
+ atomic_ptr m_pNext; ///< Next item in bottom-list (list at level 0)
+ unsigned int m_nHeight; ///< Node height (size of m_arrNext array). For node at level 0 the height is 1.
+ atomic_ptr * m_arrNext; ///< Array of next items for levels 1 .. m_nHeight - 1. For node at level 0 \p m_arrNext is \p nullptr
+
+ public:
+ /// Constructs a node of height 1 (a bottom-list node)
+ node()
+ : m_pNext( nullptr )
+ , m_nHeight(1)
+ , m_arrNext( nullptr )
+ {}
+
+ /// Constructs a node of height \p nHeight
+ void make_tower( unsigned int nHeight, atomic_ptr * nextTower )
+ {
+ assert( nHeight > 0 );
+ assert( (nHeight == 1 && nextTower == nullptr) // bottom-list node
+ || (nHeight > 1 && nextTower != nullptr) // node at level of more than 0
+ );
+
+ m_arrNext = nextTower;
+ m_nHeight = nHeight;
+ }
+
+ atomic_ptr * release_tower()
+ {
+ atomic_ptr * pTower = m_arrNext;
+ m_arrNext = nullptr;
+ m_nHeight = 1;
+ return pTower;
+ }
+
+ atomic_ptr * get_tower() const
+ {
+ return m_arrNext;
+ }
+
+ /// Access to element of next pointer array
+ atomic_ptr& next( unsigned int nLevel )
+ {
+ assert( nLevel < height());
+ assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr));
+
+ return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
+ }
+
+ /// Access to element of next pointer array (const version)
+ atomic_ptr const& next( unsigned int nLevel ) const
+ {
+ assert( nLevel < height());
+ assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr );
+
+ return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
+ }
+
+ /// Access to element of next pointer array (same as \ref next function)
+ atomic_ptr& operator[]( unsigned int nLevel )
+ {
+ return next( nLevel );
+ }
+
+ /// Access to element of next pointer array (same as \ref next function)
+ atomic_ptr const& operator[]( unsigned int nLevel ) const
+ {
+ return next( nLevel );
+ }
+
+ /// Height of the node
+ unsigned int height() const
+ {
+ return m_nHeight;
+ }
+
+ /// Clears internal links
+ void clear()
+ {
+ assert( m_arrNext == nullptr );
+ m_pNext.store( nullptr, atomics::memory_order_release );
+ }
+
+ bool is_cleared() const
+ {
+ return m_pNext.load( atomics::memory_order_relaxed ) == nullptr
+ && m_arrNext == nullptr
+ && m_nHeight <= 1
+;
+ }
+ };
+ } // namespace skip_list
+
+ namespace skip_list { namespace details {
+
+ template <typename NodeTraits, typename BackOff, bool IsConst>
+ class iterator< cds::gc::nogc, NodeTraits, BackOff, IsConst>
+ {
+ public:
+ typedef cds::gc::nogc gc;
+ typedef NodeTraits node_traits;
+ typedef BackOff back_off;
+ typedef typename node_traits::node_type node_type;
+ typedef typename node_traits::value_type value_type;
+ static constexpr bool const c_isConst = IsConst;
+
+ typedef typename std::conditional< c_isConst, value_type const &, value_type &>::type value_ref;
+ friend class iterator< gc, node_traits, back_off, !c_isConst >;
+
+ protected:
+ typedef typename node_type::atomic_ptr atomic_ptr;
+ node_type * m_pNode;
+
+ public: // for internal use only!!!
+ iterator( node_type& refHead )
+ : m_pNode( refHead[0].load( atomics::memory_order_relaxed ))
+ {}
+
+ static iterator from_node( node_type * pNode )
+ {
+ iterator it;
+ it.m_pNode = pNode;
+ return it;
+ }
+
+ public:
+ iterator()
+ : m_pNode( nullptr )
+ {}
+
+ iterator( iterator const& s)
+ : m_pNode( s.m_pNode )
+ {}
+
+ value_type * operator ->() const
+ {
+ assert( m_pNode != nullptr );
+ assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
+
+ return node_traits::to_value_ptr( m_pNode );
+ }
+
+ value_ref operator *() const
+ {
+ assert( m_pNode != nullptr );
+ assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
+
+ return *node_traits::to_value_ptr( m_pNode );
+ }
+
+ /// Pre-increment
+ iterator& operator ++()
+ {
+ if ( m_pNode )
+ m_pNode = m_pNode->next(0).load( atomics::memory_order_relaxed );
+ return *this;
+ }
+
+ iterator& operator =(const iterator& src)
+ {
+ m_pNode = src.m_pNode;
+ return *this;
+ }
+
+ template <typename Bkoff, bool C>
+ bool operator ==(iterator<gc, node_traits, Bkoff, C> const& i ) const
+ {
+ return m_pNode == i.m_pNode;
+ }
+ template <typename Bkoff, bool C>
+ bool operator !=(iterator<gc, node_traits, Bkoff, C> const& i ) const
+ {
+ return !( *this == i );
+ }
+ };
+ }} // namespace skip_list::details
+ //@endcond
+
+ /// Lock-free skip-list set (template specialization for gc::nogc)
+ /** @ingroup cds_intrusive_map
+ @anchor cds_intrusive_SkipListSet_nogc
+
+ This specialization is so-called append-only when no item
+ reclamation may be performed. The class does not support deleting of list item.
+
+ See \ref cds_intrusive_SkipListSet_hp "SkipListSet" for description of skip-list.
+
+ <b>Template arguments</b> :
+ - \p T - type to be stored in the set. The type must be based on \p skip_list::node (for \p skip_list::base_hook)
+ or it must have a member of type \p skip_list::node (for \p skip_list::member_hook).
+ - \p Traits - type traits, default is \p skip_list::traits.
+ It is possible to declare option-based list with \p cds::intrusive::skip_list::make_traits metafunction
+ istead of \p Traits template argument.
+
+ <b>Iterators</b>
+
+ The class supports a forward iterator (\ref iterator and \ref const_iterator).
+ The iteration is ordered.
+
+ The iterator class supports the following minimalistic interface:
+ \code
+ struct iterator {
+ // Default ctor
+ iterator();
+
+ // Copy ctor
+ iterator( iterator const& s);
+
+ value_type * operator ->() const;
+ value_type& operator *() const;
+
+ // Pre-increment
+ iterator& operator ++();
+
+ // Copy assignment
+ iterator& operator = (const iterator& src);
+
+ bool operator ==(iterator const& i ) const;
+ bool operator !=(iterator const& i ) const;
+ };
+ \endcode
+ Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
+
+ <b>How to use</b>
+
+ You should incorporate \p skip_list::node into your struct \p T and provide
+ appropriate \p skip_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits you
+ define a struct based on \p skip_list::traits.
+
+ Example for base hook:
+ \code
+ #include <cds/intrusive/skip_list_nogc.h>
+
+ // Data stored in skip list
+ struct my_data: public cds::intrusive::skip_list::node< cds::gc::nogc >
+ {
+ // key field
+ std::string strKey;
+
+ // other data
+ // ...
+ };
+
+ // my_data compare functor
+ struct my_data_cmp {
+ int operator()( const my_data& d1, const my_data& d2 )
+ {
+ return d1.strKey.compare( d2.strKey );
+ }
+
+ int operator()( const my_data& d, const std::string& s )
+ {
+ return d.strKey.compare(s);
+ }
+
+ int operator()( const std::string& s, const my_data& d )
+ {
+ return s.compare( d.strKey );
+ }
+ };
+
+
+ // Declare traits
+ struct my_traits: public cds::intrusive::skip_list::traits
+ {
+ typedef cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::nogc > > hook;
+ typedef my_data_cmp compare;
+ };
+
+ // Declare skip-list set type
+ typedef cds::intrusive::SkipListSet< cds::gc::nogc, my_data, my_traits > traits_based_set;
+ \endcode
+
+ Equivalent option-based code:
+ \code
+ // GC-related specialization
+ #include <cds/intrusive/skip_list_nogc.h>
+
+ struct my_data {
+ // see above
+ };
+ struct compare {
+ // see above
+ };
+
+ // Declare option-based skip-list set
+ typedef cds::intrusive::SkipListSet< cds::gc::nogc
+ ,my_data
+ , typename cds::intrusive::skip_list::make_traits<
+ cds::intrusive::opt::hook< cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::nogc > > >
+ ,cds::intrusive::opt::compare< my_data_cmp >
+ >::type
+ > option_based_set;
+ \endcode
+ */
+ template <
+ typename T
+#ifdef CDS_DOXYGEN_INVOKED
+ ,typename Traits = skip_list::traits
+#else
+ ,typename Traits
+#endif
+ >
+ class SkipListSet< cds::gc::nogc, T, Traits >
+ {
+ public:
+ 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 typename traits::hook hook; ///< hook type
+ typedef typename hook::node_type node_type; ///< node type
+
+# ifdef CDS_DOXYGEN_INVOKED
+ typedef implementation_defined key_comparator; ///< key comparison functor based on \p Traits::compare and \p Traits::less
+# else
+ typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
+# endif
+ typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
+
+ typedef typename traits::item_counter item_counter; ///< Item counting policy
+ typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
+ typedef typename traits::random_level_generator random_level_generator ; ///< random level generator
+ typedef typename traits::allocator allocator_type; ///< allocator for maintaining array of next pointers of the node
+ typedef typename traits::back_off back_off; ///< Back-off strategy
+ typedef typename traits::stat stat; ///< internal statistics type
+ typedef typename traits::disposer disposer; ///< disposer
+
+ /// Max node height. The actual node height should be in range <tt>[0 .. c_nMaxHeight)</tt>
+ /**
+ The max height is specified by \ref skip_list::random_level_generator "random level generator" constant \p m_nUpperBound
+ but it should be no more than 32 (\p skip_list::c_nHeightLimit).
+ */
+ static unsigned int const c_nMaxHeight = std::conditional<
+ (random_level_generator::c_nUpperBound <= skip_list::c_nHeightLimit),
+ std::integral_constant< unsigned int, random_level_generator::c_nUpperBound >,
+ std::integral_constant< unsigned int, skip_list::c_nHeightLimit >
+ >::type::value;
+
+ //@cond
+ static unsigned int const c_nMinHeight = 3;
+ //@endcond
+
+ protected:
+ typedef typename node_type::atomic_ptr atomic_node_ptr; ///< Atomic node pointer
+
+ protected:
+ //@cond
+ typedef skip_list::details::intrusive_node_builder< node_type, atomic_node_ptr, allocator_type > intrusive_node_builder;
+
+ typedef typename std::conditional<
+ std::is_same< typename traits::internal_node_builder, cds::opt::none >::value
+ ,intrusive_node_builder
+ ,typename traits::internal_node_builder
+ >::type node_builder;
+
+ typedef std::unique_ptr< node_type, typename node_builder::node_disposer > scoped_node_ptr;
+
+ struct position {
+ node_type * pPrev[ c_nMaxHeight ];
+ node_type * pSucc[ c_nMaxHeight ];
+
+ node_type * pCur;
+ };
+
+ class head_node: public node_type
+ {
+ typename node_type::atomic_ptr m_Tower[c_nMaxHeight];
+
+ public:
+ head_node( unsigned int nHeight )
+ {
+ for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
+ m_Tower[i].store( nullptr, atomics::memory_order_relaxed );
+
+ node_type::make_tower( nHeight, m_Tower );
+ }
+
+ node_type * head() const
+ {
+ return const_cast<node_type *>( static_cast<node_type const *>(this));
+ }
+
+ void clear()
+ {
+ for (unsigned int i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
+ m_Tower[i].store( nullptr, atomics::memory_order_relaxed );
+ node_type::m_pNext.store( nullptr, atomics::memory_order_relaxed );
+ }
+ };
+ //@endcond
+
+ protected:
+ 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
+ mutable stat m_Stat; ///< internal statistics
+
+ protected:
+ //@cond
+ unsigned int random_level()
+ {
+ // Random generator produces a number from range [0..31]
+ // We need a number from range [1..32]
+ return m_RandomLevelGen() + 1;
+ }
+
+ template <typename Q>
+ node_type * build_node( Q v )
+ {
+ return node_builder::make_tower( v, m_RandomLevelGen );
+ }
+
+ static void dispose_node( node_type * pNode )
+ {
+ assert( pNode != nullptr );
+ typename node_builder::node_disposer()( pNode );
+ disposer()( node_traits::to_value_ptr( pNode ));
+ }
+
+ template <typename Q, typename Compare >
+ bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound, bool bStrictSearch ) const
+ {
+ node_type * pPred;
+ node_type * pSucc;
+ node_type * pCur = nullptr;
+
+ int nCmp = 1;
+
+ unsigned int nHeight = c_nMaxHeight;
+ retry:
+ if ( !bStrictSearch )
+ nHeight = m_nHeight.load( memory_model::memory_order_relaxed );
+ pPred = m_Head.head();
+
+ for ( int nLevel = (int) nHeight - 1; nLevel >= 0; --nLevel ) {
+ while ( true ) {
+ pCur = pPred->next( nLevel ).load( memory_model::memory_order_relaxed );
+
+ if ( !pCur ) {
+ // end of the list at level nLevel - goto next level
+ break;
+ }
+
+ pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
+
+ if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ) != pCur
+ || pCur->next( nLevel ).load( memory_model::memory_order_acquire ) != pSucc )
+ {
+ goto retry;
+ }
+
+ nCmp = cmp( *node_traits::to_value_ptr( pCur ), val );
+ if ( nCmp < 0 )
+ pPred = pCur;
+ else if ( nCmp == 0 && bStopIfFound )
+ goto found;
+ else
+ break;
+ }
+
+ pos.pPrev[ nLevel ] = pPred;
+ pos.pSucc[ nLevel ] = pCur;
+ }
+
+ if ( nCmp != 0 )
+ return false;
+
+ found:
+ pos.pCur = pCur;
+ return pCur && nCmp == 0;
+ }
+
+ template <typename Func>
+ bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
+ {
+ unsigned int nHeight = pNode->height();
+
+ for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
+ pNode->next( nLevel ).store( nullptr, memory_model::memory_order_relaxed );
+
+ {
+ node_type * p = pos.pSucc[0];
+ pNode->next( 0 ).store( pos.pSucc[ 0 ], memory_model::memory_order_release );
+ if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed )) {
+ return false;
+ }
+ f( val );
+ }
+
+ for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
+ node_type * p = nullptr;
+ while ( true ) {
+ node_type * q = pos.pSucc[ nLevel ];
+
+ if ( pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, memory_model::memory_order_relaxed )) {
+ p = q;
+ if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ))
+ break;
+ }
+
+ // Renew insert position
+ find_position( val, pos, key_comparator(), false, true );
+ }
+ }
+ return true;
+ }
+
+ template <typename Q, typename Compare, typename Func>
+ node_type * find_with_( Q& val, Compare cmp, Func f ) const
+ {
+ position pos;
+ if ( find_position( val, pos, cmp, true, false )) {
+ assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
+
+ f( *node_traits::to_value_ptr( pos.pCur ), val );
+
+ m_Stat.onFindFastSuccess();
+ return pos.pCur;
+ }
+ else {
+ m_Stat.onFindFastFailed();
+ return nullptr;
+ }
+ }
+
+ void increase_height( unsigned int nHeight )
+ {
+ unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
+ while ( nCur < nHeight && !m_nHeight.compare_exchange_weak( nCur, nHeight, memory_model::memory_order_acquire, atomics::memory_order_relaxed ));
+ }
+ //@endcond
+
+ public:
+ /// Default constructor
+ /**
+ The constructor checks whether the count of guards is enough
+ for skip-list and may raise an exception if not.
+ */
+ SkipListSet()
+ : m_Head( c_nMaxHeight )
+ , m_nHeight( c_nMinHeight )
+ {
+ static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
+
+ // Barrier for head node
+ atomics::atomic_thread_fence( memory_model::memory_order_release );
+ }
+
+ /// Clears and destructs the skip-list
+ ~SkipListSet()
+ {
+ clear();
+ }
+
+ public:
+ ///@name Forward iterators
+ //@{
+ /// Forward iterator
+ /**
+ The forward iterator for a split-list has some features:
+ - it has no post-increment operator
+ - it depends on iterator of underlying \p OrderedList
+ */
+ typedef skip_list::details::iterator< gc, node_traits, back_off, false > iterator;
+
+ /// Const iterator type
+ typedef skip_list::details::iterator< gc, node_traits, back_off, true > const_iterator;
+
+ /// Returns a forward iterator addressing the first element in a set
+ iterator begin()
+ {
+ return iterator( *m_Head.head());
+ }
+
+ /// Returns a forward const iterator addressing the first element in a set
+ const_iterator begin() const
+ {
+ return const_iterator( *m_Head.head());
+ }
+ /// Returns a forward const iterator addressing the first element in a set
+ const_iterator cbegin() const
+ {
+ return const_iterator( *m_Head.head());
+ }
+
+ /// Returns a forward iterator that addresses the location succeeding the last element in a set.
+ iterator end()
+ {
+ return iterator();
+ }
+
+ /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
+ const_iterator end() const
+ {
+ return const_iterator();
+ }
+ /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
+ const_iterator cend() const
+ {
+ return const_iterator();
+ }
+ //@}
+
+ protected:
+ //@cond
+ iterator nonconst_end() const
+ {
+ return iterator();
+ }
+ //@endcond
+
+ public:
+ /// Inserts new node
+ /**
+ The function inserts \p val in the set if it does not contain
+ an item with key equal to \p val.
+
+ Returns \p true if \p val is placed into the set, \p false otherwise.
+ */
+ bool insert( value_type& val )
+ {
+ node_type * pNode = node_traits::to_node_ptr( val );
+ scoped_node_ptr scp( pNode );
+ unsigned int nHeight = pNode->height();
+ bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
+ bool bTowerMade = false;
+
+ position pos;
+ while ( true )
+ {
+ bool bFound = find_position( val, pos, key_comparator(), true, true );
+ if ( bFound ) {
+ // scoped_node_ptr deletes the node tower if we create it
+ if ( !bTowerMade )
+ scp.release();
+
+ m_Stat.onInsertFailed();
+ return false;
+ }
+
+ if ( !bTowerOk ) {
+ build_node( pNode );
+ nHeight = pNode->height();
+ bTowerMade =
+ bTowerOk = true;
+ }
+
+ if ( !insert_at_position( val, pNode, pos, []( value_type& ) {} )) {
+ m_Stat.onInsertRetry();
+ continue;
+ }
+
+ increase_height( nHeight );
+ ++m_ItemCounter;
+ m_Stat.onAddNode( nHeight );
+ m_Stat.onInsertSuccess();
+ scp.release();
+ return true;
+ }
+ }
+
+ /// Updates the node
+ /**
+ The operation performs inserting or changing data with lock-free manner.
+
+ If the item \p val is not found in the set, then \p val is inserted into the set
+ iff \p bInsert is \p true.
+ Otherwise, the functor \p func is called with item found.
+ The functor signature is:
+ \code
+ void func( bool bNew, value_type& item, value_type& val );
+ \endcode
+ with arguments:
+ - \p bNew - \p true if the item has been inserted, \p false otherwise
+ - \p item - item of the set
+ - \p val - argument \p val passed into the \p %update() function
+ If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
+ refer to the same thing.
+
+ The functor can change non-key fields of the \p item; however, \p func must guarantee
+ that during changing no any other modifications could be made on this item by concurrent threads.
+
+ Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
+ \p second is \p true if new item has been added or \p false if the item with \p key
+ already is in the set.
+
+ @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
+ */
+ template <typename Func>
+ std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
+ {
+ node_type * pNode = node_traits::to_node_ptr( val );
+ scoped_node_ptr scp( pNode );
+ unsigned int nHeight = pNode->height();
+ bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
+ bool bTowerMade = false;
+
+ position pos;
+ while ( true )
+ {
+ bool bFound = find_position( val, pos, key_comparator(), true, true );
+ if ( bFound ) {
+ // scoped_node_ptr deletes the node tower if we create it before
+ if ( !bTowerMade )
+ scp.release();
+
+ func( false, *node_traits::to_value_ptr(pos.pCur), val );
+ m_Stat.onUpdateExist();
+ return std::make_pair( true, false );
+ }
+
+ if ( !bInsert ) {
+ scp.release();
+ return std::make_pair( false, false );
+ }
+
+ if ( !bTowerOk ) {
+ build_node( pNode );
+ nHeight = pNode->height();
+ bTowerMade =
+ bTowerOk = true;
+ }
+
+ if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
+ m_Stat.onInsertRetry();
+ continue;
+ }
+
+ increase_height( nHeight );
+ ++m_ItemCounter;
+ scp.release();
+ m_Stat.onAddNode( nHeight );
+ m_Stat.onUpdateNew();
+ return std::make_pair( true, true );
+ }
+ }
+ //@cond
+ template <typename Func>
+ CDS_DEPRECATED("ensure() is deprecated, use update()")
+ std::pair<bool, bool> ensure( value_type& val, Func func )
+ {
+ return update( val, func, true );
+ }
+ //@endcond
+
+ /// Finds \p key
+ /** \anchor cds_intrusive_SkipListSet_nogc_find_func
+ The function searches the item with key equal to \p key and calls the functor \p f for item found.
+ The interface of \p Func functor is:
+ \code
+ struct functor {
+ void operator()( value_type& item, Q& key );
+ };
+ \endcode
+ where \p item is the item found, \p key is the <tt>find</tt> function argument.
+
+ The functor can change non-key fields of \p item. Note that the functor is only guarantee
+ that \p item cannot be disposed during functor is executing.
+ The functor does not serialize simultaneous access to the set \p item. If such access is
+ possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
+
+ The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
+ can modify both arguments.
+
+ Note the hash functor specified for class \p Traits template parameter
+ should accept a parameter of type \p Q that can be not the same as \p value_type.
+
+ The function returns \p true if \p key is found, \p false otherwise.
+ */
+ template <typename Q, typename Func>
+ bool find( Q& key, Func f ) const
+ {
+ return find_with_( key, key_comparator(), f ) != nullptr;
+ }
+ //@cond
+ template <typename Q, typename Func>
+ bool find( Q const& key, Func f ) const
+ {
+ return find_with_( key, key_comparator(), f ) != nullptr;
+ }
+ //@endcond
+
+ /// Finds the key \p key using \p pred predicate for comparing
+ /**
+ The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_func "find(Q&, Func)"
+ but \p pred predicate is used for key compare.
+ \p Less has the interface like \p std::less.
+ \p pred must imply the same element order as the comparator used for building the set.
+ */
+ template <typename Q, typename Less, typename Func>
+ bool find_with( Q& key, Less pred, Func f ) const
+ {
+ CDS_UNUSED( pred );
+ return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
+ }
+ //@cond
+ template <typename Q, typename Less, typename Func>
+ bool find_with( Q const& key, Less pred, Func f ) const
+ {
+ CDS_UNUSED( pred );
+ return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
+ }
+ //@endcond
+
+ /// Checks whether the set contains \p key
+ /**
+ The function searches the item with key equal to \p key
+ and returns pointer to item found or \p nullptr.
+ */
+ template <typename Q>
+ value_type * contains( Q const& key ) const
+ {
+ node_type * pNode = find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
+ if ( pNode )
+ return node_traits::to_value_ptr( pNode );
+ return nullptr;
+ }
+ //@cond
+ template <typename Q>
+ CDS_DEPRECATED("deprecated, use contains()")
+ value_type * find( Q const& key ) const
+ {
+ return contains( key );
+ }
+ //@endcond
+
+ /// Checks whether the set contains \p key using \p pred predicate for searching
+ /**
+ The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
+ \p Less functor has the interface like \p std::less.
+ \p Less must imply the same element order as the comparator used for building the set.
+ */
+ template <typename Q, typename Less>
+ value_type * contains( Q const& key, Less pred ) const
+ {
+ CDS_UNUSED( pred );
+ node_type * pNode = find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
+ if ( pNode )
+ return node_traits::to_value_ptr( pNode );
+ return nullptr;
+ }
+ //@cond
+ template <typename Q, typename Less>
+ CDS_DEPRECATED("deprecated, use contains()")
+ value_type * find_with( Q const& key, Less pred ) const
+ {
+ return contains( key, pred );
+ }
+ //@endcond
+
+ /// Gets minimum key from the set
+ /**
+ If the set is empty the function returns \p nullptr
+ */
+ value_type * get_min() const
+ {
+ return node_traits::to_value_ptr( m_Head.head()->next( 0 ));
+ }
+
+ /// Gets maximum key from the set
+ /**
+ The function returns \p nullptr if the set is empty
+ */
+ value_type * get_max() const
+ {
+ node_type * pPred;
+
+ unsigned int nHeight = m_nHeight.load( memory_model::memory_order_relaxed );
+ pPred = m_Head.head();
+
+ for ( int nLevel = (int) nHeight - 1; nLevel >= 0; --nLevel ) {
+ while ( true ) {
+ node_type * pCur = pPred->next( nLevel ).load( memory_model::memory_order_relaxed );
+
+ if ( !pCur ) {
+ // end of the list at level nLevel - goto next level
+ break;
+ }
+ pPred = pCur;
+ }
+ }
+ return pPred && pPred != m_Head.head() ? node_traits::to_value_ptr( pPred ) : nullptr;
+ }
+
+ /// 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, \p clear() may be used only for debugging purposes.
+ */
+ void clear()
+ {
+ node_type * pNode = m_Head.head()->next(0).load( memory_model::memory_order_relaxed );
+ m_Head.clear();
+ m_ItemCounter.reset();
+ m_nHeight.store( c_nMinHeight, memory_model::memory_order_release );
+
+ while ( pNode ) {
+ node_type * pNext = pNode->next(0).load( memory_model::memory_order_relaxed );
+ dispose_node( pNode );
+ pNode = pNext;
+ }
+ }
+
+ /// Returns item count in the set
+ /**
+ The value returned depends on item counter type provided by \p Traits template parameter.
+ For \p atomicity::empty_item_counter the function always returns 0.
+ The function is not suitable for checking the set emptiness, use \p empty().
+ */
+ size_t size() const
+ {
+ return m_ItemCounter;
+ }
+
+ /// Checks if the set is empty
+ bool empty() const
+ {
+ return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
+ }
+
+ /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
+ static constexpr unsigned int max_height() noexcept
+ {
+ return c_nMaxHeight;
+ }
+
+ /// Returns const reference to internal statistics
+ stat const& statistics() const
+ {
+ return m_Stat;
+ }
+ };
+
+}} // namespace cds::intrusive
+
+
+#endif // #ifndef CDSLIB_INTRUSIVE_SKIP_LIST_IMPL_H
projects / c11concurrency-benchmarks.git / blobdiff