cds/intrusive/lazy_list_rcu.h

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