cds/intrusive/fcstack.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_INTRUSIVE_FCSTACK_H
  32 #define CDSLIB_INTRUSIVE_FCSTACK_H
  33
  34 #include <cds/algo/flat_combining.h>
  35 #include <cds/algo/elimination_opt.h>
  36 #include <cds/intrusive/options.h>
  37 #include <boost/intrusive/slist.hpp>
  38
  39 namespace cds { namespace intrusive {
  40
  41     /// FCStack related definitions
  42     namespace fcstack {
  43
  44         /// FCStack internal statistics
  45         template <typename Counter = cds::atomicity::event_counter >
  46         struct stat: public cds::algo::flat_combining::stat<Counter>
  47         {
  48             typedef cds::algo::flat_combining::stat<Counter>    flat_combining_stat; ///< Flat-combining statistics
  49             typedef typename flat_combining_stat::counter_type  counter_type;        ///< Counter type
  50
  51             counter_type    m_nPush     ;   ///< Count of push operations
  52             counter_type    m_nPop      ;   ///< Count of success pop operations
  53             counter_type    m_nFailedPop;   ///< Count of failed pop operations (pop from empty stack)
  54             counter_type    m_nCollided ;   ///< How many pairs of push/pop were collided, if elimination is enabled
  55
  56             //@cond
  57             void    onPush()               { ++m_nPush; }
  58             void    onPop( bool bFailed )  { if ( bFailed ) ++m_nFailedPop; else ++m_nPop;  }
  59             void    onCollide()            { ++m_nCollided; }
  60             //@endcond
  61         };
  62
  63         /// FCStack dummy statistics, no overhead
  64         struct empty_stat: public cds::algo::flat_combining::empty_stat
  65         {
  66             //@cond
  67             void    onPush()        {}
  68             void    onPop(bool)     {}
  69             void    onCollide()     {}
  70             //@endcond
  71         };
  72
  73         /// FCStack type traits
  74         struct traits: public cds::algo::flat_combining::traits
  75         {
  76             typedef cds::intrusive::opt::v::empty_disposer  disposer ; ///< Disposer to erase removed elements. Used only in \p FCStack::clear() function
  77             typedef empty_stat      stat;   ///< Internal statistics
  78             static CDS_CONSTEXPR const bool enable_elimination = false; ///< Enable \ref cds_elimination_description "elimination"
  79         };
  80
  81         /// Metafunction converting option list to traits
  82         /**
  83             \p Options are:
  84             - \p opt::lock_type - mutex type, default is \p cds::sync::spin
  85             - \p opt::back_off - back-off strategy, defalt is \p cds::backoff::Default
  86             - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::intrusive::v::empty_disposer.
  87                 This option is used only in \p FCStack::clear() function.
  88             - \p opt::allocator - allocator type, default is \ref CDS_DEFAULT_ALLOCATOR
  89             - \p opt::stat - internal statistics, possible type: \p fcstack::stat, \p fcstack::empty_stat (the default)
  90             - \p opt::memory_model - C++ memory ordering model.
  91                 List of all available memory ordering see \p opt::memory_model.
  92                 Default is \p cds::opt::v:relaxed_ordering
  93             - \p opt::enable_elimination - enable/disable operation \ref cds_elimination_description "elimination"
  94                 By default, the elimination is disabled.
  95         */
  96         template <typename... Options>
  97         struct make_traits {
  98 #   ifdef CDS_DOXYGEN_INVOKED
  99             typedef implementation_defined type ;   ///< Metafunction result
 100 #   else
 101             typedef typename cds::opt::make_options<
 102                 typename cds::opt::find_type_traits< traits, Options... >::type
 103                 ,Options...
 104             >::type   type;
 105 #   endif
 106         };
 107
 108     } // namespace fcstack
 109
 110     /// Flat-combining intrusive stack
 111     /**
 112         @ingroup cds_intrusive_stack
 113         @ingroup cds_flat_combining_intrusive
 114
 115         \ref cds_flat_combining_description "Flat combining" sequential intrusive stack.
 116
 117         Template parameters:
 118         - \p T - a value type stored in the stack
 119         - \p Container - sequential intrusive container with \p push_front and \p pop_front functions.
 120             Possible containers are \p boost::intrusive::slist (the default), \p boost::inrtrusive::list
 121         - \p Traits - type traits of flat combining, default is \p fcstack::traits.
 122             \p fcstack::make_traits metafunction can be used to construct specialized \p %traits
 123     */
 124     template <typename T
 125         ,class Container = boost::intrusive::slist<T>
 126         ,typename Traits = fcstack::traits
 127     >
 128     class FCStack
 129 #ifndef CDS_DOXYGEN_INVOKED
 130         : public cds::algo::flat_combining::container
 131 #endif
 132     {
 133     public:
 134         typedef T           value_type;     ///< Value type
 135         typedef Container   container_type; ///< Sequential container type
 136         typedef Traits      traits;         ///< Stack traits
 137
 138         typedef typename traits::disposer  disposer;   ///< The disposer functor. The disposer is used only in \ref clear() function
 139         typedef typename traits::stat  stat;   ///< Internal statistics type
 140         static CDS_CONSTEXPR const bool c_bEliminationEnabled = traits::enable_elimination; ///< \p true if elimination is enabled
 141
 142     protected:
 143         //@cond
 144         /// Stack operation IDs
 145         enum fc_operation {
 146             op_push = cds::algo::flat_combining::req_Operation, ///< Push
 147             op_pop,                 ///< Pop
 148             op_clear,               ///< Clear
 149             op_clear_and_dispose    ///< Clear and dispose
 150         };
 151
 152         /// Flat combining publication list record
 153         struct fc_record: public cds::algo::flat_combining::publication_record
 154         {
 155             value_type * pVal;  ///< Value to push or pop
 156             bool         bEmpty; ///< \p true if the stack is empty
 157         };
 158         //@endcond
 159
 160         /// Flat combining kernel
 161         typedef cds::algo::flat_combining::kernel< fc_record, traits > fc_kernel;
 162
 163     protected:
 164         //@cond
 165         fc_kernel       m_FlatCombining;
 166         container_type  m_Stack;
 167         //@endcond
 168
 169     public:
 170         /// Initializes empty stack object
 171         FCStack()
 172         {}
 173
 174         /// Initializes empty stack object and gives flat combining parameters
 175         FCStack(
 176             unsigned int nCompactFactor     ///< Flat combining: publication list compacting factor
 177             ,unsigned int nCombinePassCount ///< Flat combining: number of combining passes for combiner thread
 178             )
 179             : m_FlatCombining( nCompactFactor, nCombinePassCount )
 180         {}
 181
 182         /// Inserts a new element at the top of stack
 183         /**
 184             The content of the new element initialized to a copy of \p val.
 185         */
 186         bool push( value_type& val )
 187         {
 188             fc_record * pRec = m_FlatCombining.acquire_record();
 189             pRec->pVal = &val;
 190
 191             if ( c_bEliminationEnabled )
 192                 m_FlatCombining.batch_combine( op_push, pRec, *this );
 193             else
 194                 m_FlatCombining.combine( op_push, pRec, *this );
 195
 196             assert( pRec->is_done() );
 197             m_FlatCombining.release_record( pRec );
 198             m_FlatCombining.internal_statistics().onPush();
 199             return true;
 200         }
 201
 202         /// Removes the element on top of the stack
 203         value_type * pop()
 204         {
 205             fc_record * pRec = m_FlatCombining.acquire_record();
 206             pRec->pVal = nullptr;
 207
 208             if ( c_bEliminationEnabled )
 209                 m_FlatCombining.batch_combine( op_pop, pRec, *this );
 210             else
 211                 m_FlatCombining.combine( op_pop, pRec, *this );
 212
 213             assert( pRec->is_done() );
 214             m_FlatCombining.release_record( pRec );
 215
 216             m_FlatCombining.internal_statistics().onPop( pRec->bEmpty );
 217             return pRec->pVal;
 218         }
 219
 220         /// Clears the stack
 221         /**
 222             If \p bDispose is \p true, the disposer provided in \p Traits class' template parameter
 223             will be called for each removed element.
 224         */
 225         void clear( bool bDispose = false )
 226         {
 227             fc_record * pRec = m_FlatCombining.acquire_record();
 228
 229             if ( c_bEliminationEnabled )
 230                 m_FlatCombining.batch_combine( bDispose ? op_clear_and_dispose : op_clear, pRec, *this );
 231             else
 232                 m_FlatCombining.combine( bDispose ? op_clear_and_dispose : op_clear, pRec, *this );
 233
 234             assert( pRec->is_done() );
 235             m_FlatCombining.release_record( pRec );
 236         }
 237
 238         /// Returns the number of elements in the stack.
 239         /**
 240             Note that <tt>size() == 0</tt> is not mean that the stack is empty because
 241             combining record can be in process.
 242             To check emptiness use \ref empty function.
 243         */
 244         size_t size() const
 245         {
 246             return m_Stack.size();
 247         }
 248
 249         /// Checks if the stack is empty
 250         /**
 251             If the combining is in process the function waits while it is done.
 252         */
 253         bool empty() const
 254         {
 255             m_FlatCombining.wait_while_combining();
 256             return m_Stack.empty();
 257         }
 258
 259         /// Internal statistics
 260         stat const& statistics() const
 261         {
 262             return m_FlatCombining.statistics();
 263         }
 264
 265
 266     public: // flat combining cooperation, not for direct use!
 267         //@cond
 268         /// Flat combining supporting function. Do not call it directly!
 269         /**
 270             The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
 271             object if the current thread becomes a combiner. Invocation of the function means that
 272             the stack should perform an action recorded in \p pRec.
 273         */
 274         void fc_apply( fc_record * pRec )
 275         {
 276             assert( pRec );
 277
 278             // this function is called under FC mutex, so switch TSan off
 279             CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
 280             switch ( pRec->op() ) {
 281             case op_push:
 282                 assert( pRec->pVal );
 283                 m_Stack.push_front( *(pRec->pVal ) );
 284                 break;
 285             case op_pop:
 286                 pRec->bEmpty = m_Stack.empty();
 287                 if ( !pRec->bEmpty ) {
 288                     pRec->pVal = &m_Stack.front();
 289                     m_Stack.pop_front();
 290                 }
 291                 break;
 292             case op_clear:
 293                 m_Stack.clear();
 294                 break;
 295             case op_clear_and_dispose:
 296                 m_Stack.clear_and_dispose( disposer() );
 297                 break;
 298             default:
 299                 assert(false);
 300                 break;
 301             }
 302             CDS_TSAN_ANNOTATE_IGNORE_RW_END;
 303         }
 304
 305         /// Batch-processing flat combining
 306         void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
 307         {
 308             // this function is called under FC mutex, so switch TSan off
 309             CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
 310
 311             typedef typename fc_kernel::iterator fc_iterator;
 312             for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
 313                 switch ( it->op() ) {
 314                 case op_push:
 315                 case op_pop:
 316                     if ( itPrev != itEnd && collide( *itPrev, *it ))
 317                         itPrev = itEnd;
 318                     else
 319                         itPrev = it;
 320                     break;
 321                 }
 322             }
 323             CDS_TSAN_ANNOTATE_IGNORE_RW_END;
 324         }
 325         //@endcond
 326
 327     private:
 328         //@cond
 329         bool collide( fc_record& rec1, fc_record& rec2 )
 330         {
 331             switch ( rec1.op() ) {
 332                 case op_push:
 333                     if ( rec2.op() == op_pop ) {
 334                         assert(rec1.pVal);
 335                         rec2.pVal = rec1.pVal;
 336                         rec2.bEmpty = false;
 337                         m_FlatCombining.operation_done( rec1 );
 338                         m_FlatCombining.operation_done( rec2 );
 339                         m_FlatCombining.internal_statistics().onCollide();
 340                         return true;
 341                     }
 342                     break;
 343                 case op_pop:
 344                     if ( rec2.op() == op_push ) {
 345                         assert(rec2.pVal);
 346                         rec1.pVal = rec2.pVal;
 347                         rec1.bEmpty = false;
 348                         m_FlatCombining.operation_done( rec1 );
 349                         m_FlatCombining.operation_done( rec2 );
 350                         m_FlatCombining.internal_statistics().onCollide();
 351                         return true;
 352                     }
 353                     break;
 354             }
 355             return false;
 356         }
 357         //@endcond
 358
 359     };
 360
 361 }} // namespace cds::intrusive
 362
 363 #endif // #ifndef CDSLIB_INTRUSIVE_FCSTACK_H