cds/intrusive/lazy_list_rcu.h

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