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