cds/intrusive/michael_deque.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_MICHAEL_DEQUE_H
   4 #define __CDS_INTRUSIVE_MICHAEL_DEQUE_H
   5
   6 #include <cds/intrusive/michael_list_impl.h>
   7 #include <cds/intrusive/michael_set.h>
   8 #include <cds/intrusive/deque_stat.h>
   9 #include <cds/ref.h>
  10 #include <cds/details/aligned_type.h>
  11 #include <cds/gc/default_gc.h>
  12
  13 #include <cds/details/std/type_traits.h>
  14
  15 namespace cds { namespace intrusive {
  16
  17     //@cond
  18     struct michael_deque_tag;
  19     //@endcond
  20
  21     /// MichaelDeque related definitions
  22     /** @ingroup cds_intrusive_helper
  23     */
  24     namespace michael_deque
  25     {
  26         /// Anchor contains left/right sibling items
  27         /**
  28             The anchor object is maintained by one CAS instruction.
  29         */
  30         struct anchor
  31         {
  32             unsigned int  idxLeft ;     ///< Left sibling index; the most-significant bit contains left-stable flag
  33             unsigned int  idxRight  ;   ///< Right sibling index; the most-significant bit contains right-stable flag
  34
  35 #       ifdef CDS_CXX11_EXPLICITLY_DEFAULTED_FUNCTION_SUPPORT
  36             //@cond
  37             anchor() CDS_NOEXCEPT_DEFAULTED = default;
  38             anchor( anchor const& ) CDS_NOEXCEPT_DEFAULTED = default;
  39             ~anchor() CDS_NOEXCEPT_DEFAULTED = default;
  40             anchor& operator=(anchor const&) CDS_NOEXCEPT_DEFAULTED = default;
  41 #       if defined(CDS_MOVE_SEMANTICS_SUPPORT) && !defined(CDS_DISABLE_DEFAULT_MOVE_CTOR)
  42             anchor( anchor&&) CDS_NOEXCEPT_DEFAULTED = default;
  43             anchor& operator=(anchor&&) CDS_NOEXCEPT_DEFAULTED = default;
  44 #       endif
  45             //@endcond
  46 #       else
  47             /// Default ctor does not initialize left/right indices
  48             anchor() CDS_NOEXCEPT
  49                 : idxLeft( 0 )
  50                 , idxRight( 0 )
  51             {
  52                 static_check();
  53             }
  54
  55             anchor( anchor const& a) CDS_NOEXCEPT
  56                 : idxLeft( a.idxLeft )
  57                 , idxRight( a.idxRight )
  58             {
  59                 static_check();
  60             }
  61 #       endif
  62
  63             /// Constructor sets \p left / \p right indices
  64             anchor( unsigned int left, unsigned int right ) CDS_NOEXCEPT
  65                 : idxLeft( left )
  66                 , idxRight( right )
  67             {
  68                 static_check();
  69             }
  70
  71             /// Anchor equal operator
  72             bool operator ==( anchor const& a) const CDS_NOEXCEPT
  73             {
  74                 return idxLeft == a.idxLeft && idxRight == a.idxRight;
  75             }
  76
  77             /// Anchor non-equal operator
  78             bool operator !=( anchor const& a) const CDS_NOEXCEPT
  79             {
  80                 return !( *this == a );
  81             }
  82
  83         private:
  84             //@cond
  85             static void static_check()
  86             {
  87                 static_assert( sizeof(unsigned int) * 2 <= 8, "The index type must be no more than 32bit long" );
  88                 static_assert( sizeof(anchor) <= 8, "The anchor type must be no more than 64bit long" );
  89             }
  90             //@endcond
  91         };
  92
  93         /// Michael's deque node
  94         /**
  95             Template parameters:
  96             - GC - garbage collector
  97             - Tag - a tag used to distinguish between different implementation
  98         */
  99         template <class GC, typename Tag = opt::none>
 100         struct node: public michael_list::node< GC, michael_deque_tag >
 101         {
 102             typedef GC              gc  ;   ///< Garbage collector
 103             typedef Tag             tag ;   ///< tag
 104
 105             //@cond
 106             typedef michael_list::node< gc, michael_deque_tag > mapper_node_type;
 107             //@endcond
 108
 109             typedef typename gc::template atomic_type< anchor >   atomic_anchor  ;    ///< atomic reference to left/right node
 110
 111             CDS_DATA_ALIGNMENT(8) atomic_anchor   m_Links ;   ///< Left/right sibling links
 112             unsigned int    m_nIndex;   ///< Item index
 113
 114             //@cond
 115             node()
 116             {
 117                 m_Links.store( anchor(0,0), CDS_ATOMIC::memory_order_release );
 118             }
 119
 120             explicit node( anchor const& a )
 121                 : m_Links()
 122                 , m_nIndex(0)
 123             {
 124                 m_Links.store( a, CDS_ATOMIC::memory_order_release );
 125             }
 126             //@endcond
 127         };
 128
 129         //@cond
 130         struct default_hook {
 131             typedef cds::gc::default_gc gc;
 132             typedef opt::none           tag;
 133             typedef unsigned int        index_type;
 134         };
 135         //@endcond
 136
 137         //@cond
 138         template < typename HookType, CDS_DECL_OPTIONS3>
 139         struct hook
 140         {
 141             typedef typename opt::make_options< default_hook, CDS_OPTIONS3>::type  options;
 142             typedef typename options::gc    gc;
 143             typedef typename options::tag   tag;
 144             typedef typename options::index_type index_type;
 145
 146             typedef node<gc, tag>   node_type;
 147             typedef HookType        hook_type;
 148         };
 149         //@endcond
 150
 151
 152         /// Base hook
 153         /**
 154             \p Options are:
 155             - opt::gc - garbage collector used.
 156             - opt::tag - tag
 157             - opt::index_type - integral index type
 158         */
 159         template < CDS_DECL_OPTIONS3 >
 160         struct base_hook: public hook< opt::base_hook_tag, CDS_OPTIONS3 >
 161         {};
 162
 163         /// Member hook
 164         /**
 165             \p MemberOffset defines offset in bytes of \ref node member into your structure.
 166             Use \p offsetof macro to define \p MemberOffset
 167
 168             \p Options are:
 169             - opt::gc - garbage collector used.
 170             - opt::tag - tag
 171             - opt::index_type - integral index type
 172         */
 173         template < size_t MemberOffset, CDS_DECL_OPTIONS3 >
 174         struct member_hook: public hook< opt::member_hook_tag, CDS_OPTIONS3 >
 175         {
 176             //@cond
 177             static const size_t c_nMemberOffset = MemberOffset;
 178             //@endcond
 179         };
 180
 181         /// Traits hook
 182         /**
 183             \p NodeTraits defines type traits for node.
 184             See \ref node_traits for \p NodeTraits interface description
 185
 186             \p Options are:
 187             - opt::gc - garbage collector used.
 188             - opt::tag - tag
 189             - opt::index_type - integral index type
 190         */
 191         template <typename NodeTraits, CDS_DECL_OPTIONS3 >
 192         struct traits_hook: public hook< opt::traits_hook_tag, CDS_OPTIONS3 >
 193         {
 194             //@cond
 195             typedef NodeTraits node_traits;
 196             //@endcond
 197         };
 198
 199         /// Deque internal statistics. May be used for debugging or profiling
 200         /**
 201             Template argument \p Counter defines type of counter.
 202             Default is cds::atomics::event_counter.
 203             You may use other counter type like as cds::atomics::item_counter,
 204             or even integral type, for example, \p int.
 205
 206             The class extends intrusive::deque_stat interface for MichaelDeque.
 207         */
 208         template <typename Counter = cds::atomicity::event_counter >
 209         struct stat: public cds::intrusive::deque_stat<Counter>
 210         {
 211             //@cond
 212             typedef cds::intrusive::deque_stat<Counter> base_class;
 213             typedef typename base_class::counter_type   counter_type;
 214             //@endcond
 215
 216             counter_type m_StabilizeFrontCount  ;  ///< stabilize left event count
 217             counter_type m_StabilizeBackCount   ;  ///< stabilize right event count
 218
 219             /// Register "stabilize left" event
 220             void onStabilizeFront()          { ++m_StabilizeFrontCount; }
 221
 222             /// Register "stabilize right" event
 223             void onStabilizeBack()          { ++m_StabilizeBackCount; }
 224         };
 225
 226         /// Dummy deque statistics - no counting is performed. Support interface like \ref michael_deque::stat
 227         struct dummy_stat: public cds::intrusive::deque_dummy_stat
 228         {
 229             //@cond
 230             void onStabilizeFront() {}
 231             void onStabilizeBack()  {}
 232             //@endcond
 233         };
 234
 235         //@cond
 236         template < typename NodeType, opt::link_check_type LinkType>
 237         struct link_checker
 238         {
 239             typedef NodeType node_type;
 240
 241             static void is_empty( const node_type * pNode )
 242             {
 243 #           ifdef _DEBUG
 244                 anchor a = pNode->m_Links.load(CDS_ATOMIC::memory_order_relaxed);
 245                 assert( a.idxLeft == 0 && a.idxRight == 0 );
 246 #           endif
 247             }
 248         };
 249
 250         template < typename NodeType>
 251         struct link_checker<NodeType, opt::never_check_link>
 252         {
 253             typedef NodeType node_type;
 254
 255             static void is_empty( const node_type * /*pNode*/ )
 256             {}
 257         };
 258         //@endcond
 259     }   // namespace michael_deque
 260
 261     /// Michael's intrusive deque
 262     /** @ingroup cds_intrusive_deque
 263         Implementation of Michael's deque algorithm.
 264
 265         \par Source:
 266             [2003] Maged Michael "CAS-based Lock-free Algorithm for Shared Deque"
 267
 268         <b>Short description</b> (from Michael's paper)
 269
 270         The deque is represented as a doubly-linked list. Each node in the list contains two link pointers,
 271         \p pRight and \p pLeft, and a data field. A shared variable, \p Anchor, holds the two anchor
 272         pointers to the leftmost and rightmost nodes in the list, if any, and a three-value
 273         status tag. Anchor must fit in a memory block that can be read and manipulated
 274         using CAS or LL/SC, atomically. Initially both anchor pointers have null values
 275         and the status tag holds the value stable, indicating an empty deque.
 276
 277         The status tag serves to indicate if the deque is in an unstable state. When
 278         a process finds the deque in an unstable state, it must first attempt to take it
 279         to a stable state before attempting its own operation.
 280
 281         The algorithm can use single-word CAS or LL/SC.
 282         In \p libcds implementation of the algorithm the node contains two
 283         31bit link indices instead of pointers + one bit for status tag;
 284         this trick allows use 64bit CAS to manipulate \p Anchor. Internal mapper
 285         (based on MichaelHashSet intrusive container)
 286         reflects link indices to item pointers. The maximum number of item in
 287         the deque is limited by 2**31 that is practically unbounded.
 288
 289         Template arguments:
 290         - \p GC - garbage collector type: gc::HP or gc::PTB. Note that gc::HRC is not supported
 291         - \p T - type to be stored in the queue, should be convertible to michael_deque::node
 292         - \p Options - options
 293
 294         Type of node: \ref michael_deque::node
 295
 296         \p Options are:
 297         - opt::hook - hook used. Possible values are: michael_deque::base_hook, michael_deque::member_hook, michael_deque::traits_hook.
 298             If the option is not specified, <tt>michael_deque::base_hook<></tt> is used.
 299         - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
 300         - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer. This option is used
 301             in \ref pop_front and \ref pop_back functions.
 302         - opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link
 303         - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter (no item counting feature)
 304         - opt::stat - the type to gather internal statistics.
 305             Possible option value are: \ref michael_deque::stat, \ref michael_deque::dummy_stat, user-provided class that supports michael_deque::stat interface.
 306             Default is \ref michael_deque::dummy_stat.
 307         - opt::alignment - the alignment for internal deque data. Default is opt::cache_line_alignment
 308         - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
 309             or opt::v::sequential_consistent (sequentially consisnent memory model).
 310         - opt::allocator - allocator using for internal memory mapper based on MichaelHashSet. Default is CDS_DEFAULT_ALLOCATOR.
 311     */
 312     template <typename GC, typename T, CDS_DECL_OPTIONS10>
 313     class MichaelDeque
 314     {
 315         //@cond
 316         struct default_options
 317         {
 318             typedef cds::backoff::empty             back_off;
 319             typedef michael_deque::base_hook<>      hook;
 320             typedef opt::v::empty_disposer          disposer;
 321             typedef atomicity::empty_item_counter   item_counter;
 322             typedef michael_deque::dummy_stat       stat;
 323             typedef opt::v::relaxed_ordering        memory_model;
 324             static const opt::link_check_type link_checker = opt::debug_check_link;
 325             enum { alignment = opt::cache_line_alignment };
 326             typedef CDS_DEFAULT_ALLOCATOR           allocator;
 327         };
 328         //@endcond
 329
 330     public:
 331         //@cond
 332         typedef typename opt::make_options<
 333             typename cds::opt::find_type_traits< default_options, CDS_OPTIONS10 >::type
 334             ,CDS_OPTIONS10
 335         >::type   options;
 336         //@endcond
 337
 338     private:
 339         //@cond
 340         typedef typename std::conditional<
 341             std::is_same<typename options::stat, cds::intrusive::deque_stat<> >::value
 342             ,michael_deque::stat<>
 343             ,typename std::conditional<
 344                 std::is_same<typename options::stat, cds::intrusive::deque_dummy_stat>::value
 345                 ,michael_deque::dummy_stat
 346                 ,typename options::stat
 347             >::type
 348         >::type stat_type_;
 349         //@endcond
 350
 351
 352     public:
 353         typedef T  value_type   ;   ///< type of value stored in the deque
 354         typedef typename options::hook      hook        ;   ///< hook type
 355         typedef typename hook::node_type    node_type   ;   ///< node type
 356         typedef typename options::disposer  disposer    ;   ///< disposer used
 357         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ;    ///< node traits
 358         typedef michael_deque::link_checker< node_type, options::link_checker > link_checker   ;   ///< link checker
 359
 360         typedef GC gc                                       ;   ///< Garbage collector
 361         typedef typename options::back_off  back_off        ;   ///< back-off strategy
 362         typedef typename options::item_counter item_counter ;   ///< Item counting policy used
 363         typedef stat_type_   stat                           ;   ///< Internal statistics policy used
 364         typedef typename options::memory_model  memory_model;   ///< Memory ordering. See cds::opt::memory_model option
 365         typedef typename options::allocator allocator_type  ;   ///< Allocator using for internal memory mapping
 366
 367         typedef typename node_type::atomic_anchor   atomic_anchor   ;   ///< Atomic anchor
 368
 369     protected:
 370         //@cond
 371         class index_mapper
 372         {
 373             struct node_less_comparator
 374             {
 375                 bool operator ()( value_type const & n1, value_type const& n2) const
 376                 {
 377                     return node_traits::to_node_ptr(n1)->m_nIndex < node_traits::to_node_ptr(n2)->m_nIndex;
 378                 }
 379                 bool operator ()( unsigned int i, value_type const& n2) const
 380                 {
 381                     return i < node_traits::to_node_ptr(n2)->m_nIndex;
 382                 }
 383                 bool operator ()( value_type const & n1, unsigned int i) const
 384                 {
 385                     return node_traits::to_node_ptr(n1)->m_nIndex < i;
 386                 }
 387             };
 388
 389             struct internal_disposer
 390             {
 391                 void operator()( value_type * p )
 392                 {
 393                     assert( p != nullptr );
 394
 395                     MichaelDeque::clear_links( node_traits::to_node_ptr(p) );
 396                     disposer()( p );
 397                 }
 398             };
 399
 400             struct mapper_node_traits
 401             {
 402                 typedef typename node_type::mapper_node_type mapper_node_type;
 403
 404                 static mapper_node_type * to_node_ptr( value_type& v )
 405                 {
 406                     return static_cast<mapper_node_type *>( node_traits::to_node_ptr(v) );
 407                 }
 408
 409                 static mapper_node_type * to_node_ptr( value_type * v )
 410                 {
 411                     return static_cast<mapper_node_type *>( node_traits::to_node_ptr(v) );
 412                 }
 413
 414                 static mapper_node_type const * to_node_ptr( value_type const& v )
 415                 {
 416                     return static_cast<mapper_node_type const *>( node_traits::to_node_ptr(v) );
 417                 }
 418
 419                 static mapper_node_type const * to_node_ptr( value_type const * v )
 420                 {
 421                     return static_cast<mapper_node_type const *>( node_traits::to_node_ptr(v) );
 422                 }
 423
 424                 static value_type * to_value_ptr( mapper_node_type&  n )
 425                 {
 426                     return node_traits::to_value_ptr( static_cast<node_type&>(n));
 427                 }
 428
 429                 static value_type * to_value_ptr( mapper_node_type *  n )
 430                 {
 431                     return node_traits::to_value_ptr( static_cast<node_type *>(n));
 432                 }
 433
 434                 static const value_type * to_value_ptr( mapper_node_type const& n )
 435                 {
 436                     return node_traits::to_value_ptr( static_cast<node_type const&>(n));
 437                 }
 438
 439                 static const value_type * to_value_ptr( mapper_node_type const * n )
 440                 {
 441                     return node_traits::to_value_ptr( static_cast<node_type const *>(n));
 442                 }
 443             };
 444
 445             typedef MichaelList< gc, value_type,
 446                 typename michael_list::make_traits<
 447                     opt::hook< michael_list::traits_hook<
 448                         mapper_node_traits
 449                         ,cds::opt::gc< gc >
 450                         ,cds::opt::tag<michael_deque_tag> >
 451                     >
 452                     ,opt::less< node_less_comparator >
 453                     ,opt::back_off< back_off >
 454                     ,opt::disposer< internal_disposer >
 455                     ,opt::memory_model< memory_model >
 456                 >::type
 457             > mapper_ordered_list;
 458
 459             struct mapper_hash {
 460                 size_t operator()( value_type const& v ) const
 461                 {
 462                     return cds::opt::v::hash<unsigned int>()( node_traits::to_node_ptr(v)->m_nIndex );
 463                 }
 464                 size_t operator()( unsigned int i ) const
 465                 {
 466                     return cds::opt::v::hash<unsigned int>()(i);
 467                 }
 468             };
 469
 470             typedef MichaelHashSet< gc, mapper_ordered_list,
 471                 typename michael_set::make_traits<
 472                     opt::hash< mapper_hash >
 473                     ,opt::allocator< allocator_type >
 474                 >::type
 475             >   mapper_type;
 476
 477 #       if !(defined(CDS_CXX11_LAMBDA_SUPPORT) && !((CDS_COMPILER == CDS_COMPILER_MSVC || CDS_COMPILER == CDS_COMPILER_INTEL) && _MSC_VER < 1700))
 478             struct at_functor {
 479                 node_type * pNode;
 480
 481                 at_functor()
 482                     : pNode( nullptr )
 483                     {}
 484
 485                 void operator()( value_type& v, unsigned int nIdx )
 486                 {
 487                     pNode = node_traits::to_node_ptr(v);
 488                     assert( pNode->m_nIndex == nIdx );
 489                 }
 490             };
 491 #       endif
 492
 493             mapper_type     m_set;
 494             CDS_ATOMIC::atomic<unsigned int>    m_nLastIndex;
 495
 496         public:
 497
 498             index_mapper( size_t nEstimatedItemCount, size_t nLoadFactor )
 499                 : m_set( nEstimatedItemCount, nLoadFactor )
 500                 , m_nLastIndex(1)
 501                 {}
 502
 503             unsigned int map( value_type& v )
 504             {
 505                 while ( true ) {
 506                     node_type * pNode = node_traits::to_node_ptr( v );
 507                     pNode->m_nIndex = m_nLastIndex.fetch_add( 1, memory_model::memory_order_relaxed );
 508                     if ( pNode->m_nIndex && m_set.insert( v ))
 509                         return pNode->m_nIndex;
 510                 }
 511             }
 512
 513             bool unmap( unsigned int nIdx )
 514             {
 515                 return m_set.erase( nIdx );
 516             }
 517
 518             node_type * at( unsigned int nIdx )
 519             {
 520 #   if defined(CDS_CXX11_LAMBDA_SUPPORT) && !((CDS_COMPILER == CDS_COMPILER_MSVC ||CDS_COMPILER == CDS_COMPILER_INTEL) && _MSC_VER < 1700)
 521                 // MS VC++2010 bug: error C2955: 'cds::intrusive::node_traits' : use of class template requires template argument list
 522                 // see declaration of 'cds::intrusive::node_traits'
 523                 node_type * pNode = nullptr;
 524                 if ( m_set.find( nIdx,
 525                     [&pNode](value_type& v, unsigned int nIdx) {
 526                         pNode = node_traits::to_node_ptr(v);
 527                         assert( pNode->m_nIndex == nIdx );
 528                     })
 529                 )
 530                     return pNode;
 531 #   else
 532                 at_functor f;
 533                 if ( m_set.find( nIdx, cds::ref(f) ))
 534                     return f.pNode;
 535 #   endif
 536                 return nullptr;
 537             }
 538         };
 539         //@endcond
 540     public:
 541
 542         /// Rebind template arguments
 543         template <typename GC2, typename T2, CDS_DECL_OTHER_OPTIONS10>
 544         struct rebind {
 545             typedef MichaelDeque< GC2, T2, CDS_OTHER_OPTIONS10> other   ;   ///< Rebinding result
 546         };
 547
 548     protected:
 549         typename cds::opt::details::alignment_setter< atomic_anchor, options::alignment >::type  m_Anchor ;   ///< Left/right heads
 550         typename cds::opt::details::alignment_setter< index_mapper, options::alignment >::type   m_Mapper ;   ///< Memory mapper
 551
 552         item_counter            m_ItemCounter   ;   ///< item counter
 553         stat                    m_Stat  ;   ///< Internal statistics
 554
 555         //@cond
 556         static const unsigned int c_nIndexMask    = ((unsigned int)(0 - 1)) >> 1;
 557         static const unsigned int c_nFlagMask     = ((unsigned int)(1)) << (sizeof(unsigned int) * 8 - 1);
 558         static const unsigned int c_nEmptyIndex   = 0;
 559         //@endcond
 560
 561     private:
 562         //@cond
 563         typedef michael_deque::anchor CDS_TYPE_ALIGNMENT(8) anchor_type;
 564         typedef intrusive::node_to_value<MichaelDeque> node_to_value;
 565
 566         static void clear_links( node_type * pNode )
 567         {
 568             pNode->m_Links.store( anchor_type(), memory_model::memory_order_release );
 569         }
 570
 571         enum anchor_status {
 572             Stable,
 573             RPush,
 574             LPush
 575         };
 576
 577         static anchor_status status( anchor_type const& a )
 578         {
 579             if ( a.idxLeft & c_nFlagMask )
 580                 return LPush;
 581             if ( a.idxRight & c_nFlagMask )
 582                 return RPush;
 583             return Stable;
 584         }
 585
 586         static unsigned int index( unsigned int i )
 587         {
 588             return i & c_nIndexMask;
 589         }
 590
 591         void stabilize( anchor_type& a )
 592         {
 593             switch ( status(a)) {
 594                 case LPush:
 595                     stabilize_front(a);
 596                     break;
 597                 case RPush:
 598                     stabilize_back(a);
 599                     break;
 600                 default:
 601                     break;
 602             }
 603         }
 604
 605         void stabilize_front( anchor_type& a )
 606         {
 607             m_Stat.onStabilizeFront();
 608
 609             typename gc::template GuardArray<3>  guards;
 610             node_type * pLeft;
 611             node_type * pRight;
 612             unsigned int const idxLeft  = index( a.idxLeft );
 613             unsigned int const idxRight = index( a.idxRight );
 614
 615             guards.assign( 0, node_traits::to_value_ptr( pLeft = m_Mapper.at( idxLeft )) );
 616             guards.assign( 1, node_traits::to_value_ptr( pRight = m_Mapper.at( idxRight )) );
 617             if ( m_Anchor.load( memory_model::memory_order_acquire ) != a )
 618                 return;
 619
 620             unsigned int idxPrev = index( pLeft->m_Links.load(memory_model::memory_order_relaxed ).idxRight );
 621             node_type * pPrev;
 622             guards.assign( 2, node_traits::to_value_ptr( pPrev = m_Mapper.at( idxPrev )) );
 623             if ( m_Anchor.load( memory_model::memory_order_acquire ) != a )
 624                 return;
 625
 626             anchor_type prevLinks( pPrev->m_Links.load( memory_model::memory_order_acquire ));
 627             if ( index( prevLinks.idxLeft ) != idxLeft ) {
 628                 if ( m_Anchor.load( memory_model::memory_order_acquire ) != a )
 629                     return;
 630
 631                 if ( !pPrev->m_Links.compare_exchange_strong( prevLinks, anchor_type( idxLeft, prevLinks.idxRight ), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
 632                     return;
 633             }
 634
 635             // clear RPush/LPush flags
 636             m_Anchor.compare_exchange_weak( a, anchor_type(idxLeft, idxRight), memory_model::memory_order_release, memory_model::memory_order_relaxed );
 637         }
 638
 639         void stabilize_back( anchor_type& a )
 640         {
 641             m_Stat.onStabilizeBack();
 642
 643             typename gc::template GuardArray<3>  guards;
 644             node_type * pLeft;
 645             node_type * pRight;
 646             unsigned int const idxLeft  = index( a.idxLeft );
 647             unsigned int const idxRight = index( a.idxRight );
 648
 649             guards.assign( 0, node_traits::to_value_ptr( pLeft = m_Mapper.at( idxLeft )) );
 650             guards.assign( 1, node_traits::to_value_ptr( pRight = m_Mapper.at( idxRight )) );
 651             if ( m_Anchor.load( memory_model::memory_order_acquire ) != a )
 652                 return;
 653
 654             unsigned int idxPrev = index( pRight->m_Links.load(memory_model::memory_order_relaxed ).idxLeft );
 655             node_type * pPrev;
 656             guards.assign( 2, node_traits::to_value_ptr( pPrev = m_Mapper.at( idxPrev )) );
 657             if ( m_Anchor.load( memory_model::memory_order_acquire ) != a )
 658                 return;
 659
 660             anchor_type prevLinks( pPrev->m_Links.load( memory_model::memory_order_acquire ));
 661             if ( index( prevLinks.idxRight ) != idxRight ) {
 662                 if ( m_Anchor.load( memory_model::memory_order_acquire ) != a )
 663                     return;
 664
 665                 if ( !pPrev->m_Links.compare_exchange_strong( prevLinks, anchor_type( prevLinks.idxLeft, idxRight ), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
 666                     return;
 667             }
 668
 669             // clear RPush/LPush flags
 670             m_Anchor.compare_exchange_weak( a, anchor_type(idxLeft, idxRight), memory_model::memory_order_release, memory_model::memory_order_relaxed );
 671         }
 672
 673         //@endcond
 674
 675     protected:
 676         //@cond
 677         struct pop_result {
 678             value_type *                        pPopped;
 679             unsigned int                        nIdxPopped;
 680             typename gc::template GuardArray<2> guards;
 681         };
 682
 683         void dispose_result( pop_result& res )
 684         {
 685             m_Mapper.unmap( res.nIdxPopped );
 686         }
 687
 688         bool do_pop_back( pop_result& res )
 689         {
 690             back_off bkoff;
 691             anchor_type a;
 692
 693             while ( true ) {
 694                 a = m_Anchor.load( memory_model::memory_order_acquire );
 695
 696                 if ( a.idxRight == c_nEmptyIndex ) {
 697                     m_Stat.onPopEmpty();
 698                     return false;
 699                 }
 700
 701                 if ( a.idxLeft == a.idxRight ) {
 702                     if ( m_Anchor.compare_exchange_weak( a, anchor_type( c_nEmptyIndex, c_nEmptyIndex ), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
 703                         break;
 704                     bkoff();
 705                 }
 706                 else if ( status( a ) == Stable ) {
 707                     unsigned int idxLeft  = index( a.idxLeft );
 708                     unsigned int idxRight = index( a.idxRight );
 709                     node_type * pLeft;
 710                     res.guards.assign( 0, node_traits::to_value_ptr( pLeft = m_Mapper.at( idxLeft )) );
 711                     node_type * pRight;
 712                     res.guards.assign( 1, node_traits::to_value_ptr( pRight = m_Mapper.at( idxRight )) );
 713
 714                     if ( m_Anchor.load( memory_model::memory_order_acquire ) != a ) {
 715                         m_Stat.onPopBackContention();
 716                         continue;
 717                     }
 718
 719                     unsigned int nPrev = pRight->m_Links.load( memory_model::memory_order_acquire ).idxLeft;
 720                     if ( m_Anchor.compare_exchange_weak( a, anchor_type( a.idxLeft, nPrev ), memory_model::memory_order_release, memory_model::memory_order_relaxed ) )
 721                         break;
 722                     bkoff();
 723                     m_Stat.onPopBackContention();
 724                 }
 725                 else
 726                     stabilize( a );
 727             }
 728
 729             res.nIdxPopped = a.idxRight;
 730             res.pPopped = node_traits::to_value_ptr( m_Mapper.at( a.idxRight ));
 731
 732             --m_ItemCounter;
 733             m_Stat.onPopBack();
 734
 735             return true;
 736         }
 737
 738         bool do_pop_front( pop_result& res )
 739         {
 740             back_off bkoff;
 741             anchor_type a;
 742
 743             while ( true ) {
 744                 a = m_Anchor.load( memory_model::memory_order_acquire );
 745
 746                 if ( a.idxLeft == c_nEmptyIndex ) {
 747                     m_Stat.onPopEmpty();
 748                     return false;
 749                 }
 750
 751                 if ( a.idxLeft == a.idxRight ) {
 752                     if ( m_Anchor.compare_exchange_weak( a, anchor_type( c_nEmptyIndex, c_nEmptyIndex ), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
 753                         break;
 754                     bkoff();
 755                 }
 756                 else if ( status( a ) == Stable ) {
 757                     unsigned int idxLeft  = index( a.idxLeft );
 758                     unsigned int idxRight = index( a.idxRight );
 759                     node_type * pLeft;
 760                     res.guards.assign( 0, node_traits::to_value_ptr( pLeft = m_Mapper.at( idxLeft )) );
 761                     node_type * pRight;
 762                     res.guards.assign( 1, node_traits::to_value_ptr( pRight = m_Mapper.at( idxRight )) );
 763
 764                     if ( m_Anchor.load( memory_model::memory_order_acquire ) != a ) {
 765                         m_Stat.onPopFrontContention();
 766                         continue;
 767                     }
 768
 769                     unsigned int nPrev = pLeft->m_Links.load( memory_model::memory_order_acquire ).idxRight;
 770                     if ( m_Anchor.compare_exchange_weak( a, anchor_type( nPrev, a.idxRight ), memory_model::memory_order_release, memory_model::memory_order_relaxed ) )
 771                         break;
 772                     bkoff();
 773                     m_Stat.onPopFrontContention();
 774                 }
 775                 else
 776                     stabilize( a );
 777             }
 778
 779             res.nIdxPopped = a.idxLeft;
 780             res.pPopped = node_traits::to_value_ptr( m_Mapper.at( a.idxLeft ));
 781
 782             --m_ItemCounter;
 783             m_Stat.onPopFront();
 784
 785             return true;
 786         }
 787
 788         //@endcond
 789
 790     public:
 791         /// Default constructor
 792         /**
 793             Initializes the deque object with up to <tt>2**16 - 2</tt> items
 794         */
 795         MichaelDeque()
 796             :m_Anchor()
 797             ,m_Mapper( 4096, 4 )
 798         {
 799             m_Anchor.store( anchor_type( c_nEmptyIndex, c_nEmptyIndex ), CDS_ATOMIC::memory_order_release );
 800
 801             // GC and node_type::gc must be the same
 802             static_assert(( std::is_same<gc, typename node_type::gc>::value ), "GC and node_type::gc must be the same");
 803
 804             // cds::gc::HRC is not allowed
 805             static_assert(( !std::is_same<gc, cds::gc::HRC>::value ), "cds::gc::HRC is not allowed here");
 806         }
 807
 808         /// Constructor
 809         /**
 810             Initializes the deque object with estimated item count \p nMaxItemCount.
 811             \p nLoadFactor is a parameter of internal memory mapper based on MichaelHashSet;
 812             see MichaelHashSet ctor for details
 813         */
 814         MichaelDeque( unsigned int nMaxItemCount, unsigned int nLoadFactor = 4 )
 815             :m_Anchor()
 816             ,m_Mapper( nMaxItemCount, nLoadFactor )
 817         {
 818             m_Anchor.store( anchor_type( c_nEmptyIndex, c_nEmptyIndex ), CDS_ATOMIC::memory_order_release );
 819
 820             // GC and node_type::gc must be the same
 821             static_assert(( std::is_same<gc, typename node_type::gc>::value ), "GC and node_type::gc must be the same");
 822
 823             // cds::gc::HRC is not allowed
 824             static_assert(( !std::is_same<gc, cds::gc::HRC>::value ), "cds::gc::HRC is not allowed here");
 825         }
 826
 827         /// Destructor clears the deque
 828         ~MichaelDeque()
 829         {
 830             clear();
 831         }
 832
 833     public:
 834         /// Push back (right) side
 835         /**
 836             Push new item \p val to right side of the deque.
 837         */
 838         bool push_back( value_type& val )
 839         {
 840             back_off bkoff;
 841
 842             node_type * pNode = node_traits::to_node_ptr( val );
 843             link_checker::is_empty( pNode );
 844
 845             unsigned int nIdx = m_Mapper.map( val );
 846             if ( nIdx == c_nEmptyIndex )
 847                 return false;
 848
 849             while ( true ) {
 850                 anchor_type a = m_Anchor.load( memory_model::memory_order_acquire );
 851                 if ( a.idxRight == c_nEmptyIndex ) {
 852                     if ( m_Anchor.compare_exchange_weak( a, anchor_type( nIdx, nIdx ), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
 853                         break;
 854                     bkoff();
 855                     m_Stat.onPushBackContention();
 856                 }
 857                 else if ( status(a) == Stable ) {
 858                     pNode->m_Links.store( anchor_type( a.idxRight, c_nEmptyIndex ), memory_model::memory_order_release );
 859                     anchor_type aNew( a.idxLeft, nIdx | c_nFlagMask );
 860                     if ( m_Anchor.compare_exchange_weak( a, aNew, memory_model::memory_order_release, memory_model::memory_order_relaxed) ) {
 861                         stabilize_back( aNew );
 862                         break;
 863                     }
 864                     bkoff();
 865                     m_Stat.onPushBackContention();
 866                 }
 867                 else
 868                     stabilize( a );
 869             }
 870
 871             ++m_ItemCounter;
 872             m_Stat.onPushBack();
 873             return true;
 874         }
 875
 876         /// Push front (left) side
 877         /**
 878             Push new item \p val to left side of the deque.
 879         */
 880         bool push_front( value_type& val )
 881         {
 882             back_off bkoff;
 883             node_type * pNode = node_traits::to_node_ptr( val );
 884             link_checker::is_empty( pNode );
 885
 886             unsigned int nIdx = m_Mapper.map( val );
 887             if ( nIdx == c_nEmptyIndex )
 888                 return false;
 889
 890             while ( true ) {
 891                 anchor_type a = m_Anchor.load( memory_model::memory_order_acquire );
 892                 if ( a.idxLeft == c_nEmptyIndex ) {
 893                     if ( m_Anchor.compare_exchange_weak( a, anchor_type( nIdx, nIdx ), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
 894                         break;
 895                     bkoff();
 896                     m_Stat.onPushFrontContention();
 897                 }
 898                 else if ( status(a) == Stable ) {
 899                     pNode->m_Links.store( anchor_type( c_nEmptyIndex, a.idxLeft ), memory_model::memory_order_release );
 900                     anchor_type aNew( nIdx | c_nFlagMask, a.idxRight );
 901                     if ( m_Anchor.compare_exchange_weak( a, aNew, memory_model::memory_order_release, memory_model::memory_order_relaxed )) {
 902                         stabilize_front( aNew );
 903                         break;
 904                     }
 905                     bkoff();
 906                     m_Stat.onPushFrontContention();
 907                 }
 908                 else
 909                     stabilize( a );
 910             }
 911
 912             ++m_ItemCounter;
 913             m_Stat.onPushFront();
 914             return true;
 915         }
 916
 917         /// Pop back
 918         /**
 919             Pops rightmost item from the deque. If the deque is empty then returns \p NULL.
 920
 921             For popped object the disposer specified in \p Options template parameters is called.
 922         */
 923         value_type * pop_back()
 924         {
 925             pop_result res;
 926             if ( do_pop_back( res )) {
 927                 dispose_result( res );
 928                 return res.pPopped;
 929             }
 930
 931             return nullptr;
 932         }
 933
 934         /// Pop front
 935         /**
 936             Pops leftmost item from the deque. If the deque is empty then returns \p NULL.
 937
 938             For popped object the disposer specified in \p Options template parameters is called.
 939         */
 940         value_type * pop_front()
 941         {
 942             pop_result res;
 943             if ( do_pop_front( res )) {
 944                 dispose_result( res );
 945                 return res.pPopped;
 946             }
 947
 948             return nullptr;
 949         }
 950
 951         /// Returns deque's item count
 952         /**
 953             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 954             this function always returns 0.
 955
 956             <b>Warning</b>: even if you use real item counter and it returns 0, this fact does not mean that the deque
 957             is empty. To check deque emptyness use \ref empty() method.
 958         */
 959         size_t size() const
 960         {
 961             return m_ItemCounter.value();
 962         }
 963
 964         /// Checks if the dequeue is empty
 965         bool empty() const
 966         {
 967             anchor_type a = m_Anchor.load( memory_model::memory_order_relaxed );
 968             return a.idxLeft == c_nEmptyIndex && a.idxRight == c_nEmptyIndex;
 969         }
 970
 971         /// Clear the deque
 972         /**
 973             The function repeatedly calls \ref pop_back until it returns \p NULL.
 974             The disposer defined in template \p Options is called for each item
 975             that can be safely disposed.
 976         */
 977         void clear()
 978         {
 979             while ( pop_back() != nullptr );
 980         }
 981
 982         /// Returns reference to internal statistics
 983         const stat& statistics() const
 984         {
 985             return m_Stat;
 986         }
 987     };
 988
 989
 990 }}  // namespace cds::intrusive
 991
 992
 993 #endif // #ifndef __CDS_INTRUSIVE_MICHAEL_DEQUE_H