cds/intrusive/lazy_list_rcu.h

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