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         //@cond
 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 \ref 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             The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
 531             deadlock checking policy is opt::v::rcu_throw_deadlock.
 532         */
 533         bool unlink( value_type& val )
 534         {
 535             return unlink_at( &m_Head, val );
 536         }
 537
 538         /// Deletes the item from the list
 539         /** \anchor cds_intrusive_LazyList_rcu_find_erase
 540             The function searches an item with key equal to \p key in the list,
 541             unlinks it from the list, and returns \p true.
 542             If the item with the key equal to \p key is not found the function return \p false.
 543
 544             RCU \p synchronize method can be called. The RCU should not be locked.
 545             Note that depending on RCU type used the \ref disposer call can be deferred.
 546
 547             The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
 548             deadlock checking policy is opt::v::rcu_throw_deadlock.
 549         */
 550         template <typename Q>
 551         bool erase( Q const& key )
 552         {
 553             return erase_at( &m_Head, key, key_comparator());
 554         }
 555
 556         /// Deletes the item from the list using \p pred predicate for searching
 557         /**
 558             The function is an analog of \ref cds_intrusive_LazyList_rcu_find_erase "erase(Q const&)"
 559             but \p pred is used for key comparing.
 560             \p Less functor has the interface like \p std::less.
 561             \p pred must imply the same element order as the comparator used for building the list.
 562         */
 563         template <typename Q, typename Less>
 564         bool erase_with( Q const& key, Less pred )
 565         {
 566             CDS_UNUSED( pred );
 567             return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
 568         }
 569
 570         /// Deletes the item from the list
 571         /** \anchor cds_intrusive_LazyList_rcu_find_erase_func
 572             The function searches an item with key equal to \p key in the list,
 573             call \p func functor with item found, unlinks it from the list, and returns \p true.
 574             The \p Func interface is
 575             \code
 576             struct functor {
 577                 void operator()( value_type const& item );
 578             };
 579             \endcode
 580
 581             If the item with the key equal to \p key is not found the function return \p false.
 582
 583             RCU \p synchronize method can be called. The RCU should not be locked.
 584             Note that depending on RCU type used the \ref disposer call can be deferred.
 585
 586             The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
 587             deadlock checking policy is opt::v::rcu_throw_deadlock.
 588         */
 589         template <typename Q, typename Func>
 590         bool erase( Q const& key, Func func )
 591         {
 592             return erase_at( &m_Head, key, key_comparator(), func );
 593         }
 594
 595         /// Deletes the item from the list using \p pred predicate for searching
 596         /**
 597             The function is an analog of \ref cds_intrusive_LazyList_rcu_find_erase_func "erase(Q const&, Func)"
 598             but \p pred is used for key comparing.
 599             \p Less functor has the interface like \p std::less.
 600             \p pred must imply the same element order as the comparator used for building the list.
 601         */
 602         template <typename Q, typename Less, typename Func>
 603         bool erase_with( Q const& key, Less pred, Func func )
 604         {
 605             CDS_UNUSED( pred );
 606             return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), func );
 607         }
 608
 609         /// Extracts an item from the list
 610         /**
 611         \anchor cds_intrusive_LazyList_rcu_extract
 612             The function searches an item with key equal to \p key in the list,
 613             unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
 614             If the item is not found the function returns empty \p exempt_ptr.
 615
 616             @note The function does NOT call RCU read-side lock or synchronization,
 617             and does NOT dispose the item found. It just unlinks the item from the list
 618             and returns a pointer to it.
 619             You should manually lock RCU before calling this function, and you should manually synchronize RCU
 620             outside the RCU lock region before reusing returned pointer.
 621
 622             \code
 623             #include <cds/urcu/general_buffered.h>
 624             #include <cds/intrusive/lazy_list_rcu.h>
 625
 626             typedef cds::urcu::gc< general_buffered<> > rcu;
 627             typedef cds::intrusive::LazyList< rcu, Foo > rcu_lazy_list;
 628
 629             rcu_lazy_list theList;
 630             // ...
 631
 632             rcu_lazy_list::exempt_ptr p1;
 633             {
 634                 // first, we should lock RCU
 635                 rcu::scoped_lock sl;
 636
 637                 // Now, you can apply extract function
 638                 // Note that you must not delete the item found inside the RCU lock
 639                 p1 = theList.extract(  10 )
 640                 if ( p1 ) {
 641                     // do something with p1
 642                     ...
 643                 }
 644             }
 645
 646             // We may safely release p1 here
 647             // release() passes the pointer to RCU reclamation cycle:
 648             // it invokes RCU retire_ptr function with the disposer you provided for the list.
 649             p1.release();
 650             \endcode
 651         */
 652         template <typename Q>
 653         exempt_ptr extract( Q const& key )
 654         {
 655             return exempt_ptr( extract_at( &m_Head, key, key_comparator()));
 656         }
 657
 658         /// Extracts an item from the list using \p pred predicate for searching
 659         /**
 660             This function is the analog for \p extract(Q const&).
 661
 662             The \p pred is a predicate used for key comparing.
 663             \p Less has the interface like \p std::less.
 664             \p pred must imply the same element order as \ref key_comparator.
 665         */
 666         template <typename Q, typename Less>
 667         exempt_ptr extract_with( Q const& key, Less pred )
 668         {
 669             CDS_UNUSED( pred );
 670             return exempt_ptr( extract_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>()));
 671         }
 672
 673         /// Finds the key \p key
 674         /** \anchor cds_intrusive_LazyList_rcu_find_func
 675             The function searches the item with key equal to \p key
 676             and calls the functor \p f for item found.
 677             The interface of \p Func functor is:
 678             \code
 679             struct functor {
 680                 void operator()( value_type& item, Q& key );
 681             };
 682             \endcode
 683             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 684
 685             The functor may change non-key fields of \p item.
 686             While the functor \p f is calling the item found \p item is locked.
 687
 688             The function returns \p true if \p key is found, \p false otherwise.
 689         */
 690         template <typename Q, typename Func>
 691         bool find( Q& key, Func f ) const
 692         {
 693             return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator(), f );
 694         }
 695         //@cond
 696         template <typename Q, typename Func>
 697         bool find( Q const& key, Func f ) const
 698         {
 699             return find_at( const_cast<node_type *>(&m_Head), key, key_comparator(), f );
 700         }
 701         //@endcond
 702
 703         /// Finds the key \p key using \p pred predicate for searching
 704         /**
 705             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 706             \p Less functor has the interface like \p std::less.
 707             \p pred must imply the same element order as the comparator used for building the list.
 708         */
 709         template <typename Q, typename Less, typename Func>
 710         bool find_with( Q& key, Less pred, Func f ) const
 711         {
 712             CDS_UNUSED( pred );
 713             return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>(), f );
 714         }
 715         //@cond
 716         template <typename Q, typename Less, typename Func>
 717         bool find_with( Q const& key, Less pred, Func f ) const
 718         {
 719             CDS_UNUSED( pred );
 720             return find_at( const_cast<node_type *>(&m_Head), key, cds::opt::details::make_comparator_from_less<Less>(), f );
 721         }
 722         //@endcond
 723
 724         /// Checks whether the list contains \p key
 725         /**
 726             The function searches the item with key equal to \p key
 727             and returns \p true if it is found, and \p false otherwise.
 728         */
 729         template <typename Q>
 730         bool contains( Q const& key ) const
 731         {
 732             return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator());
 733         }
 734         //@cond
 735         template <typename Q>
 736         CDS_DEPRECATED("deprecated, use contains()")
 737         bool find( Q const& key ) const
 738         {
 739             return contains( key );
 740         }
 741         //@endcond
 742
 743         /// Checks whether the map contains \p key using \p pred predicate for searching
 744         /**
 745             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 746             \p Less functor has the interface like \p std::less.
 747             \p Less must imply the same element order as the comparator used for building the list.
 748         */
 749         template <typename Q, typename Less>
 750         bool contains( Q const& key, Less pred ) const
 751         {
 752             CDS_UNUSED( pred );
 753             return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>());
 754         }
 755         //@cond
 756         template <typename Q, typename Less>
 757         CDS_DEPRECATED("deprecated, use contains()")
 758         bool find_with( Q const& key, Less pred ) const
 759         {
 760             return contains( key, pred );
 761         }
 762         //@endcond
 763
 764         /// Finds the key \p key and return the item found
 765         /** \anchor cds_intrusive_LazyList_rcu_get
 766             The function searches the item with key equal to \p key and returns the pointer to item found.
 767             If \p key is not found it returns \p nullptr.
 768
 769             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 770
 771             RCU should be locked before call of this function.
 772             Returned item is valid only while RCU is locked:
 773             \code
 774             typedef cds::intrusive::LazyList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
 775             ord_list theList;
 776             // ...
 777             {
 778                 // Lock RCU
 779                 typename ord_list::rcu_lock lock;
 780
 781                 foo * pVal = theList.get( 5 );
 782                 if ( pVal ) {
 783                     // Deal with pVal
 784                     //...
 785                 }
 786                 // Unlock RCU by rcu_lock destructor
 787                 // pVal can be retired by disposer at any time after RCU has been unlocked
 788             }
 789             \endcode
 790         */
 791         template <typename Q>
 792         value_type * get( Q const& key ) const
 793         {
 794             return get_at( const_cast<node_type *>( &m_Head ), key, key_comparator());
 795         }
 796
 797         /// Finds the key \p key and return the item found
 798         /**
 799             The function is an analog of \ref cds_intrusive_LazyList_rcu_get "get(Q const&)"
 800             but \p pred is used for comparing the keys.
 801
 802             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 803             in any order.
 804             \p pred must imply the same element order as the comparator used for building the list.
 805         */
 806         template <typename Q, typename Less>
 807         value_type * get_with( Q const& key, Less pred ) const
 808         {
 809             CDS_UNUSED( pred );
 810             return get_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>());
 811         }
 812
 813         /// Clears the list using default disposer
 814         /**
 815             The function clears the list using default (provided in class template) disposer functor.
 816
 817             RCU \p synchronize method can be called.
 818             Note that depending on RCU type used the \ref disposer call can be deferred.
 819
 820             The function can throw \p cds::urcu::rcu_deadlock exception if deadlock is encountered and
 821             deadlock checking policy is \p opt::v::rcu_throw_deadlock.
 822         */
 823         void clear()
 824         {
 825             if( !empty()) {
 826                 deadlock_policy::check();
 827
 828                 node_type * pHead;
 829                 for (;;) {
 830                     {
 831                         rcu_lock l;
 832                         pHead = m_Head.m_pNext.load(memory_model::memory_order_acquire).ptr();
 833                         if ( pHead == &m_Tail )
 834                             break;
 835
 836                         m_Head.m_Lock.lock();
 837                         pHead->m_Lock.lock();
 838
 839                         if ( m_Head.m_pNext.load(memory_model::memory_order_relaxed).all() == pHead )
 840                             unlink_node( &m_Head, pHead, &m_Head );
 841
 842                         pHead->m_Lock.unlock();
 843                         m_Head.m_Lock.unlock();
 844                     }
 845
 846                     --m_ItemCounter;
 847                     dispose_node( pHead );
 848                 }
 849             }
 850         }
 851
 852         /// Checks if the list is empty
 853         bool empty() const
 854         {
 855             return m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail;
 856         }
 857
 858         /// Returns list's item count
 859         /**
 860             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 861             this function always returns 0.
 862
 863             <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
 864             is empty. To check list emptyness use \ref empty() method.
 865         */
 866         size_t size() const
 867         {
 868             return m_ItemCounter.value();
 869         }
 870
 871     protected:
 872         //@cond
 873         // split-list support
 874         bool insert_aux_node( node_type * pNode )
 875         {
 876             return insert_aux_node( &m_Head, pNode );
 877         }
 878
 879         // split-list support
 880         bool insert_aux_node( node_type * pHead, node_type * pNode )
 881         {
 882             assert( pHead != nullptr );
 883             assert( pNode != nullptr );
 884
 885             // Hack: convert node_type to value_type.
 886             // Actually, an auxiliary node should not be converted to value_type
 887             // We assume that comparator can correctly distinguish aux and regular node.
 888             return insert_at( pHead, *node_traits::to_value_ptr( pNode ));
 889         }
 890
 891         bool insert_at( node_type * pHead, value_type& val )
 892         {
 893             rcu_lock l;
 894             return insert_at_locked( pHead, val );
 895         }
 896
 897         template <typename Func>
 898         bool insert_at( node_type * pHead, value_type& val, Func f )
 899         {
 900             link_checker::is_empty( node_traits::to_node_ptr( val ));
 901             position pos;
 902             key_comparator  cmp;
 903
 904             rcu_lock l;
 905             while ( true ) {
 906                 search( pHead, val, pos );
 907                 {
 908                     scoped_position_lock sl( pos );
 909                     if ( validate( pos.pPred, pos.pCur )) {
 910                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
 911                             // failed: key already in list
 912                             return false;
 913                         }
 914
 915                         f( val );
 916                         link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 917                         ++m_ItemCounter;
 918                         return true;
 919                     }
 920                 }
 921             }
 922         }
 923
 924         iterator insert_at_( node_type * pHead, value_type& val )
 925         {
 926             rcu_lock l;
 927             if ( insert_at_locked( pHead, val ))
 928                 return iterator( node_traits::to_node_ptr( val ));
 929             return end();
 930         }
 931
 932
 933         template <typename Func>
 934         std::pair<iterator, bool> update_at_( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
 935         {
 936             rcu_lock l;
 937             return update_at_locked( pHead, val, func, bAllowInsert );
 938         }
 939
 940         template <typename Func>
 941         std::pair<bool, bool> update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
 942         {
 943             rcu_lock l;
 944             std::pair<iterator, bool> ret = update_at_locked( pHead, val, func, bAllowInsert );
 945             return std::make_pair( ret.first != end(), ret.second );
 946         }
 947
 948         bool unlink_at( node_type * pHead, value_type& val )
 949         {
 950             position pos;
 951             key_comparator  cmp;
 952             deadlock_policy::check();
 953
 954             while ( true ) {
 955                 int nResult = 0;
 956                 {
 957                     rcu_lock l;
 958                     search( pHead, val, pos );
 959                     {
 960                         scoped_position_lock alp( pos );
 961                         if ( validate( pos.pPred, pos.pCur )) {
 962                             if ( pos.pCur != &m_Tail
 963                                 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
 964                                 && node_traits::to_value_ptr( pos.pCur ) == &val )
 965                             {
 966                                 // item found
 967                                 unlink_node( pos.pPred, pos.pCur, pHead );
 968                                 --m_ItemCounter;
 969                                 nResult = 1;
 970                             }
 971                             else
 972                                 nResult = -1;
 973                         }
 974                     }
 975                 }
 976
 977                 if ( nResult ) {
 978                     if ( nResult > 0 ) {
 979                         dispose_node( pos.pCur );
 980                         return true;
 981                     }
 982                     return false;
 983                 }
 984             }
 985         }
 986
 987         template <typename Q, typename Compare, typename Func>
 988         bool erase_at( node_type * const pHead, Q const& val, Compare cmp, Func f, position& pos )
 989         {
 990             deadlock_policy::check();
 991
 992             while ( true ) {
 993                 int nResult = 0;
 994                 {
 995                     rcu_lock l;
 996                     search( pHead, val, pos, cmp );
 997                     {
 998                         scoped_position_lock alp( pos );
 999                         if ( validate( pos.pPred, pos.pCur )) {
1000                             if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1001                                 // key found
1002                                 unlink_node( pos.pPred, pos.pCur, pHead );
1003                                 f( *node_traits::to_value_ptr( *pos.pCur ));
1004                                 --m_ItemCounter;
1005                                 nResult = 1;
1006                             }
1007                             else
1008                                 nResult = -1;
1009                         }
1010                     }
1011                 }
1012
1013                 if ( nResult ) {
1014                     if ( nResult > 0 ) {
1015                         dispose_node( pos.pCur );
1016                         return true;
1017                     }
1018                     return false;
1019                 }
1020             }
1021         }
1022
1023         template <typename Q, typename Compare, typename Func>
1024         bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f )
1025         {
1026             position pos;
1027             return erase_at( pHead, val, cmp, f, pos );
1028         }
1029
1030         template <typename Q, typename Compare>
1031         bool erase_at( node_type * pHead, Q const& val, Compare cmp )
1032         {
1033             position pos;
1034             return erase_at( pHead, val, cmp, [](value_type const&){}, pos );
1035         }
1036
1037         template <typename Q, typename Compare>
1038         value_type * extract_at( node_type * const pHead, Q const& val, Compare cmp )
1039         {
1040             position pos;
1041             assert( gc::is_locked()) ; // RCU must be locked
1042
1043             while ( true ) {
1044                 search( pHead, val, pos, cmp );
1045                 int nResult = 0;
1046                 {
1047                     scoped_position_lock alp( pos );
1048                     if ( validate( pos.pPred, pos.pCur )) {
1049                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1050                             // key found
1051                             unlink_node( pos.pPred, pos.pCur, pHead );
1052                             --m_ItemCounter;
1053                             nResult = 1;
1054                         }
1055                         else {
1056                             nResult = -1;
1057                         }
1058                     }
1059                 }
1060
1061                 if ( nResult ) {
1062                     if ( nResult > 0 )
1063                         return node_traits::to_value_ptr( pos.pCur );
1064                     return nullptr;
1065                 }
1066             }
1067         }
1068
1069         template <typename Q, typename Compare, typename Func>
1070         bool find_at( node_type * pHead, Q& val, Compare cmp, Func f ) const
1071         {
1072             position pos;
1073
1074             rcu_lock l;
1075             search( pHead, val, pos, cmp );
1076             if ( pos.pCur != &m_Tail ) {
1077                 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1078                 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1079                 {
1080                     f( *node_traits::to_value_ptr( *pos.pCur ), val );
1081                     return true;
1082                 }
1083             }
1084             return false;
1085         }
1086
1087         template <typename Q, typename Compare>
1088         bool find_at( node_type * pHead, Q& val, Compare cmp ) const
1089         {
1090             rcu_lock l;
1091             return find_at_( pHead, val, cmp ) != end();
1092         }
1093
1094         template <typename Q, typename Compare>
1095         const_iterator find_at_( node_type * pHead, Q& val, Compare cmp ) const
1096         {
1097             assert( gc::is_locked());
1098
1099             position pos;
1100
1101             search( pHead, val, pos, cmp );
1102             if ( pos.pCur != &m_Tail ) {
1103                 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1104                     return const_iterator( pos.pCur );
1105             }
1106             return end();
1107         }
1108
1109         template <typename Q, typename Compare>
1110         value_type * get_at( node_type * pHead, Q const& val, Compare cmp ) const
1111         {
1112             value_type * pFound = nullptr;
1113             return find_at( pHead, val, cmp, [&pFound](value_type& found, Q const& ) { pFound = &found; } )
1114                 ? pFound : nullptr;
1115         }
1116
1117         //@endcond
1118
1119     protected:
1120         //@cond
1121         template <typename Q>
1122         void search( node_type * const pHead, Q const& key, position& pos ) const
1123         {
1124             search( pHead, key, pos, key_comparator());
1125         }
1126
1127         template <typename Q, typename Compare>
1128         void search( node_type * const pHead, Q const& key, position& pos, Compare cmp ) const
1129         {
1130             // RCU should be locked
1131             assert( gc::is_locked());
1132
1133             node_type const* pTail = &m_Tail;
1134
1135             marked_node_ptr pCur(pHead);
1136             marked_node_ptr pPrev(pHead);
1137
1138             while ( pCur != pTail && ( pCur == pHead || cmp( *node_traits::to_value_ptr( *pCur.ptr()), key ) < 0 )) {
1139                 pPrev = pCur;
1140                 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
1141                 if ( pCur.bits())
1142                     pPrev = pCur = pHead;
1143             }
1144
1145             pos.pCur = pCur.ptr();
1146             pos.pPred = pPrev.ptr();
1147         }
1148
1149         static bool validate( node_type * pPred, node_type * pCur ) CDS_NOEXCEPT
1150         {
1151             // RCU lock should be locked
1152             assert( gc::is_locked());
1153
1154             return !pPred->is_marked()
1155                 && !pCur->is_marked()
1156                 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1157         }
1158
1159         //@endcond
1160
1161     private:
1162         //@cond
1163         bool insert_at_locked( node_type * pHead, value_type& val )
1164         {
1165             // RCU lock should be locked
1166             assert( gc::is_locked());
1167
1168             link_checker::is_empty( node_traits::to_node_ptr( val ));
1169             position pos;
1170             key_comparator  cmp;
1171
1172             while ( true ) {
1173                 search( pHead, val, pos );
1174                 {
1175                     scoped_position_lock alp( pos );
1176                     if ( validate( pos.pPred, pos.pCur )) {
1177                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1178                             // failed: key already in list
1179                             return false;
1180                         }
1181
1182                         link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
1183                         ++m_ItemCounter;
1184                         return true;
1185                     }
1186                 }
1187             }
1188         }
1189
1190         template <typename Func>
1191         std::pair<iterator, bool> update_at_locked( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
1192         {
1193             // RCU lock should be locked
1194             assert( gc::is_locked());
1195
1196             position pos;
1197             key_comparator  cmp;
1198
1199             while ( true ) {
1200                 search( pHead, val, pos );
1201                 {
1202                     scoped_position_lock alp( pos );
1203                     if ( validate( pos.pPred, pos.pCur )) {
1204                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1205                             // key already in the list
1206
1207                             func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
1208                             return std::make_pair( iterator( pos.pCur ), false );
1209                         }
1210                         else {
1211                             // new key
1212                             if ( !bAllowInsert )
1213                                 return std::make_pair( end(), false );
1214
1215                             link_checker::is_empty( node_traits::to_node_ptr( val ));
1216
1217                             func( true, val, val );
1218                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
1219                             ++m_ItemCounter;
1220                             return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
1221                         }
1222                     }
1223                 }
1224             }
1225         }
1226         //@endcond
1227     };
1228
1229 }}  // namespace cds::intrusive
1230
1231 #endif  // #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_RCU_H