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             - 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             // this function is called under FC mutex, so switch TSan off
 305             CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
 306             switch ( pRec->op()) {
 307             case op_push:
 308                 assert( pRec->pValPush );
 309                 m_Stack.push( *(pRec->pValPush ));
 310                 break;
 311             case op_push_move:
 312                 assert( pRec->pValPush );
 313                 m_Stack.push( std::move( *(pRec->pValPush )));
 314                 break;
 315             case op_pop:
 316                 assert( pRec->pValPop );
 317                 pRec->bEmpty = m_Stack.empty();
 318                 if ( !pRec->bEmpty ) {
 319                     *(pRec->pValPop) = std::move( m_Stack.top());
 320                     m_Stack.pop();
 321                 }
 322                 break;
 323             case op_clear:
 324                 while ( !m_Stack.empty())
 325                     m_Stack.pop();
 326                 break;
 327             case op_empty:
 328                 pRec->bEmpty = m_Stack.empty();
 329                 break;
 330             default:
 331                 assert(false);
 332                 break;
 333             }
 334             CDS_TSAN_ANNOTATE_IGNORE_RW_END;
 335         }
 336
 337         /// Batch-processing flat combining
 338         void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
 339         {
 340             // this function is called under FC mutex, so switch TSan off
 341             CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
 342
 343             typedef typename fc_kernel::iterator fc_iterator;
 344             for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
 345                 switch ( it->op()) {
 346                 case op_push:
 347                 case op_push_move:
 348                 case op_pop:
 349                     if ( itPrev != itEnd && collide( *itPrev, *it ))
 350                         itPrev = itEnd;
 351                     else
 352                         itPrev = it;
 353                     break;
 354                 }
 355             }
 356             CDS_TSAN_ANNOTATE_IGNORE_RW_END;
 357         }
 358         //@endcond
 359
 360     private:
 361         //@cond
 362         bool collide( fc_record& rec1, fc_record& rec2 )
 363         {
 364             switch ( rec1.op()) {
 365                 case op_push:
 366                     if ( rec2.op() == op_pop ) {
 367                         assert(rec1.pValPush);
 368                         assert(rec2.pValPop);
 369                         *rec2.pValPop = *rec1.pValPush;
 370                         rec2.bEmpty = false;
 371                         goto collided;
 372                     }
 373                     break;
 374                 case op_push_move:
 375                     if ( rec2.op() == op_pop ) {
 376                         assert(rec1.pValPush);
 377                         assert(rec2.pValPop);
 378                         *rec2.pValPop = std::move( *rec1.pValPush );
 379                         rec2.bEmpty = false;
 380                         goto collided;
 381                     }
 382                     break;
 383                 case op_pop:
 384                     switch ( rec2.op()) {
 385                     case op_push:
 386                     case op_push_move:
 387                         return collide( rec2, rec1 );
 388                     }
 389             }
 390             return false;
 391
 392         collided:
 393             m_FlatCombining.operation_done( rec1 );
 394             m_FlatCombining.operation_done( rec2 );
 395             m_FlatCombining.internal_statistics().onCollide();
 396             return true;
 397         }
 398         //@endcond
 399     };
 400 }} // namespace cds::container
 401
 402 #endif // #ifndef CDSLIB_CONTAINER_FCSTACK_H