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