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