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             @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             return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
 440         }
 441
 442         /// Deletes the item from the list
 443         /** \anchor cds_intrusive_MichaelList_rcu_erase_func
 444             The function searches an item with key equal to \p key in the list,
 445             call \p func functor with item found, unlinks it from the list, and returns \p true.
 446             The \p Func interface is
 447             \code
 448             struct functor {
 449                 void operator()( value_type const& item );
 450             };
 451             \endcode
 452
 453             If the item with the key equal to \p key is not found the function return \p false.
 454
 455             RCU \p synchronize method can be called.
 456             Note that depending on RCU type used the \ref disposer call can be deferred.
 457
 458             The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
 459             the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
 460         */
 461         template <typename Q, typename Func>
 462         bool erase( Q const& key, Func func )
 463         {
 464             return erase_at( m_pHead, key, key_comparator(), func );
 465         }
 466
 467         /// Deletes the item from the list using \p pred predicate for searching
 468         /**
 469             The function is an analog of \ref cds_intrusive_MichaelList_rcu_erase_func "erase(Q const&, Func)"
 470             but \p pred is used for key comparing.
 471             \p Less functor has the interface like \p std::less.
 472             \p pred must imply the same element order as the comparator used for building the list.
 473         */
 474         template <typename Q, typename Less, typename Func>
 475         bool erase_with( Q const& key, Less pred, Func func )
 476         {
 477             return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), func );
 478         }
 479
 480         /// Extracts an item from the list
 481         /**
 482         @anchor cds_intrusive_MichaelList_rcu_extract
 483             The function searches an item with key equal to \p key in the list,
 484             unlinks it from the list, and returns pointer to an item found in \p dest parameter.
 485             If \p key is not found the function returns \p false, \p dest is empty.
 486
 487             @note The function does NOT call RCU read-side lock or synchronization,
 488             and does NOT dispose the item found. It just unlinks the item from the list
 489             and returns a pointer to item found.
 490             You should lock RCU before calling this function, and you should manually release
 491             \p dest exempt pointer outside the RCU lock before reusing the pointer.
 492
 493             \code
 494             #include <cds/urcu/general_buffered.h>
 495             #include <cds/intrusive/michael_list_rcu.h>
 496
 497             typedef cds::urcu::gc< general_buffered<> > rcu;
 498             typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
 499
 500             rcu_michael_list theList;
 501             // ...
 502
 503             rcu_michael_list::exempt_ptr p1;
 504             {
 505                 // first, we should lock RCU
 506                 rcu::scoped_lock sl;
 507
 508                 // Now, you can apply extract function
 509                 // Note that you must not delete the item found inside the RCU lock
 510                 if ( theList.extract( p1, 10 )) {
 511                     // do something with p1
 512                     ...
 513                 }
 514             }
 515
 516             // We may safely release p1 here
 517             // release() passes the pointer to RCU reclamation cycle:
 518             // it invokes RCU retire_ptr function with the disposer you provided for the list.
 519             p1.release();
 520             \endcode
 521         */
 522         template <typename Q>
 523         bool extract( exempt_ptr& dest, Q const& key )
 524         {
 525             dest = extract_at( m_pHead, key, key_comparator() );
 526             return !dest.empty();
 527         }
 528
 529         /// Extracts an item from the list using \p pred predicate for searching
 530         /**
 531             This function is the analog for \ref cds_intrusive_MichaelList_rcu_extract "extract(exempt_ptr&, Q const&)".
 532
 533             The \p pred is a predicate used for key comparing.
 534             \p Less has the interface like \p std::less.
 535             \p pred must imply the same element order as \ref key_comparator.
 536         */
 537         template <typename Q, typename Less>
 538         bool extract_with( exempt_ptr& dest, Q const& key, Less pred )
 539         {
 540             dest = extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
 541             return !dest.empty();
 542         }
 543
 544         /// Find the key \p val
 545         /** \anchor cds_intrusive_MichaelList_rcu_find_func
 546             The function searches the item with key equal to \p key
 547             and calls the functor \p f for item found.
 548             The interface of \p Func functor is:
 549             \code
 550             struct functor {
 551                 void operator()( value_type& item, Q& key );
 552             };
 553             \endcode
 554             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 555
 556             The functor can change non-key fields of \p item.
 557             The function \p find does not serialize simultaneous access to the list \p item. If such access is
 558             possible you must provide your own synchronization schema to exclude unsafe item modifications.
 559
 560             The function makes RCU lock internally.
 561
 562             The function returns \p true if \p val is found, \p false otherwise.
 563         */
 564         template <typename Q, typename Func>
 565         bool find( Q& key, Func f ) const
 566         {
 567             return find_at( const_cast<atomic_node_ptr&>(m_pHead), key, key_comparator(), f );
 568         }
 569
 570         /// Finds \p key using \p pred predicate for searching
 571         /**
 572             The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_func "find(Q&, Func)"
 573             but \p pred is used for key comparing.
 574             \p Less functor has the interface like \p std::less.
 575             \p pred must imply the same element order as the comparator used for building the list.
 576         */
 577         template <typename Q, typename Less, typename Func>
 578         bool find_with( Q& key, Less pred, Func f ) const
 579         {
 580             return find_at( const_cast<atomic_node_ptr&>( m_pHead ), key, cds::opt::details::make_comparator_from_less<Less>(), f );
 581         }
 582
 583         /// Finds \p key
 584         /** \anchor cds_intrusive_MichaelList_rcu_find_val
 585             The function searches the item with key equal to \p key
 586             and returns \p true if \p val found or \p false otherwise.
 587         */
 588         template <typename Q>
 589         bool find( Q const& key ) const
 590         {
 591             return find_at( const_cast<atomic_node_ptr&>( m_pHead ), key, key_comparator() );
 592         }
 593
 594         /// Finds \p key using \p pred predicate for searching
 595         /**
 596             The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_val "find(Q const&)"
 597             but \p pred is used for key comparing.
 598             \p Less functor has the interface like \p std::less.
 599             \p pred must imply the same element order as the comparator used for building the list.
 600         */
 601         template <typename Q, typename Less>
 602         bool find_with( Q const& key, Less pred ) const
 603         {
 604             return find_at( const_cast<atomic_node_ptr&>( m_pHead ), key, cds::opt::details::make_comparator_from_less<Less>() );
 605         }
 606
 607         /// Finds \p key and return the item found
 608         /** \anchor cds_intrusive_MichaelList_rcu_get
 609             The function searches the item with key equal to \p key and returns the pointer to item found.
 610             If \p key is not found it returns \p nullptr.
 611
 612             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 613
 614             RCU should be locked before call of this function.
 615             Returned item is valid only while RCU is locked:
 616             \code
 617             typedef cds::intrusive::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
 618             ord_list theList;
 619             // ...
 620             {
 621                 // Lock RCU
 622                 ord_list::rcu_lock lock;
 623
 624                 foo * pVal = theList.get( 5 );
 625                 if ( pVal ) {
 626                     // Deal with pVal
 627                     //...
 628                 }
 629                 // Unlock RCU by rcu_lock destructor
 630                 // pVal can be retired by disposer at any time after RCU has been unlocked
 631             }
 632             \endcode
 633         */
 634         template <typename Q>
 635         value_type * get( Q const& key ) const
 636         {
 637             return get_at( const_cast<atomic_node_ptr&>( m_pHead ), key, key_comparator());
 638         }
 639
 640         /// Finds \p key and return the item found
 641         /**
 642             The function is an analog of \ref cds_intrusive_MichaelList_rcu_get "get(Q const&)"
 643             but \p pred is used for comparing the keys.
 644
 645             \p Less functor has the semantics like \p std::less but should take arguments of type \p value_type and \p Q
 646             in any order.
 647             \p pred must imply the same element order as the comparator used for building the list.
 648         */
 649         template <typename Q, typename Less>
 650         value_type * get_with( Q const& key, Less pred ) const
 651         {
 652             return get_at( const_cast<atomic_node_ptr&>( m_pHead ), key, cds::opt::details::make_comparator_from_less<Less>());
 653         }
 654
 655         /// Clears the list using default disposer
 656         /**
 657             The function clears the list using default (provided by \p Traits class template argument) disposer functor.
 658
 659             RCU \p synchronize method can be called.
 660             Note that depending on RCU type used the \ref disposer invocation can be deferred.
 661
 662             The function can throw cds::urcu::rcu_deadlock exception if an deadlock is encountered and
 663             deadlock checking policy is opt::v::rcu_throw_deadlock.
 664         */
 665         void clear()
 666         {
 667             if( !empty() ) {
 668                 check_deadlock_policy::check();
 669
 670                 marked_node_ptr pHead;
 671                 for (;;) {
 672                     {
 673                         rcu_lock l;
 674                         pHead = m_pHead.load(memory_model::memory_order_consume);
 675                         if ( !pHead.ptr() )
 676                             break;
 677                         marked_node_ptr pNext( pHead->m_pNext.load(memory_model::memory_order_relaxed) );
 678                         if ( !pHead->m_pNext.compare_exchange_weak( pNext, pNext | 1, memory_model::memory_order_acquire, memory_model::memory_order_relaxed ))
 679                             continue;
 680                         if ( !m_pHead.compare_exchange_weak( pHead, marked_node_ptr(pNext.ptr()), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
 681                             continue;
 682                     }
 683
 684                     --m_ItemCounter;
 685                     dispose_node( pHead.ptr() );
 686                 }
 687             }
 688         }
 689
 690         /// Check if the list is empty
 691         bool empty() const
 692         {
 693             return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
 694         }
 695
 696         /// Returns list's item count
 697         /**
 698             The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
 699             this function always returns 0.
 700
 701             @note Even if you use real item counter and it returns 0, this fact does not mean that the list
 702             is empty. To check list emptyness use \p empty() method.
 703         */
 704         size_t size() const
 705         {
 706             return m_ItemCounter.value();
 707         }
 708
 709     protected:
 710         //@cond
 711         // split-list support
 712         bool insert_aux_node( node_type * pNode )
 713         {
 714             return insert_aux_node( m_pHead, pNode );
 715         }
 716
 717         // split-list support
 718         bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
 719         {
 720             assert( pNode != nullptr );
 721
 722             // Hack: convert node_type to value_type.
 723             // In principle, auxiliary node can be non-reducible to value_type
 724             // We assume that comparator can correctly distinguish between aux and regular node.
 725             return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
 726         }
 727
 728         bool insert_at( atomic_node_ptr& refHead, value_type& val, bool bLock = true )
 729         {
 730             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 731             position pos;
 732
 733             rcu_lock l( bLock );
 734             while ( true ) {
 735                 if ( search( refHead, val, pos, key_comparator() ) )
 736                     return false;
 737
 738                 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
 739                     ++m_ItemCounter;
 740                     return true;
 741                 }
 742
 743                 // clear next field
 744                 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 745             }
 746         }
 747
 748         template <typename Func>
 749         bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
 750         {
 751             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 752             position pos;
 753
 754             rcu_lock l;
 755             while ( true ) {
 756                 if ( search( refHead, val, pos, key_comparator() ) )
 757                     return false;
 758
 759                 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
 760                     f( val );
 761                     ++m_ItemCounter;
 762                     return true;
 763                 }
 764
 765                 // clear next field
 766                 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 767             }
 768         }
 769
 770         iterator insert_at_( atomic_node_ptr& refHead, value_type& val, bool bLock = true )
 771         {
 772             rcu_lock l( bLock );
 773             if ( insert_at( refHead, val, false ))
 774                 return iterator( node_traits::to_node_ptr( val ));
 775             return end();
 776         }
 777
 778         template <typename Func>
 779         std::pair<iterator, bool> ensure_at_( atomic_node_ptr& refHead, value_type& val, Func func, bool bLock = true )
 780         {
 781             position pos;
 782
 783             rcu_lock l( bLock );
 784             while ( true ) {
 785                 if ( search( refHead, val, pos, key_comparator() ) ) {
 786                     assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
 787
 788                     func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
 789                     return std::make_pair( iterator( pos.pCur ), false );
 790                 }
 791                 else {
 792                     link_checker::is_empty( node_traits::to_node_ptr( val ) );
 793
 794                     if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
 795                         ++m_ItemCounter;
 796                         func( true, val , val );
 797                         return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
 798                     }
 799
 800                     // clear the next field
 801                     node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 802                 }
 803             }
 804         }
 805
 806         template <typename Func>
 807         std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bLock = true )
 808         {
 809             rcu_lock l( bLock );
 810             std::pair<iterator, bool> ret = ensure_at_( refHead, val, func, false );
 811             return std::make_pair( ret.first != end(), ret.second );
 812         }
 813
 814         bool unlink_at( atomic_node_ptr& refHead, value_type& val )
 815         {
 816             position pos;
 817             back_off bkoff;
 818             check_deadlock_policy::check();
 819
 820             for (;;) {
 821                 {
 822                     rcu_lock l;
 823                     if ( !search( refHead, val, pos, key_comparator() ) || node_traits::to_value_ptr( *pos.pCur ) != &val )
 824                         return false;
 825                     if ( !unlink_node( pos )) {
 826                         bkoff();
 827                         continue;
 828                     }
 829                 }
 830
 831                 --m_ItemCounter;
 832                 dispose_node( pos.pCur );
 833                 return true;
 834             }
 835         }
 836
 837         template <typename Q, typename Compare, typename Func>
 838         bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f, position& pos )
 839         {
 840             back_off bkoff;
 841             check_deadlock_policy::check();
 842
 843             for (;;) {
 844                 {
 845                     rcu_lock l;
 846                     if ( !search( refHead, val, pos, cmp ) )
 847                         return false;
 848                     if ( !unlink_node( pos )) {
 849                         bkoff();
 850                         continue;
 851                     }
 852                 }
 853
 854                 f( *node_traits::to_value_ptr( *pos.pCur ) );
 855                 --m_ItemCounter;
 856                 dispose_node( pos.pCur );
 857                 return true;
 858             }
 859         }
 860
 861         template <typename Q, typename Compare, typename Func>
 862         bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f )
 863         {
 864             position pos;
 865             return erase_at( refHead, val, cmp, f, pos );
 866         }
 867
 868         template <typename Q, typename Compare>
 869         bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp )
 870         {
 871             position pos;
 872             return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
 873         }
 874
 875         template <typename Q, typename Compare >
 876         value_type * extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
 877         {
 878             position pos;
 879             back_off bkoff;
 880             assert( gc::is_locked() )  ;   // RCU must be locked!!!
 881
 882             for (;;) {
 883                 if ( !search( refHead, val, pos, cmp ) )
 884                     return nullptr;
 885                 if ( !unlink_node( pos )) {
 886                     bkoff();
 887                     continue;
 888                 }
 889
 890                 --m_ItemCounter;
 891                 return node_traits::to_value_ptr( pos.pCur );
 892             }
 893         }
 894
 895         template <typename Q, typename Compare, typename Func>
 896         bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f, bool bLock = true ) const
 897         {
 898             position pos;
 899
 900             rcu_lock l( bLock );
 901             if ( search( refHead, val, pos, cmp ) ) {
 902                 assert( pos.pCur != nullptr );
 903                 f( *node_traits::to_value_ptr( *pos.pCur ), val );
 904                 return true;
 905             }
 906             return false;
 907         }
 908
 909         template <typename Q, typename Compare>
 910         bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp ) const
 911         {
 912             rcu_lock l;
 913             return find_at_( refHead, val, cmp ) != end();
 914         }
 915
 916         template <typename Q, typename Compare>
 917         value_type * get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp ) const
 918         {
 919             value_type * pFound = nullptr;
 920             return find_at( refHead, val, cmp,
 921                 [&pFound](value_type& found, Q const& ) { pFound = &found; } )
 922                 ? pFound : nullptr;
 923         }
 924
 925         template <typename Q, typename Compare>
 926         const_iterator find_at_( atomic_node_ptr& refHead, Q const& val, Compare cmp ) const
 927         {
 928             assert( gc::is_locked() );
 929             position pos;
 930
 931             if ( search( refHead, val, pos, cmp ) ) {
 932                 assert( pos.pCur != nullptr );
 933                 return const_iterator( pos.pCur );
 934             }
 935             return end();
 936         }
 937
 938         //@endcond
 939
 940     protected:
 941
 942         //@cond
 943         template <typename Q, typename Compare>
 944         bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp ) const
 945         {
 946             // RCU lock should be locked!!!
 947             assert( gc::is_locked() );
 948
 949             atomic_node_ptr * pPrev;
 950             marked_node_ptr pNext;
 951             marked_node_ptr pCur;
 952
 953             back_off        bkoff;
 954
 955         try_again:
 956             pPrev = &refHead;
 957             pCur = pPrev->load(memory_model::memory_order_acquire);
 958             pNext = nullptr;
 959
 960             while ( true ) {
 961                 if ( !pCur.ptr() ) {
 962                     pos.pPrev = pPrev;
 963                     pos.pCur = pCur.ptr();
 964                     pos.pNext = pNext.ptr();
 965                     return false;
 966                 }
 967
 968                 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
 969
 970                 if ( pPrev->load(memory_model::memory_order_acquire) != pCur
 971                     || pNext != pCur->m_pNext.load(memory_model::memory_order_acquire)
 972                     || pNext.bits() != 0 )  // pNext contains deletion mark for pCur
 973                 {
 974                     // if pCur is marked as deleted (pNext.bits() != 0)
 975                     // we wait for physical removal.
 976                     // Helping technique is not suitable for RCU since it requires
 977                     // that the RCU should be in unlocking state.
 978                     bkoff();
 979                     goto try_again;
 980                 }
 981
 982                 assert( pCur.ptr() != nullptr );
 983                 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
 984                 if ( nCmp >= 0 ) {
 985                     pos.pPrev = pPrev;
 986                     pos.pCur = pCur.ptr();
 987                     pos.pNext = pNext.ptr();
 988                     return nCmp == 0;
 989                 }
 990                 pPrev = &( pCur->m_pNext );
 991                 pCur = pNext;
 992             }
 993         }
 994         //@endcond
 995     };
 996
 997 }}  // namespace cds::intrusive
 998
 999 #endif  // #ifndef __CDS_INTRUSIVE_MICHAEL_LIST_NOGC_H