Adds a few single-threaded test cases for queue, stack, and set

[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 dd5b0ab8fb954fd9d116fc13aec2bd0db3894018..fc6ae8edf1a0b53f060528079c116835db62009f 100644 (file)
--- a/cds/intrusive/skip_list_nogc.h
+++ b/cds/intrusive/skip_list_nogc.h
@@ -1,11 +1,11 @@
 /*
     This file is a part of libcds - Concurrent Data Structures library
 
-    (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+    (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:
 
@@ -25,7 +25,7 @@
     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.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #ifndef CDSLIB_INTRUSIVE_SKIP_LIST_NOGC_H
@@ -93,8 +93,8 @@ namespace cds { namespace intrusive {
             /// Access to element of next pointer array
             atomic_ptr& next( unsigned int nLevel )
             {
-                assert( nLevel < height() );
-                assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr) );
+                assert( nLevel < height());
+                assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr));
 
                 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
             }
@@ -102,7 +102,7 @@ namespace cds { namespace intrusive {
             /// Access to element of next pointer array (const version)
             atomic_ptr const& next( unsigned int nLevel ) const
             {
-                assert( nLevel < height() );
+                assert( nLevel < height());
                 assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr );
 
                 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
@@ -165,7 +165,7 @@ namespace cds { namespace intrusive {
 
         public: // for internal use only!!!
             iterator( node_type& refHead )
-                : m_pNode( refHead[0].load( atomics::memory_order_relaxed ) )
+                : m_pNode( refHead[0].load( atomics::memory_order_relaxed ))
             {}
 
             static iterator from_node( node_type * pNode )
@@ -445,9 +445,9 @@ namespace cds { namespace intrusive {
     protected:
         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
+        item_counter                m_ItemCounter;    ///< item counter
         mutable stat                m_Stat;           ///< internal statistics
 
     protected:
@@ -536,7 +536,7 @@ namespace cds { namespace intrusive {
             {
                 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 ) ) {
+                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 );
@@ -549,7 +549,7 @@ namespace cds { namespace intrusive {
 
                     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 ) )
+                        if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ))
                             break;
                     }
 
@@ -581,7 +581,7 @@ namespace cds { namespace intrusive {
         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 ) );
+            while ( nCur < nHeight && !m_nHeight.compare_exchange_weak( nCur, nHeight, memory_model::memory_order_acquire, atomics::memory_order_relaxed ));
         }
         //@endcond
 
@@ -608,7 +608,14 @@ namespace cds { namespace intrusive {
         }
 
     public:
-        /// Iterator type
+    ///@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
@@ -617,18 +624,18 @@ namespace cds { namespace intrusive {
         /// Returns a forward iterator addressing the first element in a set
         iterator begin()
         {
-            return iterator( *m_Head.head() );
+            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() );
+            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() );
+            return const_iterator( *m_Head.head());
         }
 
         /// Returns a forward iterator that addresses the location succeeding the last element in a set.
@@ -647,6 +654,7 @@ namespace cds { namespace intrusive {
         {
             return const_iterator();
         }
+    //@}
 
     protected:
         //@cond
@@ -727,7 +735,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.
 
-            Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
+            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.