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
 359         /// Finds the key \p key using \p pred predicate for searching
 360         /**
 361             The function is an analog of \ref cds_intrusive_MichaelList_nogc_find_func "find(Q&, Func)"
 362             but \p pred is used for key comparing.
 363             \p Less functor has the interface like \p std::less.
 364             \p pred must imply the same element order as the comparator used for building the list.
 365         */
 366         template <typename Q, typename Less, typename Func>
 367         bool find_with( Q& key, Less pred, Func f )
 368         {
 369             return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 370         }
 371
 372         /// Finds \p key
 373         /** \anchor cds_intrusive_MichaelList_nogc_find_val
 374             The function searches the item with key equal to \p key
 375             and returns pointer to value found or \p nullptr.
 376         */
 377         template <typename Q>
 378         value_type * find( Q const& key )
 379         {
 380             return find_at( m_pHead, key, key_comparator() );
 381         }
 382
 383         /// Finds \p key using \p pred predicate for searching
 384         /**
 385             The function is an analog of \ref cds_intrusive_MichaelList_nogc_find_val "find(Q const&, Func)"
 386             but \p pred is used for key comparing.
 387             \p Less functor has the interface like \p std::less.
 388             \p pred must imply the same element order as the comparator used for building the list.
 389         */
 390         template <typename Q, typename Less>
 391         value_type * find_with( Q const& key, Less pred )
 392         {
 393             return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
 394         }
 395
 396         /// Clears the list
 397         /**
 398             The function unlink all items from the list.
 399
 400             For each unlinked item the item disposer \p disp is called after unlinking.
 401         */
 402         template <typename Disposer>
 403         void clear( Disposer disp )
 404         {
 405             node_type * pHead = m_pHead.load(memory_model::memory_order_relaxed);
 406             do {} while ( !m_pHead.compare_exchange_weak( pHead, nullptr, memory_model::memory_order_relaxed ) );
 407
 408             while ( pHead ) {
 409                 node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed);
 410                 dispose_node( pHead, disp );
 411                 pHead = p;
 412                 --m_ItemCounter;
 413             }
 414         }
 415
 416         /// Clears the list using default disposer
 417         /**
 418             The function clears the list using default (provided in class template) disposer functor.
 419         */
 420         void clear()
 421         {
 422             clear( disposer() );
 423         }
 424
 425         /// Checks if the list is empty
 426         bool empty() const
 427         {
 428             return m_pHead.load( memory_model::memory_order_relaxed ) == nullptr;
 429         }
 430
 431         /// Returns list's item count
 432         /**
 433             The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
 434             this function always returns 0.
 435
 436             @note Even if you use real item counter and it returns 0, this fact does not mean that the list
 437             is empty. To check list emptyness use \p empty() method.
 438         */
 439         size_t size() const
 440         {
 441             return m_ItemCounter.value();
 442         }
 443
 444     protected:
 445         //@cond
 446         // split-list support
 447         bool insert_aux_node( node_type * pNode )
 448         {
 449             return insert_aux_node( m_pHead, pNode );
 450         }
 451
 452         // split-list support
 453         bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
 454         {
 455             assert( pNode != nullptr );
 456
 457             // Hack: convert node_type to value_type.
 458             // In principle, auxiliary node can be non-reducible to value_type
 459             // We assume that comparator can correctly distinguish aux and regular node.
 460             return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
 461         }
 462
 463         bool insert_at( atomic_node_ptr& refHead, value_type& val )
 464         {
 465             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 466             position pos;
 467
 468             while ( true ) {
 469                 if ( search( refHead, val, key_comparator(), pos ) )
 470                     return false;
 471
 472                 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
 473                     ++m_ItemCounter;
 474                     return true;
 475                 }
 476             }
 477         }
 478
 479         iterator insert_at_( atomic_node_ptr& refHead, value_type& val )
 480         {
 481             if ( insert_at( refHead, val ))
 482                 return iterator( node_traits::to_node_ptr( val ));
 483             return end();
 484         }
 485
 486         template <typename Func>
 487         std::pair<iterator, bool> ensure_at_( atomic_node_ptr& refHead, value_type& val, Func func )
 488         {
 489             position pos;
 490
 491             while ( true ) {
 492                 if ( search( refHead, val, key_comparator(), pos ) ) {
 493                     assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
 494
 495                     func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
 496                     return std::make_pair( iterator( pos.pCur ), false );
 497                 }
 498                 else {
 499                     link_checker::is_empty( node_traits::to_node_ptr( val ) );
 500
 501                     if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
 502                         ++m_ItemCounter;
 503                         func( true, val , val );
 504                         return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
 505                     }
 506                 }
 507             }
 508         }
 509
 510         template <typename Func>
 511         std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func )
 512         {
 513             std::pair<iterator, bool> ret = ensure_at_( refHead, val, func );
 514             return std::make_pair( ret.first != end(), ret.second );
 515         }
 516
 517         template <typename Q, typename Compare, typename Func>
 518         bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
 519         {
 520             position pos;
 521
 522             if ( search( refHead, val, cmp, pos ) ) {
 523                 assert( pos.pCur != nullptr );
 524                 f( *node_traits::to_value_ptr( *pos.pCur ), val );
 525                 return true;
 526             }
 527             return false;
 528         }
 529
 530         template <typename Q, typename Compare>
 531         value_type * find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
 532         {
 533             iterator it = find_at_( refHead, val, cmp );
 534             if ( it != end() )
 535                 return &*it;
 536             return nullptr;
 537         }
 538
 539         template <typename Q, typename Compare>
 540         iterator find_at_( atomic_node_ptr& refHead, Q const& val, Compare cmp )
 541         {
 542             position pos;
 543
 544             if ( search( refHead, val, cmp, pos ) ) {
 545                 assert( pos.pCur != nullptr );
 546                 return iterator( pos.pCur );
 547             }
 548             return end();
 549         }
 550
 551         //@endcond
 552
 553     protected:
 554
 555         //@cond
 556         template <typename Q, typename Compare >
 557         bool search( atomic_node_ptr& refHead, const Q& val, Compare cmp, position& pos )
 558         {
 559             atomic_node_ptr * pPrev;
 560             node_type * pNext;
 561             node_type * pCur;
 562
 563             back_off        bkoff;
 564
 565         try_again:
 566             pPrev = &refHead;
 567             pCur = pPrev->load(memory_model::memory_order_acquire);
 568             pNext = nullptr;
 569
 570             while ( true ) {
 571                 if ( !pCur ) {
 572                     pos.pPrev = pPrev;
 573                     pos.pCur = pCur;
 574                     pos.pNext = pNext;
 575                     return false;
 576                 }
 577
 578                 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
 579                 if ( pCur->m_pNext.load(memory_model::memory_order_acquire) != pNext ) {
 580                     bkoff();
 581                     goto try_again;
 582                 }
 583
 584                 if ( pPrev->load(memory_model::memory_order_acquire) != pCur ) {
 585                     bkoff();
 586                     goto try_again;
 587                 }
 588
 589                 assert( pCur != nullptr );
 590                 int nCmp = cmp( *node_traits::to_value_ptr( *pCur ), val );
 591                 if ( nCmp >= 0 ) {
 592                     pos.pPrev = pPrev;
 593                     pos.pCur = pCur;
 594                     pos.pNext = pNext;
 595                     return nCmp == 0;
 596                 }
 597                 pPrev = &( pCur->m_pNext );
 598                 pCur = pNext;
 599             }
 600         }
 601         //@endcond
 602     };
 603
 604 }}  // namespace cds::intrusive
 605
 606 #endif  // #ifndef __CDS_INTRUSIVE_MICHAEL_LIST_NOGC_H