cds/intrusive/michael_list_rcu.h

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