cds/intrusive/lazy_list_rcu.h

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