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