cds/intrusive/michael_list_rcu.h

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