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         const_iterator cend() const
 299         {
 300             return const_iterator( const_cast<node_type *>(&m_Tail) );
 301         }
 302
 303     public:
 304         /// Default constructor initializes empty list
 305         LazyList()
 306         {
 307             static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
 308             m_Head.m_pNext.store( &m_Tail, memory_model::memory_order_relaxed );
 309         }
 310
 311         /// Destroys the list object
 312         ~LazyList()
 313         {
 314             clear();
 315             assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail );
 316             m_Head.m_pNext.store( nullptr, memory_model::memory_order_relaxed );
 317         }
 318
 319         /// Inserts new node
 320         /**
 321             The function inserts \p val in the list if the list does not contain
 322             an item with key equal to \p val.
 323
 324             Returns \p true if \p val is linked into the list, \p false otherwise.
 325         */
 326         bool insert( value_type& val )
 327         {
 328             return insert_at( &m_Head, val );
 329         }
 330
 331         /// Ensures that the \p item exists in the list
 332         /**
 333             The operation performs inserting or changing data with lock-free manner.
 334
 335             If the item \p val not found in the list, then \p val is inserted into the list.
 336             Otherwise, the functor \p func is called with item found.
 337             The functor signature is:
 338             \code
 339             struct functor {
 340                 void operator()( bool bNew, value_type& item, value_type& val );
 341             };
 342             \endcode
 343             with arguments:
 344             - \p bNew - \p true if the item has been inserted, \p false otherwise
 345             - \p item - item of the list
 346             - \p val - argument \p val passed into the \p ensure function
 347             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 348             refers to the same thing.
 349
 350             The functor may change non-key fields of the \p item.
 351             While the functor \p f is calling the item \p item is locked.
 352
 353             Returns <tt> std::pair<bool, bool>  </tt> where \p first is true if operation is successfull,
 354             \p second is true if new item has been added or \p false if the item with \p key
 355             already is in the list.
 356         */
 357
 358         template <typename Func>
 359         std::pair<bool, bool> ensure( value_type& val, Func func )
 360         {
 361             return ensure_at( &m_Head, val, func );
 362         }
 363
 364         /// Finds the key \p key
 365         /** \anchor cds_intrusive_LazyList_nogc_find_func
 366             The function searches the item with key equal to \p key
 367             and calls the functor \p f for item found.
 368             The interface of \p Func functor is:
 369             \code
 370             struct functor {
 371                 void operator()( value_type& item, Q& key );
 372             };
 373             \endcode
 374             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 375
 376             The functor may change non-key fields of \p item.
 377             While the functor \p f is calling the item found \p item is locked.
 378
 379             The function returns \p true if \p key is found, \p false otherwise.
 380         */
 381         template <typename Q, typename Func>
 382         bool find( Q& key, Func f )
 383         {
 384             return find_at( &m_Head, key, key_comparator(), f );
 385         }
 386
 387         /// Finds the key \p key using \p pred predicate for searching
 388         /**
 389             The function is an analog of \ref cds_intrusive_LazyList_nogc_find_func "find(Q&, Func)"
 390             but \p pred is used for key comparing.
 391             \p Less functor has the interface like \p std::less.
 392             \p pred must imply the same element order as the comparator used for building the list.
 393         */
 394         template <typename Q, typename Less, typename Func>
 395         bool find_with( Q& key, Less pred, Func f )
 396         {
 397             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 398         }
 399
 400         /// Finds the key \p key
 401         /** \anchor cds_intrusive_LazyList_nogc_find_val
 402             The function searches the item with key equal to \p key
 403             and returns pointer to value found or \p nullptr.
 404         */
 405         template <typename Q>
 406         value_type * find( Q const& key )
 407         {
 408             return find_at( &m_Head, key, key_comparator() );
 409         }
 410
 411         /// Finds the key \p key using \p pred predicate for searching
 412         /**
 413             The function is an analog of \ref cds_intrusive_LazyList_nogc_find_val "find(Q const&)"
 414             but \p pred is used for key comparing.
 415             \p Less functor has the interface like \p std::less.
 416             \p pred must imply the same element order as the comparator used for building the list.
 417         */
 418         template <typename Q, typename Less>
 419         value_type * find_with( Q const & key, Less pred )
 420         {
 421             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>() );
 422         }
 423
 424         /// Clears the list
 425         /**
 426             The function unlink all items from the list.
 427             For each unlinked item the item disposer \p disp is called after unlinking.
 428
 429             This function is not thread-safe.
 430         */
 431         template <typename Disposer>
 432         void clear( Disposer disp )
 433         {
 434             node_type * pHead = m_Head.m_pNext.exchange( &m_Tail, memory_model::memory_order_release );
 435
 436             while ( pHead != &m_Tail ) {
 437                 node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed);
 438                 dispose_node( pHead, disp );
 439                 pHead = p;
 440             }
 441         }
 442
 443         /// Clears the list using default disposer
 444         /**
 445             The function clears the list using default (provided in class template) disposer functor.
 446         */
 447         void clear()
 448         {
 449             clear( disposer() );
 450         }
 451
 452         /// Checks if the list is empty
 453         bool empty() const
 454         {
 455             return m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail;
 456         }
 457
 458         /// Returns list's item count
 459         /**
 460             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 461             this function always returns 0.
 462
 463             <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
 464             is empty. To check list emptyness use \ref empty() method.
 465         */
 466         size_t size() const
 467         {
 468             return m_ItemCounter.value();
 469         }
 470
 471     protected:
 472         //@cond
 473         // split-list support
 474         bool insert_aux_node( node_type * pNode )
 475         {
 476             return insert_aux_node( &m_Head, pNode );
 477         }
 478
 479         // split-list support
 480         bool insert_aux_node( node_type * pHead, node_type * pNode )
 481         {
 482             assert( pHead != nullptr );
 483             assert( pNode != nullptr );
 484
 485             // Hack: convert node_type to value_type.
 486             // In principle, auxiliary node can be non-reducible to value_type
 487             // We assume that comparator can correctly distinguish aux and regular node.
 488             return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
 489         }
 490
 491         bool insert_at( node_type * pHead, value_type& val )
 492         {
 493             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 494             position pos;
 495             key_comparator  cmp;
 496
 497             while ( true ) {
 498                 search( pHead, val, pos, key_comparator() );
 499                 {
 500                     auto_lock_position alp( pos );
 501                     if ( validate( pos.pPred, pos.pCur )) {
 502                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
 503                             // failed: key already in list
 504                             return false;
 505                         }
 506                         else {
 507                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 508                             ++m_ItemCounter;
 509                             return true;
 510                         }
 511                     }
 512                 }
 513             }
 514         }
 515
 516         iterator insert_at_( node_type * pHead, value_type& val )
 517         {
 518             if ( insert_at( pHead, val ))
 519                 return iterator( node_traits::to_node_ptr( val ));
 520             return end();
 521         }
 522
 523
 524         template <typename Func>
 525         std::pair<iterator, bool> ensure_at_( node_type * pHead, value_type& val, Func func )
 526         {
 527             position pos;
 528             key_comparator  cmp;
 529
 530             while ( true ) {
 531                 search( pHead, val, pos, key_comparator() );
 532                 {
 533                     auto_lock_position alp( pos );
 534                     if ( validate( pos.pPred, pos.pCur )) {
 535                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
 536                             // key already in the list
 537
 538                             func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
 539                             return std::make_pair( iterator( pos.pCur ), false );
 540                         }
 541                         else {
 542                             // new key
 543                             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 544
 545                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 546                             func( true, val, val );
 547                             ++m_ItemCounter;
 548                             return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
 549                         }
 550                     }
 551                 }
 552             }
 553         }
 554
 555         template <typename Func>
 556         std::pair<bool, bool> ensure_at( node_type * pHead, value_type& val, Func func )
 557         {
 558             std::pair<iterator, bool> ret = ensure_at_( pHead, val, func );
 559             return std::make_pair( ret.first != end(), ret.second );
 560         }
 561
 562         template <typename Q, typename Compare, typename Func>
 563         bool find_at( node_type * pHead, Q& val, Compare cmp, Func f )
 564         {
 565             position pos;
 566
 567             search( pHead, val, pos, cmp );
 568             if ( pos.pCur != &m_Tail ) {
 569                 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
 570                 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
 571                 {
 572                     f( *node_traits::to_value_ptr( *pos.pCur ), val );
 573                     return true;
 574                 }
 575             }
 576             return false;
 577         }
 578
 579         template <typename Q, typename Compare>
 580         value_type * find_at( node_type * pHead, Q& val, Compare cmp)
 581         {
 582             iterator it = find_at_( pHead, val, cmp );
 583             if ( it != end() )
 584                 return &*it;
 585             return nullptr;
 586         }
 587
 588         template <typename Q, typename Compare>
 589         iterator find_at_( node_type * pHead, Q& val, Compare cmp)
 590         {
 591             position pos;
 592
 593             search( pHead, val, pos, cmp );
 594             if ( pos.pCur != &m_Tail ) {
 595                 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
 596                 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
 597                 {
 598                     return iterator( pos.pCur );
 599                 }
 600             }
 601             return end();
 602         }
 603
 604         //@endcond
 605
 606     protected:
 607         //@cond
 608         template <typename Q, typename Compare>
 609         void search( node_type * pHead, const Q& key, position& pos, Compare cmp )
 610         {
 611             const node_type * pTail = &m_Tail;
 612
 613             node_type * pCur = pHead;
 614             node_type * pPrev = pHead;
 615
 616             while ( pCur != pTail && ( pCur == pHead || cmp( *node_traits::to_value_ptr( *pCur ), key ) < 0 )) {
 617                 pPrev = pCur;
 618                 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
 619             }
 620
 621             pos.pCur = pCur;
 622             pos.pPred = pPrev;
 623         }
 624
 625         static bool validate( node_type * pPred, node_type * pCur )
 626         {
 627             return pPred->m_pNext.load(memory_model::memory_order_acquire) == pCur;
 628         }
 629
 630         //@endcond
 631     };
 632
 633 }}  // namespace cds::intrusive
 634
 635 #endif  // #ifndef __CDS_INTRUSIVE_LAZY_LIST_NOGC_H