cds/intrusive/michael_list_impl.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_MICHAEL_LIST_IMPL_H
   4 #define __CDS_INTRUSIVE_MICHAEL_LIST_IMPL_H
   5
   6 #include <cds/intrusive/michael_list_base.h>
   7 #include <cds/gc/guarded_ptr.h>
   8
   9 namespace cds { namespace intrusive {
  10
  11     /// Michael's lock-free ordered single-linked list
  12     /** @ingroup cds_intrusive_list
  13         \anchor cds_intrusive_MichaelList_hp
  14
  15         Usually, ordered single-linked list is used as a building block for the hash table implementation.
  16         The complexity of searching is <tt>O(N)</tt>.
  17
  18         Source:
  19             - [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
  20
  21         Template arguments:
  22         - \p GC - Garbage collector used. Note the \p GC must be the same as the GC used for item type \p T (see michael_list::node).
  23         - \p T - type to be stored in the list. The type must be based on michael_list::node (for michael_list::base_hook)
  24             or it must have a member of type michael_list::node (for michael_list::member_hook).
  25         - \p Traits - type traits. See michael_list::type_traits for explanation.
  26
  27         It is possible to declare option-based list with cds::intrusive::michael_list::make_traits metafunction istead of \p Traits template
  28         argument.
  29
  30         Template argument list \p Options of cds::intrusive::michael_list::make_traits metafunction are:
  31         - opt::hook - hook used. Possible values are: michael_list::base_hook, michael_list::member_hook, michael_list::traits_hook.
  32             If the option is not specified, <tt>michael_list::base_hook<></tt> and gc::HP is used.
  33         - opt::compare - key comparison functor. No default functor is provided.
  34             If the option is not specified, the opt::less is used.
  35         - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
  36         - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
  37         - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer. Due the nature
  38             of GC schema the disposer may be called asynchronously.
  39         - opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link
  40         - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
  41         - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
  42             or opt::v::sequential_consistent (sequentially consisnent memory model).
  43
  44         For example, the following traits-based declaration of gc::HP Michael's list
  45         \code
  46         #include <cds/intrusive/michael_list_hp.h>
  47         // Declare item stored in your list
  48         struct item: public cds::intrusive::michael_list::node< cds::gc::HP >
  49         {
  50             int nKey;
  51             // .... other data
  52         };
  53
  54         // Declare comparator for the item
  55         struct my_compare {
  56             int operator()( item const& i1, item const& i2 ) const
  57             {
  58                 return i1.nKey - i2.nKey;
  59             }
  60         };
  61
  62         // Declare type_traits
  63         struct my_traits: public cds::intrusive::michael_list::type_traits
  64         {
  65             typedef cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > >   hook;
  66             typedef my_compare compare;
  67         };
  68
  69         // Declare traits-based list
  70         typedef cds::intrusive::MichaelList< cds::gc::HP, item, my_traits >     traits_based_list;
  71         \endcode
  72
  73         is equivalent for the following option-based list
  74         \code
  75         #include <cds/intrusive/michael_list_hp.h>
  76
  77         // item struct and my_compare are the same
  78
  79         // Declare option-based list
  80         typedef cds::intrusive::MichaelList< cds::gc::HP, item,
  81             typename cds::intrusive::michael_list::make_traits<
  82                 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > >    // hook option
  83                 ,cds::intrusive::opt::compare< my_compare >     // item comparator option
  84             >::type
  85         >     option_based_list;
  86         \endcode
  87
  88         \par Usage
  89         There are different specializations of this template for each garbage collecting schema used.
  90         You should select GC needed and include appropriate .h-file:
  91         - for gc::HP: \code #include <cds/intrusive/michael_list_hp.h> \endcode
  92         - for gc::PTB: \code #include <cds/intrusive/michael_list_ptb.h> \endcode
  93         - for gc::HRC: \code #include <cds/intrusive/michael_list_hrc.h> \endcode
  94         - for \ref cds_urcu_gc "RCU type" - see \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
  95         - for gc::nogc: \code #include <cds/intrusive/michael_list_nogc.h> \endcode
  96             See \ref cds_intrusive_MichaelList_nogc "non-GC MichaelList"
  97
  98         Then, you should incorporate michael_list::node into your struct \p T and provide
  99         appropriate michael_list::type_traits::hook in your \p Traits template parameters. Usually, for \p Traits you
 100         define a struct based on michael_list::type_traits.
 101
 102         Example for gc::PTB and base hook:
 103         \code
 104         // Include GC-related Michael's list specialization
 105         #include <cds/intrusive/michael_list_ptb.h>
 106
 107         // Data stored in Michael's list
 108         struct my_data: public cds::intrusive::michael_list::node< cds::gc::PTB >
 109         {
 110             // key field
 111             std::string     strKey;
 112
 113             // other data
 114             // ...
 115         };
 116
 117         // my_data comparing functor
 118         struct my_data_cmp {
 119             int operator()( const my_data& d1, const my_data& d2 )
 120             {
 121                 return d1.strKey.compare( d2.strKey );
 122             }
 123
 124             int operator()( const my_data& d, const std::string& s )
 125             {
 126                 return d.strKey.compare(s);
 127             }
 128
 129             int operator()( const std::string& s, const my_data& d )
 130             {
 131                 return s.compare( d.strKey );
 132             }
 133         };
 134
 135
 136         // Declare type_traits
 137         struct my_traits: public cds::intrusive::michael_list::type_traits
 138         {
 139             typedef cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::PTB > >   hook;
 140             typedef my_data_cmp compare;
 141         };
 142
 143         // Declare list type
 144         typedef cds::intrusive::MichaelList< cds::gc::PTB, my_data, my_traits >     traits_based_list;
 145         \endcode
 146
 147         Equivalent option-based code:
 148         \code
 149         // GC-related specialization
 150         #include <cds/intrusive/michael_list_ptb.h>
 151
 152         struct my_data {
 153             // see above
 154         };
 155         struct compare {
 156             // see above
 157         };
 158
 159         // Declare option-based list
 160         typedef cds::intrusive::MichaelList< cds::gc::PTB
 161             ,my_data
 162             , typename cds::intrusive::michael_list::make_traits<
 163                 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::PTB > > >
 164                 ,cds::intrusive::opt::compare< my_data_cmp >
 165             >::type
 166         > option_based_list;
 167
 168         \endcode
 169     */
 170     template <
 171         class GC
 172         ,typename T
 173 #ifdef CDS_DOXYGEN_INVOKED
 174         ,class Traits = michael_list::type_traits
 175 #else
 176         ,class Traits
 177 #endif
 178     >
 179     class MichaelList
 180     {
 181     public:
 182         typedef T       value_type      ;   ///< type of value stored in the list
 183         typedef Traits  options         ;   ///< Traits template parameter
 184
 185         typedef typename options::hook      hook        ;   ///< hook type
 186         typedef typename hook::node_type    node_type   ;   ///< node type
 187
 188 #   ifdef CDS_DOXYGEN_INVOKED
 189         typedef implementation_defined key_comparator  ;    ///< key comparison functor based on opt::compare and opt::less option setter.
 190 #   else
 191         typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
 192 #   endif
 193
 194         typedef typename options::disposer  disposer    ;   ///< disposer used
 195         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ;    ///< node traits
 196         typedef typename michael_list::get_link_checker< node_type, options::link_checker >::type link_checker   ;   ///< link checker
 197
 198         typedef GC  gc          ;   ///< Garbage collector
 199         typedef typename options::back_off  back_off    ;   ///< back-off strategy
 200         typedef typename options::item_counter item_counter ;   ///< Item counting policy used
 201         typedef typename options::memory_model  memory_model;   ///< Memory ordering. See cds::opt::memory_model option
 202
 203         typedef cds::gc::guarded_ptr< gc, value_type > guarded_ptr; ///< Guarded pointer
 204
 205         //@cond
 206         // Rebind options (split-list support)
 207         template <CDS_DECL_OPTIONS7>
 208         struct rebind_options {
 209             typedef MichaelList<
 210                 gc
 211                 , value_type
 212                 , typename cds::opt::make_options< options, CDS_OPTIONS7>::type
 213             >   type;
 214         };
 215         //@endcond
 216
 217     protected:
 218         typedef typename node_type::atomic_marked_ptr   atomic_node_ptr ;   ///< Atomic node pointer
 219         typedef typename node_type::marked_ptr          marked_node_ptr ;   ///< Node marked pointer
 220
 221         typedef atomic_node_ptr     auxiliary_head      ;   ///< Auxiliary head type (for split-list support)
 222
 223         atomic_node_ptr     m_pHead         ;   ///< Head pointer
 224         item_counter        m_ItemCounter   ;   ///< Item counter
 225
 226         //@cond
 227         /// Position pointer for item search
 228         struct position {
 229             atomic_node_ptr * pPrev ;   ///< Previous node
 230             node_type * pCur        ;   ///< Current node
 231             node_type * pNext       ;   ///< Next node
 232
 233             typename gc::template GuardArray<3> guards  ;   ///< Guards array
 234
 235             enum {
 236                 guard_prev_item,
 237                 guard_current_item,
 238                 guard_next_item
 239             };
 240         };
 241
 242 #   ifndef CDS_CXX11_LAMBDA_SUPPORT
 243         struct empty_erase_functor {
 244             void operator()( value_type const & item )
 245             {}
 246         };
 247 #   endif
 248
 249         struct clean_disposer {
 250             void operator()( value_type * p )
 251             {
 252                 michael_list::node_cleaner<gc, node_type, memory_model>()( node_traits::to_node_ptr( p ) );
 253                 disposer()( p );
 254             }
 255         };
 256
 257         //@endcond
 258
 259     protected:
 260         //@cond
 261         void retire_node( node_type * pNode )
 262         {
 263             assert( pNode != null_ptr<node_type *>() );
 264             gc::template retire<clean_disposer>( node_traits::to_value_ptr( *pNode ) );
 265         }
 266
 267         bool link_node( node_type * pNode, position& pos )
 268         {
 269             assert( pNode != null_ptr<node_type *>() );
 270             link_checker::is_empty( pNode );
 271
 272             marked_node_ptr cur(pos.pCur);
 273             pNode->m_pNext.store( cur, memory_model::memory_order_relaxed );
 274             return pos.pPrev->compare_exchange_strong( cur, marked_node_ptr(pNode), memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
 275         }
 276
 277         bool unlink_node( position& pos )
 278         {
 279             assert( pos.pPrev != null_ptr<atomic_node_ptr *>() );
 280             assert( pos.pCur != null_ptr<node_type *>() );
 281
 282             // Mark the node (logical deleting)
 283             marked_node_ptr next(pos.pNext, 0);
 284             if ( pos.pCur->m_pNext.compare_exchange_strong( next, marked_node_ptr(pos.pNext, 1), memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed )) {
 285                 // physical deletion may be performed by search function if it detects that a node is logically deleted (marked)
 286                 // CAS may be successful here or in other thread that searching something
 287                 marked_node_ptr cur(pos.pCur);
 288                 if ( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr( pos.pNext ), memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ))
 289                     retire_node( pos.pCur );
 290                 return true;
 291             }
 292             return false;
 293         }
 294         //@endcond
 295
 296     protected:
 297         //@cond
 298         template <bool IsConst>
 299         class iterator_type
 300         {
 301             friend class MichaelList;
 302
 303         protected:
 304             value_type * m_pNode;
 305             typename gc::Guard  m_Guard;
 306
 307             void next()
 308             {
 309                 if ( m_pNode ) {
 310                     typename gc::Guard g;
 311                     node_type * pCur = node_traits::to_node_ptr( *m_pNode );
 312
 313                     marked_node_ptr pNext;
 314                     do {
 315                         pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
 316                         g.assign( node_traits::to_value_ptr( pNext.ptr() ));
 317                     } while ( pNext != pCur->m_pNext.load(memory_model::memory_order_acquire) );
 318
 319                     if ( pNext.ptr() ) {
 320                         m_pNode = m_Guard.assign( g.template get<value_type>() );
 321                     }
 322                     else {
 323                         m_pNode = null_ptr<value_type *>();
 324                         m_Guard.clear();
 325                     }
 326                 }
 327             }
 328
 329             iterator_type( atomic_node_ptr const& pNode )
 330             {
 331                 for (;;) {
 332                     marked_node_ptr p = pNode.load(memory_model::memory_order_relaxed);
 333                     if ( p.ptr() ) {
 334                         m_pNode = m_Guard.assign( node_traits::to_value_ptr( p.ptr() ) );
 335                     }
 336                     else {
 337                         m_pNode = null_ptr<value_type *>();
 338                         m_Guard.clear();
 339                     }
 340                     if ( p == pNode.load(memory_model::memory_order_acquire) )
 341                         break;
 342                 }
 343             }
 344
 345         public:
 346             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 347             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 348
 349             iterator_type()
 350                 : m_pNode( null_ptr<value_type *>() )
 351             {}
 352
 353             iterator_type( iterator_type const& src )
 354             {
 355                 if ( src.m_pNode ) {
 356                     m_pNode = m_Guard.assign( src.m_pNode );
 357                 }
 358                 else
 359                     m_pNode = null_ptr<value_type *>();
 360             }
 361
 362             value_ptr operator ->() const
 363             {
 364                 return m_pNode;
 365             }
 366
 367             value_ref operator *() const
 368             {
 369                 assert( m_pNode != null_ptr<value_type *>() );
 370                 return *m_pNode;
 371             }
 372
 373             /// Pre-increment
 374             iterator_type& operator ++()
 375             {
 376                 next();
 377                 return *this;
 378             }
 379
 380             iterator_type& operator = (iterator_type const& src)
 381             {
 382                 m_pNode = src.m_pNode;
 383                 m_Guard.assign( m_pNode );
 384                 return *this;
 385             }
 386
 387             /*
 388             /// Post-increment
 389             void operator ++(int)
 390             {
 391                 next();
 392             }
 393             */
 394
 395             template <bool C>
 396             bool operator ==(iterator_type<C> const& i ) const
 397             {
 398                 return m_pNode == i.m_pNode;
 399             }
 400             template <bool C>
 401             bool operator !=(iterator_type<C> const& i ) const
 402             {
 403                 return m_pNode != i.m_pNode;
 404             }
 405         };
 406         //@endcond
 407
 408     public:
 409         /// Forward iterator
 410         /**
 411             The forward iterator for Michael's list has some features:
 412             - it has no post-increment operator
 413             - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
 414               For some GC (gc::HP, gc::HRC), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
 415               may be thrown if a limit of guard count per thread is exceeded.
 416             - The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
 417             - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
 418               deleting operations it is no guarantee that you iterate all item in the list.
 419
 420             Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
 421             for debug purpose only.
 422
 423             The iterator interface:
 424             \code
 425             class iterator {
 426             public:
 427                 // Default constructor
 428                 iterator();
 429
 430                 // Copy construtor
 431                 iterator( iterator const& src );
 432
 433                 // Dereference operator
 434                 value_type * operator ->() const;
 435
 436                 // Dereference operator
 437                 value_type& operator *() const;
 438
 439                 // Preincrement operator
 440                 iterator& operator ++();
 441
 442                 // Assignment operator
 443                 iterator& operator = (iterator const& src);
 444
 445                 // Equality operators
 446                 bool operator ==(iterator const& i ) const;
 447                 bool operator !=(iterator const& i ) const;
 448             };
 449             \endcode
 450         */
 451         typedef iterator_type<false>    iterator;
 452         /// Const forward iterator
 453         /**
 454             For iterator's features and requirements see \ref iterator
 455         */
 456         typedef iterator_type<true>     const_iterator;
 457
 458         /// Returns a forward iterator addressing the first element in a list
 459         /**
 460             For empty list \code begin() == end() \endcode
 461         */
 462         iterator begin()
 463         {
 464             return iterator( m_pHead );
 465         }
 466
 467         /// Returns an iterator that addresses the location succeeding the last element in a list
 468         /**
 469             Do not use the value returned by <tt>end</tt> function to access any item.
 470             Internally, <tt>end</tt> returning value equals to <tt>NULL</tt>.
 471
 472             The returned value can be used only to control reaching the end of the list.
 473             For empty list <tt>begin() == end()</tt>
 474         */
 475         iterator end()
 476         {
 477             return iterator();
 478         }
 479
 480         /// Returns a forward const iterator addressing the first element in a list
 481         const_iterator cbegin()
 482         {
 483             return const_iterator( m_pHead );
 484         }
 485
 486         /// Returns a forward const iterator addressing the first element in a list
 487         const_iterator begin() const
 488         {
 489             return const_iterator( m_pHead );
 490         }
 491
 492         /// Returns an const iterator that addresses the location succeeding the last element in a list
 493         const_iterator end() const
 494         {
 495             return const_iterator();
 496         }
 497
 498         /// Returns an const iterator that addresses the location succeeding the last element in a list
 499         const_iterator cend()
 500         {
 501             return const_iterator();
 502         }
 503
 504     public:
 505         /// Default constructor initializes empty list
 506         MichaelList()
 507             : m_pHead(null_ptr<node_type *>())
 508         {
 509             static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
 510         }
 511
 512         /// Destroys the list object
 513         ~MichaelList()
 514         {
 515             clear();
 516         }
 517
 518         /// Inserts new node
 519         /**
 520             The function inserts \p val in the list if the list does not contain
 521             an item with key equal to \p val.
 522
 523             Returns \p true if \p val is linked into the list, \p false otherwise.
 524         */
 525         bool insert( value_type& val )
 526         {
 527             return insert_at( m_pHead, val );
 528         }
 529
 530         /// Inserts new node
 531         /**
 532             This function is intended for derived non-intrusive containers.
 533
 534             The function allows to split new item creating into two part:
 535             - create item with key only
 536             - insert new item into the list
 537             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 538
 539             The functor signature is:
 540             \code
 541                 void func( value_type& val );
 542             \endcode
 543             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
 544             \p val no any other changes could be made on this list's item by concurrent threads.
 545             The user-defined functor is called only if the inserting is success and may be passed by reference
 546             using <tt>boost::ref</tt>.
 547         */
 548         template <typename Func>
 549         bool insert( value_type& val, Func f )
 550         {
 551             return insert_at( m_pHead, val, f );
 552         }
 553
 554         /// Ensures that the \p item exists in the list
 555         /**
 556             The operation performs inserting or changing data with lock-free manner.
 557
 558             If the item \p val not found in the list, then \p val is inserted into the list.
 559             Otherwise, the functor \p func is called with item found.
 560             The functor signature is:
 561             \code
 562                 void func( bool bNew, value_type& item, value_type& val );
 563             \endcode
 564             with arguments:
 565             - \p bNew - \p true if the item has been inserted, \p false otherwise
 566             - \p item - item of the list
 567             - \p val - argument \p val passed into the \p ensure function
 568             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 569             refers to the same thing.
 570
 571             The functor may change non-key fields of the \p item; however, \p func must guarantee
 572             that during changing no any other modifications could be made on this item by concurrent threads.
 573
 574             You may pass \p func argument by reference using <tt>boost::ref</tt> or cds::ref.
 575
 576             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
 577             \p second is \p true if new item has been added or \p false if the item with \p key
 578             already is in the list.
 579         */
 580         template <typename Func>
 581         std::pair<bool, bool> ensure( value_type& val, Func func )
 582         {
 583             return ensure_at( m_pHead, val, func );
 584         }
 585
 586         /// Unlinks the item \p val from the list
 587         /**
 588             The function searches the item \p val in the list and unlink it from the list
 589             if it is found and it is equal to \p val.
 590
 591             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 592             and deletes the item found. \p unlink finds an item by key and deletes it
 593             only if \p val is an item of that list, i.e. the pointer to item found
 594             is equal to <tt> &val </tt>.
 595
 596             The function returns \p true if success and \p false otherwise.
 597         */
 598         bool unlink( value_type& val )
 599         {
 600             return unlink_at( m_pHead, val );
 601         }
 602
 603         /// Deletes the item from the list
 604         /** \anchor cds_intrusive_MichaelList_hp_erase_val
 605             The function searches an item with key equal to \p val in the list,
 606             unlinks it from the list, and returns \p true.
 607             If the item with the key equal to \p val is not found the function return \p false.
 608         */
 609         template <typename Q>
 610         bool erase( Q const& val )
 611         {
 612             return erase_at( m_pHead, val, key_comparator() );
 613         }
 614
 615         /// Deletes the item from the list using \p pred predicate for searching
 616         /**
 617             The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_val "erase(Q const&)"
 618             but \p pred is used for key comparing.
 619             \p Less functor has the interface like \p std::less.
 620             \p pred must imply the same element order as the comparator used for building the list.
 621         */
 622         template <typename Q, typename Less>
 623         bool erase_with( Q const& val, Less pred )
 624         {
 625             return erase_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>());
 626         }
 627
 628         /// Deletes the item from the list
 629         /** \anchor cds_intrusive_MichaelList_hp_erase_func
 630             The function searches an item with key equal to \p val in the list,
 631             call \p func functor with item found, unlinks it from the list, and returns \p true.
 632             The \p Func interface is
 633             \code
 634             struct functor {
 635                 void operator()( value_type const& item );
 636             };
 637             \endcode
 638             The functor may be passed by reference using <tt>boost:ref</tt>
 639
 640             If the item with the key equal to \p val is not found the function return \p false.
 641         */
 642         template <typename Q, typename Func>
 643         bool erase( Q const& val, Func func )
 644         {
 645             return erase_at( m_pHead, val, key_comparator(), func );
 646         }
 647
 648         /// Deletes the item from the list using \p pred predicate for searching
 649         /**
 650             The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_func "erase(Q const&, Func)"
 651             but \p pred is used for key comparing.
 652             \p Less functor has the interface like \p std::less.
 653             \p pred must imply the same element order as the comparator used for building the list.
 654         */
 655         template <typename Q, typename Less, typename Func>
 656         bool erase_with( Q const& val, Less pred, Func f )
 657         {
 658             return erase_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>(), f );
 659         }
 660
 661         /// Extracts the item from the list with specified \p key
 662         /** \anchor cds_intrusive_MichaelList_hp_extract
 663             The function searches an item with key equal to \p key,
 664             unlinks it from the list, and returns it in \p dest parameter.
 665             If the item with key equal to \p key is not found the function returns \p false.
 666
 667             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 668
 669             The \ref disposer specified in \p Traits class template parameter is called automatically
 670             by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
 671             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 672
 673             Usage:
 674             \code
 675             typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits >  ord_list;
 676             ord_list theList;
 677             // ...
 678             {
 679                 ord_list::guarded_ptr gp;
 680                 theList.extract( gp, 5 );
 681                 // Deal with gp
 682                 // ...
 683
 684                 // Destructor of gp releases internal HP guard
 685             }
 686             \endcode
 687         */
 688         template <typename Q>
 689         bool extract( guarded_ptr& dest, Q const& key )
 690         {
 691             return extract_at( m_pHead, dest.guard(), key, key_comparator() );
 692         }
 693
 694         /// Extracts the item using compare functor \p pred
 695         /**
 696             The function is an analog of \ref cds_intrusive_MichaelList_hp_extract "extract(guarded_ptr&, Q const&)"
 697             but \p pred predicate is used for key comparing.
 698
 699             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 700             in any order.
 701             \p pred must imply the same element order as the comparator used for building the list.
 702         */
 703         template <typename Q, typename Less>
 704         bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
 705         {
 706             return extract_at( m_pHead, dest.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
 707         }
 708
 709         /// Finds the key \p val
 710         /** \anchor cds_intrusive_MichaelList_hp_find_func
 711             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 712             The interface of \p Func functor is:
 713             \code
 714             struct functor {
 715                 void operator()( value_type& item, Q& val );
 716             };
 717             \endcode
 718             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 719
 720             You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 721
 722             The functor may change non-key fields of \p item. Note that the function is only guarantee
 723             that \p item cannot be disposed during functor is executing.
 724             The function does not serialize simultaneous access to the list \p item. If such access is
 725             possible you must provide your own synchronization schema to exclude unsafe item modifications.
 726
 727             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 728             may modify both arguments.
 729
 730             The function returns \p true if \p val is found, \p false otherwise.
 731         */
 732         template <typename Q, typename Func>
 733         bool find( Q& val, Func f )
 734         {
 735             return find_at( m_pHead, val, key_comparator(), f );
 736         }
 737
 738         /// Finds the key \p val using \p pred predicate for searching
 739         /**
 740             The function is an analog of \ref cds_intrusive_MichaelList_hp_find_func "find(Q&, Func)"
 741             but \p pred is used for key comparing.
 742             \p Less functor has the interface like \p std::less.
 743             \p pred must imply the same element order as the comparator used for building the list.
 744         */
 745         template <typename Q, typename Less, typename Func>
 746         bool find_with( Q& val, Less pred, Func f )
 747         {
 748             return find_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>(), f );
 749         }
 750
 751         /// Finds the key \p val
 752         /** \anchor cds_intrusive_MichaelList_hp_find_cfunc
 753             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 754             The interface of \p Func functor is:
 755             \code
 756             struct functor {
 757                 void operator()( value_type& item, Q const& val );
 758             };
 759             \endcode
 760             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 761
 762             You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 763
 764             The functor may change non-key fields of \p item. Note that the function is only guarantee
 765             that \p item cannot be disposed during functor is executing.
 766             The function does not serialize simultaneous access to the list \p item. If such access is
 767             possible you must provide your own synchronization schema to exclude unsafe item modifications.
 768
 769             The function returns \p true if \p val is found, \p false otherwise.
 770         */
 771         template <typename Q, typename Func>
 772         bool find( Q const& val, Func f )
 773         {
 774             return find_at( m_pHead, val, key_comparator(), f );
 775         }
 776
 777         /// Finds the key \p val using \p pred predicate for searching
 778         /**
 779             The function is an analog of \ref cds_intrusive_MichaelList_hp_find_cfunc "find(Q const&, Func)"
 780             but \p pred is used for key comparing.
 781             \p Less functor has the interface like \p std::less.
 782             \p pred must imply the same element order as the comparator used for building the list.
 783         */
 784         template <typename Q, typename Less, typename Func>
 785         bool find_with( Q const& val, Less pred, Func f )
 786         {
 787             return find_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>(), f );
 788         }
 789
 790         /// Finds the key \p val
 791         /** \anchor cds_intrusive_MichaelList_hp_find_val
 792             The function searches the item with key equal to \p val
 793             and returns \p true if it is found, and \p false otherwise
 794         */
 795         template <typename Q>
 796         bool find( Q const & val )
 797         {
 798             return find_at( m_pHead, val, key_comparator() );
 799         }
 800
 801         /// Finds the key \p val using \p pred predicate for searching
 802         /**
 803             The function is an analog of \ref cds_intrusive_MichaelList_hp_find_val "find(Q const&)"
 804             but \p pred is used for key comparing.
 805             \p Less functor has the interface like \p std::less.
 806             \p pred must imply the same element order as the comparator used for building the list.
 807         */
 808         template <typename Q, typename Less>
 809         bool find_with( Q const& val, Less pred )
 810         {
 811             return find_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>() );
 812         }
 813
 814         /// Finds the key \p val and return the item found
 815         /** \anchor cds_intrusive_MichaelList_hp_get
 816             The function searches the item with key equal to \p val
 817             and assigns the item found to guarded pointer \p ptr.
 818             The function returns \p true if \p val is found, and \p false otherwise.
 819             If \p val is not found the \p ptr parameter is not changed.
 820
 821             The \ref disposer specified in \p Traits class template parameter is called
 822             by garbage collector \p GC automatically when returned \ref guarded_ptr object
 823             will be destroyed or released.
 824             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 825
 826             Usage:
 827             \code
 828             typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits >  ord_list;
 829             ord_list theList;
 830             // ...
 831             {
 832                 ord_list::guarded_ptr gp;
 833                 if ( theList.get( gp, 5 )) {
 834                     // Deal with gp
 835                     //...
 836                 }
 837                 // Destructor of guarded_ptr releases internal HP guard
 838             }
 839             \endcode
 840
 841             Note the compare functor specified for \p Traits template parameter
 842             should accept a parameter of type \p Q that can be not the same as \p value_type.
 843         */
 844         template <typename Q>
 845         bool get( guarded_ptr& ptr, Q const& val )
 846         {
 847             return get_at( m_pHead, ptr.guard(), val, key_comparator() );
 848         }
 849
 850         /// Finds the key \p val and return the item found
 851         /**
 852             The function is an analog of \ref cds_intrusive_MichaelList_hp_get "get( guarded_ptr& ptr, Q const&)"
 853             but \p pred is used for comparing the keys.
 854
 855             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 856             in any order.
 857             \p pred must imply the same element order as the comparator used for building the list.
 858         */
 859         template <typename Q, typename Less>
 860         bool get_with( guarded_ptr& ptr, Q const& val, Less pred )
 861         {
 862             return get_at( m_pHead, ptr.guard(), val, cds::opt::details::make_comparator_from_less<Less>() );
 863         }
 864
 865         /// Clears the list
 866         /**
 867             The function unlink all items from the list.
 868         */
 869         void clear()
 870         {
 871             typename gc::Guard guard;
 872             marked_node_ptr head;
 873             while ( true ) {
 874                 head = m_pHead.load(memory_model::memory_order_relaxed);
 875                 if ( head.ptr() )
 876                     guard.assign( node_traits::to_value_ptr( *head.ptr() ));
 877                 if ( m_pHead.load(memory_model::memory_order_acquire) == head ) {
 878                     if ( head.ptr() == null_ptr<node_type *>() )
 879                         break;
 880                     value_type& val = *node_traits::to_value_ptr( *head.ptr() );
 881                     unlink( val );
 882                 }
 883             }
 884         }
 885
 886         /// Checks if the list is empty
 887         bool empty() const
 888         {
 889             return m_pHead.load(memory_model::memory_order_relaxed).all() == null_ptr<node_type *>();
 890         }
 891
 892         /// Returns list's item count
 893         /**
 894             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 895             this function always returns 0.
 896
 897             <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
 898             is empty. To check list emptyness use \ref empty() method.
 899         */
 900         size_t size() const
 901         {
 902             return m_ItemCounter.value();
 903         }
 904
 905     protected:
 906         //@cond
 907         // split-list support
 908         bool insert_aux_node( node_type * pNode )
 909         {
 910             return insert_aux_node( m_pHead, pNode );
 911         }
 912
 913         // split-list support
 914         bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
 915         {
 916             assert( pNode != null_ptr<node_type *>() );
 917
 918             // Hack: convert node_type to value_type.
 919             // In principle, auxiliary node can be non-reducible to value_type
 920             // We assume that comparator can correctly distinguish aux and regular node.
 921             return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
 922         }
 923
 924         bool insert_at( atomic_node_ptr& refHead, value_type& val )
 925         {
 926             node_type * pNode = node_traits::to_node_ptr( val );
 927             link_checker::is_empty( pNode );
 928             position pos;
 929
 930             while ( true ) {
 931                 if ( search( refHead, val, pos, key_comparator() ) )
 932                     return false;
 933
 934                 if ( link_node( pNode, pos ) ) {
 935                     ++m_ItemCounter;
 936                     return true;
 937                 }
 938
 939                 // clear next field
 940                 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 941             }
 942         }
 943
 944         template <typename Func>
 945         bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
 946         {
 947             node_type * pNode = node_traits::to_node_ptr( val );
 948             link_checker::is_empty( pNode );
 949             position pos;
 950
 951             while ( true ) {
 952                 if ( search( refHead, val, pos, key_comparator() ) )
 953                     return false;
 954
 955                 typename gc::Guard guard;
 956                 guard.assign( &val );
 957                 if ( link_node( pNode, pos ) ) {
 958                     cds::unref(f)( val );
 959                     ++m_ItemCounter;
 960                     return true;
 961                 }
 962
 963                 // clear next field
 964                 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 965             }
 966         }
 967
 968         template <typename Func>
 969         std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func )
 970         {
 971             position pos;
 972
 973             node_type * pNode = node_traits::to_node_ptr( val );
 974             while ( true ) {
 975                 if ( search( refHead, val, pos, key_comparator() ) ) {
 976                     if ( pos.pCur->m_pNext.load(memory_model::memory_order_acquire).bits() ) {
 977                         back_off()();
 978                         continue        ;   // the node found is marked as deleted
 979                     }
 980                     assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
 981
 982                     unref(func)( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
 983                     return std::make_pair( true, false );
 984                 }
 985                 else {
 986                     typename gc::Guard guard;
 987                     guard.assign( &val );
 988                     if ( link_node( pNode, pos ) ) {
 989                         ++m_ItemCounter;
 990                         unref(func)( true, val, val );
 991                         return std::make_pair( true, true );
 992                     }
 993                     // clear next field
 994                     pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 995                 }
 996             }
 997         }
 998
 999         bool unlink_at( atomic_node_ptr& refHead, value_type& val )
1000         {
1001             position pos;
1002
1003             back_off bkoff;
1004             while ( search( refHead, val, pos, key_comparator() ) ) {
1005                 if ( node_traits::to_value_ptr( *pos.pCur ) == &val ) {
1006                     if ( unlink_node( pos ) ) {
1007                         --m_ItemCounter;
1008                         return true;
1009                     }
1010                     else
1011                         bkoff();
1012                 }
1013                 else
1014                     break;
1015             }
1016             return false;
1017         }
1018
1019         template <typename Q, typename Compare, typename Func>
1020         bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos )
1021         {
1022             back_off bkoff;
1023             while ( search( refHead, val, pos, cmp )) {
1024                 if ( unlink_node( pos ) ) {
1025                     cds::unref(f)( *node_traits::to_value_ptr( *pos.pCur ) );
1026                     --m_ItemCounter;
1027                     return true;
1028                 }
1029                 else
1030                     bkoff();
1031             }
1032             return false;
1033         }
1034
1035         template <typename Q, typename Compare, typename Func>
1036         bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f )
1037         {
1038             position pos;
1039             return erase_at( refHead, val, cmp, f, pos );
1040         }
1041
1042         template <typename Q, typename Compare>
1043         bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1044         {
1045             position pos;
1046 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1047             return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
1048 #       else
1049             return erase_at( refHead, val, cmp, empty_erase_functor(), pos );
1050 #       endif
1051         }
1052
1053         template <typename Q, typename Compare>
1054         bool extract_at( atomic_node_ptr& refHead, typename gc::Guard& dest, Q const& val, Compare cmp )
1055         {
1056             position pos;
1057             back_off bkoff;
1058             while ( search( refHead, val, pos, cmp )) {
1059                 if ( unlink_node( pos ) ) {
1060                     dest.assign( pos.guards.template get<value_type>( position::guard_current_item ) );
1061                     --m_ItemCounter;
1062                     return true;
1063                 }
1064                 else
1065                     bkoff();
1066             }
1067             return false;
1068         }
1069
1070         template <typename Q, typename Compare>
1071         bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1072         {
1073             position pos;
1074             return search( refHead, val, pos, cmp );
1075         }
1076
1077         template <typename Q, typename Compare, typename Func>
1078         bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
1079         {
1080             position pos;
1081             if ( search( refHead, val, pos, cmp )) {
1082                 cds::unref(f)( *node_traits::to_value_ptr( *pos.pCur ), val );
1083                 return true;
1084             }
1085             return false;
1086         }
1087
1088         template <typename Q, typename Compare>
1089         bool get_at( atomic_node_ptr& refHead, typename gc::Guard& guard, Q const& val, Compare cmp )
1090         {
1091             position pos;
1092             if ( search( refHead, val, pos, cmp )) {
1093                 guard.assign( pos.guards.template get<value_type>( position::guard_current_item ));
1094                 return true;
1095             }
1096             return false;
1097         }
1098
1099         //@endcond
1100
1101     protected:
1102
1103         //@cond
1104         template <typename Q, typename Compare >
1105         bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1106         {
1107             atomic_node_ptr * pPrev;
1108             marked_node_ptr pNext;
1109             marked_node_ptr pCur;
1110
1111             back_off        bkoff;
1112
1113 try_again:
1114             pPrev = &refHead;
1115             pNext = null_ptr<node_type *>();
1116
1117             pCur = pPrev->load(memory_model::memory_order_relaxed);
1118             pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ) );
1119             if ( pPrev->load(memory_model::memory_order_acquire) != pCur.ptr() )
1120                 goto try_again;
1121
1122             while ( true ) {
1123                 if ( pCur.ptr() == null_ptr<node_type *>() ) {
1124                     pos.pPrev = pPrev;
1125                     pos.pCur = pCur.ptr();
1126                     pos.pNext = pNext.ptr();
1127                     return false;
1128                 }
1129
1130                 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
1131                 pos.guards.assign( position::guard_next_item, node_traits::to_value_ptr( pNext.ptr() ));
1132                 if ( pCur->m_pNext.load(memory_model::memory_order_relaxed).all() != pNext.all() ) {
1133                     bkoff();
1134                     goto try_again;
1135                 }
1136
1137                 if ( pPrev->load(memory_model::memory_order_relaxed).all() != pCur.ptr() ) {
1138                     bkoff();
1139                     goto try_again;
1140                 }
1141
1142                 // pNext contains deletion mark for pCur
1143                 if ( pNext.bits() == 1 ) {
1144                     // pCur marked i.e. logically deleted. Help the erase/unlink function to unlink pCur node
1145                     marked_node_ptr cur( pCur.ptr());
1146                     if ( pPrev->compare_exchange_strong( cur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed )) {
1147                         retire_node( pCur.ptr() );
1148                     }
1149                     else {
1150                         bkoff();
1151                         goto try_again;
1152                     }
1153                 }
1154                 else {
1155                     assert( pCur.ptr() != null_ptr<node_type *>() );
1156                     int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1157                     if ( nCmp >= 0 ) {
1158                         pos.pPrev = pPrev;
1159                         pos.pCur = pCur.ptr();
1160                         pos.pNext = pNext.ptr();
1161                         return nCmp == 0;
1162                     }
1163                     pPrev = &( pCur->m_pNext );
1164                     pos.guards.assign( position::guard_prev_item, node_traits::to_value_ptr( pCur.ptr() ) );
1165                 }
1166                 pCur = pNext;
1167                 pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ));
1168             }
1169         }
1170         //@endcond
1171     };
1172 }} // namespace cds::intrusive
1173
1174 #endif // #ifndef __CDS_INTRUSIVE_MICHAEL_LIST_IMPL_H