Move libcds 1.6.0 from SVN
[libcds.git] / 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