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