cds/intrusive/michael_list_nogc.h

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