Adds parameter for both RCU and HP based map test cases

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

diff --git a/cds/intrusive/mspriority_queue.h b/cds/intrusive/mspriority_queue.h
index 6c7827283cbb589402ce6772bb5f1c901004ac51..a41cd9893650fe9491810570de6b104fb84e1bab 100644 (file)
--- a/cds/intrusive/mspriority_queue.h
+++ b/cds/intrusive/mspriority_queue.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:
 
@@ -103,7 +103,7 @@ namespace cds { namespace intrusive {
                 the \p buffer::rebind member metafunction is called to change type
                 of values stored in the buffer.
             */
-            typedef opt::v::initialized_dynamic_buffer<void *, CDS_DEFAULT_ALLOCATOR, false>  buffer;
+            typedef opt::v::initialized_dynamic_buffer<void *>  buffer;
 
             /// Priority compare functor
             /**
@@ -117,11 +117,11 @@ namespace cds { namespace intrusive {
             */
             typedef opt::none       less;
 
-            /// Type of mutual-exclusion lock
+            /// Type of mutual-exclusion lock. The lock is not need to be recursive.
             typedef cds::sync::spin lock_type;
 
             /// Back-off strategy
-            typedef backoff::yield      back_off;
+            typedef backoff::Default    back_off;
 
             /// Internal statistics
             /**
@@ -198,9 +198,10 @@ namespace cds { namespace intrusive {
         typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
 #   endif
 
-        typedef typename traits::lock_type lock_type;   ///< heap's size lock type
-        typedef typename traits::back_off  back_off;    ///< Back-off strategy
-        typedef typename traits::stat      stat;        ///< internal statistics type
+        typedef typename traits::lock_type      lock_type;   ///< heap's size lock type
+        typedef typename traits::back_off       back_off;    ///< Back-off strategy
+        typedef typename traits::stat           stat;        ///< internal statistics type, see \p mspriority_queue::traits::stat
+        typedef typename cds::bitop::bit_reverse_counter<> item_counter;///< Item counter type
 
     protected:
         //@cond
@@ -222,7 +223,7 @@ namespace cds { namespace intrusive {
             /// Creates empty node
             node()
                 : m_pVal( nullptr )
-                , m_nTag( tag_type(Empty) )
+                , m_nTag( tag_type(Empty))
             {}
 
             /// Lock the node
@@ -243,12 +244,11 @@ namespace cds { namespace intrusive {
         typedef typename traits::buffer::template rebind<node>::other   buffer_type ;   ///< Heap array buffer type
 
         //@cond
-        typedef cds::bitop::bit_reverse_counter<>           item_counter_type;
-        typedef typename item_counter_type::counter_type    counter_type;
+        typedef typename item_counter::counter_type    counter_type;
         //@endcond
 
     protected:
-        item_counter_type   m_ItemCounter   ;   ///< Item counter
+        item_counter        m_ItemCounter   ;   ///< Item counter
         mutable lock_type   m_Lock          ;   ///< Heap's size lock
         buffer_type         m_Heap          ;   ///< Heap array
         stat                m_Stat          ;   ///< internal statistics accumulator
@@ -283,7 +283,7 @@ namespace cds { namespace intrusive {
 
             // Insert new item at bottom of the heap
             m_Lock.lock();
-            if ( m_ItemCounter.value() >= capacity() ) {
+            if ( m_ItemCounter.value() >= capacity()) {
                 // the heap is full
                 m_Lock.unlock();
                 m_Stat.onPushFailed();
@@ -291,7 +291,7 @@ namespace cds { namespace intrusive {
             }
 
             counter_type i = m_ItemCounter.inc();
-            assert( i < m_Heap.capacity() );
+            assert( i < m_Heap.capacity());
 
             node& refNode = m_Heap[i];
             refNode.lock();
@@ -316,6 +316,8 @@ namespace cds { namespace intrusive {
         */
         value_type * pop()
         {
+            node& refTop = m_Heap[1];
+
             m_Lock.lock();
             if ( m_ItemCounter.value() == 0 ) {
                 // the heap is empty
@@ -324,10 +326,21 @@ namespace cds { namespace intrusive {
                 return nullptr;
             }
             counter_type nBottom = m_ItemCounter.dec();
-            assert( nBottom < m_Heap.capacity() );
+            assert( nBottom < m_Heap.capacity());
             assert( nBottom > 0 );
 
-            node& refBottom = m_Heap[ nBottom ];
+            refTop.lock();
+            if ( nBottom == 1 ) {
+                refTop.m_nTag = tag_type( Empty );
+                value_type * pVal = refTop.m_pVal;
+                refTop.m_pVal = nullptr;
+                refTop.unlock();
+                m_Lock.unlock();
+                m_Stat.onPopSuccess();
+                return pVal;
+            }
+
+            node& refBottom = m_Heap[nBottom];
             refBottom.lock();
             m_Lock.unlock();
             refBottom.m_nTag = tag_type(Empty);
@@ -335,9 +348,7 @@ namespace cds { namespace intrusive {
             refBottom.m_pVal = nullptr;
             refBottom.unlock();
 
-            node& refTop = m_Heap[ 1 ];
-            refTop.lock();
-            if ( refTop.m_nTag == tag_type(Empty) ) {
+            if ( refTop.m_nTag == tag_type(Empty)) {
                 // nBottom == nTop
                 refTop.unlock();
                 m_Stat.onPopSuccess();
@@ -380,11 +391,9 @@ namespace cds { namespace intrusive {
         template <typename Func>
         void clear_with( Func f )
         {
-            while ( !empty() ) {
-                value_type * pVal = pop();
-                if ( pVal )
-                    f( *pVal );
-            }
+            value_type * pVal;
+            while (( pVal = pop()) != nullptr )
+                f( *pVal );
         }
 
         /// Checks is the priority queue is empty
@@ -448,7 +457,7 @@ namespace cds { namespace intrusive {
                         i = 0;
                     }
                 }
-                else if ( refParent.m_nTag == tag_type( Empty ) ) {
+                else if ( refParent.m_nTag == tag_type( Empty )) {
                     m_Stat.onItemMovedTop();
                     i = 0;
                 }