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