cds/intrusive/lazy_list_rcu.h

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