cds/container/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_CONTAINER_FCSTACK_H
  32 #define CDSLIB_CONTAINER_FCSTACK_H
  33
  34 #include <cds/algo/flat_combining.h>
  35 #include <cds/algo/elimination_opt.h>
  36 #include <stack>
  37
  38 namespace cds { namespace container {
  39
  40     /// FCStack related definitions
  41     /** @ingroup cds_nonintrusive_helper
  42     */
  43     namespace fcstack {
  44
  45         /// FCStack internal statistics
  46         template <typename Counter = cds::atomicity::event_counter >
  47         struct stat: public cds::algo::flat_combining::stat<Counter>
  48         {
  49             typedef cds::algo::flat_combining::stat<Counter>    flat_combining_stat; ///< Flat-combining statistics
  50             typedef typename flat_combining_stat::counter_type  counter_type;        ///< Counter type
  51
  52             counter_type    m_nPush     ;   ///< Count of push operations
  53             counter_type    m_nPushMove ;   ///< Count of push operations with move semantics
  54             counter_type    m_nPop      ;   ///< Count of success pop operations
  55             counter_type    m_nFailedPop;   ///< Count of failed pop operations (pop from empty stack)
  56             counter_type    m_nCollided ;   ///< How many pairs of push/pop were collided, if elimination is enabled
  57
  58             //@cond
  59             void    onPush()               { ++m_nPush; }
  60             void    onPushMove()           { ++m_nPushMove; }
  61             void    onPop( bool bFailed )  { if ( bFailed ) ++m_nFailedPop; else ++m_nPop;  }
  62             void    onCollide()            { ++m_nCollided; }
  63             //@endcond
  64         };
  65
  66         /// FCStack dummy statistics, no overhead
  67         struct empty_stat: public cds::algo::flat_combining::empty_stat
  68         {
  69             //@cond
  70             void    onPush()        {}
  71             void    onPushMove()    {}
  72             void    onPop(bool)     {}
  73             void    onCollide()     {}
  74             //@endcond
  75         };
  76
  77         /// FCStack type traits
  78         struct traits: public cds::algo::flat_combining::traits
  79         {
  80             typedef empty_stat      stat;   ///< Internal statistics
  81             static CDS_CONSTEXPR const bool enable_elimination = false; ///< Enable \ref cds_elimination_description "elimination"
  82         };
  83
  84         /// Metafunction converting option list to traits
  85         /**
  86             \p Options are:
  87             - \p opt::lock_type - mutex type, default is \p cds::sync::spin
  88             - \p opt::back_off - back-off strategy, defalt is \p cds::backoff::Default
  89             - \p opt::allocator - allocator type, default is \ref CDS_DEFAULT_ALLOCATOR
  90             - \p opt::stat - internal statistics, possible type: \p fcstack::stat, \p fcstack::empty_stat (the default)
  91             - \p opt::memory_model - C++ memory ordering model.
  92                 List of all available memory ordering see \p opt::memory_model.
  93                 Default is \p cds::opt::v:relaxed_ordering
  94             - \p opt::enable_elimination - enable/disable operation \ref cds_elimination_description "elimination"
  95                 By default, the elimination is disabled.
  96         */
  97         template <typename... Options>
  98         struct make_traits {
  99 #   ifdef CDS_DOXYGEN_INVOKED
 100             typedef implementation_defined type ;   ///< Metafunction result
 101 #   else
 102             typedef typename cds::opt::make_options<
 103                 typename cds::opt::find_type_traits< traits, Options... >::type
 104                 ,Options...
 105             >::type   type;
 106 #   endif
 107         };
 108
 109     } // namespace fcstack
 110
 111     /// Flat-combining stack
 112     /**
 113         @ingroup cds_nonintrusive_stack
 114         @ingroup cds_flat_combining_container
 115
 116         \ref cds_flat_combining_description "Flat combining" sequential stack.
 117
 118         Template parameters:
 119         - \p T - a value type stored in the stack
 120         - \p Stack - sequential stack implementation, default is \p std::stack<T>
 121         - \p Trats - type traits of flat combining, default is \p fcstack::traits
 122             \p fcstack::make_traits metafunction can be used to construct specialized \p %fcstack::traits
 123     */
 124     template <typename T,
 125         class Stack = std::stack<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 Stack       stack_type;     ///< Sequential stack class
 136         typedef Traits      traits;         ///< Stack traits
 137
 138         typedef typename traits::stat  stat;   ///< Internal statistics type
 139         static CDS_CONSTEXPR const bool c_bEliminationEnabled = traits::enable_elimination; ///< \p true if elimination is enabled
 140
 141     protected:
 142         //@cond
 143         /// Stack operation IDs
 144         enum fc_operation {
 145             op_push = cds::algo::flat_combining::req_Operation, ///< Push
 146             op_push_move,   ///< Push (move semantics)
 147             op_pop,         ///< Pop
 148             op_clear,       ///< Clear
 149             op_empty        ///< Empty
 150         };
 151
 152         /// Flat combining publication list record
 153         struct fc_record: public cds::algo::flat_combining::publication_record
 154         {
 155             union {
 156                 value_type const *  pValPush; ///< Value to push
 157                 value_type *        pValPop;  ///< Pop destination
 158             };
 159             bool            bEmpty; ///< \p true if the stack is empty
 160         };
 161         //@endcond
 162
 163         /// Flat combining kernel
 164         typedef cds::algo::flat_combining::kernel< fc_record, traits > fc_kernel;
 165
 166     protected:
 167         //@cond
 168         fc_kernel   m_FlatCombining;
 169         stack_type  m_Stack;
 170         //@endcond
 171
 172     public:
 173         /// Initializes empty stack object
 174         FCStack()
 175         {}
 176
 177         /// Initializes empty stack object and gives flat combining parameters
 178         FCStack(
 179             unsigned int nCompactFactor     ///< Flat combining: publication list compacting factor
 180             ,unsigned int nCombinePassCount ///< Flat combining: number of combining passes for combiner thread
 181             )
 182             : m_FlatCombining( nCompactFactor, nCombinePassCount )
 183         {}
 184
 185         /// Inserts a new element at the top of stack
 186         /**
 187             The content of the new element initialized to a copy of \p val.
 188         */
 189         bool push( value_type const& val )
 190         {
 191             fc_record * pRec = m_FlatCombining.acquire_record();
 192             pRec->pValPush = &val;
 193
 194             if ( c_bEliminationEnabled )
 195                 m_FlatCombining.batch_combine( op_push, pRec, *this );
 196             else
 197                 m_FlatCombining.combine( op_push, pRec, *this );
 198
 199             assert( pRec->is_done() );
 200             m_FlatCombining.release_record( pRec );
 201             m_FlatCombining.internal_statistics().onPush();
 202             return true;
 203         }
 204
 205         /// Inserts a new element at the top of stack (move semantics)
 206         /**
 207             The content of the new element initialized to a copy of \p val.
 208         */
 209         bool push( value_type&& val )
 210         {
 211             fc_record * pRec = m_FlatCombining.acquire_record();
 212             pRec->pValPush = &val;
 213
 214             if ( c_bEliminationEnabled )
 215                 m_FlatCombining.batch_combine( op_push_move, pRec, *this );
 216             else
 217                 m_FlatCombining.combine( op_push_move, pRec, *this );
 218
 219             assert( pRec->is_done() );
 220             m_FlatCombining.release_record( pRec );
 221
 222             m_FlatCombining.internal_statistics().onPushMove();
 223             return true;
 224         }
 225
 226         /// Removes the element on top of the stack
 227         /**
 228             \p val takes a copy of top element
 229         */
 230         bool pop( value_type& val )
 231         {
 232             fc_record * pRec = m_FlatCombining.acquire_record();
 233             pRec->pValPop = &val;
 234
 235             if ( c_bEliminationEnabled )
 236                 m_FlatCombining.batch_combine( op_pop, pRec, *this );
 237             else
 238                 m_FlatCombining.combine( op_pop, pRec, *this );
 239
 240             assert( pRec->is_done() );
 241             m_FlatCombining.release_record( pRec );
 242
 243             m_FlatCombining.internal_statistics().onPop( pRec->bEmpty );
 244             return !pRec->bEmpty;
 245         }
 246
 247         /// Clears the stack
 248         void clear()
 249         {
 250             fc_record * pRec = m_FlatCombining.acquire_record();
 251
 252             if ( c_bEliminationEnabled )
 253                 m_FlatCombining.batch_combine( op_clear, pRec, *this );
 254             else
 255                 m_FlatCombining.combine( op_clear, pRec, *this );
 256
 257             assert( pRec->is_done() );
 258             m_FlatCombining.release_record( pRec );
 259         }
 260
 261         /// Returns the number of elements in the stack.
 262         /**
 263             Note that <tt>size() == 0</tt> is not mean that the stack is empty because
 264             combining record can be in process.
 265             To check emptiness use \ref empty function.
 266         */
 267         size_t size() const
 268         {
 269             return m_Stack.size();
 270         }
 271
 272         /// Checks if the stack is empty
 273         /**
 274             If the combining is in process the function waits while combining done.
 275         */
 276         bool empty()
 277         {
 278             fc_record * pRec = m_FlatCombining.acquire_record();
 279
 280             if ( c_bEliminationEnabled )
 281                 m_FlatCombining.batch_combine( op_empty, pRec, *this );
 282             else
 283                 m_FlatCombining.combine( op_empty, pRec, *this );
 284
 285             assert( pRec->is_done() );
 286             m_FlatCombining.release_record( pRec );
 287             return pRec->bEmpty;
 288         }
 289
 290         /// Internal statistics
 291         stat const& statistics() const
 292         {
 293             return m_FlatCombining.statistics();
 294         }
 295
 296
 297     public: // flat combining cooperation, not for direct use!
 298         //@cond
 299         /// Flat combining supporting function. Do not call it directly!
 300         /**
 301             The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
 302             object if the current thread becomes a combiner. Invocation of the function means that
 303             the stack should perform an action recorded in \p pRec.
 304         */
 305         void fc_apply( fc_record * pRec )
 306         {
 307             assert( pRec );
 308
 309             // this function is called under FC mutex, so switch TSan off
 310             CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
 311             switch ( pRec->op() ) {
 312             case op_push:
 313                 assert( pRec->pValPush );
 314                 m_Stack.push( *(pRec->pValPush ) );
 315                 break;
 316             case op_push_move:
 317                 assert( pRec->pValPush );
 318                 m_Stack.push( std::move( *(pRec->pValPush )) );
 319                 break;
 320             case op_pop:
 321                 assert( pRec->pValPop );
 322                 pRec->bEmpty = m_Stack.empty();
 323                 if ( !pRec->bEmpty ) {
 324                     *(pRec->pValPop) = m_Stack.top();
 325                     m_Stack.pop();
 326                 }
 327                 break;
 328             case op_clear:
 329                 while ( !m_Stack.empty() )
 330                     m_Stack.pop();
 331                 break;
 332             case op_empty:
 333                 pRec->bEmpty = m_Stack.empty();
 334                 break;
 335             default:
 336                 assert(false);
 337                 break;
 338             }
 339             CDS_TSAN_ANNOTATE_IGNORE_RW_END;
 340         }
 341
 342         /// Batch-processing flat combining
 343         void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
 344         {
 345             // this function is called under FC mutex, so switch TSan off
 346             CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
 347
 348             typedef typename fc_kernel::iterator fc_iterator;
 349             for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
 350                 switch ( it->op() ) {
 351                 case op_push:
 352                 case op_push_move:
 353                 case op_pop:
 354                     if ( itPrev != itEnd && collide( *itPrev, *it ))
 355                         itPrev = itEnd;
 356                     else
 357                         itPrev = it;
 358                     break;
 359                 }
 360             }
 361             CDS_TSAN_ANNOTATE_IGNORE_RW_END;
 362         }
 363         //@endcond
 364
 365     private:
 366         //@cond
 367         bool collide( fc_record& rec1, fc_record& rec2 )
 368         {
 369             switch ( rec1.op() ) {
 370                 case op_push:
 371                     if ( rec2.op() == op_pop ) {
 372                         assert(rec1.pValPush);
 373                         assert(rec2.pValPop);
 374                         *rec2.pValPop = *rec1.pValPush;
 375                         rec2.bEmpty = false;
 376                         goto collided;
 377                     }
 378                     break;
 379                 case op_push_move:
 380                     if ( rec2.op() == op_pop ) {
 381                         assert(rec1.pValPush);
 382                         assert(rec2.pValPop);
 383                         *rec2.pValPop = std::move( *rec1.pValPush );
 384                         rec2.bEmpty = false;
 385                         goto collided;
 386                     }
 387                     break;
 388                 case op_pop:
 389                     switch ( rec2.op() ) {
 390                     case op_push:
 391                     case op_push_move:
 392                         return collide( rec2, rec1 );
 393                     }
 394             }
 395             return false;
 396
 397         collided:
 398             m_FlatCombining.operation_done( rec1 );
 399             m_FlatCombining.operation_done( rec2 );
 400             m_FlatCombining.internal_statistics().onCollide();
 401             return true;
 402         }
 403         //@endcond
 404     };
 405 }} // namespace cds::container
 406
 407 #endif // #ifndef CDSLIB_CONTAINER_FCSTACK_H