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