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         typedef cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void > exempt_ptr ; ///< pointer to extracted node
 234
 235     protected:
 236         //@cond
 237         template <bool IsConst>
 238         class iterator_type
 239         {
 240             friend class LazyList;
 241
 242         protected:
 243             value_type * m_pNode;
 244
 245             void next()
 246             {
 247                 assert( m_pNode != nullptr );
 248
 249                 node_type * pNode = node_traits::to_node_ptr( m_pNode );
 250                 node_type * pNext = pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr();
 251                 if ( pNext != nullptr )
 252                     m_pNode = node_traits::to_value_ptr( pNext );
 253             }
 254
 255             void skip_deleted()
 256             {
 257                 if ( m_pNode != nullptr ) {
 258                     node_type * pNode = node_traits::to_node_ptr( m_pNode );
 259
 260                     // Dummy tail node could not be marked
 261                     while ( pNode->is_marked() )
 262                         pNode = pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr();
 263
 264                     if ( pNode != node_traits::to_node_ptr( m_pNode ) )
 265                         m_pNode = node_traits::to_value_ptr( pNode );
 266                 }
 267             }
 268
 269             iterator_type( node_type * pNode )
 270             {
 271                 m_pNode = node_traits::to_value_ptr( pNode );
 272                 skip_deleted();
 273             }
 274
 275         public:
 276             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 277             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 278
 279             iterator_type()
 280                 : m_pNode( nullptr )
 281             {}
 282
 283             iterator_type( iterator_type const& src )
 284                 : m_pNode( src.m_pNode )
 285             {}
 286
 287             value_ptr operator ->() const
 288             {
 289                 return m_pNode;
 290             }
 291
 292             value_ref operator *() const
 293             {
 294                 assert( m_pNode != nullptr );
 295                 return *m_pNode;
 296             }
 297
 298             /// Pre-increment
 299             iterator_type& operator ++()
 300             {
 301                 next();
 302                 skip_deleted();
 303                 return *this;
 304             }
 305
 306             /// Post-increment
 307             iterator_type operator ++(int)
 308             {
 309                 iterator_type i(*this);
 310                 next();
 311                 skip_deleted();
 312                 return i;
 313             }
 314
 315             iterator_type& operator = (iterator_type const& src)
 316             {
 317                 m_pNode = src.m_pNode;
 318                 return *this;
 319             }
 320
 321             template <bool C>
 322             bool operator ==(iterator_type<C> const& i ) const
 323             {
 324                 return m_pNode == i.m_pNode;
 325             }
 326             template <bool C>
 327             bool operator !=(iterator_type<C> const& i ) const
 328             {
 329                 return m_pNode != i.m_pNode;
 330             }
 331         };
 332         //@endcond
 333
 334     public:
 335         /// Forward iterator
 336         typedef iterator_type<false>    iterator;
 337         /// Const forward iterator
 338         typedef iterator_type<true>     const_iterator;
 339
 340         /// Returns a forward iterator addressing the first element in a list
 341         /**
 342             For empty list \code begin() == end() \endcode
 343         */
 344         iterator begin()
 345         {
 346             iterator it( &m_Head );
 347             ++it        ;   // skip dummy head
 348             return it;
 349         }
 350
 351         /// Returns an iterator that addresses the location succeeding the last element in a list
 352         /**
 353             Do not use the value returned by <tt>end</tt> function to access any item.
 354
 355             The returned value can be used only to control reaching the end of the list.
 356             For empty list \code begin() == end() \endcode
 357         */
 358         iterator end()
 359         {
 360             return iterator( &m_Tail );
 361         }
 362
 363         /// Returns a forward const iterator addressing the first element in a list
 364         //@{
 365         const_iterator begin() const
 366         {
 367             return get_const_begin();
 368         }
 369         const_iterator cbegin()
 370         {
 371             return get_const_begin();
 372         }
 373         //@}
 374
 375         /// Returns an const iterator that addresses the location succeeding the last element in a list
 376         //@{
 377         const_iterator end() const
 378         {
 379             return get_const_end();
 380         }
 381         const_iterator cend()
 382         {
 383             return get_const_end();
 384         }
 385         //@}
 386
 387     private:
 388         //@cond
 389         const_iterator get_const_begin() const
 390         {
 391             const_iterator it( const_cast<node_type *>( &m_Head ));
 392             ++it        ;   // skip dummy head
 393             return it;
 394         }
 395         const_iterator get_const_end() const
 396         {
 397             return const_iterator( const_cast<node_type *>( &m_Tail ));
 398         }
 399         //@endcond
 400
 401     public:
 402         /// Default constructor initializes empty list
 403         LazyList()
 404         {
 405             static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
 406             m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
 407         }
 408
 409         /// Destroys the list object
 410         ~LazyList()
 411         {
 412             clear();
 413
 414             assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail );
 415             m_Head.m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 416         }
 417
 418         /// Inserts new node
 419         /**
 420             The function inserts \p val in the list if the list does not contain
 421             an item with key equal to \p val.
 422
 423             Returns \p true if \p val is linked into the list, \p false otherwise.
 424         */
 425         bool insert( value_type& val )
 426         {
 427             return insert_at( &m_Head, val );
 428         }
 429
 430         /// Inserts new node
 431         /**
 432             This function is intended for derived non-intrusive containers.
 433
 434             The function allows to split new item creating into two part:
 435             - create item with key only
 436             - insert new item into the list
 437             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 438
 439             The functor signature is:
 440             \code
 441                 void func( value_type& val );
 442             \endcode
 443             where \p val is the item inserted.
 444             While the functor \p f is working the item \p val is locked.
 445             The user-defined functor is called only if the inserting is success.
 446         */
 447         template <typename Func>
 448         bool insert( value_type& val, Func f )
 449         {
 450             return insert_at( &m_Head, val, f );
 451         }
 452
 453         /// Ensures that the \p item exists in the list
 454         /**
 455             The operation performs inserting or changing data with lock-free manner.
 456
 457             If the item \p val not found in the list, then \p val is inserted into the list.
 458             Otherwise, the functor \p func is called with item found.
 459             The functor signature is:
 460             \code
 461             struct functor {
 462                 void operator()( bool bNew, value_type& item, value_type& val );
 463             };
 464             \endcode
 465             with arguments:
 466             - \p bNew - \p true if the item has been inserted, \p false otherwise
 467             - \p item - item of the list
 468             - \p val - argument \p val passed into the \p ensure function
 469             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 470             refers to the same thing.
 471
 472             The functor may change non-key fields of the \p item.
 473             While the functor \p f is calling the item \p item is locked.
 474
 475             Returns <tt> std::pair<bool, bool>  </tt> where \p first is true if operation is successfull,
 476             \p second is true if new item has been added or \p false if the item with \p key
 477             already is in the list.
 478         */
 479
 480         template <typename Func>
 481         std::pair<bool, bool> ensure( value_type& val, Func func )
 482         {
 483             return ensure_at( &m_Head, val, func );
 484         }
 485
 486         /// Unlinks the item \p val from the list
 487         /**
 488             The function searches the item \p val in the list and unlink it from the list
 489             if it is found and it is equal to \p val.
 490
 491             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 492             and deletes the item found. \p unlink finds an item by key and deletes it
 493             only if \p val is an item of that list, i.e. the pointer to item found
 494             is equal to <tt> &val </tt>.
 495
 496             The function returns \p true if success and \p false otherwise.
 497
 498             RCU \p synchronize method can be called.
 499             Note that depending on RCU type used the \ref disposer call can be deferred.
 500
 501             The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
 502             deadlock checking policy is opt::v::rcu_throw_deadlock.
 503         */
 504         bool unlink( value_type& val )
 505         {
 506             return unlink_at( &m_Head, val );
 507         }
 508
 509         /// Deletes the item from the list
 510         /** \anchor cds_intrusive_LazyList_rcu_find_erase
 511             The function searches an item with key equal to \p key in the list,
 512             unlinks it from the list, and returns \p true.
 513             If the item with the key equal to \p key is not found the function return \p false.
 514
 515             RCU \p synchronize method can be called.
 516             Note that depending on RCU type used the \ref disposer call can be deferred.
 517
 518             The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
 519             deadlock checking policy is opt::v::rcu_throw_deadlock.
 520         */
 521         template <typename Q>
 522         bool erase( Q const& key )
 523         {
 524             return erase_at( &m_Head, key, key_comparator() );
 525         }
 526
 527         /// Deletes the item from the list using \p pred predicate for searching
 528         /**
 529             The function is an analog of \ref cds_intrusive_LazyList_rcu_find_erase "erase(Q const&)"
 530             but \p pred is used for key comparing.
 531             \p Less functor has the interface like \p std::less.
 532             \p pred must imply the same element order as the comparator used for building the list.
 533         */
 534         template <typename Q, typename Less>
 535         bool erase_with( Q const& key, Less pred )
 536         {
 537             return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
 538         }
 539
 540
 541         /// Deletes the item from the list
 542         /** \anchor cds_intrusive_LazyList_rcu_find_erase_func
 543             The function searches an item with key equal to \p key in the list,
 544             call \p func functor with item found, unlinks it from the list, and returns \p true.
 545             The \p Func interface is
 546             \code
 547             struct functor {
 548                 void operator()( value_type const& item );
 549             };
 550             \endcode
 551
 552             If the item with the key equal to \p key is not found the function return \p false.
 553
 554             RCU \p synchronize method can be called.
 555             Note that depending on RCU type used the \ref disposer call can be deferred.
 556
 557             The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
 558             deadlock checking policy is opt::v::rcu_throw_deadlock.
 559         */
 560         template <typename Q, typename Func>
 561         bool erase( Q const& key, Func func )
 562         {
 563             return erase_at( &m_Head, key, key_comparator(), func );
 564         }
 565
 566         /// Deletes the item from the list using \p pred predicate for searching
 567         /**
 568             The function is an analog of \ref cds_intrusive_LazyList_rcu_find_erase_func "erase(Q const&, Func)"
 569             but \p pred is used for key comparing.
 570             \p Less functor has the interface like \p std::less.
 571             \p pred must imply the same element order as the comparator used for building the list.
 572         */
 573         template <typename Q, typename Less, typename Func>
 574         bool erase_with( Q const& key, Less pred, Func func )
 575         {
 576             return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), func );
 577         }
 578
 579         /// Extracts an item from the list
 580         /**
 581         \anchor cds_intrusive_LazyList_rcu_extract
 582             The function searches an item with key equal to \p key in the list,
 583             unlinks it from the list, and returns pointer to an item found in \p dest parameter.
 584             If the item with the key equal to \p key is not found the function returns \p false,
 585             \p dest is empty.
 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 item found.
 590             You should 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                 if ( theList.extract( p1, 10 )) {
 611                     // do something with p1
 612                     ...
 613                 }
 614             }
 615
 616             // We may safely release p1 here
 617             // release() passes the pointer to RCU reclamation cycle:
 618             // it invokes RCU retire_ptr function with the disposer you provided for the list.
 619             p1.release();
 620             \endcode
 621         */
 622         template <typename Q>
 623         bool extract( exempt_ptr& dest, Q const& key )
 624         {
 625             dest = extract_at( &m_Head, key, key_comparator() );
 626             return !dest.empty();
 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         bool extract_with( exempt_ptr& dest, Q const& key, Less pred )
 639         {
 640             dest = extract_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>() );
 641             return !dest.empty();
 642         }
 643
 644         /// Finds the key \p key
 645         /** \anchor cds_intrusive_LazyList_rcu_find_func
 646             The function searches the item with key equal to \p key
 647             and calls the functor \p f for item found.
 648             The interface of \p Func functor is:
 649             \code
 650             struct functor {
 651                 void operator()( value_type& item, Q& key );
 652             };
 653             \endcode
 654             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 655
 656             You may pass \p f argument by reference using \p std::ref.
 657
 658             The functor may change non-key fields of \p item.
 659             While the functor \p f is calling the item found \p item is locked.
 660
 661             The function returns \p true if \p key is found, \p false otherwise.
 662         */
 663         template <typename Q, typename Func>
 664         bool find( Q& key, Func f ) const
 665         {
 666             return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator(), f );
 667         }
 668
 669         /// Finds the key \p key using \p pred predicate for searching
 670         /**
 671             The function is an analog of \ref cds_intrusive_LazyList_rcu_find_func "find(Q&, Func)"
 672             but \p pred is used for key comparing.
 673             \p Less functor has the interface like \p std::less.
 674             \p pred must imply the same element order as the comparator used for building the list.
 675         */
 676         template <typename Q, typename Less, typename Func>
 677         bool find_with( Q& key, Less pred, Func f ) const
 678         {
 679             return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>(), f );
 680         }
 681
 682         /// Finds the key \p key
 683         /** \anchor cds_intrusive_LazyList_rcu_find_val
 684             The function searches the item with key equal to \p key
 685             and returns \p true if \p key found or \p false otherwise.
 686         */
 687         template <typename Q>
 688         bool find( Q const& key ) const
 689         {
 690             return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator() );
 691         }
 692
 693         /// Finds the key \p key using \p pred predicate for searching
 694         /**
 695             The function is an analog of \ref cds_intrusive_LazyList_rcu_find_val "find(Q const&)"
 696             but \p pred is used for key comparing.
 697             \p Less functor has the interface like \p std::less.
 698             \p pred must imply the same element order as the comparator used for building the list.
 699         */
 700         template <typename Q, typename Less>
 701         bool find_with( Q const& key, Less pred ) const
 702         {
 703             return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>() );
 704         }
 705
 706         /// Finds the key \p key and return the item found
 707         /** \anchor cds_intrusive_LazyList_rcu_get
 708             The function searches the item with key equal to \p key and returns the pointer to item found.
 709             If \p key is not found it returns \p nullptr.
 710
 711             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 712
 713             RCU should be locked before call of this function.
 714             Returned item is valid only while RCU is locked:
 715             \code
 716             typedef cds::intrusive::LazyList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
 717             ord_list theList;
 718             // ...
 719             {
 720                 // Lock RCU
 721                 ord_list::rcu_lock lock;
 722
 723                 foo * pVal = theList.get( 5 );
 724                 if ( pVal ) {
 725                     // Deal with pVal
 726                     //...
 727                 }
 728                 // Unlock RCU by rcu_lock destructor
 729                 // pVal can be retired by disposer at any time after RCU has been unlocked
 730             }
 731             \endcode
 732         */
 733         template <typename Q>
 734         value_type * get( Q const& key ) const
 735         {
 736             return get_at( const_cast<node_type *>( &m_Head ), key, key_comparator());
 737         }
 738
 739         /// Finds the key \p key and return the item found
 740         /**
 741             The function is an analog of \ref cds_intrusive_LazyList_rcu_get "get(Q const&)"
 742             but \p pred is used for comparing the keys.
 743
 744             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 745             in any order.
 746             \p pred must imply the same element order as the comparator used for building the list.
 747         */
 748         template <typename Q, typename Less>
 749         value_type * get_with( Q const& key, Less pred ) const
 750         {
 751             return get_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>());
 752         }
 753
 754         /// Clears the list using default disposer
 755         /**
 756             The function clears the list using default (provided in class template) disposer functor.
 757
 758             RCU \p synchronize method can be called.
 759             Note that depending on RCU type used the \ref disposer call can be deferred.
 760
 761             The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
 762             deadlock checking policy is opt::v::rcu_throw_deadlock.
 763         */
 764         void clear()
 765         {
 766             if( !empty() ) {
 767                 check_deadlock_policy::check();
 768
 769                 node_type * pHead;
 770                 for (;;) {
 771                     {
 772                         rcu_lock l;
 773                         pHead = m_Head.m_pNext.load(memory_model::memory_order_acquire).ptr();
 774                         if ( pHead == &m_Tail )
 775                             break;
 776
 777                         m_Head.m_Lock.lock();
 778                         pHead->m_Lock.lock();
 779
 780                         if ( m_Head.m_pNext.load(memory_model::memory_order_relaxed).all() == pHead )
 781                             unlink_node( &m_Head, pHead, &m_Head );
 782
 783                         pHead->m_Lock.unlock();
 784                         m_Head.m_Lock.unlock();
 785                     }
 786
 787                     --m_ItemCounter;
 788                     dispose_node( pHead );
 789                 }
 790             }
 791         }
 792
 793         /// Checks if the list is empty
 794         bool empty() const
 795         {
 796             return m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail;
 797         }
 798
 799         /// Returns list's item count
 800         /**
 801             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 802             this function always returns 0.
 803
 804             <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
 805             is empty. To check list emptyness use \ref empty() method.
 806         */
 807         size_t size() const
 808         {
 809             return m_ItemCounter.value();
 810         }
 811
 812     protected:
 813         //@cond
 814         // split-list support
 815         bool insert_aux_node( node_type * pNode )
 816         {
 817             return insert_aux_node( &m_Head, pNode );
 818         }
 819
 820         // split-list support
 821         bool insert_aux_node( node_type * pHead, node_type * pNode )
 822         {
 823             assert( pHead != nullptr );
 824             assert( pNode != nullptr );
 825
 826             // Hack: convert node_type to value_type.
 827             // In principle, auxiliary node can be non-reducible to value_type
 828             // We assume that comparator can correctly distinguish aux and regular node.
 829             return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
 830         }
 831
 832         bool insert_at( node_type * pHead, value_type& val, bool bLock = true )
 833         {
 834             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 835             position pos;
 836             key_comparator  cmp;
 837
 838             rcu_lock l( bLock );
 839             while ( true ) {
 840                 search( pHead, val, pos );
 841                 {
 842                     auto_lock_position alp( pos );
 843                     if ( validate( pos.pPred, pos.pCur )) {
 844                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
 845                             // failed: key already in list
 846                             return false;
 847                         }
 848                         else {
 849                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 850                             ++m_ItemCounter;
 851                             return true;
 852                         }
 853                     }
 854                 }
 855             }
 856         }
 857
 858         template <typename Func>
 859         bool insert_at( node_type * pHead, value_type& val, Func f )
 860         {
 861             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 862             position pos;
 863             key_comparator  cmp;
 864
 865             rcu_lock l;
 866             while ( true ) {
 867                 search( pHead, val, pos );
 868                 {
 869                     auto_lock_position alp( pos );
 870                     if ( validate( pos.pPred, pos.pCur )) {
 871                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
 872                             // failed: key already in list
 873                             return false;
 874                         }
 875                         else {
 876                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 877                             f( val );
 878                             ++m_ItemCounter;
 879                             return true;
 880                         }
 881                     }
 882                 }
 883             }
 884         }
 885
 886         iterator insert_at_( node_type * pHead, value_type& val, bool bLock = true )
 887         {
 888             rcu_lock l( bLock );
 889             if ( insert_at( pHead, val, false ))
 890                 return iterator( node_traits::to_node_ptr( val ));
 891             return end();
 892         }
 893
 894
 895         template <typename Func>
 896         std::pair<iterator, bool> ensure_at_( node_type * pHead, value_type& val, Func func, bool bLock = true )
 897         {
 898             position pos;
 899             key_comparator  cmp;
 900
 901             rcu_lock l( bLock );
 902             while ( true ) {
 903                 search( pHead, val, pos );
 904                 {
 905                     auto_lock_position alp( pos );
 906                     if ( validate( pos.pPred, pos.pCur )) {
 907                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
 908                             // key already in the list
 909
 910                             func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
 911                             return std::make_pair( iterator( pos.pCur ), false );
 912                         }
 913                         else {
 914                             // new key
 915                             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 916
 917                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 918                             func( true, val, val );
 919                             ++m_ItemCounter;
 920                             return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
 921                         }
 922                     }
 923                 }
 924             }
 925         }
 926
 927         template <typename Func>
 928         std::pair<bool, bool> ensure_at( node_type * pHead, value_type& val, Func func, bool bLock = true )
 929         {
 930             rcu_lock l( bLock );
 931             std::pair<iterator, bool> ret = ensure_at_( pHead, val, func, false );
 932             return std::make_pair( ret.first != end(), ret.second );
 933         }
 934
 935         bool unlink_at( node_type * pHead, value_type& val )
 936         {
 937             position pos;
 938             key_comparator  cmp;
 939             check_deadlock_policy::check();
 940
 941             while ( true ) {
 942                 int nResult = 0;
 943                 {
 944                     rcu_lock l;
 945                     search( pHead, val, pos );
 946                     {
 947                         auto_lock_position alp( pos );
 948                         if ( validate( pos.pPred, pos.pCur ) ) {
 949                             if ( pos.pCur != &m_Tail
 950                                 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
 951                                 && node_traits::to_value_ptr( pos.pCur ) == &val )
 952                             {
 953                                 // item found
 954                                 unlink_node( pos.pPred, pos.pCur, pHead );
 955                                 --m_ItemCounter;
 956                                 nResult = 1;
 957                             }
 958                             else
 959                                 nResult = -1;
 960                         }
 961                     }
 962                 }
 963
 964                 if ( nResult ) {
 965                     if ( nResult > 0 ) {
 966                         dispose_node( pos.pCur );
 967                         return true;
 968                     }
 969                     return false;
 970                 }
 971             }
 972         }
 973
 974         template <typename Q, typename Compare, typename Func>
 975         bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f, position& pos )
 976         {
 977             check_deadlock_policy::check();
 978
 979             while ( true ) {
 980                 int nResult = 0;
 981                 {
 982                     rcu_lock l;
 983                     search( pHead, val, pos, cmp );
 984                     {
 985                         auto_lock_position alp( pos );
 986                         if ( validate( pos.pPred, pos.pCur )) {
 987                             if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
 988                                 // key found
 989                                 unlink_node( pos.pPred, pos.pCur, pHead );
 990                                 f( *node_traits::to_value_ptr( *pos.pCur ) );
 991                                 --m_ItemCounter;
 992                                 nResult = 1;
 993                             }
 994                             else {
 995                                 nResult = -1;
 996                             }
 997                         }
 998                     }
 999                 }
1000
1001                 if ( nResult ) {
1002                     if ( nResult > 0 ) {
1003                         dispose_node( pos.pCur );
1004                         return true;
1005                     }
1006                     return false;
1007                 }
1008             }
1009         }
1010
1011         template <typename Q, typename Compare, typename Func>
1012         bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f )
1013         {
1014             position pos;
1015             return erase_at( pHead, val, cmp, f, pos );
1016         }
1017
1018         template <typename Q, typename Compare>
1019         bool erase_at( node_type * pHead, Q const& val, Compare cmp )
1020         {
1021             position pos;
1022             return erase_at( pHead, val, cmp, [](value_type const &){}, pos );
1023         }
1024
1025         template <typename Q, typename Compare>
1026         value_type * extract_at( node_type * pHead, Q const& val, Compare cmp )
1027         {
1028             position pos;
1029             assert( gc::is_locked() ) ; // RCU must be locked!!!
1030
1031             while ( true ) {
1032                 search( pHead, val, pos, cmp );
1033                 int nResult = 0;
1034                 {
1035                     auto_lock_position alp( pos );
1036                     if ( validate( pos.pPred, pos.pCur )) {
1037                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1038                             // key found
1039                             unlink_node( pos.pPred, pos.pCur, pHead );
1040                             --m_ItemCounter;
1041                             nResult = 1;
1042                         }
1043                         else {
1044                             nResult = -1;
1045                         }
1046                     }
1047                 }
1048
1049                 if ( nResult ) {
1050                     if ( nResult > 0 )
1051                         return node_traits::to_value_ptr( pos.pCur );
1052                     return nullptr;
1053                 }
1054             }
1055         }
1056
1057         template <typename Q, typename Compare, typename Func>
1058         bool find_at( node_type * pHead, Q& val, Compare cmp, Func f, bool bLock = true ) const
1059         {
1060             position pos;
1061
1062             rcu_lock l( bLock );
1063             search( pHead, val, pos, cmp );
1064             if ( pos.pCur != &m_Tail ) {
1065                 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1066                 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1067                 {
1068                     f( *node_traits::to_value_ptr( *pos.pCur ), val );
1069                     return true;
1070                 }
1071             }
1072             return false;
1073         }
1074
1075         template <typename Q, typename Compare>
1076         bool find_at( node_type * pHead, Q& val, Compare cmp ) const
1077         {
1078             rcu_lock l;
1079             return find_at_( pHead, val, cmp ) != end();
1080         }
1081
1082         template <typename Q, typename Compare>
1083         const_iterator find_at_( node_type * pHead, Q& val, Compare cmp ) const
1084         {
1085             assert( gc::is_locked() );
1086
1087             position pos;
1088
1089             search( pHead, val, pos, cmp );
1090             if ( pos.pCur != &m_Tail ) {
1091                 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1092                 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1093                 {
1094                     return const_iterator( pos.pCur );
1095                 }
1096             }
1097             return end();
1098         }
1099
1100         template <typename Q, typename Compare>
1101         value_type * get_at( node_type * pHead, Q const& val, Compare cmp ) const
1102         {
1103             value_type * pFound = nullptr;
1104             return find_at( pHead, val, cmp, [&pFound](value_type& found, Q const& ) { pFound = &found; } )
1105                 ? pFound : nullptr;
1106         }
1107
1108         //@endcond
1109
1110     protected:
1111         //@cond
1112         template <typename Q>
1113         void search( node_type * pHead, Q const& key, position& pos ) const
1114         {
1115             search( pHead, key, pos, key_comparator() );
1116         }
1117
1118         template <typename Q, typename Compare>
1119         void search( node_type * pHead, Q const& key, position& pos, Compare cmp ) const
1120         {
1121             // RCU should be locked!!!
1122             assert( gc::is_locked() );
1123
1124             node_type const* pTail = &m_Tail;
1125
1126             marked_node_ptr pCur(pHead);
1127             marked_node_ptr pPrev(pHead);
1128
1129             while ( pCur.ptr() != pTail && ( pCur.ptr() == pHead || cmp( *node_traits::to_value_ptr( *pCur.ptr() ), key ) < 0 )) {
1130                 pPrev = pCur;
1131                 pCur = pCur->m_pNext.load(memory_model::memory_order_relaxed);
1132             }
1133
1134             pos.pCur = pCur.ptr();
1135             pos.pPred = pPrev.ptr();
1136         }
1137
1138         static bool validate( node_type * pPred, node_type * pCur )
1139         {
1140             // RCU lock should be locked!!!
1141             assert( gc::is_locked() );
1142
1143             return !pPred->is_marked()
1144                 && !pCur->is_marked()
1145                 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1146         }
1147
1148         //@endcond
1149     };
1150
1151 }}  // namespace cds::intrusive
1152
1153 #endif  // #ifndef __CDS_INTRUSIVE_LAZY_LIST_RCU_H