intrusive MSQueue refactoring (not tested)

[libcds.git] / cds / intrusive / skip_list_nogc.h

diff --git a/cds/intrusive/skip_list_nogc.h b/cds/intrusive/skip_list_nogc.h
index 112e1b278d5afc99631b559c2fc4e6bc7855dd20..ba4ce74658afdbbc7718b9d42e239e6120dd8522 100644 (file)
--- a/cds/intrusive/skip_list_nogc.h
+++ b/cds/intrusive/skip_list_nogc.h
@@ -5,10 +5,10 @@
 
 #include <type_traits>
 #include <memory>
 
 #include <type_traits>
 #include <memory>

+#include <functional>   // ref

 #include <cds/gc/nogc.h>
 #include <cds/gc/nogc.h>

-#include <cds/intrusive/skip_list_base.h>
+#include <cds/intrusive/details/skip_list_base.h>

 #include <cds/opt/compare.h>
 #include <cds/opt/compare.h>

-#include <cds/ref.h>

 #include <cds/details/binary_functor_wrapper.h>
 
 namespace cds { namespace intrusive {
 #include <cds/details/binary_functor_wrapper.h>
 
 namespace cds { namespace intrusive {


@@ -22,13 +22,13 @@ namespace cds { namespace intrusive {
             typedef cds::gc::nogc   gc          ;   ///< Garbage collector
             typedef Tag             tag         ;   ///< tag
 
             typedef cds::gc::nogc   gc          ;   ///< Garbage collector
             typedef Tag             tag         ;   ///< tag
 

-            typedef CDS_ATOMIC::atomic<node * > atomic_ptr;
+            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.
             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 NULL
+            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)
 
         public:
             /// Constructs a node of height 1 (a bottom-list node)


@@ -103,12 +103,12 @@ namespace cds { namespace intrusive {
             void clear()
             {
                 assert( m_arrNext == nullptr );
             void clear()
             {
                 assert( m_arrNext == nullptr );

-                m_pNext.store( nullptr, CDS_ATOMIC::memory_order_release );
+                m_pNext.store( nullptr, atomics::memory_order_release );

             }
 
             bool is_cleared() const
             {
             }
 
             bool is_cleared() const
             {

-                return m_pNext.load( CDS_ATOMIC::memory_order_relaxed ) == nullptr
+                return m_pNext.load( atomics::memory_order_relaxed ) == nullptr

                     && m_arrNext == nullptr
                     && m_nHeight <= 1
 ;
                     && m_arrNext == nullptr
                     && m_nHeight <= 1
 ;


@@ -137,7 +137,7 @@ namespace cds { namespace intrusive {
 
         public: // for internal use only!!!
             iterator( node_type& refHead )
 
         public: // for internal use only!!!
             iterator( node_type& refHead )

-                : m_pNode( refHead[0].load( CDS_ATOMIC::memory_order_relaxed ) )
+                : m_pNode( refHead[0].load( atomics::memory_order_relaxed ) )

             {}
 
             static iterator from_node( node_type * pNode )
             {}
 
             static iterator from_node( node_type * pNode )


@@ -176,7 +176,7 @@ namespace cds { namespace intrusive {
             iterator& operator ++()
             {
                 if ( m_pNode )
             iterator& operator ++()
             {
                 if ( m_pNode )

-                    m_pNode = m_pNode->next(0).load( CDS_ATOMIC::memory_order_relaxed );
+                    m_pNode = m_pNode->next(0).load( atomics::memory_order_relaxed );

                 return *this;
             }
 
                 return *this;
             }
 


@@ -264,7 +264,7 @@ namespace cds { namespace intrusive {
             bool operator !=(iterator const& i ) const;
         };
         \endcode
             bool operator !=(iterator const& i ) const;
         };
         \endcode

-        Note, the iterator object returned by \ref end, \p cend member functions points to \p NULL and should not be dereferenced.
+        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>
 
 
         <b>How to use</b>
 


@@ -410,31 +410,6 @@ namespace cds { namespace intrusive {
             node_type *   pCur;
         };
 
             node_type *   pCur;
         };
 

-#   ifndef CDS_CXX11_LAMBDA_SUPPORT
-        struct empty_insert_functor {
-            void operator()( value_type& )
-            {}
-        };
-
-        struct empty_find_functor {
-            template <typename Q>
-            void operator()( value_type& item, Q& val )
-            {}
-        };
-
-        template <typename Func>
-        struct insert_at_ensure_functor {
-            Func m_func;
-            insert_at_ensure_functor( Func f ) : m_func(f) {}
-
-            void operator()( value_type& item )
-            {
-                cds::unref( m_func)( true, item, item );
-            }
-        };
-
-#   endif // ifndef CDS_CXX11_LAMBDA_SUPPORT
-

         class head_node: public node_type
         {
             typename node_type::atomic_ptr   m_Tower[c_nMaxHeight];
         class head_node: public node_type
         {
             typename node_type::atomic_ptr   m_Tower[c_nMaxHeight];


@@ -443,7 +418,7 @@ namespace cds { namespace intrusive {
             head_node( unsigned int nHeight )
             {
                 for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
             head_node( unsigned int nHeight )
             {
                 for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )

-                    m_Tower[i].store( nullptr, CDS_ATOMIC::memory_order_relaxed );
+                    m_Tower[i].store( nullptr, atomics::memory_order_relaxed );

 
                 node_type::make_tower( nHeight, m_Tower );
             }
 
                 node_type::make_tower( nHeight, m_Tower );
             }


@@ -456,8 +431,8 @@ namespace cds { namespace intrusive {
             void clear()
             {
                 for (unsigned int i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
             void clear()
             {
                 for (unsigned int i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )

-                    m_Tower[i].store( nullptr, CDS_ATOMIC::memory_order_relaxed );
-                node_type::m_pNext.store( nullptr, CDS_ATOMIC::memory_order_relaxed );
+                    m_Tower[i].store( nullptr, atomics::memory_order_relaxed );
+                node_type::m_pNext.store( nullptr, atomics::memory_order_relaxed );

             }
         };
         //@endcond
             }
         };
         //@endcond


@@ -467,7 +442,7 @@ namespace cds { namespace intrusive {
 
         item_counter                m_ItemCounter       ;   ///< item counter
         random_level_generator      m_RandomLevelGen    ;   ///< random level generator instance
 
         item_counter                m_ItemCounter       ;   ///< item counter
         random_level_generator      m_RandomLevelGen    ;   ///< random level generator instance

-        CDS_ATOMIC::atomic<unsigned int>    m_nHeight   ;   ///< estimated high level
+        atomics::atomic<unsigned int>    m_nHeight   ;   ///< estimated high level

         mutable stat                m_Stat              ;   ///< internal statistics
 
     protected:
         mutable stat                m_Stat              ;   ///< internal statistics
 
     protected:


@@ -559,7 +534,7 @@ namespace cds { namespace intrusive {
                 if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ) ) {
                     return false;
                 }
                 if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ) ) {
                     return false;
                 }

-                cds::unref( f )( val );
+                f( val );

             }
 
             for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
             }
 
             for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {


@@ -587,7 +562,7 @@ namespace cds { namespace intrusive {
             if ( find_position( val, pos, cmp, true, false )) {
                 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
 
             if ( find_position( val, pos, cmp, true, false )) {
                 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
 

-                cds::unref(f)( *node_traits::to_value_ptr( pos.pCur ), val );
+                f( *node_traits::to_value_ptr( pos.pCur ), val );

 
                 m_Stat.onFindFastSuccess();
                 return pos.pCur;
 
                 m_Stat.onFindFastSuccess();
                 return pos.pCur;


@@ -601,7 +576,7 @@ namespace cds { namespace intrusive {
         void increase_height( unsigned int nHeight )
         {
             unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
         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, CDS_ATOMIC::memory_order_relaxed ) );
+            while ( nCur < nHeight && !m_nHeight.compare_exchange_weak( nCur, nHeight, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) );

         }
         //@endcond
 
         }
         //@endcond
 


@@ -618,7 +593,7 @@ namespace cds { namespace intrusive {
             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
             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

-            CDS_ATOMIC::atomic_thread_fence( memory_model::memory_order_release );
+            atomics::atomic_thread_fence( memory_model::memory_order_release );

         }
 
         /// Clears and destructs the skip-list
         }
 
         /// Clears and destructs the skip-list


@@ -714,12 +689,7 @@ namespace cds { namespace intrusive {
                         bTowerOk = true;
                 }
 
                         bTowerOk = true;
                 }
 

-#       ifndef CDS_CXX11_LAMBDA_SUPPORT
-                if ( !insert_at_position( val, pNode, pos, empty_insert_functor() ))
-#       else
-                if ( !insert_at_position( val, pNode, pos, []( value_type& ) {} ))
-#       endif
-                {
+                if ( !insert_at_position( val, pNode, pos, []( value_type& ) {} )) {

                     m_Stat.onInsertRetry();
                     continue;
                 }
                     m_Stat.onInsertRetry();
                     continue;
                 }


@@ -753,7 +723,7 @@ namespace cds { namespace intrusive {
             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.
 
             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.
 

-            You can pass \p func argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
+            You can pass \p func argument by value or by reference using \p std::ref.

 
             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
             \p second is \p true if new item has been added or \p false if the item with \p key
 
             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
             \p second is \p true if new item has been added or \p false if the item with \p key


@@ -768,10 +738,6 @@ namespace cds { namespace intrusive {
             bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
             bool bTowerMade = false;
 
             bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
             bool bTowerMade = false;
 

-#       ifndef CDS_CXX11_LAMBDA_SUPPORT
-            insert_at_ensure_functor<Func> wrapper( func );
-#       endif
-

             position pos;
             while ( true )
             {
             position pos;
             while ( true )
             {


@@ -781,7 +747,7 @@ namespace cds { namespace intrusive {
                     if ( !bTowerMade )
                         scp.release();
 
                     if ( !bTowerMade )
                         scp.release();
 

-                    cds::unref(func)( false, *node_traits::to_value_ptr(pos.pCur), val );
+                    func( false, *node_traits::to_value_ptr(pos.pCur), val );

                     m_Stat.onEnsureExist();
                     return std::make_pair( true, false );
                 }
                     m_Stat.onEnsureExist();
                     return std::make_pair( true, false );
                 }


@@ -793,12 +759,7 @@ namespace cds { namespace intrusive {
                         bTowerOk = true;
                 }
 
                         bTowerOk = true;
                 }
 

-#       ifdef CDS_CXX11_LAMBDA_SUPPORT
-                if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { cds::unref(func)( true, item, item ); }))
-#       else
-                if ( !insert_at_position( val, pNode, pos, cds::ref(wrapper) ))
-#       endif
-                {
+                if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {

                     m_Stat.onInsertRetry();
                     continue;
                 }
                     m_Stat.onInsertRetry();
                     continue;
                 }


@@ -823,7 +784,7 @@ namespace cds { namespace intrusive {
             \endcode
             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 
             \endcode
             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 

-            You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
+            You can pass \p f argument by value or by reference using \p std::ref.

 
             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 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.


@@ -868,7 +829,7 @@ namespace cds { namespace intrusive {
             \endcode
             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 
             \endcode
             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 

-            You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
+            You can pass \p f argument by value or by reference using \p std::ref.

 
             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 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.


@@ -910,12 +871,7 @@ namespace cds { namespace intrusive {
         template <typename Q>
         value_type * find( Q const& val ) const
         {
         template <typename Q>
         value_type * find( Q const& val ) const
         {

-            node_type * pNode =
-#       ifdef CDS_CXX11_LAMBDA_SUPPORT
-                find_with_( val, key_comparator(), [](value_type& , Q const& ) {} );
-#       else
-                find_with_( val, key_comparator(), empty_find_functor() );
-#       endif
+            node_type * pNode = find_with_( val, key_comparator(), [](value_type& , Q const& ) {} );

             if ( pNode )
                 return node_traits::to_value_ptr( pNode );
             return nullptr;
             if ( pNode )
                 return node_traits::to_value_ptr( pNode );
             return nullptr;


@@ -931,12 +887,7 @@ namespace cds { namespace intrusive {
         template <typename Q, typename Less>
         value_type * find_with( Q const& val, Less pred ) const
         {
         template <typename Q, typename Less>
         value_type * find_with( Q const& val, Less pred ) const
         {

-            node_type * pNode =
-#       ifdef CDS_CXX11_LAMBDA_SUPPORT
-                find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
-#       else
-                find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), empty_find_functor() );
-#       endif
+            node_type * pNode = find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );

             if ( pNode )
                 return node_traits::to_value_ptr( pNode );
             return nullptr;
             if ( pNode )
                 return node_traits::to_value_ptr( pNode );
             return nullptr;


@@ -944,7 +895,7 @@ namespace cds { namespace intrusive {
 
         /// Gets minimum key from the set
         /**
 
         /// Gets minimum key from the set
         /**

-            If the set is empty the function returns \p NULL
+            If the set is empty the function returns \p nullptr

         */
         value_type * get_min() const
         {
         */
         value_type * get_min() const
         {


@@ -953,7 +904,7 @@ namespace cds { namespace intrusive {
 
         /// Gets maximum key from the set
         /**
 
         /// Gets maximum key from the set
         /**

-            The function returns \p NULL if the set is empty
+            The function returns \p nullptr if the set is empty

         */
         value_type * get_max() const
         {
         */
         value_type * get_max() const
         {