cds/intrusive/michael_list_rcu.h

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