cds/intrusive/lazy_list_nogc.h

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