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