cds/intrusive/lazy_list_rcu.h

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