cds/intrusive/lazy_list_nogc.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_NOGC_H
   4 #define CDSLIB_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::sync::spin
  16              - Tag - a \ref cds_intrusive_hook_tag "tag"
  17         */
  18         template <
  19 #ifdef CDS_DOXYGEN_INVOKED
  20             typename Lock = cds::sync::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         typedef implementation_defined equal_to_comparator;
  73         typedef implementation_defined predicate_type;
  74 #   else
  75         typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
  76         typedef typename opt::details::make_equal_to< value_type, traits >::type equal_to_comparator;
  77         typedef typename std::conditional< traits::sort, key_comparator, equal_to_comparator >::type predicate_type;
  78 #   endif
  79         typedef typename traits::back_off  back_off;   ///< Back-off strategy
  80         typedef typename traits::disposer  disposer;   ///< disposer
  81         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits;    ///< node traits
  82         typedef typename lazy_list::get_link_checker< node_type, traits::link_checker >::type link_checker;   ///< link checker
  83
  84         typedef typename traits::item_counter item_counter;  ///< Item counting policy used
  85         typedef typename traits::memory_model  memory_model; ///< C++ memory ordering (see lazy_list::traits::memory_model)
  86
  87         //@cond
  88         // Rebind traits (split-list support)
  89         template <typename... Options>
  90         struct rebind_traits {
  91             typedef LazyList<
  92                 gc
  93                 , value_type
  94                 , typename cds::opt::make_options< traits, Options...>::type
  95             >   type;
  96         };
  97         //@endcond
  98
  99     protected:
 100         typedef node_type *     auxiliary_head   ;   ///< Auxiliary head type (for split-list support)
 101
 102     protected:
 103         node_type       m_Head;        ///< List head (dummy node)
 104         node_type       m_Tail;        ///< List tail (dummy node)
 105         item_counter    m_ItemCounter; ///< Item counter
 106
 107         //@cond
 108
 109         /// Position pointer for item search
 110         struct position {
 111             node_type *     pPred   ;    ///< Previous node
 112             node_type *     pCur    ;    ///< Current node
 113
 114             /// Locks nodes \p pPred and \p pCur
 115             void lock()
 116             {
 117                 pPred->m_Lock.lock();
 118                 pCur->m_Lock.lock();
 119             }
 120
 121             /// Unlocks nodes \p pPred and \p pCur
 122             void unlock()
 123             {
 124                 pCur->m_Lock.unlock();
 125                 pPred->m_Lock.unlock();
 126             }
 127         };
 128
 129         class auto_lock_position {
 130             position&   m_pos;
 131         public:
 132             auto_lock_position( position& pos )
 133                 : m_pos(pos)
 134             {
 135                 pos.lock();
 136             }
 137             ~auto_lock_position()
 138             {
 139                 m_pos.unlock();
 140             }
 141         };
 142         //@endcond
 143
 144     protected:
 145         //@cond
 146         void clear_links( node_type * pNode )
 147         {
 148             pNode->m_pNext.store( nullptr, memory_model::memory_order_relaxed );
 149         }
 150
 151         template <class Disposer>
 152         void dispose_node( node_type * pNode, Disposer disp )
 153         {
 154             clear_links( pNode );
 155             disp( node_traits::to_value_ptr( *pNode ));
 156         }
 157
 158         template <class Disposer>
 159         void dispose_value( value_type& val, Disposer disp )
 160         {
 161             dispose_node( node_traits::to_node_ptr( val ), disp );
 162         }
 163
 164         void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
 165         {
 166             assert( pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur );
 167
 168             pNode->m_pNext.store( pCur, memory_model::memory_order_release );
 169             pPred->m_pNext.store( pNode, memory_model::memory_order_release );
 170         }
 171         //@endcond
 172
 173     protected:
 174         //@cond
 175         template <bool IsConst>
 176         class iterator_type
 177         {
 178             friend class LazyList;
 179
 180         protected:
 181             value_type * m_pNode;
 182
 183             void next()
 184             {
 185                 assert( m_pNode != nullptr );
 186
 187                 node_type * pNode = node_traits::to_node_ptr( m_pNode );
 188                 node_type * pNext = pNode->m_pNext.load(memory_model::memory_order_relaxed);
 189                 if ( pNext != nullptr )
 190                     m_pNode = node_traits::to_value_ptr( pNext );
 191             }
 192
 193             iterator_type( node_type * pNode )
 194             {
 195                 m_pNode = node_traits::to_value_ptr( pNode );
 196             }
 197
 198         public:
 199             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 200             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 201
 202             iterator_type()
 203                 : m_pNode( nullptr )
 204             {}
 205
 206             iterator_type( const iterator_type& src )
 207                 : m_pNode( src.m_pNode )
 208             {}
 209
 210             value_ptr operator ->() const
 211             {
 212                 return m_pNode;
 213             }
 214
 215             value_ref operator *() const
 216             {
 217                 assert( m_pNode != nullptr );
 218                 return *m_pNode;
 219             }
 220
 221             /// Pre-increment
 222             iterator_type& operator ++()
 223             {
 224                 next();
 225                 return *this;
 226             }
 227
 228             /// Post-increment
 229             iterator_type operator ++(int)
 230             {
 231                 iterator_type i(*this);
 232                 next();
 233                 return i;
 234             }
 235
 236             iterator_type& operator = (const iterator_type& src)
 237             {
 238                 m_pNode = src.m_pNode;
 239                 return *this;
 240             }
 241
 242             template <bool C>
 243             bool operator ==(iterator_type<C> const& i ) const
 244             {
 245                 return m_pNode == i.m_pNode;
 246             }
 247             template <bool C>
 248             bool operator !=(iterator_type<C> const& i ) const
 249             {
 250                 return m_pNode != i.m_pNode;
 251             }
 252         };
 253         //@endcond
 254
 255     public:
 256         /// Forward iterator
 257         typedef iterator_type<false>    iterator;
 258         /// Const forward iterator
 259         typedef iterator_type<true>     const_iterator;
 260
 261         /// Returns a forward iterator addressing the first element in a list
 262         /**
 263             For empty list \code begin() == end() \endcode
 264         */
 265         iterator begin()
 266         {
 267             iterator it( &m_Head );
 268             ++it        ;   // skip dummy head
 269             return it;
 270         }
 271
 272         /// Returns an iterator that addresses the location succeeding the last element in a list
 273         /**
 274             Do not use the value returned by <tt>end</tt> function to access any item.
 275
 276             The returned value can be used only to control reaching the end of the list.
 277             For empty list \code begin() == end() \endcode
 278         */
 279         iterator end()
 280         {
 281             return iterator( &m_Tail );
 282         }
 283
 284         /// Returns a forward const iterator addressing the first element in a list
 285         const_iterator begin() const
 286         {
 287             return cbegin();
 288         }
 289         /// Returns a forward const iterator addressing the first element in a list
 290         const_iterator cbegin() const
 291         {
 292             const_iterator it( const_cast<node_type *>(&m_Head) );
 293             ++it;   // skip dummy head
 294             return it;
 295         }
 296
 297         /// Returns an const iterator that addresses the location succeeding the last element in a list
 298         const_iterator end() const
 299         {
 300             return cend();
 301         }
 302         /// Returns an const iterator that addresses the location succeeding the last element in a list
 303         const_iterator cend() const
 304         {
 305             return const_iterator( const_cast<node_type *>(&m_Tail) );
 306         }
 307
 308     public:
 309         /// Default constructor initializes empty list
 310         LazyList()
 311         {
 312             static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
 313             m_Head.m_pNext.store( &m_Tail, memory_model::memory_order_relaxed );
 314         }
 315
 316         /// Destroys the list object
 317         ~LazyList()
 318         {
 319             clear();
 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             Returns <tt> std::pair<bool, bool>  </tt> where \p first is true if operation is successfull,
 359             \p second is true if new item has been added or \p false if the item with \p key
 360             already is in the list.
 361         */
 362
 363         template <typename Func>
 364         std::pair<bool, bool> ensure( value_type& val, Func func )
 365         {
 366             return ensure_at( &m_Head, val, func );
 367         }
 368
 369         /// Finds the key \p key
 370         /** \anchor cds_intrusive_LazyList_nogc_find_func
 371             The function searches the item with key equal to \p key
 372             and calls the functor \p f for item found.
 373             The interface of \p Func functor is:
 374             \code
 375             struct functor {
 376                 void operator()( value_type& item, Q& key );
 377             };
 378             \endcode
 379             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 380
 381             The functor may change non-key fields of \p item.
 382             While the functor \p f is calling the item found \p item is locked.
 383
 384             The function returns \p true if \p key is found, \p false otherwise.
 385         */
 386         template <typename Q, typename Func>
 387         bool find( Q& key, Func f )
 388         {
 389             return find_at( &m_Head, key, predicate_type(), f );
 390         }
 391         //@cond
 392         template <typename Q, typename Func>
 393         bool find( Q const& key, Func f )
 394         {
 395             return find_at( &m_Head, key, predicate_type(), f );
 396         }
 397         //@endcond
 398
 399         /// Finds the key \p key using \p pred predicate for searching.
 400         /**
 401             The function is an analog of \ref cds_intrusive_LazyList_nogc_find_func "find(Q&, Func)"
 402             but \p pred is used for key comparing.
 403             \p Less functor has the interface like \p std::less.
 404             \p pred must imply the same element order as the comparator used for building the list.
 405         */
 406         template <typename Q, typename Less, typename Func, bool Sort = traits::sort>
 407         typename std::enable_if<Sort, bool>::type find_with( Q& key, Less pred, Func f )
 408         {
 409             CDS_UNUSED( pred );
 410             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 411         }
 412         //@cond
 413         template <typename Q, typename Less, typename Func, bool Sort = traits::sort>
 414         typename std::enable_if<Sort, bool>::type find_with( Q const& key, Less pred, Func f )
 415         {
 416             CDS_UNUSED( pred );
 417             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 418         }
 419         //@endcond
 420
 421         /// Finds the key \p key
 422         /** \anchor cds_intrusive_LazyList_nogc_find_val
 423             The function searches the item with key equal to \p key
 424             and returns pointer to value found or \p nullptr.
 425         */
 426         template <typename Q>
 427         value_type * find( Q const& key )
 428         {
 429             return find_at( &m_Head, key, predicate_type() );
 430         }
 431
 432         /// Finds the key \p key using \p pred predicate for searching. Disabled for unordered lists.
 433         /**
 434             The function is an analog of \ref cds_intrusive_LazyList_nogc_find_val "find(Q const&)"
 435             but \p pred is used for key comparing.
 436             \p Less functor has the interface like \p std::less.
 437             \p pred must imply the same element order as the comparator used for building the list.
 438         */
 439         template <typename Q, typename Less, bool Sort = traits::sort>
 440         typename std::enable_if<Sort, value_type *>::type find_with( Q const& key, Less pred )
 441         {
 442             CDS_UNUSED( pred );
 443             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>() );
 444         }
 445
 446         /// Clears the list
 447         /**
 448             The function unlink all items from the list.
 449             For each unlinked item the item disposer \p disp is called after unlinking.
 450
 451             This function is not thread-safe.
 452         */
 453         template <typename Disposer>
 454         void clear( Disposer disp )
 455         {
 456             node_type * pHead = m_Head.m_pNext.exchange( &m_Tail, memory_model::memory_order_release );
 457
 458             while ( pHead != &m_Tail ) {
 459                 node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed);
 460                 dispose_node( pHead, disp );
 461                 pHead = p;
 462             }
 463         }
 464
 465         /// Clears the list using default disposer
 466         /**
 467             The function clears the list using default (provided in class template) disposer functor.
 468         */
 469         void clear()
 470         {
 471             clear( disposer() );
 472         }
 473
 474         /// Checks if the list is empty
 475         bool empty() const
 476         {
 477             return m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail;
 478         }
 479
 480         /// Returns list's item count
 481         /**
 482             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 483             this function always returns 0.
 484
 485             <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
 486             is empty. To check list emptyness use \ref empty() method.
 487         */
 488         size_t size() const
 489         {
 490             return m_ItemCounter.value();
 491         }
 492
 493     protected:
 494         //@cond
 495         // split-list support
 496         bool insert_aux_node( node_type * pNode )
 497         {
 498             return insert_aux_node( &m_Head, pNode );
 499         }
 500
 501         // split-list support
 502         bool insert_aux_node( node_type * pHead, node_type * pNode )
 503         {
 504             assert( pHead != nullptr );
 505             assert( pNode != nullptr );
 506
 507             // Hack: convert node_type to value_type.
 508             // In principle, auxiliary node can be non-reducible to value_type
 509             // We assume that comparator can correctly distinguish aux and regular node.
 510             return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
 511         }
 512
 513         bool insert_at( node_type * pHead, value_type& val )
 514         {
 515             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 516             position pos;
 517             predicate_type pred;
 518
 519             while ( true ) {
 520                 search( pHead, val, pos, pred );
 521                 {
 522                     auto_lock_position alp( pos );
 523                     if ( validate( pos.pPred, pos.pCur )) {
 524                         if ( pos.pCur != &m_Tail && equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ) ) {
 525                             // failed: key already in list
 526                             return false;
 527                         }
 528                         else {
 529                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 530                             ++m_ItemCounter;
 531                             return true;
 532                         }
 533                     }
 534                 }
 535             }
 536         }
 537
 538         iterator insert_at_( node_type * pHead, value_type& val )
 539         {
 540             if ( insert_at( pHead, val ))
 541                 return iterator( node_traits::to_node_ptr( val ));
 542             return end();
 543         }
 544
 545
 546         template <typename Func>
 547         std::pair<iterator, bool> ensure_at_( node_type * pHead, value_type& val, Func func )
 548         {
 549             position pos;
 550             predicate_type pred;
 551
 552             while ( true ) {
 553                 search( pHead, val, pos, pred );
 554                 {
 555                     auto_lock_position alp( pos );
 556                     if ( validate( pos.pPred, pos.pCur )) {
 557                         if ( pos.pCur != &m_Tail && equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ) ) {
 558                             // key already in the list
 559
 560                             func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
 561                             return std::make_pair( iterator( pos.pCur ), false );
 562                         }
 563                         else {
 564                             // new key
 565                             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 566
 567                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 568                             func( true, val, val );
 569                             ++m_ItemCounter;
 570                             return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
 571                         }
 572                     }
 573                 }
 574             }
 575         }
 576
 577         template <typename Func>
 578         std::pair<bool, bool> ensure_at( node_type * pHead, value_type& val, Func func )
 579         {
 580             std::pair<iterator, bool> ret = ensure_at_( pHead, val, func );
 581             return std::make_pair( ret.first != end(), ret.second );
 582         }
 583
 584         template <typename Q, typename Pred, typename Func>
 585         bool find_at( node_type * pHead, Q& val, Pred pred, Func f )
 586         {
 587             position pos;
 588
 589             search( pHead, val, pos, pred );
 590             if ( pos.pCur != &m_Tail ) {
 591                 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
 592                 if ( equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ) )
 593                 {
 594                     f( *node_traits::to_value_ptr( *pos.pCur ), val );
 595                     return true;
 596                 }
 597             }
 598             return false;
 599         }
 600
 601         template <typename Q, typename Pred>
 602         value_type * find_at( node_type * pHead, Q& val, Pred pred)
 603         {
 604             iterator it = find_at_( pHead, val, pred );
 605             if ( it != end() )
 606                 return &*it;
 607             return nullptr;
 608         }
 609
 610         template <typename Q, typename Pred>
 611         iterator find_at_( node_type * pHead, Q& val, Pred pred)
 612         {
 613             position pos;
 614
 615             search( pHead, val, pos, pred );
 616             if ( pos.pCur != &m_Tail ) {
 617                 if ( equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ) )
 618                     return iterator( pos.pCur );
 619             }
 620             return end();
 621         }
 622
 623         //@endcond
 624
 625     protected:
 626         //@cond
 627         template <typename Q, typename Equal, bool Sort = traits::sort>
 628         typename std::enable_if<!Sort, void>::type search( node_type * pHead, const Q& key, position& pos, Equal eq )
 629         {
 630             const node_type * pTail = &m_Tail;
 631
 632             node_type * pCur = pHead;
 633             node_type * pPrev = pHead;
 634
 635             while ( pCur != pTail && ( pCur == pHead || !equal( *node_traits::to_value_ptr( *pCur ), key, eq ) )) {
 636                 pPrev = pCur;
 637                 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
 638             }
 639
 640             pos.pCur = pCur;
 641             pos.pPred = pPrev;
 642         }
 643
 644         template <typename Q, typename Compare, bool Sort = traits::sort>
 645         typename std::enable_if<Sort, void>::type search( node_type * pHead, const Q& key, position& pos, Compare cmp )
 646         {
 647             const node_type * pTail = &m_Tail;
 648
 649             node_type * pCur = pHead;
 650             node_type * pPrev = pHead;
 651
 652             while ( pCur != pTail && ( pCur == pHead || cmp( *node_traits::to_value_ptr( *pCur ), key ) < 0 )) {
 653                 pPrev = pCur;
 654                 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
 655             }
 656
 657             pos.pCur = pCur;
 658             pos.pPred = pPrev;
 659         }
 660
 661         template <typename L, typename R, typename Equal, bool Sort = traits::sort>
 662         static typename std::enable_if<!Sort, bool>::type equal( L const& l, R const& r, Equal eq )
 663         {
 664             return eq(l, r);
 665         }
 666
 667         template <typename L, typename R, typename Compare, bool Sort = traits::sort>
 668         static typename std::enable_if<Sort, bool>::type equal( L const& l, R const& r, Compare cmp )
 669         {
 670             return cmp(l, r) == 0;
 671         }
 672
 673         static bool validate( node_type * pPred, node_type * pCur )
 674         {
 675             return pPred->m_pNext.load(memory_model::memory_order_acquire) == pCur;
 676         }
 677
 678         //@endcond
 679     };
 680
 681 }}  // namespace cds::intrusive
 682
 683 #endif  // #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_NOGC_H