cds/intrusive/michael_list_rcu.h

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