cds/intrusive/michael_list_rcu.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_INTRUSIVE_MICHAEL_LIST_RCU_H
   4 #define CDSLIB_INTRUSIVE_MICHAEL_LIST_RCU_H
   5
   6 #include <cds/intrusive/details/michael_list_base.h>
   7 #include <cds/urcu/details/check_deadlock.h>
   8 #include <cds/details/binary_functor_wrapper.h>
   9 #include <cds/details/make_const_type.h>
  10 #include <cds/urcu/exempt_ptr.h>
  11
  12 namespace cds { namespace intrusive {
  13
  14     //@cond
  15     namespace michael_list {
  16
  17         /// Node specialization for uRCU
  18         template <class RCU, typename Tag>
  19         struct node< cds::urcu::gc< RCU >, Tag >
  20         {
  21             typedef cds::urcu::gc< RCU > gc;   ///< Garbage collector
  22             typedef Tag                  tag;  ///< tag
  23
  24             typedef cds::details::marked_ptr<node, 1>   marked_ptr         ;   ///< marked pointer
  25             typedef typename gc::template atomic_marked_ptr< marked_ptr>     atomic_marked_ptr   ;   ///< atomic marked pointer specific for GC
  26
  27             atomic_marked_ptr m_pNext ; ///< pointer to the next node in the container
  28             node *            m_pDelChain; ///< Deleted node chain (local for a thread)
  29
  30             CDS_CONSTEXPR node() CDS_NOEXCEPT
  31                 : m_pNext( nullptr )
  32                 , m_pDelChain( nullptr )
  33             {}
  34         };
  35     } // namespace michael_list
  36     //@endcond
  37
  38     /// Michael's lock-free ordered single-linked list (template specialization for \ref cds_urcu_desc "RCU")
  39     /** @ingroup cds_intrusive_list
  40         \anchor cds_intrusive_MichaelList_rcu
  41
  42         Usually, ordered single-linked list is used as a building block for the hash table implementation.
  43         The complexity of searching is <tt>O(N)</tt>.
  44
  45         Template arguments:
  46         - \p RCU - one of \ref cds_urcu_gc "RCU type"
  47         - \p T - type to be stored in the list; the type \p T should be based on (or has a member of type)
  48             cds::intrusive::micheal_list::node
  49         - \p Traits - type traits. See \p michael_list::traits for explanation. It is possible to declare option-based
  50              list with \p cds::intrusive::michael_list::make_traits metafunction,
  51              see \ref cds_intrusive_MichaelList_hp "here" for explanations.
  52
  53         \par Usage
  54             Before including <tt><cds/intrusive/michael_list_rcu.h></tt> you should include appropriate RCU header file,
  55             see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
  56             For example, for \ref cds_urcu_general_buffered_gc "general-purpose buffered RCU" you should include:
  57             \code
  58             #include <cds/urcu/general_buffered.h>
  59             #include <cds/intrusive/michael_list_rcu.h>
  60
  61             // Now, you can declare Michael's list for type Foo and default traits:
  62             typedef cds::intrusive::MichaelList<cds::urcu::gc< cds::urcu::general_buffered<> >, Foo > rcu_michael_list;
  63             \endcode
  64     */
  65     template < typename RCU, typename T,
  66 #ifdef CDS_DOXYGEN_INVOKED
  67     class Traits = michael_list::traits
  68 #else
  69     class Traits
  70 #endif
  71     >
  72     class MichaelList<cds::urcu::gc<RCU>, T, Traits>
  73     {
  74     public:
  75         typedef T       value_type; ///< type of value stored in the list
  76         typedef Traits  traits;     ///< Traits template parameter
  77
  78         typedef typename traits::hook    hook;      ///< hook type
  79         typedef typename hook::node_type node_type; ///< node type
  80
  81 #   ifdef CDS_DOXYGEN_INVOKED
  82         typedef implementation_defined key_comparator  ;    ///< key comparison functor based on opt::compare and opt::less option setter.
  83 #   else
  84         typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
  85 #   endif
  86
  87         typedef typename traits::disposer  disposer;   ///< disposer used
  88         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ;    ///< node traits
  89         typedef typename michael_list::get_link_checker< node_type, traits::link_checker >::type link_checker;   ///< link checker
  90
  91         typedef cds::urcu::gc<RCU>                     gc;           ///< RCU schema
  92         typedef typename traits::back_off              back_off;     ///< back-off strategy
  93         typedef typename traits::item_counter          item_counter; ///< Item counting policy used
  94         typedef typename traits::memory_model          memory_model; ///< Memory ordering. See cds::opt::memory_model option
  95         typedef typename traits::rcu_check_deadlock    rcu_check_deadlock; ///< Deadlock checking policy
  96
  97         typedef typename gc::scoped_lock    rcu_lock ;  ///< RCU scoped lock
  98         static CDS_CONSTEXPR const bool c_bExtractLockExternal = true; ///< Group of \p extract_xxx functions require external locking
  99
 100         //@cond
 101         // Rebind traits (split-list support)
 102         template <typename... Options>
 103         struct rebind_traits {
 104             typedef MichaelList<
 105                 gc
 106                 , value_type
 107                 , typename cds::opt::make_options< traits, Options...>::type
 108             >   type;
 109         };
 110         //@endcond
 111
 112     protected:
 113         typedef typename node_type::marked_ptr         marked_node_ptr ; ///< Marked node pointer
 114         typedef typename node_type::atomic_marked_ptr  atomic_node_ptr ; ///< Atomic node pointer
 115         typedef atomic_node_ptr                 auxiliary_head      ;   ///< Auxiliary head type (for split-list support)
 116
 117         atomic_node_ptr     m_pHead         ;   ///< Head pointer
 118         item_counter        m_ItemCounter   ;   ///< Item counter
 119
 120         //@cond
 121         /// Position pointer for item search
 122         struct position {
 123             atomic_node_ptr * pPrev ;   ///< Previous node
 124             node_type * pCur        ;   ///< Current node
 125             node_type * pNext       ;   ///< Next node
 126
 127             atomic_node_ptr& refHead;
 128             node_type * pDelChain; ///< Head of deleted node chain
 129
 130             position( atomic_node_ptr& head )
 131                 : refHead( head )
 132                 , pDelChain( nullptr )
 133             {}
 134
 135 #       ifdef _DEBUG
 136             ~position()
 137             {
 138                 assert( pDelChain == nullptr );
 139             }
 140 #       endif
 141         };
 142
 143         enum {
 144             erase_mask   = 1,
 145             extract_mask = 3
 146         };
 147
 148         typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock>   check_deadlock_policy;
 149
 150         static void clear_links( node_type * pNode )
 151         {
 152             pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 153             pNode->m_pDelChain = nullptr;
 154         }
 155
 156         struct clear_and_dispose {
 157             void operator()( value_type * p )
 158             {
 159                 assert( p != nullptr );
 160                 clear_links( node_traits::to_node_ptr(p));
 161                 disposer()( p );
 162             }
 163         };
 164         //@endcond
 165
 166     public:
 167         using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void >; ///< pointer to extracted node
 168
 169     protected:
 170         //@cond
 171
 172         static void dispose_node( node_type * pNode )
 173         {
 174             assert( pNode );
 175             assert( !gc::is_locked() );
 176
 177             gc::template retire_ptr<clear_and_dispose>( node_traits::to_value_ptr( *pNode ) );
 178         }
 179
 180         bool link_node( node_type * pNode, position& pos )
 181         {
 182             assert( pNode != nullptr );
 183             link_checker::is_empty( pNode );
 184
 185             marked_node_ptr p( pos.pCur );
 186             pNode->m_pNext.store( p, memory_model::memory_order_release );
 187             return pos.pPrev->compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed );
 188         }
 189
 190         static void link_to_remove_chain( position& pos, node_type * pDel )
 191         {
 192             assert( pDel->m_pDelChain == nullptr );
 193
 194             pDel->m_pDelChain = pos.pDelChain;
 195             pos.pDelChain = pDel;
 196         }
 197
 198         static void free_node_chain( position& pos )
 199         {
 200             assert( !gc::is_locked() );
 201
 202             node_type * p = pos.pDelChain;
 203             if ( p ) {
 204                 pos.pDelChain = nullptr;
 205                 while ( p ) {
 206                     node_type * pNext = p->m_pDelChain;
 207                     dispose_node( p );
 208                     p = pNext;
 209                 }
 210             }
 211         }
 212
 213         bool unlink_node( position& pos, bool bExtract )
 214         {
 215             // Mark the node (logical deletion)
 216             marked_node_ptr next(pos.pNext, 0);
 217
 218             int const nMask = bExtract ? extract_mask : erase_mask;
 219             if ( pos.pCur->m_pNext.compare_exchange_strong( next, next | nMask, memory_model::memory_order_acq_rel, atomics::memory_order_relaxed )) {
 220
 221                 // Try physical removal
 222                 marked_node_ptr cur(pos.pCur);
 223                 if ( pos.pPrev->compare_exchange_strong(cur, marked_node_ptr(pos.pNext), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
 224                     if ( !bExtract )
 225                         link_to_remove_chain( pos, pos.pCur );
 226                 }
 227                 else {
 228                     search( pos.refHead, *node_traits::to_value_ptr( pos.pCur ), pos, key_comparator() );
 229                 }
 230                 return true;
 231             }
 232             return false;
 233         }
 234         //@endcond
 235
 236     protected:
 237         //@cond
 238         template <bool IsConst>
 239         class iterator_type
 240         {
 241             friend class MichaelList;
 242             value_type * m_pNode;
 243
 244             void next()
 245             {
 246                 if ( m_pNode ) {
 247                     node_type * p = node_traits::to_node_ptr( *m_pNode )->m_pNext.load(memory_model::memory_order_relaxed).ptr();
 248                     m_pNode = p ? node_traits::to_value_ptr( p ) : nullptr;
 249                 }
 250             }
 251
 252         protected:
 253             explicit iterator_type( node_type * pNode)
 254             {
 255                 if ( pNode )
 256                     m_pNode = node_traits::to_value_ptr( *pNode );
 257                 else
 258                     m_pNode = nullptr;
 259             }
 260             explicit iterator_type( atomic_node_ptr const& refNode)
 261             {
 262                 node_type * pNode = refNode.load(memory_model::memory_order_relaxed).ptr();
 263                 m_pNode = pNode ? node_traits::to_value_ptr( *pNode ) : nullptr;
 264             }
 265
 266         public:
 267             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 268             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 269
 270             iterator_type()
 271                 : m_pNode( nullptr )
 272             {}
 273
 274             iterator_type( const iterator_type& src )
 275                 : m_pNode( src.m_pNode )
 276             {}
 277
 278             value_ptr operator ->() const
 279             {
 280                 return m_pNode;
 281             }
 282
 283             value_ref operator *() const
 284             {
 285                 assert( m_pNode != nullptr );
 286                 return *m_pNode;
 287             }
 288
 289             /// Pre-increment
 290             iterator_type& operator ++()
 291             {
 292                 next();
 293                 return *this;
 294             }
 295
 296             /// Post-increment
 297             iterator_type operator ++(int)
 298             {
 299                 iterator_type i(*this);
 300                 next();
 301                 return i;
 302             }
 303
 304             iterator_type& operator = (const iterator_type& src)
 305             {
 306                 m_pNode = src.m_pNode;
 307                 return *this;
 308             }
 309
 310             template <bool C>
 311             bool operator ==(iterator_type<C> const& i ) const
 312             {
 313                 return m_pNode == i.m_pNode;
 314             }
 315             template <bool C>
 316             bool operator !=(iterator_type<C> const& i ) const
 317             {
 318                 return m_pNode != i.m_pNode;
 319             }
 320         };
 321         //@endcond
 322
 323     public:
 324         /// Forward iterator
 325         typedef iterator_type<false>    iterator;
 326         /// Const forward iterator
 327         typedef iterator_type<true>     const_iterator;
 328
 329         /// Returns a forward iterator addressing the first element in a list
 330         /**
 331             For empty list \code begin() == end() \endcode
 332         */
 333         iterator begin()
 334         {
 335             return iterator( m_pHead );
 336         }
 337
 338         /// Returns an iterator that addresses the location succeeding the last element in a list
 339         /**
 340             Do not use the value returned by <tt>end</tt> function to access any item.
 341             Internally, <tt>end</tt> returning value equals to \p nullptr.
 342
 343             The returned value can be used only to control reaching the end of the list.
 344             For empty list \code begin() == end() \endcode
 345         */
 346         iterator end()
 347         {
 348             return iterator();
 349         }
 350
 351         /// Returns a forward const iterator addressing the first element in a list
 352         const_iterator begin() const
 353         {
 354             return const_iterator(m_pHead );
 355         }
 356         /// Returns a forward const iterator addressing the first element in a list
 357         const_iterator cbegin() const
 358         {
 359             return const_iterator(m_pHead );
 360         }
 361
 362         /// Returns an const iterator that addresses the location succeeding the last element in a list
 363         const_iterator end() const
 364         {
 365             return const_iterator();
 366         }
 367         /// Returns an const iterator that addresses the location succeeding the last element in a list
 368         const_iterator cend() const
 369         {
 370             return const_iterator();
 371         }
 372
 373     public:
 374         /// Default constructor initializes empty list
 375         MichaelList()
 376             : m_pHead( nullptr )
 377         {
 378             static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
 379         }
 380
 381         /// Destroy list
 382         ~MichaelList()
 383         {
 384             clear();
 385         }
 386
 387         /// Inserts new node
 388         /**
 389             The function inserts \p val in the list if the list does not contain
 390             an item with key equal to \p val.
 391
 392             The function makes RCU lock internally.
 393
 394             Returns \p true if \p val is linked into the list, \p false otherwise.
 395         */
 396         bool insert( value_type& val )
 397         {
 398             return insert_at( m_pHead, val );
 399         }
 400
 401         /// Inserts new node
 402         /**
 403             This function is intended for derived non-intrusive containers.
 404
 405             The function allows to split new item creating into two part:
 406             - create item with key only
 407             - insert new item into the list
 408             - if inserting is success, calls \p f functor to initialize value-field of \p val.
 409
 410             The functor signature is:
 411             \code
 412                 void func( value_type& val );
 413             \endcode
 414             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
 415             \p val no any other changes could be made on this list's item by concurrent threads.
 416             The user-defined functor is called only if the inserting is success.
 417
 418             The function makes RCU lock internally.
 419
 420             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
 421         */
 422         template <typename Func>
 423         bool insert( value_type& val, Func f )
 424         {
 425             return insert_at( m_pHead, val, f );
 426         }
 427
 428         /// Ensures that the \p item exists in the list
 429         /**
 430             The operation performs inserting or changing data with lock-free manner.
 431
 432             If the item \p val not found in the list, then \p val is inserted into the list.
 433             Otherwise, the functor \p func is called with item found.
 434             The functor signature is:
 435             \code
 436             struct functor {
 437                 void operator()( bool bNew, value_type& item, value_type& val );
 438             };
 439             \endcode
 440             with arguments:
 441             - \p bNew - \p true if the item has been inserted, \p false otherwise
 442             - \p item - item of the list
 443             - \p val - argument \p val passed into the \p ensure function
 444             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 445             refer to the same thing.
 446
 447             The functor may change non-key fields of the \p item; however, \p func must guarantee
 448             that during changing no any other modifications could be made on this item by concurrent threads.
 449
 450             Returns <tt> std::pair<bool, bool>  </tt> where \p first is true if operation is successfull,
 451             \p second is true if new item has been added or \p false if the item with \p key
 452             already is in the list.
 453
 454             The function makes RCU lock internally.
 455
 456             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
 457         */
 458         template <typename Func>
 459         std::pair<bool, bool> ensure( value_type& val, Func func )
 460         {
 461             return ensure_at( m_pHead, val, func );
 462         }
 463
 464         /// Unlinks the item \p val from the list
 465         /**
 466             The function searches the item \p val in the list and unlink it from the list
 467             if it is found and it is equal to \p val.
 468
 469             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 470             and deletes the item found. \p unlink finds an item by key and deletes it
 471             only if \p val is an item of that list, i.e. the pointer to the item found
 472             is equal to <tt> &val </tt>.
 473
 474             The function returns \p true if success and \p false otherwise.
 475
 476             RCU \p synchronize method can be called.
 477             Note that depending on RCU type used the \ref disposer call can be deferred.
 478
 479             The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
 480             deadlock checking policy is opt::v::rcu_throw_deadlock.
 481         */
 482         bool unlink( value_type& val )
 483         {
 484             return unlink_at( m_pHead, val );
 485         }
 486
 487         /// Deletes the item from the list
 488         /** \anchor cds_intrusive_MichaelList_rcu_erase_val
 489             The function searches an item with key equal to \p key in the list,
 490             unlinks it from the list, and returns \p true.
 491             If the item with the key equal to \p key is not found the function return \p false.
 492
 493             RCU \p synchronize method can be called.
 494             Note that depending on RCU type used the \ref disposer call can be deferred.
 495
 496             The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
 497             the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
 498         */
 499         template <typename Q>
 500         bool erase( Q const& key )
 501         {
 502             return erase_at( m_pHead, key, key_comparator() );
 503         }
 504
 505         /// Deletes the item from the list using \p pred predicate for searching
 506         /**
 507             The function is an analog of \ref cds_intrusive_MichaelList_rcu_erase_val "erase(Q const&)"
 508             but \p pred is used for key comparing.
 509             \p Less functor has the interface like \p std::less.
 510             \p pred must imply the same element order as the comparator used for building the list.
 511         */
 512         template <typename Q, typename Less>
 513         bool erase_with( Q const& key, Less pred )
 514         {
 515             CDS_UNUSED( pred );
 516             return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
 517         }
 518
 519         /// Deletes the item from the list
 520         /** \anchor cds_intrusive_MichaelList_rcu_erase_func
 521             The function searches an item with key equal to \p key in the list,
 522             call \p func functor with item found, unlinks it from the list, and returns \p true.
 523             The \p Func interface is
 524             \code
 525             struct functor {
 526                 void operator()( value_type const& item );
 527             };
 528             \endcode
 529
 530             If the item with the key equal to \p key is not found the function return \p false.
 531
 532             RCU \p synchronize method can be called.
 533             Note that depending on RCU type used the \ref disposer call can be deferred.
 534
 535             The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
 536             the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
 537         */
 538         template <typename Q, typename Func>
 539         bool erase( Q const& key, Func func )
 540         {
 541             return erase_at( m_pHead, key, key_comparator(), func );
 542         }
 543
 544         /// Deletes the item from the list using \p pred predicate for searching
 545         /**
 546             The function is an analog of \ref cds_intrusive_MichaelList_rcu_erase_func "erase(Q const&, Func)"
 547             but \p pred is used for key comparing.
 548             \p Less functor has the interface like \p std::less.
 549             \p pred must imply the same element order as the comparator used for building the list.
 550         */
 551         template <typename Q, typename Less, typename Func>
 552         bool erase_with( Q const& key, Less pred, Func func )
 553         {
 554             CDS_UNUSED( pred );
 555             return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), func );
 556         }
 557
 558         /// Extracts an item from the list
 559         /**
 560         @anchor cds_intrusive_MichaelList_rcu_extract
 561             The function searches an item with key equal to \p key in the list,
 562             unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
 563             If \p key is not found the function returns an empty \p exempt_ptr.
 564
 565             @note The function does NOT call RCU read-side lock or synchronization,
 566             and does NOT dispose the item found. It just unlinks the item from the list
 567             and returns a pointer to item found.
 568             You should lock RCU before calling this function, and you should manually release
 569             \p dest exempt pointer outside the RCU lock before reusing the pointer.
 570
 571             \code
 572             #include <cds/urcu/general_buffered.h>
 573             #include <cds/intrusive/michael_list_rcu.h>
 574
 575             typedef cds::urcu::gc< general_buffered<> > rcu;
 576             typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
 577
 578             rcu_michael_list theList;
 579             // ...
 580
 581             rcu_michael_list::exempt_ptr p1;
 582             {
 583                 // first, we should lock RCU
 584                 rcu::scoped_lock sl;
 585
 586                 // Now, you can apply extract function
 587                 // Note that you must not delete the item found inside the RCU lock
 588                 p1 = theList.extract( 10 )
 589                 if ( p1 ) {
 590                     // do something with p1
 591                     ...
 592                 }
 593             }
 594
 595             // We may safely release p1 here
 596             // release() passes the pointer to RCU reclamation cycle:
 597             // it invokes RCU retire_ptr function with the disposer you provided for the list.
 598             p1.release();
 599             \endcode
 600         */
 601         template <typename Q>
 602         exempt_ptr extract( Q const& key )
 603         {
 604             return exempt_ptr( extract_at( m_pHead, key, key_comparator() ));
 605         }
 606
 607         /// Extracts an item from the list using \p pred predicate for searching
 608         /**
 609             This function is the analog for \p extract(Q const&)
 610
 611             The \p pred is a predicate used for key comparing.
 612             \p Less has the interface like \p std::less.
 613             \p pred must imply the same element order as \ref key_comparator.
 614         */
 615         template <typename Q, typename Less>
 616         exempt_ptr extract_with( Q const& key, Less pred )
 617         {
 618             CDS_UNUSED( pred );
 619             return exempt_ptr( extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() ));
 620         }
 621
 622         /// Find the key \p val
 623         /** \anchor cds_intrusive_MichaelList_rcu_find_func
 624             The function searches the item with key equal to \p key
 625             and calls the functor \p f for item found.
 626             The interface of \p Func functor is:
 627             \code
 628             struct functor {
 629                 void operator()( value_type& item, Q& key );
 630             };
 631             \endcode
 632             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 633
 634             The functor can change non-key fields of \p item.
 635             The function \p find does not serialize simultaneous access to the list \p item. If such access is
 636             possible you must provide your own synchronization schema to exclude unsafe item modifications.
 637
 638             The function makes RCU lock internally.
 639
 640             The function returns \p true if \p val is found, \p false otherwise.
 641         */
 642         template <typename Q, typename Func>
 643         bool find( Q& key, Func f ) const
 644         {
 645             return find_at( const_cast<atomic_node_ptr&>(m_pHead), key, key_comparator(), f );
 646         }
 647         //@cond
 648         template <typename Q, typename Func>
 649         bool find( Q const& key, Func f ) const
 650         {
 651             return find_at( const_cast<atomic_node_ptr&>(m_pHead), key, key_comparator(), f );
 652         }
 653         //@endcond
 654
 655         /// Finds \p key using \p pred predicate for searching
 656         /**
 657             The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_func "find(Q&, Func)"
 658             but \p pred is used for key comparing.
 659             \p Less functor has the interface like \p std::less.
 660             \p pred must imply the same element order as the comparator used for building the list.
 661         */
 662         template <typename Q, typename Less, typename Func>
 663         bool find_with( Q& key, Less pred, Func f ) const
 664         {
 665             CDS_UNUSED( pred );
 666             return find_at( const_cast<atomic_node_ptr&>( m_pHead ), key, cds::opt::details::make_comparator_from_less<Less>(), f );
 667         }
 668         //@cond
 669         template <typename Q, typename Less, typename Func>
 670         bool find_with( Q const& key, Less pred, Func f ) const
 671         {
 672             CDS_UNUSED( pred );
 673             return find_at( const_cast<atomic_node_ptr&>(m_pHead), key, cds::opt::details::make_comparator_from_less<Less>(), f );
 674         }
 675         //@endcond
 676
 677         /// Finds \p key
 678         /** \anchor cds_intrusive_MichaelList_rcu_find_val
 679             The function searches the item with key equal to \p key
 680             and returns \p true if \p val found or \p false otherwise.
 681         */
 682         template <typename Q>
 683         bool find( Q const& key ) const
 684         {
 685             return find_at( const_cast<atomic_node_ptr&>( m_pHead ), key, key_comparator() );
 686         }
 687
 688         /// Finds \p key using \p pred predicate for searching
 689         /**
 690             The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_val "find(Q const&)"
 691             but \p pred is used for key comparing.
 692             \p Less functor has the interface like \p std::less.
 693             \p pred must imply the same element order as the comparator used for building the list.
 694         */
 695         template <typename Q, typename Less>
 696         bool find_with( Q const& key, Less pred ) const
 697         {
 698             CDS_UNUSED( pred );
 699             return find_at( const_cast<atomic_node_ptr&>( m_pHead ), key, cds::opt::details::make_comparator_from_less<Less>() );
 700         }
 701
 702         /// Finds \p key and return the item found
 703         /** \anchor cds_intrusive_MichaelList_rcu_get
 704             The function searches the item with key equal to \p key and returns the pointer to item found.
 705             If \p key is not found it returns \p nullptr.
 706
 707             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 708
 709             RCU should be locked before call of this function.
 710             Returned item is valid only while RCU is locked:
 711             \code
 712             typedef cds::intrusive::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
 713             ord_list theList;
 714             // ...
 715             {
 716                 // Lock RCU
 717                 ord_list::rcu_lock lock;
 718
 719                 foo * pVal = theList.get( 5 );
 720                 if ( pVal ) {
 721                     // Deal with pVal
 722                     //...
 723                 }
 724                 // Unlock RCU by rcu_lock destructor
 725                 // pVal can be retired by disposer at any time after RCU has been unlocked
 726             }
 727             \endcode
 728         */
 729         template <typename Q>
 730         value_type * get( Q const& key ) const
 731         {
 732             return get_at( const_cast<atomic_node_ptr&>( m_pHead ), key, key_comparator());
 733         }
 734
 735         /// Finds \p key and return the item found
 736         /**
 737             The function is an analog of \ref cds_intrusive_MichaelList_rcu_get "get(Q const&)"
 738             but \p pred is used for comparing the keys.
 739
 740             \p Less functor has the semantics like \p std::less but should take arguments of type \p value_type and \p Q
 741             in any order.
 742             \p pred must imply the same element order as the comparator used for building the list.
 743         */
 744         template <typename Q, typename Less>
 745         value_type * get_with( Q const& key, Less pred ) const
 746         {
 747             CDS_UNUSED( pred );
 748             return get_at( const_cast<atomic_node_ptr&>( m_pHead ), key, cds::opt::details::make_comparator_from_less<Less>());
 749         }
 750
 751         /// Clears the list using default disposer
 752         /**
 753             The function clears the list using default (provided by \p Traits class template argument) disposer functor.
 754
 755             RCU \p synchronize method can be called.
 756             Note that depending on RCU type used the \ref disposer invocation can be deferred.
 757
 758             The function can throw \p cds::urcu::rcu_deadlock exception if an deadlock is encountered and
 759             deadlock checking policy is \p opt::v::rcu_throw_deadlock.
 760         */
 761         void clear()
 762         {
 763             if( !empty() ) {
 764                 check_deadlock_policy::check();
 765
 766                 marked_node_ptr pHead;
 767                 for (;;) {
 768                     {
 769                         rcu_lock l;
 770                         pHead = m_pHead.load(memory_model::memory_order_acquire);
 771                         if ( !pHead.ptr() )
 772                             break;
 773                         marked_node_ptr pNext( pHead->m_pNext.load(memory_model::memory_order_relaxed) );
 774                         if ( !pHead->m_pNext.compare_exchange_weak( pNext, pNext | 1, memory_model::memory_order_acquire, memory_model::memory_order_relaxed ))
 775                             continue;
 776                         if ( !m_pHead.compare_exchange_weak( pHead, marked_node_ptr(pNext.ptr()), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
 777                             continue;
 778                     }
 779
 780                     --m_ItemCounter;
 781                     dispose_node( pHead.ptr() );
 782                 }
 783             }
 784         }
 785
 786         /// Check if the list is empty
 787         bool empty() const
 788         {
 789             return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
 790         }
 791
 792         /// Returns list's item count
 793         /**
 794             The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
 795             this function always returns 0.
 796
 797             @note Even if you use real item counter and it returns 0, this fact does not mean that the list
 798             is empty. To check list emptyness use \p empty() method.
 799         */
 800         size_t size() const
 801         {
 802             return m_ItemCounter.value();
 803         }
 804
 805     protected:
 806         //@cond
 807         // split-list support
 808         bool insert_aux_node( node_type * pNode )
 809         {
 810             return insert_aux_node( m_pHead, pNode );
 811         }
 812
 813         // split-list support
 814         bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
 815         {
 816             assert( pNode != nullptr );
 817
 818             // Hack: convert node_type to value_type.
 819             // In principle, auxiliary node can be non-reducible to value_type
 820             // We assume that comparator can correctly distinguish between aux and regular node.
 821             return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
 822         }
 823
 824         bool insert_at( atomic_node_ptr& refHead, value_type& val )
 825         {
 826             rcu_lock l;
 827             return insert_at_locked( refHead, val );
 828         }
 829
 830         bool insert_at_locked( atomic_node_ptr& refHead, value_type& val )
 831         {
 832             // RCU lock should be locked!!!
 833             assert( gc::is_locked() );
 834
 835             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 836             position pos( refHead );
 837
 838             while ( true ) {
 839                 if ( search( refHead, val, pos, key_comparator() ) )
 840                     return false;
 841
 842                 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
 843                     ++m_ItemCounter;
 844                     return true;
 845                 }
 846
 847                 // clear next field
 848                 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 849             }
 850         }
 851
 852         template <typename Func>
 853         bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
 854         {
 855             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 856             position pos( refHead );
 857
 858             rcu_lock l;
 859             while ( true ) {
 860                 if ( search( refHead, val, pos, key_comparator() ) )
 861                     return false;
 862
 863                 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
 864                     f( val );
 865                     ++m_ItemCounter;
 866                     return true;
 867                 }
 868
 869                 // clear next field
 870                 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 871             }
 872         }
 873
 874         iterator insert_at_( atomic_node_ptr& refHead, value_type& val )
 875         {
 876             rcu_lock l;
 877             if ( insert_at_locked( refHead, val ))
 878                 return iterator( node_traits::to_node_ptr( val ));
 879             return end();
 880         }
 881
 882         template <typename Func>
 883         std::pair<iterator, bool> ensure_at_( atomic_node_ptr& refHead, value_type& val, Func func )
 884         {
 885             rcu_lock l;
 886             return ensure_at_locked( refHead, val, func );
 887         }
 888
 889         template <typename Func>
 890         std::pair<iterator, bool> ensure_at_locked( atomic_node_ptr& refHead, value_type& val, Func func )
 891         {
 892             position pos( refHead );
 893
 894             // RCU lock should be locked!!!
 895             assert( gc::is_locked() );
 896
 897             while ( true ) {
 898                 if ( search( refHead, val, pos, key_comparator() ) ) {
 899                     assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
 900
 901                     func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
 902                     return std::make_pair( iterator( pos.pCur ), false );
 903                 }
 904                 else {
 905                     link_checker::is_empty( node_traits::to_node_ptr( val ) );
 906
 907                     if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
 908                         ++m_ItemCounter;
 909                         func( true, val , val );
 910                         return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
 911                     }
 912
 913                     // clear the next field
 914                     node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 915                 }
 916             }
 917         }
 918
 919         template <typename Func>
 920         std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func )
 921         {
 922             rcu_lock l;
 923             std::pair<iterator, bool> ret = ensure_at_locked( refHead, val, func );
 924             return std::make_pair( ret.first != end(), ret.second );
 925         }
 926
 927         bool unlink_at( atomic_node_ptr& refHead, value_type& val )
 928         {
 929             position pos( refHead );
 930             back_off bkoff;
 931             check_deadlock_policy::check();
 932
 933             for (;;) {
 934                 {
 935                     rcu_lock l;
 936                     if ( !search( refHead, val, pos, key_comparator() ) || node_traits::to_value_ptr( *pos.pCur ) != &val )
 937                         return false;
 938                     if ( !unlink_node( pos, false )) {
 939                         bkoff();
 940                         continue;
 941                     }
 942                 }
 943
 944                 --m_ItemCounter;
 945                 free_node_chain( pos );
 946                 return true;
 947             }
 948         }
 949
 950         template <typename Q, typename Compare, typename Func>
 951         bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f, position& pos )
 952         {
 953             back_off bkoff;
 954             check_deadlock_policy::check();
 955
 956             for (;;) {
 957                 {
 958                     rcu_lock l;
 959                     if ( !search( refHead, val, pos, cmp ) )
 960                         return false;
 961                     if ( !unlink_node( pos, false )) {
 962                         bkoff();
 963                         continue;
 964                     }
 965                 }
 966
 967                 f( *node_traits::to_value_ptr( *pos.pCur ) );
 968                 --m_ItemCounter;
 969                 free_node_chain( pos );
 970                 return true;
 971             }
 972         }
 973
 974         template <typename Q, typename Compare, typename Func>
 975         bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f )
 976         {
 977             position pos( refHead );
 978             return erase_at( refHead, val, cmp, f, pos );
 979         }
 980
 981         template <typename Q, typename Compare>
 982         bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp )
 983         {
 984             position pos( refHead );
 985             return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
 986         }
 987
 988         template <typename Q, typename Compare >
 989         value_type * extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
 990         {
 991             position pos( refHead );
 992             back_off bkoff;
 993             assert( gc::is_locked() )  ;   // RCU must be locked!!!
 994
 995             for (;;) {
 996                 if ( !search( refHead, val, pos, cmp ) )
 997                     return nullptr;
 998                 if ( !unlink_node( pos, true )) {
 999                     bkoff();
1000                     continue;
1001                 }
1002
1003                 --m_ItemCounter;
1004                 return node_traits::to_value_ptr( pos.pCur );
1005             }
1006         }
1007
1008         template <typename Q, typename Compare, typename Func>
1009         bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f ) const
1010         {
1011             position pos( refHead );
1012
1013             rcu_lock l;
1014             if ( search( refHead, val, pos, cmp ) ) {
1015                 assert( pos.pCur != nullptr );
1016                 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1017                 return true;
1018             }
1019             return false;
1020         }
1021
1022         template <typename Q, typename Compare>
1023         bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp ) const
1024         {
1025             rcu_lock l;
1026             return find_at_( refHead, val, cmp ) != end();
1027         }
1028
1029         template <typename Q, typename Compare>
1030         value_type * get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp ) const
1031         {
1032             value_type * pFound = nullptr;
1033             return find_at( refHead, val, cmp,
1034                 [&pFound](value_type& found, Q const& ) { pFound = &found; } )
1035                 ? pFound : nullptr;
1036         }
1037
1038         template <typename Q, typename Compare>
1039         const_iterator find_at_( atomic_node_ptr& refHead, Q const& val, Compare cmp ) const
1040         {
1041             assert( gc::is_locked() );
1042             position pos( refHead );
1043
1044             if ( search( refHead, val, pos, cmp ) ) {
1045                 assert( pos.pCur != nullptr );
1046                 return const_iterator( pos.pCur );
1047             }
1048             return end();
1049         }
1050
1051         //@endcond
1052
1053     protected:
1054
1055         //@cond
1056         template <typename Q, typename Compare>
1057         bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1058         {
1059             // RCU lock should be locked!!!
1060             assert( gc::is_locked() );
1061
1062             atomic_node_ptr * pPrev;
1063             marked_node_ptr pNext;
1064             marked_node_ptr pCur;
1065
1066             back_off        bkoff;
1067
1068         try_again:
1069             pPrev = &refHead;
1070             pCur = pPrev->load(memory_model::memory_order_acquire);
1071             pNext = nullptr;
1072
1073             while ( true ) {
1074                 if ( !pCur.ptr() ) {
1075                     pos.pPrev = pPrev;
1076                     pos.pCur = nullptr;
1077                     pos.pNext = nullptr;
1078                     return false;
1079                 }
1080
1081                 pNext = pCur->m_pNext.load(memory_model::memory_order_acquire);
1082
1083                 if ( pPrev->load(memory_model::memory_order_relaxed) != pCur
1084                     || pNext != pCur->m_pNext.load(memory_model::memory_order_relaxed))
1085                 {
1086                     bkoff();
1087                     goto try_again;
1088                 }
1089
1090                 if ( pNext.bits() ) {
1091                     // pCur is marked as deleted. Try to unlink it from the list
1092                     if ( pPrev->compare_exchange_weak( pCur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1093                         if ( pNext.bits() == erase_mask )
1094                             link_to_remove_chain( pos, pCur.ptr() );
1095                     }
1096
1097                     goto try_again;
1098                 }
1099
1100                 assert( pCur.ptr() != nullptr );
1101                 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1102                 if ( nCmp >= 0 ) {
1103                     pos.pPrev = pPrev;
1104                     pos.pCur = pCur.ptr();
1105                     pos.pNext = pNext.ptr();
1106                     return nCmp == 0;
1107                 }
1108                 pPrev = &( pCur->m_pNext );
1109                 pCur = pNext;
1110             }
1111         }
1112         //@endcond
1113     };
1114
1115 }}  // namespace cds::intrusive
1116
1117 #endif  // #ifndef CDSLIB_INTRUSIVE_MICHAEL_LIST_NOGC_H