cds/algo/elimination.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_ALGO_ELIMINATION_H
   4 #define __CDS_ALGO_ELIMINATION_H
   5
   6 #include <cds/algo/elimination_tls.h>
   7 #include <cds/algo/elimination_opt.h>
   8 #include <cds/cxx11_atomic.h>
   9 #include <cds/threading/model.h>
  10
  11 namespace cds { namespace algo {
  12
  13     /// Elimination technique
  14     /** @anchor cds_elimination_description
  15         Elimination technique allows highly distributed coupling and execution of operations with reverse
  16         semantics like the pushes and pops on a stack. If a push followed by a pop are performed
  17         on a stack, the data structure's state does not change (similarly for a pop followed by a push).
  18         This means that if one can cause pairs of pushes and pops to meet and pair up in
  19         separate locations, the threads can exchange values without having to touch a centralized structure
  20         since they have anyhow "eliminated" each other's effect on it. Elimination can be implemented
  21         by using a collision array in which threads pick random locations in order to try and collide.
  22         Pairs of threads that "collide" in some location run through a synchronization protocol,
  23         and all such disjoint collisions can be performed in parallel. If a thread has not met another
  24         in the selected location or if it met a thread with an operation that cannot be eliminated
  25         (such as two push operations), an alternative scheme must be used.
  26     */
  27     namespace elimination {
  28
  29         /// Base class describing an operation for eliminating
  30         /**
  31             This class contains some debugng info.
  32             Actual operation descriptor depends on real container and its interface.
  33         */
  34         struct operation_desc
  35         {
  36             record * pOwner;    ///< Owner of the descriptor
  37         };
  38
  39         /// Acquires elimination record for the current thread
  40         template <typename OperationDesc>
  41         static inline record * init_record( OperationDesc& op )
  42         {
  43             record& rec = cds::threading::elimination_record();
  44             assert( rec.is_free());
  45             op.pOwner = &rec;
  46             rec.pOp = static_cast<operation_desc *>( &op );
  47             return &rec;
  48         }
  49
  50         /// Releases elimination record for the current thread
  51         static inline void clear_record()
  52         {
  53             cds::threading::elimination_record().pOp = null_ptr<operation_desc*>();
  54         }
  55     } // namespace elimination
  56 }} // namespace cds::algo
  57
  58 #endif // __CDS_ALGO_ELIMINATION_H