Fixed MichaelList assertion

[libcds.git] / cds / intrusive / impl / michael_list.h

diff --git a/cds/intrusive/impl/michael_list.h b/cds/intrusive/impl/michael_list.h
index c85ca20dc8ce17c8996a217283fb0814abb1cfb0..079996d4af20b0677756d7d25a9fb2637a62f2c5 100644 (file)
--- a/cds/intrusive/impl/michael_list.h
+++ b/cds/intrusive/impl/michael_list.h
@@ -211,6 +211,8 @@ namespace cds { namespace intrusive {
 
         typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
 
+        static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 4; ///< Count of hazard pointer required for the algorithm
+
         //@cond
         // Rebind traits (split-list support)
         template <typename... Options>
@@ -272,7 +274,11 @@ namespace cds { namespace intrusive {
 
             marked_node_ptr cur(pos.pCur);
             pNode->m_pNext.store( cur, memory_model::memory_order_release );
-            return pos.pPrev->compare_exchange_strong( cur, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed );
+            if ( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed ))
+                return true;
+
+            pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
+            return false;
         }
 
         static bool unlink_node( position& pos )
@@ -406,6 +412,8 @@ namespace cds { namespace intrusive {
         //@endcond
 
     public:
+    ///@name Forward iterators (only for debugging purpose)
+    //@{
         /// Forward iterator
         /**
             The forward iterator for Michael's list has some features:
@@ -415,10 +423,10 @@ namespace cds { namespace intrusive {
               may be thrown if the limit of guard count per thread is exceeded.
             - The iterator cannot be moved across thread boundary since it contains thread-private GC's guard.
             - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
-              deleting operations there is no guarantee that you iterate all item in the list.
+              deleting operations there is no guarantee that you iterate all item in the list. 
+              Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
 
-            Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
-            for debug purpose only.
+            @warning Use this iterator on the concurrent container for debugging purpose only.
 
             The iterator interface:
             \code
@@ -500,6 +508,7 @@ namespace cds { namespace intrusive {
         {
             return const_iterator();
         }
+    //@}
 
     public:
         /// Default constructor initializes empty list
@@ -945,7 +954,6 @@ namespace cds { namespace intrusive {
         bool insert_at( atomic_node_ptr& refHead, value_type& val )
         {
             node_type * pNode = node_traits::to_node_ptr( val );
-            link_checker::is_empty( pNode );
             position pos;
 
             while ( true ) {
@@ -966,7 +974,6 @@ namespace cds { namespace intrusive {
         bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
         {
             node_type * pNode = node_traits::to_node_ptr( val );
-            link_checker::is_empty( pNode );
             position pos;
 
             while ( true ) {