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