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