X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=blobdiff_plain;f=cds%2Fintrusive%2Ffree_list_tagged.h;h=af3e7875261eca99d2a4f0df28f58ec64fa31a98;hp=d1fbbd5dec523bf42f4e56e750ff6697676df9ff;hb=bce7cbd187ae50a4a86d597ac66e825389f67d53;hpb=7448008aa977fe42a83738fbbc63ce11d8ab86f9

diff --git a/cds/intrusive/free_list_tagged.h b/cds/intrusive/free_list_tagged.h
index d1fbbd5d..af3e7875 100644
--- a/cds/intrusive/free_list_tagged.h
+++ b/cds/intrusive/free_list_tagged.h
@@ -5,7 +5,7 @@
 
     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_FREE_LIST_TAGGED_H
@@ -36,7 +36,8 @@
 namespace cds { namespace intrusive {
 
     /// Lock-free free list based on tagged pointers (required double-width CAS)
-    /** @ingroup cds_intrusive_helper
+    /** @ingroup cds_intrusive_freelist
+
         This variant of \p FreeList is intended for processor architectures that support double-width CAS.
         It uses <a href="https://en.wikipedia.org/wiki/Tagged_pointer">tagged pointer</a> technique to solve ABA problem.
 
@@ -92,9 +93,31 @@ namespace cds { namespace intrusive {
             //@endcond
         };
 
+    private:
+        //@cond
+        struct tagged_ptr
+        {
+            node *    ptr;
+            uintptr_t tag;
+
+            tagged_ptr()
+                : ptr( nullptr )
+                , tag( 0 )
+            {}
+
+            tagged_ptr( node* p )
+                : ptr( p )
+                , tag( 0 )
+            {}
+        };
+
+        static_assert(sizeof( tagged_ptr ) == sizeof( void * ) * 2, "sizeof( tagged_ptr ) violation");
+        //@endcond
+
     public:
         /// Creates empty free-list
         TaggedFreeList()
+            : m_Head( tagged_ptr())
         {
             // Your platform must support double-width CAS
             assert( m_Head.is_lock_free());
@@ -110,16 +133,17 @@ namespace cds { namespace intrusive {
             assert( empty() );
         }
 
-
         /// Puts \p pNode to the free list
         void put( node * pNode )
         {
+            assert( m_Head.is_lock_free());
+
             tagged_ptr currentHead = m_Head.load( atomics::memory_order_relaxed );
             tagged_ptr newHead = { pNode };
             do {
                 newHead.tag = currentHead.tag + 1;
                 pNode->m_freeListNext.store( currentHead.ptr, atomics::memory_order_relaxed );
-            } while ( !m_Head.compare_exchange_weak( currentHead, newHead, atomics::memory_order_release, atomics::memory_order_relaxed ));
+            } while ( cds_unlikely( !m_Head.compare_exchange_weak( currentHead, newHead, atomics::memory_order_release, atomics::memory_order_relaxed )));
         }
 
         /// Gets a node from the free list. If the list is empty, returns \p nullptr
@@ -130,7 +154,7 @@ namespace cds { namespace intrusive {
             while ( currentHead.ptr != nullptr ) {
                 newHead.ptr = currentHead.ptr->m_freeListNext.load( atomics::memory_order_relaxed );
                 newHead.tag = currentHead.tag + 1;
-                if ( m_Head.compare_exchange_weak( currentHead, newHead, atomics::memory_order_release, atomics::memory_order_acquire ) )
+                if ( cds_likely( m_Head.compare_exchange_weak( currentHead, newHead, atomics::memory_order_release, atomics::memory_order_acquire )))
                     break;
             }
             return currentHead.ptr;
@@ -169,23 +193,10 @@ namespace cds { namespace intrusive {
 
     private:
         //@cond
-        struct tagged_ptr
-        {
-            node *    ptr;
-            uintptr_t tag;
-
-            tagged_ptr()
-                : ptr( nullptr )
-                , tag( 0 )
-            {}
-        };
-
-        static_assert(sizeof( tagged_ptr ) == sizeof(void *) * 2, "sizeof( tagged_ptr ) violation" );
-
         atomics::atomic<tagged_ptr> m_Head;
         //@endcond    
     };
 
 }} // namespace cds::intrusive
 
-#endif // CDSLIB_INTRUSIVE_FREE_LIST_TAGGED_H
\ No newline at end of file
+#endif // CDSLIB_INTRUSIVE_FREE_LIST_TAGGED_H