X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Ffcpriority_queue.h;h=c06a9ce960a65bfa56047462342a9453cff99b36;hb=f31988b031453d7fdf7fe212f966554fa558af3e;hp=37c40fe05ec171cd346b80ea6759f0df91d5f14f;hpb=e5a7366d7fd32c9d0d540e094a7810120c31856c;p=libcds.git diff --git a/cds/container/fcpriority_queue.h b/cds/container/fcpriority_queue.h index 37c40fe0..c06a9ce9 100644 --- a/cds/container/fcpriority_queue.h +++ b/cds/container/fcpriority_queue.h @@ -1,7 +1,35 @@ -//$$CDS-header$$ - -#ifndef __CDS_CONTAINER_FCPRIORITY_QUEUE_H -#define __CDS_CONTAINER_FCPRIORITY_QUEUE_H +/* + This file is a part of libcds - Concurrent Data Structures library + + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 + + 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: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + 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. +*/ + +#ifndef CDSLIB_CONTAINER_FCPRIORITY_QUEUE_H +#define CDSLIB_CONTAINER_FCPRIORITY_QUEUE_H #include #include @@ -52,13 +80,8 @@ namespace cds { namespace container { /// Metafunction converting option list to traits /** \p Options are: - - \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 + - any \p cds::algo::flat_combining::make_traits options - \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 \p opt::memory_model. - Default is \p cds::opt::v:relaxed_ordering */ template struct make_traits { @@ -130,8 +153,8 @@ namespace cds { namespace container { protected: //@cond - fc_kernel m_FlatCombining; - priority_queue_type m_PQueue; + mutable fc_kernel m_FlatCombining; + priority_queue_type m_PQueue; //@endcond public: @@ -155,7 +178,7 @@ namespace cds { namespace container { value_type const& val ///< Value to be copied to inserted element ) { - fc_record * pRec = m_FlatCombining.acquire_record(); + auto pRec = m_FlatCombining.acquire_record(); pRec->pValPush = &val; m_FlatCombining.combine( op_push, pRec, *this ); @@ -174,7 +197,7 @@ namespace cds { namespace container { value_type&& val ///< Value to be moved to inserted element ) { - fc_record * pRec = m_FlatCombining.acquire_record(); + auto pRec = m_FlatCombining.acquire_record(); pRec->pValPush = &val; m_FlatCombining.combine( op_push_move, pRec, *this ); @@ -194,7 +217,7 @@ namespace cds { namespace container { value_type& val ///< Target to be received the copy of top element ) { - fc_record * pRec = m_FlatCombining.acquire_record(); + auto pRec = m_FlatCombining.acquire_record(); pRec->pValPop = &val; m_FlatCombining.combine( op_pop, pRec, *this ); @@ -208,7 +231,7 @@ namespace cds { namespace container { /// Clears the priority queue void clear() { - fc_record * pRec = m_FlatCombining.acquire_record(); + auto pRec = m_FlatCombining.acquire_record(); m_FlatCombining.combine( op_clear, pRec, *this ); @@ -231,10 +254,12 @@ 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(); + bool bRet = false; + auto const& pq = m_PQueue; + m_FlatCombining.invoke_exclusive( [&pq, &bRet]() { bRet = pq.empty(); } ); + return bRet; } /// Internal statistics @@ -254,6 +279,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 ); @@ -267,7 +295,7 @@ namespace cds { namespace container { assert( pRec->pValPop ); pRec->bEmpty = m_PQueue.empty(); if ( !pRec->bEmpty ) { - *(pRec->pValPop) = m_PQueue.top(); + *(pRec->pValPop) = std::move( m_PQueue.top()); m_PQueue.pop(); } break; @@ -279,10 +307,12 @@ namespace cds { namespace container { 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