tests/unit/stack/intrusive_stack_type.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDSUNIT_INTRUSIVE_STACK_TYPES_H
   4 #define __CDSUNIT_INTRUSIVE_STACK_TYPES_H
   5
   6 #include <cds/intrusive/treiber_stack.h>
   7 #include <cds/intrusive/fcstack.h>
   8
   9 #include <cds/gc/hp.h>
  10 #include <cds/gc/dhp.h>
  11
  12 #include <mutex>
  13 #include <cds/lock/spinlock.h>
  14 #include <stack>
  15 #include <list>
  16 #include <vector>
  17 #include <boost/intrusive/list.hpp>
  18
  19 namespace istack {
  20
  21     namespace details {
  22
  23         template < typename T, typename Stack, typename Lock>
  24         class StdStack
  25         {
  26             Stack   m_Impl;
  27             mutable Lock    m_Lock;
  28             cds::intrusive::treiber_stack::empty_stat m_stat;
  29
  30             typedef std::unique_lock<Lock>  unique_lock;
  31
  32         public:
  33             typedef T value_type;
  34
  35             bool push( T& v )
  36             {
  37                 unique_lock l( m_Lock );
  38                 m_Impl.push( &v );
  39                 return true;
  40             }
  41
  42             T * pop()
  43             {
  44                 unique_lock l( m_Lock );
  45                 if ( !m_Impl.empty() ) {
  46                      T * v = m_Impl.top();
  47                     m_Impl.pop();
  48                     return v;
  49                 }
  50                 return nullptr;
  51             }
  52
  53             bool empty() const
  54             {
  55                 unique_lock l( m_Lock );
  56                 return m_Impl.empty();
  57             }
  58
  59             cds::intrusive::treiber_stack::empty_stat const& statistics() const
  60             {
  61                 return m_stat;
  62             }
  63         };
  64     }
  65
  66     template <typename T>
  67     struct Types {
  68
  69         template <class GC>
  70         using base_hook = cds::intrusive::treiber_stack::base_hook < cds::opt::gc< GC > >;
  71
  72     // TreiberStack
  73         typedef cds::intrusive::TreiberStack< cds::gc::HP,  T > Treiber_HP;
  74         struct traits_Treiber_DHP: public
  75             cds::intrusive::treiber_stack::make_traits <
  76                 cds::intrusive::opt::hook< base_hook<cds::gc::DHP> >
  77             > ::type
  78         {};
  79         typedef cds::intrusive::TreiberStack< cds::gc::DHP, T, traits_Treiber_DHP >Treiber_DHP;
  80
  81         template <class GC> struct traits_Treiber_seqcst : public
  82             cds::intrusive::treiber_stack::make_traits <
  83                 cds::intrusive::opt::hook< base_hook<GC> >
  84                 , cds::opt::memory_model<cds::opt::v::sequential_consistent>
  85             > ::type
  86         {};
  87         typedef cds::intrusive::TreiberStack< cds::gc::HP,  T, traits_Treiber_seqcst<cds::gc::HP>  > Treiber_HP_seqcst;
  88         typedef cds::intrusive::TreiberStack< cds::gc::DHP, T, traits_Treiber_seqcst<cds::gc::DHP> > Treiber_DHP_seqcst;
  89
  90         template <class GC> struct traits_Treiber_stat: public
  91             cds::intrusive::treiber_stack::make_traits <
  92                 cds::intrusive::opt::hook< base_hook<GC> >
  93                 , cds::opt::stat<cds::intrusive::treiber_stack::stat<> >
  94             > ::type
  95         {};
  96         typedef cds::intrusive::TreiberStack< cds::gc::HP,  T, traits_Treiber_stat<cds::gc::HP>  > Treiber_HP_stat;
  97         typedef cds::intrusive::TreiberStack< cds::gc::DHP, T, traits_Treiber_stat<cds::gc::DHP> > Treiber_DHP_stat;
  98
  99         template <class GC> struct traits_Treiber_yield: public
 100             cds::intrusive::treiber_stack::make_traits <
 101                 cds::intrusive::opt::hook< base_hook<GC> >
 102                 , cds::opt::back_off<cds::backoff::yield>
 103                 , cds::opt::memory_model<cds::opt::v::relaxed_ordering>
 104             > ::type
 105         {};
 106         typedef cds::intrusive::TreiberStack< cds::gc::HP,  T, traits_Treiber_yield<cds::gc::HP>  > Treiber_HP_yield;
 107         typedef cds::intrusive::TreiberStack< cds::gc::DHP, T, traits_Treiber_yield<cds::gc::DHP> > Treiber_DHP_yield;
 108
 109         template <class GC> struct traits_Treiber_pause: public
 110             cds::intrusive::treiber_stack::make_traits <
 111                 cds::intrusive::opt::hook< base_hook<GC> >
 112                 , cds::opt::back_off<cds::backoff::pause>
 113             > ::type
 114         {};
 115         typedef cds::intrusive::TreiberStack< cds::gc::HP,  T, traits_Treiber_pause<cds::gc::HP>  > Treiber_HP_pause;
 116         typedef cds::intrusive::TreiberStack< cds::gc::DHP, T, traits_Treiber_pause<cds::gc::DHP> > Treiber_DHP_pause;
 117
 118         template <class GC> struct traits_Treiber_exp: public
 119             cds::intrusive::treiber_stack::make_traits <
 120                 cds::intrusive::opt::hook< base_hook<GC> >
 121                 ,cds::opt::back_off<
 122                     cds::backoff::exponential<
 123                         cds::backoff::pause,
 124                         cds::backoff::yield
 125                     >
 126                 >
 127             > ::type
 128         {};
 129         typedef cds::intrusive::TreiberStack< cds::gc::HP,  T, traits_Treiber_exp<cds::gc::HP>  > Treiber_HP_exp;
 130         typedef cds::intrusive::TreiberStack< cds::gc::DHP, T, traits_Treiber_exp<cds::gc::DHP> > Treiber_DHP_exp;
 131
 132
 133     // Elimination stack
 134         template <class GC> struct traits_Elimination_on : public
 135             cds::intrusive::treiber_stack::make_traits <
 136                 cds::intrusive::opt::hook< base_hook<GC> >
 137                 , cds::opt::enable_elimination<true>
 138             > ::type
 139         {};
 140         typedef cds::intrusive::TreiberStack< cds::gc::HP,  T, traits_Elimination_on<cds::gc::HP>  > Elimination_HP;
 141         typedef cds::intrusive::TreiberStack< cds::gc::DHP, T, traits_Elimination_on<cds::gc::DHP> > Elimination_DHP;
 142
 143         template <class GC> struct traits_Elimination_seqcst : public
 144             cds::intrusive::treiber_stack::make_traits <
 145                 cds::intrusive::opt::hook< base_hook<GC> >
 146                 , cds::opt::enable_elimination<true>
 147                 , cds::opt::memory_model< cds::opt::v::sequential_consistent >
 148             > ::type
 149         {};
 150         typedef cds::intrusive::TreiberStack< cds::gc::HP,  T, traits_Elimination_seqcst<cds::gc::HP>  > Elimination_HP_seqcst;
 151         typedef cds::intrusive::TreiberStack< cds::gc::DHP, T, traits_Elimination_seqcst<cds::gc::DHP> > Elimination_DHP_seqcst;
 152
 153         template <class GC> struct traits_Elimination_2ms: public
 154             cds::intrusive::treiber_stack::make_traits <
 155                 cds::intrusive::opt::hook< base_hook<GC> >
 156                 , cds::opt::enable_elimination<true>
 157                 , cds::opt::elimination_backoff< cds::backoff::delay_of<2> >
 158             > ::type
 159         {};
 160         typedef cds::intrusive::TreiberStack< cds::gc::HP,  T, traits_Elimination_2ms<cds::gc::HP>  > Elimination_HP_2ms;
 161         typedef cds::intrusive::TreiberStack< cds::gc::DHP, T, traits_Elimination_2ms<cds::gc::DHP> > Elimination_DHP_2ms;
 162
 163         template <class GC> struct traits_Elimination_2ms_stat: public
 164             cds::intrusive::treiber_stack::make_traits <
 165                 cds::intrusive::opt::hook< base_hook<GC> >
 166                 , cds::opt::enable_elimination<true>
 167                 , cds::opt::elimination_backoff< cds::backoff::delay_of<2> >
 168                 , cds::opt::stat<cds::intrusive::treiber_stack::stat<> >
 169             > ::type
 170         {};
 171         typedef cds::intrusive::TreiberStack< cds::gc::HP,  T, traits_Elimination_2ms_stat<cds::gc::HP>  > Elimination_HP_2ms_stat;
 172         typedef cds::intrusive::TreiberStack< cds::gc::DHP, T, traits_Elimination_2ms_stat<cds::gc::DHP> > Elimination_DHP_2ms_stat;
 173
 174         template <class GC> struct traits_Elimination_5ms: public
 175             cds::intrusive::treiber_stack::make_traits <
 176                 cds::intrusive::opt::hook< base_hook<GC> >
 177                 , cds::opt::enable_elimination<true>
 178                 , cds::opt::elimination_backoff< cds::backoff::delay_of<5> >
 179             > ::type
 180         {};
 181         typedef cds::intrusive::TreiberStack< cds::gc::HP,  T, traits_Elimination_5ms<cds::gc::HP>  > Elimination_HP_5ms;
 182         typedef cds::intrusive::TreiberStack< cds::gc::DHP, T, traits_Elimination_5ms<cds::gc::DHP> > Elimination_DHP_5ms;
 183
 184         template <class GC> struct traits_Elimination_5ms_stat: public
 185             cds::intrusive::treiber_stack::make_traits <
 186                 cds::intrusive::opt::hook< base_hook<GC> >
 187                 , cds::opt::enable_elimination<true>
 188                 , cds::opt::elimination_backoff< cds::backoff::delay_of<5> >
 189                 , cds::opt::stat<cds::intrusive::treiber_stack::stat<> >
 190             > ::type
 191         {};
 192         typedef cds::intrusive::TreiberStack< cds::gc::HP,  T, traits_Elimination_5ms_stat<cds::gc::HP>  > Elimination_HP_5ms_stat;
 193         typedef cds::intrusive::TreiberStack< cds::gc::DHP, T, traits_Elimination_5ms_stat<cds::gc::DHP> > Elimination_DHP_5ms_stat;
 194
 195         template <class GC> struct traits_Elimination_10ms: public
 196             cds::intrusive::treiber_stack::make_traits <
 197                 cds::intrusive::opt::hook< base_hook<GC> >
 198                 , cds::opt::enable_elimination<true>
 199                 , cds::opt::elimination_backoff< cds::backoff::delay_of<10> >
 200             > ::type
 201         {};
 202         typedef cds::intrusive::TreiberStack< cds::gc::HP,  T, traits_Elimination_10ms<cds::gc::HP>  > Elimination_HP_10ms;
 203         typedef cds::intrusive::TreiberStack< cds::gc::DHP, T, traits_Elimination_10ms<cds::gc::DHP> > Elimination_DHP_10ms;
 204
 205         template <class GC> struct traits_Elimination_10ms_stat: public
 206             cds::intrusive::treiber_stack::make_traits <
 207                 cds::intrusive::opt::hook< base_hook<GC> >
 208                 , cds::opt::enable_elimination<true>
 209                 , cds::opt::elimination_backoff< cds::backoff::delay_of<10> >
 210                 , cds::opt::stat<cds::intrusive::treiber_stack::stat<> >
 211             > ::type
 212         {};
 213         typedef cds::intrusive::TreiberStack< cds::gc::HP,  T, traits_Elimination_10ms_stat<cds::gc::HP>  > Elimination_HP_10ms_stat;
 214         typedef cds::intrusive::TreiberStack< cds::gc::DHP, T, traits_Elimination_10ms_stat<cds::gc::DHP> > Elimination_DHP_10ms_stat;
 215
 216         template <class GC> struct traits_Elimination_dyn: public
 217             cds::intrusive::treiber_stack::make_traits <
 218                 cds::intrusive::opt::hook< base_hook<GC> >
 219                 , cds::opt::enable_elimination<true>
 220                 , cds::opt::buffer< cds::opt::v::dynamic_buffer<int> >
 221             > ::type
 222         {};
 223         typedef cds::intrusive::TreiberStack< cds::gc::HP,  T, traits_Elimination_dyn<cds::gc::HP>  > Elimination_HP_dyn;
 224         typedef cds::intrusive::TreiberStack< cds::gc::DHP, T, traits_Elimination_dyn<cds::gc::DHP> > Elimination_DHP_dyn;
 225
 226         template <class GC> struct traits_Elimination_stat: public
 227             cds::intrusive::treiber_stack::make_traits <
 228                 cds::intrusive::opt::hook< base_hook<GC> >
 229                 , cds::opt::enable_elimination<true>
 230                 , cds::opt::stat<cds::intrusive::treiber_stack::stat<> >
 231             > ::type
 232         {};
 233         typedef cds::intrusive::TreiberStack< cds::gc::HP,  T, traits_Elimination_stat<cds::gc::HP>  > Elimination_HP_stat;
 234         typedef cds::intrusive::TreiberStack< cds::gc::DHP, T, traits_Elimination_stat<cds::gc::DHP> > Elimination_DHP_stat;
 235
 236         template <class GC> struct traits_Elimination_dyn_stat: public
 237             cds::intrusive::treiber_stack::make_traits <
 238                 cds::intrusive::opt::hook< base_hook<GC> >
 239                 , cds::opt::enable_elimination<true>
 240                 , cds::opt::buffer< cds::opt::v::dynamic_buffer<int> >
 241                 , cds::opt::stat<cds::intrusive::treiber_stack::stat<> >
 242             > ::type
 243         {};
 244         typedef cds::intrusive::TreiberStack< cds::gc::HP,  T, traits_Elimination_dyn_stat<cds::gc::HP>  > Elimination_HP_dyn_stat;
 245         typedef cds::intrusive::TreiberStack< cds::gc::DHP, T, traits_Elimination_dyn_stat<cds::gc::DHP> > Elimination_DHP_dyn_stat;
 246
 247         template <class GC> struct traits_Elimination_yield: public
 248             cds::intrusive::treiber_stack::make_traits <
 249                 cds::intrusive::opt::hook< base_hook<GC> >
 250                 , cds::opt::enable_elimination<true>
 251                 , cds::opt::back_off<cds::backoff::yield>
 252                 , cds::opt::memory_model<cds::opt::v::relaxed_ordering>
 253             > ::type
 254         {};
 255         typedef cds::intrusive::TreiberStack< cds::gc::HP,  T, traits_Elimination_yield<cds::gc::HP>  > Elimination_HP_yield;
 256         typedef cds::intrusive::TreiberStack< cds::gc::DHP, T, traits_Elimination_yield<cds::gc::DHP> > Elimination_DHP_yield;
 257
 258         template <class GC> struct traits_Elimination_pause: public
 259             cds::intrusive::treiber_stack::make_traits <
 260                 cds::intrusive::opt::hook< base_hook<GC> >
 261                 , cds::opt::enable_elimination<true>
 262                 , cds::opt::back_off<cds::backoff::pause>
 263             > ::type
 264         {};
 265         typedef cds::intrusive::TreiberStack< cds::gc::HP,  T, traits_Elimination_pause<cds::gc::HP>  > Elimination_HP_pause;
 266         typedef cds::intrusive::TreiberStack< cds::gc::DHP, T, traits_Elimination_pause<cds::gc::DHP> > Elimination_DHP_pause;
 267
 268         template <class GC> struct traits_Elimination_exp: public
 269             cds::intrusive::treiber_stack::make_traits <
 270                 cds::intrusive::opt::hook< base_hook<GC> >
 271                 , cds::opt::enable_elimination<true>
 272                 ,cds::opt::back_off<
 273                     cds::backoff::exponential<
 274                         cds::backoff::pause,
 275                         cds::backoff::yield
 276                     >
 277                 >
 278             > ::type
 279         {};
 280         typedef cds::intrusive::TreiberStack< cds::gc::HP,  T, traits_Elimination_exp<cds::gc::HP>  > Elimination_HP_exp;
 281         typedef cds::intrusive::TreiberStack< cds::gc::DHP, T, traits_Elimination_exp<cds::gc::DHP> > Elimination_DHP_exp;
 282
 283     // FCStack
 284         typedef cds::intrusive::FCStack< T > FCStack_slist;
 285
 286         struct traits_FCStack_stat:
 287             public cds::intrusive::fcstack::make_traits<
 288                 cds::opt::stat< cds::intrusive::fcstack::stat<> >
 289             >::type
 290         {};
 291         struct traits_FCStack_elimination:
 292             public cds::intrusive::fcstack::make_traits<
 293             cds::opt::enable_elimination< true >
 294             >::type
 295         {};
 296         struct traits_FCStack_elimination_stat:
 297             public cds::intrusive::fcstack::make_traits<
 298                 cds::opt::stat< cds::intrusive::fcstack::stat<> >,
 299                 cds::opt::enable_elimination< true >
 300             >::type
 301         {};
 302
 303         struct traits_FCStack_mutex_stat:
 304             public cds::intrusive::fcstack::make_traits<
 305                 cds::opt::stat< cds::intrusive::fcstack::stat<> >
 306                 ,cds::opt::lock_type< std::mutex >
 307             >::type
 308         {};
 309         struct traits_FCStack_mutex_elimination:
 310             public cds::intrusive::fcstack::make_traits<
 311                 cds::opt::enable_elimination< true >
 312                 ,cds::opt::lock_type< std::mutex >
 313             >::type
 314         {};
 315         struct traits_FCStack_mutex_elimination_stat:
 316             public cds::intrusive::fcstack::make_traits<
 317                 cds::opt::stat< cds::intrusive::fcstack::stat<> >
 318                 ,cds::opt::enable_elimination< true >
 319                 ,cds::opt::lock_type< std::mutex >
 320             >::type
 321         {};
 322
 323         typedef cds::intrusive::FCStack< T, boost::intrusive::slist< T >, traits_FCStack_stat > FCStack_slist_stat;
 324         typedef cds::intrusive::FCStack< T, boost::intrusive::slist< T >, traits_FCStack_elimination > FCStack_slist_elimination;
 325         typedef cds::intrusive::FCStack< T, boost::intrusive::slist< T >, traits_FCStack_elimination_stat > FCStack_slist_elimination_stat;
 326         typedef cds::intrusive::FCStack< T, boost::intrusive::slist< T >, traits_FCStack_mutex_stat > FCStack_slist_mutex_stat;
 327         typedef cds::intrusive::FCStack< T, boost::intrusive::slist< T >, traits_FCStack_mutex_elimination > FCStack_slist_mutex_elimination;
 328         typedef cds::intrusive::FCStack< T, boost::intrusive::slist< T >, traits_FCStack_mutex_elimination_stat > FCStack_slist_mutex_elimination_stat;
 329         typedef cds::intrusive::FCStack< T, boost::intrusive::list< T > > FCStack_list;
 330         typedef cds::intrusive::FCStack< T, boost::intrusive::list< T >, traits_FCStack_stat > FCStack_list_stat;
 331         typedef cds::intrusive::FCStack< T, boost::intrusive::list< T >, traits_FCStack_elimination > FCStack_list_elimination;
 332         typedef cds::intrusive::FCStack< T, boost::intrusive::list< T >, traits_FCStack_elimination_stat > FCStack_list_elimination_stat;
 333         typedef cds::intrusive::FCStack< T, boost::intrusive::list< T >, traits_FCStack_mutex_stat > FCStack_list_mutex_stat;
 334         typedef cds::intrusive::FCStack< T, boost::intrusive::list< T >, traits_FCStack_mutex_elimination > FCStack_list_mutex_elimination;
 335         typedef cds::intrusive::FCStack< T, boost::intrusive::list< T >, traits_FCStack_mutex_elimination_stat > FCStack_list_mutex_elimination_stat;
 336
 337
 338         // std::stack
 339         typedef details::StdStack< T, std::stack< T* >, std::mutex >  StdStack_Deque_Mutex;
 340         typedef details::StdStack< T, std::stack< T* >, cds::lock::Spin > StdStack_Deque_Spin;
 341         typedef details::StdStack< T, std::stack< T*, std::vector<T*> >, std::mutex >  StdStack_Vector_Mutex;
 342         typedef details::StdStack< T, std::stack< T*, std::vector<T*> >, cds::lock::Spin > StdStack_Vector_Spin;
 343         typedef details::StdStack< T, std::stack< T*, std::list<T*> >, std::mutex >  StdStack_List_Mutex;
 344         typedef details::StdStack< T, std::stack< T*, std::list<T*> >, cds::lock::Spin > StdStack_List_Spin;
 345
 346     };
 347 } // namespace istack
 348
 349 namespace std {
 350     static inline ostream& operator <<( ostream& o, cds::intrusive::treiber_stack::stat<> const& s )
 351     {
 352         return o << "\tStatistics:\n"
 353             << "\t                    Push: " << s.m_PushCount.get()              << "\n"
 354             << "\t                     Pop: " << s.m_PopCount.get()               << "\n"
 355             << "\t         Push contention: " << s.m_PushRace.get()               << "\n"
 356             << "\t          Pop contention: " << s.m_PopRace.get()                << "\n"
 357             << "\t   m_ActivePushCollision: " << s.m_ActivePushCollision.get()    << "\n"
 358             << "\t   m_PassivePopCollision: " << s.m_PassivePopCollision.get()    << "\n"
 359             << "\t    m_ActivePopCollision: " << s.m_ActivePopCollision.get()     << "\n"
 360             << "\t  m_PassivePushCollision: " << s.m_PassivePushCollision.get()   << "\n"
 361             << "\t     m_EliminationFailed: " << s.m_EliminationFailed.get()      << "\n";
 362     }
 363
 364     static inline ostream& operator <<( ostream& o, cds::intrusive::treiber_stack::empty_stat const& s )
 365     {
 366         return o;
 367     }
 368
 369     static inline ostream& operator <<( ostream& o, cds::intrusive::fcstack::empty_stat const& s )
 370     {
 371         return o;
 372     }
 373
 374     static inline ostream& operator <<( ostream& o, cds::intrusive::fcstack::stat<> const& s )
 375     {
 376         return o << "\tStatistics:\n"
 377             << "\t                    Push: " << s.m_nPush.get()              << "\n"
 378             << "\t                     Pop: " << s.m_nPop.get()               << "\n"
 379             << "\t               FailedPop: " << s.m_nFailedPop.get()         << "\n"
 380             << "\t  Collided push/pop pair: " << s.m_nCollided.get()          << "\n"
 381             << "\tFlat combining statistics:\n"
 382             << "\t        Combining factor: " << s.combining_factor()         << "\n"
 383             << "\t         Operation count: " << s.m_nOperationCount.get()    << "\n"
 384             << "\t      Combine call count: " << s.m_nCombiningCount.get()    << "\n"
 385             << "\t        Compact pub-list: " << s.m_nCompactPublicationList.get() << "\n"
 386             << "\t   Deactivate pub-record: " << s.m_nDeactivatePubRecord.get()    << "\n"
 387             << "\t     Activate pub-record: " << s.m_nActivatePubRecord.get()    << "\n"
 388             << "\t       Create pub-record: " << s.m_nPubRecordCreated.get()  << "\n"
 389             << "\t       Delete pub-record: " << s.m_nPubRecordDeteted.get()  << "\n"
 390             << "\t      Acquire pub-record: " << s.m_nAcquirePubRecCount.get()<< "\n"
 391             << "\t      Release pub-record: " << s.m_nReleasePubRecCount.get()<< "\n";
 392     }
 393
 394 } // namespace std
 395
 396 #endif // #ifndef __CDSUNIT_INTRUSIVE_STACK_TYPES_H