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         //@cond
 388         template <typename Q, typename Func>
 389         bool find( Q const& key, Func f )
 390         {
 391             return find_at( &m_Head, key, key_comparator(), f );
 392         }
 393         //@endcond
 394
 395         /// Finds the key \p key using \p pred predicate for searching
 396         /**
 397             The function is an analog of \ref cds_intrusive_LazyList_nogc_find_func "find(Q&, Func)"
 398             but \p pred is used for key comparing.
 399             \p Less functor has the interface like \p std::less.
 400             \p pred must imply the same element order as the comparator used for building the list.
 401         */
 402         template <typename Q, typename Less, typename Func>
 403         bool find_with( Q& key, Less pred, Func f )
 404         {
 405             CDS_UNUSED( pred );
 406             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 407         }
 408         //@cond
 409         template <typename Q, typename Less, typename Func>
 410         bool find_with( Q const& key, Less pred, Func f )
 411         {
 412             CDS_UNUSED( pred );
 413             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 414         }
 415         //@endcond
 416
 417         /// Finds the key \p key
 418         /** \anchor cds_intrusive_LazyList_nogc_find_val
 419             The function searches the item with key equal to \p key
 420             and returns pointer to value found or \p nullptr.
 421         */
 422         template <typename Q>
 423         value_type * find( Q const& key )
 424         {
 425             return find_at( &m_Head, key, key_comparator() );
 426         }
 427
 428         /// Finds the key \p key using \p pred predicate for searching
 429         /**
 430             The function is an analog of \ref cds_intrusive_LazyList_nogc_find_val "find(Q const&)"
 431             but \p pred is used for key comparing.
 432             \p Less functor has the interface like \p std::less.
 433             \p pred must imply the same element order as the comparator used for building the list.
 434         */
 435         template <typename Q, typename Less>
 436         value_type * find_with( Q const& key, Less pred )
 437         {
 438             CDS_UNUSED( pred );
 439             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>() );
 440         }
 441
 442         /// Clears the list
 443         /**
 444             The function unlink all items from the list.
 445             For each unlinked item the item disposer \p disp is called after unlinking.
 446
 447             This function is not thread-safe.
 448         */
 449         template <typename Disposer>
 450         void clear( Disposer disp )
 451         {
 452             node_type * pHead = m_Head.m_pNext.exchange( &m_Tail, memory_model::memory_order_release );
 453
 454             while ( pHead != &m_Tail ) {
 455                 node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed);
 456                 dispose_node( pHead, disp );
 457                 pHead = p;
 458             }
 459         }
 460
 461         /// Clears the list using default disposer
 462         /**
 463             The function clears the list using default (provided in class template) disposer functor.
 464         */
 465         void clear()
 466         {
 467             clear( disposer() );
 468         }
 469
 470         /// Checks if the list is empty
 471         bool empty() const
 472         {
 473             return m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail;
 474         }
 475
 476         /// Returns list's item count
 477         /**
 478             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 479             this function always returns 0.
 480
 481             <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
 482             is empty. To check list emptyness use \ref empty() method.
 483         */
 484         size_t size() const
 485         {
 486             return m_ItemCounter.value();
 487         }
 488
 489     protected:
 490         //@cond
 491         // split-list support
 492         bool insert_aux_node( node_type * pNode )
 493         {
 494             return insert_aux_node( &m_Head, pNode );
 495         }
 496
 497         // split-list support
 498         bool insert_aux_node( node_type * pHead, node_type * pNode )
 499         {
 500             assert( pHead != nullptr );
 501             assert( pNode != nullptr );
 502
 503             // Hack: convert node_type to value_type.
 504             // In principle, auxiliary node can be non-reducible to value_type
 505             // We assume that comparator can correctly distinguish aux and regular node.
 506             return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
 507         }
 508
 509         bool insert_at( node_type * pHead, value_type& val )
 510         {
 511             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 512             position pos;
 513             key_comparator  cmp;
 514
 515             while ( true ) {
 516                 search( pHead, val, pos, key_comparator() );
 517                 {
 518                     auto_lock_position alp( pos );
 519                     if ( validate( pos.pPred, pos.pCur )) {
 520                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
 521                             // failed: key already in list
 522                             return false;
 523                         }
 524                         else {
 525                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 526                             ++m_ItemCounter;
 527                             return true;
 528                         }
 529                     }
 530                 }
 531             }
 532         }
 533
 534         iterator insert_at_( node_type * pHead, value_type& val )
 535         {
 536             if ( insert_at( pHead, val ))
 537                 return iterator( node_traits::to_node_ptr( val ));
 538             return end();
 539         }
 540
 541
 542         template <typename Func>
 543         std::pair<iterator, bool> ensure_at_( node_type * pHead, value_type& val, Func func )
 544         {
 545             position pos;
 546             key_comparator  cmp;
 547
 548             while ( true ) {
 549                 search( pHead, val, pos, key_comparator() );
 550                 {
 551                     auto_lock_position alp( pos );
 552                     if ( validate( pos.pPred, pos.pCur )) {
 553                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
 554                             // key already in the list
 555
 556                             func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
 557                             return std::make_pair( iterator( pos.pCur ), false );
 558                         }
 559                         else {
 560                             // new key
 561                             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 562
 563                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 564                             func( true, val, val );
 565                             ++m_ItemCounter;
 566                             return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
 567                         }
 568                     }
 569                 }
 570             }
 571         }
 572
 573         template <typename Func>
 574         std::pair<bool, bool> ensure_at( node_type * pHead, value_type& val, Func func )
 575         {
 576             std::pair<iterator, bool> ret = ensure_at_( pHead, val, func );
 577             return std::make_pair( ret.first != end(), ret.second );
 578         }
 579
 580         template <typename Q, typename Compare, typename Func>
 581         bool find_at( node_type * pHead, Q& val, Compare cmp, Func f )
 582         {
 583             position pos;
 584
 585             search( pHead, val, pos, cmp );
 586             if ( pos.pCur != &m_Tail ) {
 587                 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
 588                 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
 589                 {
 590                     f( *node_traits::to_value_ptr( *pos.pCur ), val );
 591                     return true;
 592                 }
 593             }
 594             return false;
 595         }
 596
 597         template <typename Q, typename Compare>
 598         value_type * find_at( node_type * pHead, Q& val, Compare cmp)
 599         {
 600             iterator it = find_at_( pHead, val, cmp );
 601             if ( it != end() )
 602                 return &*it;
 603             return nullptr;
 604         }
 605
 606         template <typename Q, typename Compare>
 607         iterator find_at_( node_type * pHead, Q& val, Compare cmp)
 608         {
 609             position pos;
 610
 611             search( pHead, val, pos, cmp );
 612             if ( pos.pCur != &m_Tail ) {
 613                 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
 614                 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
 615                 {
 616                     return iterator( pos.pCur );
 617                 }
 618             }
 619             return end();
 620         }
 621
 622         //@endcond
 623
 624     protected:
 625         //@cond
 626         template <typename Q, typename Compare>
 627         void search( node_type * pHead, const Q& key, position& pos, Compare cmp )
 628         {
 629             const node_type * pTail = &m_Tail;
 630
 631             node_type * pCur = pHead;
 632             node_type * pPrev = pHead;
 633
 634             while ( pCur != pTail && ( pCur == pHead || cmp( *node_traits::to_value_ptr( *pCur ), key ) < 0 )) {
 635                 pPrev = pCur;
 636                 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
 637             }
 638
 639             pos.pCur = pCur;
 640             pos.pPred = pPrev;
 641         }
 642
 643         static bool validate( node_type * pPred, node_type * pCur )
 644         {
 645             return pPred->m_pNext.load(memory_model::memory_order_acquire) == pCur;
 646         }
 647
 648         //@endcond
 649     };
 650
 651 }}  // namespace cds::intrusive
 652
 653 #endif  // #ifndef __CDS_INTRUSIVE_LAZY_LIST_NOGC_H