cds/intrusive/michael_list_nogc.h

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