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