cds/intrusive/lazy_list_nogc.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_LAZY_LIST_NOGC_H
   4 #define __CDS_INTRUSIVE_LAZY_LIST_NOGC_H
   5
   6 #include <mutex>        // unique_lock
   7 #include <cds/intrusive/details/lazy_list_base.h>
   8 #include <cds/gc/nogc.h>
   9
  10 namespace cds { namespace intrusive {
  11     namespace lazy_list {
  12         /// Lazy list node for gc::nogc
  13         /**
  14             Template parameters:
  15             - Tag - a tag used to distinguish between different implementation
  16         */
  17         template <typename Lock, typename Tag>
  18         struct node<gc::nogc, Lock, Tag>
  19         {
  20             typedef gc::nogc    gc          ;   ///< Garbage collector
  21             typedef Lock        lock_type   ;   ///< Lock type
  22             typedef Tag         tag         ;   ///< tag
  23
  24             atomics::atomic<node *> m_pNext ; ///< pointer to the next node in the list
  25             mutable lock_type   m_Lock  ; ///< Node lock
  26
  27             node()
  28                 : m_pNext( nullptr )
  29             {}
  30         };
  31     }   // namespace lazy_list
  32
  33
  34     /// Lazy ordered single-linked list (template specialization for gc::nogc)
  35     /** @ingroup cds_intrusive_list
  36         \anchor cds_intrusive_LazyList_nogc
  37
  38         This specialization is intended for so-called persistent usage when no item
  39         reclamation may be performed. The class does not support deleting of list item.
  40
  41         See \ref cds_intrusive_LazyList_hp "LazyList" for description of template parameters.
  42
  43         The interface of the specialization is a slightly different.
  44
  45         The gc::nogc specialization of LazyList accepts following template argument list
  46         \p Options of cds::intrusive::lazy_list::make_traits metafunction:
  47         - opt::hook - hook used. Possible values are: lazy_list::base_hook, lazy_list::member_hook, lazy_list::traits_hook.
  48             If the option is not specified, <tt>lazy_list::base_hook<></tt> and gc::HP is used.
  49         - opt::compare - key comparison functor. No default functor is provided.
  50             If the option is not specified, the opt::less is used.
  51         - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
  52         - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
  53         - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer. The disposer
  54             provided is used only in \ref clear() function.
  55         - opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link
  56         - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
  57         - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
  58             or opt::v::sequential_consistent (sequentially consisnent memory model).
  59
  60         The opt::allocator and opt::back_off is not used for this specialization.
  61
  62     */
  63     template <
  64         typename T
  65 #ifdef CDS_DOXYGEN_INVOKED
  66         ,class Traits = lazy_list::type_traits
  67 #else
  68         ,class Traits
  69 #endif
  70     >
  71     class LazyList<gc::nogc, T, Traits>
  72     {
  73     public:
  74         typedef T       value_type      ;   ///< type of value stored in the list
  75         typedef Traits  options         ;   ///< Traits template parameter
  76
  77         typedef typename options::hook      hook        ;   ///< hook type
  78         typedef typename hook::node_type    node_type   ;   ///< node type
  79
  80 #   ifdef CDS_DOXYGEN_INVOKED
  81         typedef implementation_defined key_comparator  ;    ///< key comparison functor based on opt::compare and opt::less option setter.
  82 #   else
  83         typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
  84 #   endif
  85
  86         typedef typename options::disposer  disposer    ;   ///< disposer used
  87         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ;    ///< node traits
  88         typedef typename lazy_list::get_link_checker< node_type, options::link_checker >::type link_checker   ;   ///< link checker
  89
  90         typedef gc::nogc  gc    ;   ///< Garbage collector
  91         typedef typename options::back_off  back_off        ;   ///< back-off strategy (not used)
  92         typedef typename options::item_counter item_counter ;   ///< Item counting policy used
  93         typedef typename options::memory_model  memory_model;   ///< C++ memory ordering (see lazy_list::type_traits::memory_model)
  94
  95         //@cond
  96         // Rebind options (split-list support)
  97         template <typename... Options>
  98         struct rebind_options {
  99             typedef LazyList<
 100                 gc
 101                 , value_type
 102                 , typename cds::opt::make_options< options, Options...>::type
 103             >   type;
 104         };
 105         //@endcond
 106
 107     protected:
 108         typedef node_type *     auxiliary_head   ;   ///< Auxiliary head type (for split-list support)
 109
 110     protected:
 111         node_type       m_Head ;            ///< List head (dummy node)
 112         node_type       m_Tail;             ///< List tail (dummy node)
 113         item_counter    m_ItemCounter   ;   ///< Item counter
 114
 115         //@cond
 116
 117         /// Position pointer for item search
 118         struct position {
 119             node_type *     pPred   ;    ///< Previous node
 120             node_type *     pCur    ;    ///< Current node
 121
 122             /// Locks nodes \p pPred and \p pCur
 123             void lock()
 124             {
 125                 pPred->m_Lock.lock();
 126                 pCur->m_Lock.lock();
 127             }
 128
 129             /// Unlocks nodes \p pPred and \p pCur
 130             void unlock()
 131             {
 132                 pCur->m_Lock.unlock();
 133                 pPred->m_Lock.unlock();
 134             }
 135         };
 136
 137         class auto_lock_position {
 138             position&   m_pos;
 139         public:
 140             auto_lock_position( position& pos )
 141                 : m_pos(pos)
 142             {
 143                 pos.lock();
 144             }
 145             ~auto_lock_position()
 146             {
 147                 m_pos.unlock();
 148             }
 149         };
 150         //@endcond
 151
 152     protected:
 153         //@cond
 154         void clear_links( node_type * pNode )
 155         {
 156             pNode->m_pNext.store( nullptr, memory_model::memory_order_relaxed );
 157         }
 158
 159         template <class Disposer>
 160         void dispose_node( node_type * pNode, Disposer disp )
 161         {
 162             clear_links( pNode );
 163             disp( node_traits::to_value_ptr( *pNode ));
 164         }
 165
 166         template <class Disposer>
 167         void dispose_value( value_type& val, Disposer disp )
 168         {
 169             dispose_node( node_traits::to_node_ptr( val ), disp );
 170         }
 171
 172         void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
 173         {
 174             assert( pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur );
 175
 176             pNode->m_pNext.store( pCur, memory_model::memory_order_release );
 177             pPred->m_pNext.store( pNode, memory_model::memory_order_release );
 178         }
 179         //@endcond
 180
 181     protected:
 182         //@cond
 183         template <bool IsConst>
 184         class iterator_type
 185         {
 186             friend class LazyList;
 187
 188         protected:
 189             value_type * m_pNode;
 190
 191             void next()
 192             {
 193                 assert( m_pNode != nullptr );
 194
 195                 node_type * pNode = node_traits::to_node_ptr( m_pNode );
 196                 node_type * pNext = pNode->m_pNext.load(memory_model::memory_order_relaxed);
 197                 if ( pNext != nullptr )
 198                     m_pNode = node_traits::to_value_ptr( pNext );
 199             }
 200
 201             iterator_type( node_type * pNode )
 202             {
 203                 m_pNode = node_traits::to_value_ptr( pNode );
 204             }
 205
 206         public:
 207             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 208             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 209
 210             iterator_type()
 211                 : m_pNode( nullptr )
 212             {}
 213
 214             iterator_type( const iterator_type& src )
 215                 : m_pNode( src.m_pNode )
 216             {}
 217
 218             value_ptr operator ->() const
 219             {
 220                 return m_pNode;
 221             }
 222
 223             value_ref operator *() const
 224             {
 225                 assert( m_pNode != nullptr );
 226                 return *m_pNode;
 227             }
 228
 229             /// Pre-increment
 230             iterator_type& operator ++()
 231             {
 232                 next();
 233                 return *this;
 234             }
 235
 236             /// Post-increment
 237             iterator_type operator ++(int)
 238             {
 239                 iterator_type i(*this);
 240                 next();
 241                 return i;
 242             }
 243
 244             iterator_type& operator = (const iterator_type& src)
 245             {
 246                 m_pNode = src.m_pNode;
 247                 return *this;
 248             }
 249
 250             template <bool C>
 251             bool operator ==(iterator_type<C> const& i ) const
 252             {
 253                 return m_pNode == i.m_pNode;
 254             }
 255             template <bool C>
 256             bool operator !=(iterator_type<C> const& i ) const
 257             {
 258                 return m_pNode != i.m_pNode;
 259             }
 260         };
 261         //@endcond
 262
 263     public:
 264         /// Forward iterator
 265         typedef iterator_type<false>    iterator;
 266         /// Const forward iterator
 267         typedef iterator_type<true>     const_iterator;
 268
 269         /// Returns a forward iterator addressing the first element in a list
 270         /**
 271             For empty list \code begin() == end() \endcode
 272         */
 273         iterator begin()
 274         {
 275             iterator it( &m_Head );
 276             ++it        ;   // skip dummy head
 277             return it;
 278         }
 279
 280         /// Returns an iterator that addresses the location succeeding the last element in a list
 281         /**
 282             Do not use the value returned by <tt>end</tt> function to access any item.
 283
 284             The returned value can be used only to control reaching the end of the list.
 285             For empty list \code begin() == end() \endcode
 286         */
 287         iterator end()
 288         {
 289             return iterator( &m_Tail );
 290         }
 291
 292         /// Returns a forward const iterator addressing the first element in a list
 293         const_iterator begin() const
 294         {
 295             const_iterator it( const_cast<node_type *>( &m_Head ));
 296             ++it        ;   // skip dummy head
 297             return it;
 298         }
 299
 300         /// Returns an const iterator that addresses the location succeeding the last element in a list
 301         const_iterator end() const
 302         {
 303             return const_iterator( const_cast<node_type *>( &m_Tail ));
 304         }
 305
 306     public:
 307         /// Default constructor initializes empty list
 308         LazyList()
 309         {
 310             static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
 311
 312             m_Head.m_pNext.store( &m_Tail, memory_model::memory_order_relaxed );
 313         }
 314
 315         /// Destroys the list object
 316         ~LazyList()
 317         {
 318             clear();
 319
 320             assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail );
 321             m_Head.m_pNext.store( nullptr, memory_model::memory_order_relaxed );
 322         }
 323
 324         /// Inserts new node
 325         /**
 326             The function inserts \p val in the list if the list does not contain
 327             an item with key equal to \p val.
 328
 329             Returns \p true if \p val is linked into the list, \p false otherwise.
 330         */
 331         bool insert( value_type& val )
 332         {
 333             return insert_at( &m_Head, val );
 334         }
 335
 336         /// Ensures that the \p item exists in the list
 337         /**
 338             The operation performs inserting or changing data with lock-free manner.
 339
 340             If the item \p val not found in the list, then \p val is inserted into the list.
 341             Otherwise, the functor \p func is called with item found.
 342             The functor signature is:
 343             \code
 344             struct functor {
 345                 void operator()( bool bNew, value_type& item, value_type& val );
 346             };
 347             \endcode
 348             with arguments:
 349             - \p bNew - \p true if the item has been inserted, \p false otherwise
 350             - \p item - item of the list
 351             - \p val - argument \p val passed into the \p ensure function
 352             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 353             refers to the same thing.
 354
 355             The functor may change non-key fields of the \p item.
 356             While the functor \p f is calling the item \p item is locked.
 357
 358             You may pass \p func argument by reference using \p std::ref.
 359
 360             Returns <tt> std::pair<bool, bool>  </tt> where \p first is true if operation is successfull,
 361             \p second is true if new item has been added or \p false if the item with \p key
 362             already is in the list.
 363         */
 364
 365         template <typename Func>
 366         std::pair<bool, bool> ensure( value_type& val, Func func )
 367         {
 368             return ensure_at( &m_Head, val, func );
 369         }
 370
 371         /// Finds the key \p val
 372         /** \anchor cds_intrusive_LazyList_nogc_find_func
 373             The function searches the item with key equal to \p val
 374             and calls the functor \p f for item found.
 375             The interface of \p Func functor is:
 376             \code
 377             struct functor {
 378                 void operator()( value_type& item, Q& val );
 379             };
 380             \endcode
 381             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 382
 383             You may pass \p f argument by reference using \p std::ref.
 384
 385             The functor may change non-key fields of \p item.
 386             While the functor \p f is calling the item found \p item is locked.
 387
 388             The function returns \p true if \p val is found, \p false otherwise.
 389         */
 390         template <typename Q, typename Func>
 391         bool find( Q& val, Func f )
 392         {
 393             return find_at( &m_Head, val, key_comparator(), f );
 394         }
 395
 396         /// Finds the key \p val
 397         /** \anchor cds_intrusive_LazyList_nogc_find_cfunc
 398             The function searches the item with key equal to \p val
 399             and calls the functor \p f for item found.
 400             The interface of \p Func functor is:
 401             \code
 402             struct functor {
 403                 void operator()( value_type& item, Q const& val );
 404             };
 405             \endcode
 406             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 407
 408             You may pass \p f argument by reference using \p std::ref.
 409
 410             The functor may change non-key fields of \p item.
 411             While the functor \p f is calling the item found \p item is locked.
 412
 413             The function returns \p true if \p val is found, \p false otherwise.
 414         */
 415         template <typename Q, typename Func>
 416         bool find( Q const& val, Func f )
 417         {
 418             return find_at( &m_Head, val, key_comparator(), f );
 419         }
 420
 421         /// Finds the key \p val using \p pred predicate for searching
 422         /**
 423             The function is an analog of \ref cds_intrusive_LazyList_nogc_find_cfunc "find(Q const&, Func)"
 424             but \p pred is used for key comparing.
 425             \p Less functor has the interface like \p std::less.
 426             \p pred must imply the same element order as the comparator used for building the list.
 427         */
 428         template <typename Q, typename Less, typename Func>
 429         bool find_with( Q const& val, Less pred, Func f )
 430         {
 431             return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>(), f );
 432         }
 433
 434         /// Finds the key \p val using \p pred predicate for searching
 435         /**
 436             The function is an analog of \ref cds_intrusive_LazyList_nogc_find_func "find(Q&, Func)"
 437             but \p pred is used for key comparing.
 438             \p Less functor has the interface like \p std::less.
 439             \p pred must imply the same element order as the comparator used for building the list.
 440         */
 441         template <typename Q, typename Less, typename Func>
 442         bool find_with( Q& val, Less pred, Func f )
 443         {
 444             return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>(), f );
 445         }
 446
 447         /// Finds the key \p val
 448         /** \anchor cds_intrusive_LazyList_nogc_find_val
 449             The function searches the item with key equal to \p val
 450             and returns pointer to value found or \p nullptr.
 451         */
 452         template <typename Q>
 453         value_type * find( Q const& val )
 454         {
 455             return find_at( &m_Head, val, key_comparator() );
 456         }
 457
 458         /// Finds the key \p val using \p pred predicate for searching
 459         /**
 460             The function is an analog of \ref cds_intrusive_LazyList_nogc_find_val "find(Q const&)"
 461             but \p pred is used for key comparing.
 462             \p Less functor has the interface like \p std::less.
 463             \p pred must imply the same element order as the comparator used for building the list.
 464         */
 465         template <typename Q, typename Less>
 466         value_type * find_with( Q const & val, Less pred )
 467         {
 468             return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>() );
 469         }
 470
 471         /// Clears the list
 472         /**
 473             The function unlink all items from the list.
 474             For each unlinked item the item disposer \p disp is called after unlinking.
 475
 476             This function is not thread-safe.
 477         */
 478         template <typename Disposer>
 479         void clear( Disposer disp )
 480         {
 481             node_type * pHead = m_Head.m_pNext.exchange( &m_Tail, memory_model::memory_order_release );
 482
 483             while ( pHead != &m_Tail ) {
 484                 node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed);
 485                 dispose_node( pHead, disp );
 486                 pHead = p;
 487             }
 488         }
 489
 490         /// Clears the list using default disposer
 491         /**
 492             The function clears the list using default (provided in class template) disposer functor.
 493         */
 494         void clear()
 495         {
 496             clear( disposer() );
 497         }
 498
 499         /// Checks if the list is empty
 500         bool empty() const
 501         {
 502             return m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail;
 503         }
 504
 505         /// Returns list's item count
 506         /**
 507             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 508             this function always returns 0.
 509
 510             <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
 511             is empty. To check list emptyness use \ref empty() method.
 512         */
 513         size_t size() const
 514         {
 515             return m_ItemCounter.value();
 516         }
 517
 518     protected:
 519         //@cond
 520         // split-list support
 521         bool insert_aux_node( node_type * pNode )
 522         {
 523             return insert_aux_node( &m_Head, pNode );
 524         }
 525
 526         // split-list support
 527         bool insert_aux_node( node_type * pHead, node_type * pNode )
 528         {
 529             assert( pHead != nullptr );
 530             assert( pNode != nullptr );
 531
 532             // Hack: convert node_type to value_type.
 533             // In principle, auxiliary node can be non-reducible to value_type
 534             // We assume that comparator can correctly distinguish aux and regular node.
 535             return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
 536         }
 537
 538         bool insert_at( node_type * pHead, value_type& val )
 539         {
 540             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 541             position pos;
 542             key_comparator  cmp;
 543
 544             while ( true ) {
 545                 search( pHead, val, pos, key_comparator() );
 546                 {
 547                     auto_lock_position alp( pos );
 548                     if ( validate( pos.pPred, pos.pCur )) {
 549                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
 550                             // failed: key already in list
 551                             return false;
 552                         }
 553                         else {
 554                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 555                             ++m_ItemCounter;
 556                             return true;
 557                         }
 558                     }
 559                 }
 560             }
 561         }
 562
 563         iterator insert_at_( node_type * pHead, value_type& val )
 564         {
 565             if ( insert_at( pHead, val ))
 566                 return iterator( node_traits::to_node_ptr( val ));
 567             return end();
 568         }
 569
 570
 571         template <typename Func>
 572         std::pair<iterator, bool> ensure_at_( node_type * pHead, value_type& val, Func func )
 573         {
 574             position pos;
 575             key_comparator  cmp;
 576
 577             while ( true ) {
 578                 search( pHead, val, pos, key_comparator() );
 579                 {
 580                     auto_lock_position alp( pos );
 581                     if ( validate( pos.pPred, pos.pCur )) {
 582                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
 583                             // key already in the list
 584
 585                             func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
 586                             return std::make_pair( iterator( pos.pCur ), false );
 587                         }
 588                         else {
 589                             // new key
 590                             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 591
 592                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 593                             func( true, val, val );
 594                             ++m_ItemCounter;
 595                             return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
 596                         }
 597                     }
 598                 }
 599             }
 600         }
 601
 602         template <typename Func>
 603         std::pair<bool, bool> ensure_at( node_type * pHead, value_type& val, Func func )
 604         {
 605             std::pair<iterator, bool> ret = ensure_at_( pHead, val, func );
 606             return std::make_pair( ret.first != end(), ret.second );
 607         }
 608
 609         template <typename Q, typename Compare, typename Func>
 610         bool find_at( node_type * pHead, Q& val, Compare cmp, Func f )
 611         {
 612             position pos;
 613
 614             search( pHead, val, pos, cmp );
 615             if ( pos.pCur != &m_Tail ) {
 616                 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
 617                 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
 618                 {
 619                     f( *node_traits::to_value_ptr( *pos.pCur ), val );
 620                     return true;
 621                 }
 622             }
 623             return false;
 624         }
 625
 626         template <typename Q, typename Compare>
 627         value_type * find_at( node_type * pHead, Q& val, Compare cmp)
 628         {
 629             iterator it = find_at_( pHead, val, cmp );
 630             if ( it != end() )
 631                 return &*it;
 632             return nullptr;
 633         }
 634
 635         template <typename Q, typename Compare>
 636         iterator find_at_( node_type * pHead, Q& val, Compare cmp)
 637         {
 638             position pos;
 639
 640             search( pHead, val, pos, cmp );
 641             if ( pos.pCur != &m_Tail ) {
 642                 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
 643                 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
 644                 {
 645                     return iterator( pos.pCur );
 646                 }
 647             }
 648             return end();
 649         }
 650
 651         //@endcond
 652
 653     protected:
 654         //@cond
 655         template <typename Q, typename Compare>
 656         void search( node_type * pHead, const Q& key, position& pos, Compare cmp )
 657         {
 658             const node_type * pTail = &m_Tail;
 659
 660             node_type * pCur = pHead;
 661             node_type * pPrev = pHead;
 662
 663             while ( pCur != pTail && ( pCur == pHead || cmp( *node_traits::to_value_ptr( *pCur ), key ) < 0 )) {
 664                 pPrev = pCur;
 665                 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
 666             }
 667
 668             pos.pCur = pCur;
 669             pos.pPred = pPrev;
 670         }
 671
 672         static bool validate( node_type * pPred, node_type * pCur )
 673         {
 674             return pPred->m_pNext.load(memory_model::memory_order_acquire) == pCur;
 675         }
 676
 677         //@endcond
 678     };
 679
 680 }}  // namespace cds::intrusive
 681
 682 #endif  // #ifndef __CDS_INTRUSIVE_LAZY_LIST_NOGC_H