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-2017
   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             - any \p cds::algo::flat_combining::make_traits options
  88             - \p opt::stat - internal statistics, possible type: \p fcstack::stat, \p fcstack::empty_stat (the default)
  89             - \p opt::enable_elimination - enable/disable operation \ref cds_elimination_description "elimination"
  90                 By default, the elimination is disabled.
  91         */
  92         template <typename... Options>
  93         struct make_traits {
  94 #   ifdef CDS_DOXYGEN_INVOKED
  95             typedef implementation_defined type ;   ///< Metafunction result
  96 #   else
  97             typedef typename cds::opt::make_options<
  98                 typename cds::opt::find_type_traits< traits, Options... >::type
  99                 ,Options...
 100             >::type   type;
 101 #   endif
 102         };
 103
 104     } // namespace fcstack
 105
 106     /// Flat-combining stack
 107     /**
 108         @ingroup cds_nonintrusive_stack
 109         @ingroup cds_flat_combining_container
 110
 111         \ref cds_flat_combining_description "Flat combining" sequential stack.
 112
 113         Template parameters:
 114         - \p T - a value type stored in the stack
 115         - \p Stack - sequential stack implementation, default is \p std::stack<T>
 116         - \p Trats - type traits of flat combining, default is \p fcstack::traits
 117             \p fcstack::make_traits metafunction can be used to construct specialized \p %fcstack::traits
 118     */
 119     template <typename T,
 120         class Stack = std::stack<T>,
 121         typename Traits = fcstack::traits
 122     >
 123     class FCStack
 124 #ifndef CDS_DOXYGEN_INVOKED
 125         : public cds::algo::flat_combining::container
 126 #endif
 127     {
 128     public:
 129         typedef T           value_type;     ///< Value type
 130         typedef Stack       stack_type;     ///< Sequential stack class
 131         typedef Traits      traits;         ///< Stack traits
 132
 133         typedef typename traits::stat  stat;   ///< Internal statistics type
 134         static CDS_CONSTEXPR const bool c_bEliminationEnabled = traits::enable_elimination; ///< \p true if elimination is enabled
 135
 136     protected:
 137         //@cond
 138         /// Stack operation IDs
 139         enum fc_operation {
 140             op_push = cds::algo::flat_combining::req_Operation, ///< Push
 141             op_push_move,   ///< Push (move semantics)
 142             op_pop,         ///< Pop
 143             op_clear,       ///< Clear
 144             op_empty        ///< Empty
 145         };
 146
 147         /// Flat combining publication list record
 148         struct fc_record: public cds::algo::flat_combining::publication_record
 149         {
 150             union {
 151                 value_type const *  pValPush; ///< Value to push
 152                 value_type *        pValPop;  ///< Pop destination
 153             };
 154             bool            bEmpty; ///< \p true if the stack is empty
 155         };
 156         //@endcond
 157
 158         /// Flat combining kernel
 159         typedef cds::algo::flat_combining::kernel< fc_record, traits > fc_kernel;
 160
 161     protected:
 162         //@cond
 163         mutable fc_kernel m_FlatCombining;
 164         stack_type        m_Stack;
 165         //@endcond
 166
 167     public:
 168         /// Initializes empty stack object
 169         FCStack()
 170         {}
 171
 172         /// Initializes empty stack object and gives flat combining parameters
 173         FCStack(
 174             unsigned int nCompactFactor     ///< Flat combining: publication list compacting factor
 175             ,unsigned int nCombinePassCount ///< Flat combining: number of combining passes for combiner thread
 176             )
 177             : m_FlatCombining( nCompactFactor, nCombinePassCount )
 178         {}
 179
 180         /// Inserts a new element at the top of stack
 181         /**
 182             The content of the new element initialized to a copy of \p val.
 183         */
 184         bool push( value_type const& val )
 185         {
 186             auto pRec = m_FlatCombining.acquire_record();
 187             pRec->pValPush = &val;
 188
 189             if ( c_bEliminationEnabled )
 190                 m_FlatCombining.batch_combine( op_push, pRec, *this );
 191             else
 192                 m_FlatCombining.combine( op_push, pRec, *this );
 193
 194             assert( pRec->is_done());
 195             m_FlatCombining.release_record( pRec );
 196             m_FlatCombining.internal_statistics().onPush();
 197             return true;
 198         }
 199
 200         /// Inserts a new element at the top of stack (move semantics)
 201         /**
 202             The content of the new element initialized to a copy of \p val.
 203         */
 204         bool push( value_type&& val )
 205         {
 206             auto pRec = m_FlatCombining.acquire_record();
 207             pRec->pValPush = &val;
 208
 209             if ( c_bEliminationEnabled )
 210                 m_FlatCombining.batch_combine( op_push_move, pRec, *this );
 211             else
 212                 m_FlatCombining.combine( op_push_move, pRec, *this );
 213
 214             assert( pRec->is_done());
 215             m_FlatCombining.release_record( pRec );
 216
 217             m_FlatCombining.internal_statistics().onPushMove();
 218             return true;
 219         }
 220
 221         /// Removes the element on top of the stack
 222         /**
 223             \p val takes a copy of top element
 224         */
 225         bool pop( value_type& val )
 226         {
 227             auto pRec = m_FlatCombining.acquire_record();
 228             pRec->pValPop = &val;
 229
 230             if ( c_bEliminationEnabled )
 231                 m_FlatCombining.batch_combine( op_pop, pRec, *this );
 232             else
 233                 m_FlatCombining.combine( op_pop, pRec, *this );
 234
 235             assert( pRec->is_done());
 236             m_FlatCombining.release_record( pRec );
 237
 238             m_FlatCombining.internal_statistics().onPop( pRec->bEmpty );
 239             return !pRec->bEmpty;
 240         }
 241
 242         /// Clears the stack
 243         void clear()
 244         {
 245             auto pRec = m_FlatCombining.acquire_record();
 246
 247             if ( c_bEliminationEnabled )
 248                 m_FlatCombining.batch_combine( op_clear, pRec, *this );
 249             else
 250                 m_FlatCombining.combine( op_clear, pRec, *this );
 251
 252             assert( pRec->is_done());
 253             m_FlatCombining.release_record( pRec );
 254         }
 255
 256         /// Returns the number of elements in the stack.
 257         /**
 258             Note that <tt>size() == 0</tt> is not mean that the stack is empty because
 259             combining record can be in process.
 260             To check emptiness use \ref empty function.
 261         */
 262         size_t size() const
 263         {
 264             return m_Stack.size();
 265         }
 266
 267         /// Checks if the stack is empty
 268         /**
 269             If the combining is in process the function waits while combining done.
 270         */
 271         bool empty()
 272         {
 273             auto pRec = m_FlatCombining.acquire_record();
 274
 275             if ( c_bEliminationEnabled )
 276                 m_FlatCombining.batch_combine( op_empty, pRec, *this );
 277             else
 278                 m_FlatCombining.combine( op_empty, pRec, *this );
 279
 280             assert( pRec->is_done());
 281             m_FlatCombining.release_record( pRec );
 282             return pRec->bEmpty;
 283         }
 284
 285         /// Internal statistics
 286         stat const& statistics() const
 287         {
 288             return m_FlatCombining.statistics();
 289         }
 290
 291
 292     public: // flat combining cooperation, not for direct use!
 293         //@cond
 294         /// Flat combining supporting function. Do not call it directly!
 295         /**
 296             The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
 297             object if the current thread becomes a combiner. Invocation of the function means that
 298             the stack should perform an action recorded in \p pRec.
 299         */
 300         void fc_apply( fc_record * pRec )
 301         {
 302             assert( pRec );
 303
 304             switch ( pRec->op()) {
 305             case op_push:
 306                 assert( pRec->pValPush );
 307                 m_Stack.push( *(pRec->pValPush ));
 308                 break;
 309             case op_push_move:
 310                 assert( pRec->pValPush );
 311                 m_Stack.push( std::move( *(pRec->pValPush )));
 312                 break;
 313             case op_pop:
 314                 assert( pRec->pValPop );
 315                 pRec->bEmpty = m_Stack.empty();
 316                 if ( !pRec->bEmpty ) {
 317                     *(pRec->pValPop) = std::move( m_Stack.top());
 318                     m_Stack.pop();
 319                 }
 320                 break;
 321             case op_clear:
 322                 while ( !m_Stack.empty())
 323                     m_Stack.pop();
 324                 break;
 325             case op_empty:
 326                 pRec->bEmpty = m_Stack.empty();
 327                 break;
 328             default:
 329                 assert(false);
 330                 break;
 331             }
 332         }
 333
 334         /// Batch-processing flat combining
 335         void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
 336         {
 337             typedef typename fc_kernel::iterator fc_iterator;
 338             for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
 339                 switch ( it->op( atomics::memory_order_acquire )) {
 340                 case op_push:
 341                 case op_push_move:
 342                 case op_pop:
 343                     if ( itPrev != itEnd && collide( *itPrev, *it ))
 344                         itPrev = itEnd;
 345                     else
 346                         itPrev = it;
 347                     break;
 348                 }
 349             }
 350         }
 351         //@endcond
 352
 353     private:
 354         //@cond
 355         bool collide( fc_record& rec1, fc_record& rec2 )
 356         {
 357             switch ( rec1.op()) {
 358                 case op_push:
 359                     if ( rec2.op() == op_pop ) {
 360                         assert(rec1.pValPush);
 361                         assert(rec2.pValPop);
 362                         *rec2.pValPop = *rec1.pValPush;
 363                         rec2.bEmpty = false;
 364                         goto collided;
 365                     }
 366                     break;
 367                 case op_push_move:
 368                     if ( rec2.op() == op_pop ) {
 369                         assert(rec1.pValPush);
 370                         assert(rec2.pValPop);
 371                         *rec2.pValPop = std::move( *rec1.pValPush );
 372                         rec2.bEmpty = false;
 373                         goto collided;
 374                     }
 375                     break;
 376                 case op_pop:
 377                     switch ( rec2.op()) {
 378                     case op_push:
 379                     case op_push_move:
 380                         return collide( rec2, rec1 );
 381                     }
 382             }
 383             return false;
 384
 385         collided:
 386             m_FlatCombining.operation_done( rec1 );
 387             m_FlatCombining.operation_done( rec2 );
 388             m_FlatCombining.internal_statistics().onCollide();
 389             return true;
 390         }
 391         //@endcond
 392     };
 393 }} // namespace cds::container
 394
 395 #endif // #ifndef CDSLIB_CONTAINER_FCSTACK_H