TSan exam: EllenBinTree, FCPriorityQueue

[libcds.git] / cds / container / fcpriority_queue.h

diff --git a/cds/container/fcpriority_queue.h b/cds/container/fcpriority_queue.h
index e692587b6adf83c485d6cadcc77ab1cdf4bdc53c..163537ed778e6462c075e1dd2260477d3f50dffa 100644 (file)
--- a/cds/container/fcpriority_queue.h
+++ b/cds/container/fcpriority_queue.h
@@ -1,7 +1,7 @@
 //$$CDS-header$$
 
-#ifndef __CDS_CONTAINER_FCPRIORITY_QUEUE_H
-#define __CDS_CONTAINER_FCPRIORITY_QUEUE_H
+#ifndef CDSLIB_CONTAINER_FCPRIORITY_QUEUE_H
+#define CDSLIB_CONTAINER_FCPRIORITY_QUEUE_H
 
 #include <cds/algo/flat_combining.h>
 #include <cds/algo/elimination_opt.h>
@@ -43,23 +43,22 @@ namespace cds { namespace container {
             //@endcond
         };
 
-        /// FCPriorityQueue type traits
-        struct type_traits: public cds::algo::flat_combining::type_traits
+        /// FCPriorityQueue traits
+        struct traits: public cds::algo::flat_combining::traits
         {
             typedef empty_stat      stat;   ///< Internal statistics
         };
 
         /// Metafunction converting option list to traits
         /**
-            This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
             \p Options are:
-            - \p opt::lock_type - mutex type, default is \p cds::lock::Spin
-            - \p opt::back_off - back-off strategy, defalt is \p cds::backoff::Default
+            - \p opt::lock_type - mutex type, default is \p cds::sync::spin
+            - \p opt::back_off - back-off strategy, defalt is \p cds::backoff::delay_of<2>
             - \p opt::allocator - allocator type, default is \ref CDS_DEFAULT_ALLOCATOR
-            - \p opt::stat - internal statistics, possible type: \ref stat, \ref empty_stat (the default)
+            - \p opt::stat - internal statistics, possible type: \p fcpqueue::stat, \p fcpqueue::empty_stat (the default)
             - \p opt::memory_model - C++ memory ordering model.
-                List of all available memory ordering see opt::memory_model.
-                Default is cds::opt::v:relaxed_ordering
+                List of all available memory ordering see \p opt::memory_model.
+                Default is \p cds::opt::v:relaxed_ordering
         */
         template <typename... Options>
         struct make_traits {
@@ -67,7 +66,7 @@ namespace cds { namespace container {
             typedef implementation_defined type ;   ///< Metafunction result
 #   else
             typedef typename cds::opt::make_options<
-                typename cds::opt::find_type_traits< type_traits, Options... >::type
+                typename cds::opt::find_type_traits< traits, Options... >::type
                 ,Options...
             >::type   type;
 #   endif
@@ -86,12 +85,12 @@ namespace cds { namespace container {
         Template parameters:
         - \p T - a value type stored in the queue
         - \p PriorityQueue - sequential priority queue implementation, default is \p std::priority_queue<T>
-        - \p Traits - type traits of flat combining, default is \p fcpqueue::type_traits.
-            \p fcpqueue::make_traits metafunction can be used to construct specialized \p %type_traits
+        - \p Traits - type traits of flat combining, default is \p fcpqueue::traits.
+            \p fcpqueue::make_traits metafunction can be used to construct specialized \p %fcpqueue::traits
     */
     template <typename T,
         class PriorityQueue = std::priority_queue<T>,
-        typename Traits = fcpqueue::type_traits
+        typename Traits = fcpqueue::traits
     >
     class FCPriorityQueue
 #ifndef CDS_DOXYGEN_INVOKED
@@ -101,9 +100,9 @@ namespace cds { namespace container {
     public:
         typedef T               value_type;          ///< Value type
         typedef PriorityQueue   priority_queue_type; ///< Sequential priority queue class
-        typedef Traits          type_traits;         ///< Priority queue type traits
+        typedef Traits          traits;              ///< Priority queue type traits
 
-        typedef typename type_traits::stat  stat;    ///< Internal statistics type
+        typedef typename traits::stat  stat;    ///< Internal statistics type
 
     protected:
         //@cond
@@ -112,7 +111,8 @@ namespace cds { namespace container {
             op_push = cds::algo::flat_combining::req_Operation,
             op_push_move,
             op_pop,
-            op_clear
+            op_clear,
+            op_empty
         };
 
         // Flat combining publication list record
@@ -127,7 +127,7 @@ namespace cds { namespace container {
         //@endcond
 
         /// Flat combining kernel
-        typedef cds::algo::flat_combining::kernel< fc_record, type_traits > fc_kernel;
+        typedef cds::algo::flat_combining::kernel< fc_record, traits > fc_kernel;
 
     protected:
         //@cond
@@ -232,10 +232,14 @@ namespace cds { namespace container {
         /**
             If the combining is in process the function waits while combining done.
         */
-        bool empty() const
+        bool empty()
         {
-            m_FlatCombining.wait_while_combining();
-            return m_PQueue.empty();
+            fc_record * pRec = m_FlatCombining.acquire_record();
+
+            m_FlatCombining.combine( op_empty, pRec, *this );
+            assert( pRec->is_done() );
+            m_FlatCombining.release_record( pRec );
+            return pRec->bEmpty;
         }
 
         /// Internal statistics
@@ -255,6 +259,9 @@ namespace cds { namespace container {
         {
             assert( pRec );
 
+            // this function is called under FC mutex, so switch TSan off
+            CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
+
             switch ( pRec->op() ) {
             case op_push:
                 assert( pRec->pValPush );
@@ -276,14 +283,19 @@ namespace cds { namespace container {
                 while ( !m_PQueue.empty() )
                     m_PQueue.pop();
                 break;
+            case op_empty:
+                pRec->bEmpty = m_PQueue.empty();
+                break;
             default:
                 assert(false);
                 break;
             }
+
+            CDS_TSAN_ANNOTATE_IGNORE_RW_END;
         }
         //@endcond
     };
 
 }} // namespace cds::container
 
-#endif // #ifndef __CDS_CONTAINER_FCPRIORITY_QUEUE_H
+#endif // #ifndef CDSLIB_CONTAINER_FCPRIORITY_QUEUE_H