2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
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.
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.
31 #ifndef CDSUNIT_STACK_TYPES_H
32 #define CDSUNIT_STACK_TYPES_H
34 #include <cds/container/treiber_stack.h>
35 #include <cds/container/fcstack.h>
36 #include <cds/container/fcdeque.h>
38 #include <cds/gc/hp.h>
39 #include <cds/gc/dhp.h>
42 #include <cds/sync/spinlock.h>
51 template <typename T, typename Traits=cds::container::fcdeque::traits>
52 class FCDequeL: public cds::container::FCDeque<T, std::deque<T>, Traits >
54 typedef cds::container::FCDeque<T, std::deque<T>, Traits > base_class;
60 unsigned int nCompactFactor ///< Flat combining: publication list compacting factor
61 ,unsigned int nCombinePassCount ///< Flat combining: number of combining passes for combiner thread
63 : base_class( nCompactFactor, nCombinePassCount )
66 bool push( T const& v )
68 return base_class::push_front( v );
73 return base_class::pop_front( v );
77 template <typename T, typename Traits=cds::container::fcdeque::traits>
78 class FCDequeR: public cds::container::FCDeque<T, std::deque<T>, Traits >
80 typedef cds::container::FCDeque<T, std::deque<T>, Traits > base_class;
86 unsigned int nCompactFactor ///< Flat combining: publication list compacting factor
87 ,unsigned int nCombinePassCount ///< Flat combining: number of combining passes for combiner thread
89 : base_class( nCompactFactor, nCombinePassCount )
92 bool push( T const& v )
94 return base_class::push_back( v );
99 return base_class::pop_back( v );
103 template < typename T, typename Stack, typename Lock>
108 cds::container::treiber_stack::empty_stat m_stat;
110 typedef std::unique_lock<Lock> unique_lock;
113 bool push( T const& v )
115 unique_lock l( m_Lock );
122 unique_lock l( m_Lock );
123 if ( !m_Impl.empty() ) {
133 unique_lock l( m_Lock );
134 return m_Impl.empty();
137 cds::container::treiber_stack::empty_stat const& statistics() const
144 template <typename T>
148 typedef cds::container::TreiberStack< cds::gc::HP, T > Treiber_HP;
149 typedef cds::container::TreiberStack< cds::gc::DHP, T > Treiber_DHP;
151 struct traits_Treiber_seqcst: public
152 cds::container::treiber_stack::make_traits<
153 cds::opt::memory_model<cds::opt::v::sequential_consistent>
156 typedef cds::container::TreiberStack< cds::gc::HP, T, traits_Treiber_seqcst > Treiber_HP_seqcst;
157 typedef cds::container::TreiberStack< cds::gc::DHP, T, traits_Treiber_seqcst > Treiber_DHP_seqcst;
159 struct traits_Treiber_stat: public
160 cds::container::treiber_stack::make_traits<
161 cds::opt::stat<cds::intrusive::treiber_stack::stat<> >
164 typedef cds::container::TreiberStack< cds::gc::HP, T, traits_Treiber_stat > Treiber_HP_stat;
165 typedef cds::container::TreiberStack< cds::gc::DHP, T, traits_Treiber_stat > Treiber_DHP_stat;
167 struct traits_Treiber_yield: public
168 cds::container::treiber_stack::make_traits<
169 cds::opt::back_off<cds::backoff::yield>
170 , cds::opt::memory_model<cds::opt::v::relaxed_ordering>
173 typedef cds::container::TreiberStack< cds::gc::HP, T, traits_Treiber_yield > Treiber_HP_yield;
174 typedef cds::container::TreiberStack< cds::gc::DHP, T, traits_Treiber_yield > Treiber_DHP_yield;
176 struct traits_Treiber_pause: public
177 cds::container::treiber_stack::make_traits<
178 cds::opt::back_off<cds::backoff::pause>
181 typedef cds::container::TreiberStack< cds::gc::HP, T, traits_Treiber_pause > Treiber_HP_pause;
182 typedef cds::container::TreiberStack< cds::gc::DHP, T, traits_Treiber_pause > Treiber_DHP_pause;
184 struct traits_Treiber_exp: public
185 cds::container::treiber_stack::make_traits<
187 cds::backoff::exponential<
194 typedef cds::container::TreiberStack< cds::gc::HP, T, traits_Treiber_exp > Treiber_HP_exp;
195 typedef cds::container::TreiberStack< cds::gc::DHP, T, traits_Treiber_exp > Treiber_DHP_exp;
199 struct traits_Elimination_on : public
200 cds::container::treiber_stack::make_traits <
201 cds::opt::enable_elimination<true>
204 typedef cds::container::TreiberStack< cds::gc::HP, T, traits_Elimination_on > Elimination_HP;
205 typedef cds::container::TreiberStack< cds::gc::DHP, T, traits_Elimination_on > Elimination_DHP;
207 struct traits_Elimination_stat : public
208 cds::container::treiber_stack::make_traits <
209 cds::opt::enable_elimination<true>
210 ,cds::opt::stat<cds::intrusive::treiber_stack::stat<> >
213 typedef cds::container::TreiberStack< cds::gc::HP, T, traits_Elimination_stat > Elimination_HP_stat;
214 typedef cds::container::TreiberStack< cds::gc::DHP, T, traits_Elimination_stat > Elimination_DHP_stat;
216 struct traits_Elimination_2ms: public
217 cds::container::treiber_stack::make_traits <
218 cds::opt::enable_elimination<true>
219 ,cds::opt::elimination_backoff< cds::backoff::delay_of<2> >
222 typedef cds::container::TreiberStack< cds::gc::HP, T, traits_Elimination_2ms > Elimination_HP_2ms;
223 typedef cds::container::TreiberStack< cds::gc::DHP, T, traits_Elimination_2ms > Elimination_DHP_2ms;
225 struct traits_Elimination_2ms_stat : public
226 cds::container::treiber_stack::make_traits <
227 cds::opt::enable_elimination<true>
228 , cds::opt::elimination_backoff< cds::backoff::delay_of<2> >
229 , cds::opt::stat<cds::intrusive::treiber_stack::stat<> >
232 typedef cds::container::TreiberStack< cds::gc::HP, T, traits_Elimination_2ms_stat > Elimination_HP_2ms_stat;
233 typedef cds::container::TreiberStack< cds::gc::DHP, T, traits_Elimination_2ms_stat > Elimination_DHP_2ms_stat;
235 struct traits_Elimination_5ms : public
236 cds::container::treiber_stack::make_traits <
237 cds::opt::enable_elimination<true>
238 , cds::opt::elimination_backoff< cds::backoff::delay_of<5> >
241 typedef cds::container::TreiberStack< cds::gc::HP, T, traits_Elimination_5ms > Elimination_HP_5ms;
242 typedef cds::container::TreiberStack< cds::gc::DHP, T, traits_Elimination_5ms > Elimination_DHP_5ms;
244 struct traits_Elimination_5ms_stat : public
245 cds::container::treiber_stack::make_traits <
246 cds::opt::enable_elimination<true>
247 , cds::opt::elimination_backoff< cds::backoff::delay_of<5> >
248 , cds::opt::stat<cds::intrusive::treiber_stack::stat<> >
251 typedef cds::container::TreiberStack< cds::gc::HP, T, traits_Elimination_5ms_stat > Elimination_HP_5ms_stat;
252 typedef cds::container::TreiberStack< cds::gc::DHP, T, traits_Elimination_5ms_stat > Elimination_DHP_5ms_stat;
254 struct traits_Elimination_10ms : public
255 cds::container::treiber_stack::make_traits <
256 cds::opt::enable_elimination<true>
257 , cds::opt::elimination_backoff< cds::backoff::delay_of<10> >
260 typedef cds::container::TreiberStack< cds::gc::HP, T, traits_Elimination_10ms > Elimination_HP_10ms;
261 typedef cds::container::TreiberStack< cds::gc::DHP, T, traits_Elimination_10ms > Elimination_DHP_10ms;
263 struct traits_Elimination_10ms_stat : public
264 cds::container::treiber_stack::make_traits <
265 cds::opt::enable_elimination<true>
266 , cds::opt::elimination_backoff< cds::backoff::delay_of<10> >
267 , cds::opt::stat<cds::intrusive::treiber_stack::stat<> >
270 typedef cds::container::TreiberStack< cds::gc::HP, T, traits_Elimination_10ms_stat > Elimination_HP_10ms_stat;
271 typedef cds::container::TreiberStack< cds::gc::DHP, T, traits_Elimination_10ms_stat > Elimination_DHP_10ms_stat;
273 struct traits_Elimination_dyn: public
274 cds::container::treiber_stack::make_traits <
275 cds::opt::enable_elimination<true>
276 , cds::opt::buffer< cds::opt::v::dynamic_buffer<int> >
279 typedef cds::container::TreiberStack< cds::gc::HP, T, traits_Elimination_dyn > Elimination_HP_dyn;
280 typedef cds::container::TreiberStack< cds::gc::DHP, T, traits_Elimination_dyn > Elimination_DHP_dyn;
282 struct traits_Elimination_seqcst: public
283 cds::container::treiber_stack::make_traits <
284 cds::opt::enable_elimination<true>
285 , cds::opt::memory_model<cds::opt::v::sequential_consistent>
288 typedef cds::container::TreiberStack< cds::gc::HP, T, traits_Elimination_seqcst > Elimination_HP_seqcst;
289 typedef cds::container::TreiberStack< cds::gc::DHP, T, traits_Elimination_seqcst > Elimination_DHP_seqcst;
291 struct traits_Elimination_dyn_stat: public
292 cds::container::treiber_stack::make_traits <
293 cds::opt::enable_elimination<true>
294 , cds::opt::stat<cds::intrusive::treiber_stack::stat<> >
295 , cds::opt::buffer< cds::opt::v::dynamic_buffer<int> >
298 typedef cds::container::TreiberStack< cds::gc::HP, T, traits_Elimination_dyn_stat > Elimination_HP_dyn_stat;
299 typedef cds::container::TreiberStack< cds::gc::DHP, T, traits_Elimination_dyn_stat > Elimination_DHP_dyn_stat;
301 struct traits_Elimination_yield: public
302 cds::container::treiber_stack::make_traits <
303 cds::opt::enable_elimination<true>
304 , cds::opt::back_off<cds::backoff::yield>
305 , cds::opt::memory_model<cds::opt::v::relaxed_ordering>
308 typedef cds::container::TreiberStack< cds::gc::HP, T, traits_Elimination_yield > Elimination_HP_yield;
309 typedef cds::container::TreiberStack< cds::gc::DHP, T, traits_Elimination_yield > Elimination_DHP_yield;
311 struct traits_Elimination_pause: public
312 cds::container::treiber_stack::make_traits <
313 cds::opt::enable_elimination<true>
314 , cds::opt::back_off<cds::backoff::pause>
317 typedef cds::container::TreiberStack< cds::gc::HP, T, traits_Elimination_pause > Elimination_HP_pause;
318 typedef cds::container::TreiberStack< cds::gc::DHP, T, traits_Elimination_pause > Elimination_DHP_pause;
320 struct traits_Elimination_exp: public
321 cds::container::treiber_stack::make_traits <
322 cds::opt::enable_elimination<true>
324 cds::backoff::exponential<
331 typedef cds::container::TreiberStack< cds::gc::HP, T, traits_Elimination_exp > Elimination_HP_exp;
332 typedef cds::container::TreiberStack< cds::gc::DHP, T, traits_Elimination_exp > Elimination_DHP_exp;
336 typedef cds::container::FCStack< T > FCStack_deque;
338 struct traits_FCStack_stat:
339 public cds::container::fcstack::make_traits<
340 cds::opt::stat< cds::container::fcstack::stat<> >
343 struct traits_FCStack_elimination:
344 public cds::container::fcstack::make_traits<
345 cds::opt::enable_elimination< true >
348 struct traits_FCStack_elimination_stat:
349 public cds::container::fcstack::make_traits<
350 cds::opt::stat< cds::container::fcstack::stat<> >,
351 cds::opt::enable_elimination< true >
354 struct traits_FCStack_mutex:
355 public cds::container::fcstack::make_traits<
356 cds::opt::lock_type< std::mutex >
360 typedef cds::container::FCStack< T, std::stack<T, std::deque<T> >, traits_FCStack_mutex > FCStack_deque_mutex;
361 typedef cds::container::FCStack< T, std::stack<T, std::deque<T> >, traits_FCStack_stat > FCStack_deque_stat;
362 typedef cds::container::FCStack< T, std::stack<T, std::deque<T> >, traits_FCStack_elimination > FCStack_deque_elimination;
363 typedef cds::container::FCStack< T, std::stack<T, std::deque<T> >, traits_FCStack_elimination_stat > FCStack_deque_elimination_stat;
364 typedef cds::container::FCStack< T, std::stack<T, std::vector<T> > > FCStack_vector;
365 typedef cds::container::FCStack< T, std::stack<T, std::vector<T> >, traits_FCStack_mutex > FCStack_vector_mutex;
366 typedef cds::container::FCStack< T, std::stack<T, std::vector<T> >, traits_FCStack_stat > FCStack_vector_stat;
367 typedef cds::container::FCStack< T, std::stack<T, std::vector<T> >, traits_FCStack_elimination > FCStack_vector_elimination;
368 typedef cds::container::FCStack< T, std::stack<T, std::vector<T> >, traits_FCStack_elimination_stat > FCStack_vector_elimination_stat;
369 typedef cds::container::FCStack< T, std::stack<T, std::list<T> > > FCStack_list;
370 typedef cds::container::FCStack< T, std::stack<T, std::list<T> >, traits_FCStack_mutex > FCStack_list_mutex;
371 typedef cds::container::FCStack< T, std::stack<T, std::list<T> >, traits_FCStack_stat > FCStack_list_stat;
372 typedef cds::container::FCStack< T, std::stack<T, std::list<T> >, traits_FCStack_elimination > FCStack_list_elimination;
373 typedef cds::container::FCStack< T, std::stack<T, std::list<T> >, traits_FCStack_elimination_stat > FCStack_list_elimination_stat;
376 struct traits_FCDeque_stat:
377 public cds::container::fcdeque::make_traits<
378 cds::opt::stat< cds::container::fcdeque::stat<> >
381 struct traits_FCDeque_elimination:
382 public cds::container::fcdeque::make_traits<
383 cds::opt::enable_elimination< true >
386 struct traits_FCDeque_elimination_stat:
387 public cds::container::fcdeque::make_traits<
388 cds::opt::stat< cds::container::fcdeque::stat<> >,
389 cds::opt::enable_elimination< true >
392 struct traits_FCDeque_mutex:
393 public cds::container::fcdeque::make_traits<
394 cds::opt::lock_type< std::mutex >
399 typedef details::FCDequeL< T > FCDequeL_default;
400 typedef details::FCDequeL< T, traits_FCDeque_mutex > FCDequeL_mutex;
401 typedef details::FCDequeL< T, traits_FCDeque_stat > FCDequeL_stat;
402 typedef details::FCDequeL< T, traits_FCDeque_elimination > FCDequeL_elimination;
403 typedef details::FCDequeL< T, traits_FCDeque_elimination_stat > FCDequeL_elimination_stat;
405 typedef details::FCDequeR< T > FCDequeR_default;
406 typedef details::FCDequeR< T, traits_FCDeque_mutex > FCDequeR_mutex;
407 typedef details::FCDequeR< T, traits_FCDeque_stat > FCDequeR_stat;
408 typedef details::FCDequeR< T, traits_FCDeque_elimination > FCDequeR_elimination;
409 typedef details::FCDequeR< T, traits_FCDeque_elimination_stat > FCDequeR_elimination_stat;
413 typedef details::StdStack< T, std::stack< T >, std::mutex > StdStack_Deque_Mutex;
414 typedef details::StdStack< T, std::stack< T >, cds::sync::spin > StdStack_Deque_Spin;
415 typedef details::StdStack< T, std::stack< T, std::vector<T> >, std::mutex > StdStack_Vector_Mutex;
416 typedef details::StdStack< T, std::stack< T, std::vector<T> >, cds::sync::spin > StdStack_Vector_Spin;
417 typedef details::StdStack< T, std::stack< T, std::list<T> >, std::mutex > StdStack_List_Mutex;
418 typedef details::StdStack< T, std::stack< T, std::list<T> >, cds::sync::spin > StdStack_List_Spin;
424 static inline ostream& operator <<( ostream& o, cds::container::treiber_stack::stat<> const& s )
426 return o << "\tStatistics:\n"
427 << "\t Push: " << s.m_PushCount.get() << "\n"
428 << "\t Pop: " << s.m_PopCount.get() << "\n"
429 << "\t Push contention: " << s.m_PushRace.get() << "\n"
430 << "\t Pop contention: " << s.m_PopRace.get() << "\n"
431 << "\t m_ActivePushCollision: " << s.m_ActivePushCollision.get() << "\n"
432 << "\t m_PassivePopCollision: " << s.m_PassivePopCollision.get() << "\n"
433 << "\t m_ActivePopCollision: " << s.m_ActivePopCollision.get() << "\n"
434 << "\t m_PassivePushCollision: " << s.m_PassivePushCollision.get() << "\n"
435 << "\t m_EliminationFailed: " << s.m_EliminationFailed.get() << "\n";
438 static inline ostream& operator <<(ostream& o, cds::container::treiber_stack::empty_stat const& /*s*/)
443 static inline ostream& operator <<( ostream& o, cds::container::fcstack::empty_stat const& /*s*/ )
448 static inline ostream& operator <<( ostream& o, cds::container::fcstack::stat<> const& s )
450 return o << "\tStatistics:\n"
451 << "\t Push: " << s.m_nPush.get() << "\n"
452 << "\t PushMove: " << s.m_nPushMove.get() << "\n"
453 << "\t Pop: " << s.m_nPop.get() << "\n"
454 << "\t FailedPop: " << s.m_nFailedPop.get() << "\n"
455 << "\t Collided push/pop pair: " << s.m_nCollided.get() << "\n"
456 << "\tFlat combining statistics:\n"
457 << "\t Combining factor: " << s.combining_factor() << "\n"
458 << "\t Operation count: " << s.m_nOperationCount.get() << "\n"
459 << "\t Combine call count: " << s.m_nCombiningCount.get() << "\n"
460 << "\t Compact pub-list: " << s.m_nCompactPublicationList.get() << "\n"
461 << "\t Deactivate pub-record: " << s.m_nDeactivatePubRecord.get() << "\n"
462 << "\t Activate pub-record: " << s.m_nActivatePubRecord.get() << "\n"
463 << "\t Create pub-record: " << s.m_nPubRecordCreated.get() << "\n"
464 << "\t Delete pub-record: " << s.m_nPubRecordDeteted.get() << "\n"
465 << "\t Acquire pub-record: " << s.m_nAcquirePubRecCount.get()<< "\n"
466 << "\t Release pub-record: " << s.m_nReleasePubRecCount.get()<< "\n";
469 static inline ostream& operator <<( ostream& o, cds::container::fcdeque::empty_stat const& /*s*/ )
474 static inline ostream& operator <<( ostream& o, cds::container::fcdeque::stat<> const& s )
476 return o << "\tStatistics:\n"
477 << "\t Push front: " << s.m_nPushFront.get() << "\n"
478 << "\t Push front move: " << s.m_nPushFrontMove.get() << "\n"
479 << "\t Push back: " << s.m_nPushBack.get() << "\n"
480 << "\t Push back move: " << s.m_nPushBackMove.get() << "\n"
481 << "\t Pop front: " << s.m_nPopFront.get() << "\n"
482 << "\t Failed pop front: " << s.m_nFailedPopFront.get() << "\n"
483 << "\t Pop back: " << s.m_nPopBack.get() << "\n"
484 << "\t Failed pop back: " << s.m_nFailedPopBack.get() << "\n"
485 << "\t Collided push/pop pair: " << s.m_nCollided.get() << "\n"
486 << "\tFlat combining statistics:\n"
487 << "\t Combining factor: " << s.combining_factor() << "\n"
488 << "\t Operation count: " << s.m_nOperationCount.get() << "\n"
489 << "\t Combine call count: " << s.m_nCombiningCount.get() << "\n"
490 << "\t Compact pub-list: " << s.m_nCompactPublicationList.get() << "\n"
491 << "\t Deactivate pub-record: " << s.m_nDeactivatePubRecord.get() << "\n"
492 << "\t Activate pub-record: " << s.m_nActivatePubRecord.get() << "\n"
493 << "\t Create pub-record: " << s.m_nPubRecordCreated.get() << "\n"
494 << "\t Delete pub-record: " << s.m_nPubRecordDeteted.get() << "\n"
495 << "\t Acquire pub-record: " << s.m_nAcquirePubRecCount.get()<< "\n"
496 << "\t Release pub-record: " << s.m_nReleasePubRecCount.get()<< "\n";
501 #endif // #ifndef CDSUNIT_STACK_TYPES_H