cds/intrusive/lazy_list_rcu.h

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