cds/gc/hrc_decl.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_GC_HRC_DECL_H
   4 #define __CDS_GC_HRC_DECL_H
   5
   6 #include <cds/gc/hrc/hrc.h>
   7 #include <cds/details/marked_ptr.h>
   8
   9 namespace cds { namespace gc {
  10
  11     /// Gidenstam's garbage collector
  12     /** @ingroup cds_garbage_collector
  13         @headerfile cds/gc/hrc.h
  14
  15         This class is a wrapper for Gidenstam's memory reclamation schema (HRC - Hazard pointer + Reference Counting)
  16         internal implementation.
  17
  18         Sources:
  19         - [2006] A.Gidenstam "Algorithms for synchronization and consistency
  20             in concurrent system services", Chapter 5 "Lock-Free Memory Reclamation"
  21             Thesis for the degree of Doctor    of Philosophy
  22         - [2005] Anders Gidenstam, Marina Papatriantafilou and Philippas Tsigas "Allocating
  23             memory in a lock-free manner", Proceedings of the 13th Annual European
  24             Symposium on Algorithms (ESA 2005), Lecture Notes in Computer
  25             Science Vol. 3669, pages 229 \96 242, Springer-Verlag, 2005
  26
  27         Note that HRC schema does not support cyclic references that significantly limits the applicability of this GC.
  28
  29         <h1>Usage</h1>
  30         In your \p main function you declare a object of class cds::gc::HRC. This declaration
  31         initializes internal hrc::GarbageCollector singleton.
  32         \code
  33         #include <cds/init.h>       // for cds::Initialize and cds::Terminate
  34         #include <cds/gc/hrc.h>
  35
  36         int main(int argc, char** argv)
  37         {
  38             // Initialize libcds
  39             cds::Initialize();
  40
  41             {
  42                 // Initialize HRC singleton
  43                 cds::gc::HRC hpGC();
  44
  45                 // Some useful work
  46                 ...
  47             }
  48
  49             // Terminate libcds
  50             cds::Terminate();
  51         }
  52         \endcode
  53
  54         Each thread that uses cds::gc::HRC -based containers must be attached to HRC
  55         singleton. To make attachment you should declare a object of class HRC::thread_gc:
  56         \code
  57         #include <cds/gc/hrc.h>
  58
  59         int myThreadEntryPoint()
  60         {
  61             // Attach the thread to HRC singleton
  62             cds::gc::HRC::thread_gc myThreadGC();
  63
  64             // Do some work
  65             ...
  66
  67             // The destructor of myThreadGC object detaches the thread from HRC singleton
  68         }
  69         \endcode
  70
  71         In some cases, you should work in a external thread. For example, your application
  72         is a plug-in for a server that calls your code in the threads that has been created by server.
  73         In this case, you may use persistent mode of HRC::thread_gc. In this mode, the thread attaches
  74         to the HRC singleton only if it is not yet attached and never call detaching:
  75         \code
  76         #include <cds/gc/hrc.h>
  77
  78         int myThreadEntryPoint()
  79         {
  80         // Attach the thread in persistent mode
  81         cds::gc::HRC::thread_gc myThreadGC( true );
  82
  83         // Do some work
  84         ...
  85
  86         // The destructor of myThreadGC object does NOT detach the thread from HRC singleton
  87         }
  88         \endcode
  89
  90     */
  91     class HRC
  92     {
  93     public:
  94
  95         /// Thread GC implementation for internal usage
  96         typedef hrc::ThreadGC   thread_gc_impl;
  97
  98         /// Wrapper for hrc::ThreadGC class
  99         /**
 100             @headerfile cds/gc/hrc.h
 101             This class performs automatically attaching/detaching Gidenstam's GC
 102             for the current thread.
 103         */
 104         class thread_gc: public thread_gc_impl
 105         {
 106             //@cond
 107             bool    m_bPersistent;
 108             //@endcond
 109         public:
 110             /// Constructor
 111             /**
 112                 The constructor attaches the current thread to the Gidenstam's GC
 113                 if it is not yet attached.
 114                 The \p bPersistent parameter specifies attachment persistence:
 115                 - \p true - the class destructor will not detach the thread from Gidenstam's GC.
 116                 - \p false (default) - the class destructor will detach the thread from Gidenstam's GC.
 117             */
 118             thread_gc(
 119                 bool    bPersistent = false
 120             ) ; // inline in hrc_impl.h
 121
 122             /// Destructor
 123             /**
 124                 If the object has been created in persistent mode, the destructor does nothing.
 125                 Otherwise it detaches the current thread from HRC GC.
 126             */
 127             ~thread_gc()    ;   // inline in hrc_impl.h
 128         };
 129
 130         ///@anchor hrc_gc_HRC_container_node Base for container node
 131         typedef hrc::ContainerNode container_node;
 132
 133         /// Native hazard pointer type
 134         typedef container_node * guarded_pointer;
 135
 136         /// Atomic reference
 137         /**
 138             @headerfile cds/gc/hrc.h
 139         */
 140         template <typename T>
 141         class atomic_ref: protected atomics::atomic<T *>
 142         {
 143             //@cond
 144             typedef atomics::atomic<T *> base_class;
 145             //@endcond
 146         public:
 147             //@cond
 148             atomic_ref() = default;
 149             explicit CDS_CONSTEXPR atomic_ref(T * p) CDS_NOEXCEPT
 150                 : base_class( p )
 151             {}
 152             //@endcond
 153
 154             /// Read reference value
 155             T * load( atomics::memory_order order ) const CDS_NOEXCEPT
 156             {
 157                 return base_class::load( order );
 158             }
 159             //@cond
 160             T * load( atomics::memory_order order ) const volatile CDS_NOEXCEPT
 161             {
 162                 return base_class::load( order );
 163             }
 164             //@endcond
 165
 166             /// Store new value to reference
 167             void store( T * pNew, atomics::memory_order order ) CDS_NOEXCEPT
 168             {
 169                 before_store( pNew );
 170                 T * pOld = base_class::exchange( pNew, order );
 171                 after_store( pOld, pNew );
 172             }
 173             //@cond
 174             void store( T * pNew, atomics::memory_order order ) volatile CDS_NOEXCEPT
 175             {
 176                 before_store( pNew );
 177                 T * pOld = base_class::exchange( pNew, order );
 178                 after_store( pOld, pNew );
 179             }
 180             //@endcond
 181
 182             /// Updates atomic reference from current value \p pOld to new value \p pNew (strong CAS)
 183             /**
 184                 May be used when concurrent updates are possible
 185
 186                 \p T - class derived from \ref hrc_gc_HRC_container_node "container_node" type
 187             */
 188             bool compare_exchange_strong( T *& pOld, T * pNew, atomics::memory_order mo_success, atomics::memory_order mo_fail ) CDS_NOEXCEPT
 189             {
 190                 before_cas( pNew );
 191                 bool bSuccess = base_class::compare_exchange_strong( pOld, pNew, mo_success, mo_fail );
 192                 after_cas( bSuccess, pOld, pNew );
 193                 return bSuccess;
 194             }
 195             //@cond
 196             bool compare_exchange_strong( T *& pOld, T * pNew, atomics::memory_order mo_success, atomics::memory_order mo_fail ) volatile CDS_NOEXCEPT
 197             {
 198                 before_cas( pNew );
 199                 bool bSuccess = base_class::compare_exchange_strong( pOld, pNew, mo_success, mo_fail );
 200                 after_cas( bSuccess, pOld, pNew );
 201                 return bSuccess;
 202             }
 203             bool compare_exchange_strong( T *& pOld, T * pNew, atomics::memory_order mo_success ) CDS_NOEXCEPT
 204             {
 205                 return compare_exchange_strong( pOld, pNew, mo_success, atomics::memory_order_relaxed );
 206             }
 207             bool compare_exchange_strong( T *& pOld, T * pNew, atomics::memory_order mo_success ) volatile CDS_NOEXCEPT
 208             {
 209                 return compare_exchange_strong( pOld, pNew, mo_success, atomics::memory_order_relaxed );
 210             }
 211             //@endcond
 212
 213             /// Updates atomic reference from current value \p pOld to new value \p pNew (weak CAS)
 214             /**
 215                 May be used when concurrent updates are possible
 216
 217                 \p T - class derived from \ref hrc_gc_HRC_container_node "container_node" type
 218             */
 219             bool compare_exchange_weak( T *& pOld, T * pNew, atomics::memory_order mo_success, atomics::memory_order mo_fail ) CDS_NOEXCEPT
 220             {
 221                 before_cas( pNew );
 222                 bool bSuccess = base_class::compare_exchange_weak( pOld, pNew, mo_success, mo_fail );
 223                 after_cas( bSuccess, pOld, pNew );
 224                 return bSuccess;
 225             }
 226             //@cond
 227             bool compare_exchange_weak( T *& pOld, T * pNew, atomics::memory_order mo_success, atomics::memory_order mo_fail ) volatile CDS_NOEXCEPT
 228             {
 229                 before_cas( pNew );
 230                 bool bSuccess = base_class::compare_exchange_weak( pOld, pNew, mo_success, mo_fail );
 231                 after_cas( bSuccess, pOld, pNew );
 232                 return bSuccess;
 233             }
 234             bool compare_exchange_weak( T *& pOld, T * pNew, atomics::memory_order mo_success ) CDS_NOEXCEPT
 235             {
 236                 return compare_exchange_weak( pOld, pNew, mo_success, atomics::memory_order_relaxed );
 237             }
 238             bool compare_exchange_weak( T *& pOld, T * pNew, atomics::memory_order mo_success ) volatile CDS_NOEXCEPT
 239             {
 240                 return compare_exchange_weak( pOld, pNew, mo_success, atomics::memory_order_relaxed );
 241             }
 242             //@endcond
 243
 244         private:
 245             //@cond
 246             static void before_store( T * pNew ) CDS_NOEXCEPT
 247             {
 248                 if ( pNew )
 249                     ++pNew->m_RC;
 250             }
 251             static void after_store( T * pOld, T * pNew ) CDS_NOEXCEPT
 252             {
 253                 if ( pNew )
 254                     pNew->m_bTrace.store( false, atomics::memory_order_release );
 255                 if ( pOld )
 256                     --pOld->m_RC;
 257             }
 258             static void before_cas( T * p ) CDS_NOEXCEPT
 259             {
 260                 if ( p ) {
 261                     ++p->m_RC;
 262                     p->m_bTrace.store( false, atomics::memory_order_release );
 263                 }
 264             }
 265             static void after_cas( bool bSuccess, T * pOld, T * pNew ) CDS_NOEXCEPT
 266             {
 267                 if ( bSuccess ) {
 268                     if ( pOld )
 269                         --pOld->m_RC;
 270                 }
 271                 else {
 272                     if ( pNew )
 273                         --pNew->m_RC;
 274                 }
 275             }
 276             //@endcond
 277         };
 278
 279         /// Atomic marked pointer
 280         /**
 281             @headerfile cds/gc/hrc.h
 282         */
 283         template <typename MarkedPtr>
 284         class atomic_marked_ptr
 285         {
 286             //@cond
 287             atomics::atomic< MarkedPtr >     m_a;
 288             //@endcond
 289         public:
 290             /// Marked pointer type
 291             typedef MarkedPtr    marked_ptr;
 292
 293             //@cond
 294             atomic_marked_ptr() CDS_NOEXCEPT
 295                 : m_a( marked_ptr() )
 296             {}
 297
 298             explicit CDS_CONSTEXPR atomic_marked_ptr( typename marked_ptr::value_type * p ) CDS_NOEXCEPT
 299                 : m_a( marked_ptr(p) )
 300             {}
 301
 302             atomic_marked_ptr( typename marked_ptr::value_type * ptr, int nMask ) CDS_NOEXCEPT
 303                 : m_a( marked_ptr(ptr, nMask) )
 304             {}
 305
 306             explicit atomic_marked_ptr( marked_ptr const&  ptr ) CDS_NOEXCEPT
 307                 : m_a( ptr )
 308             {}
 309             //@endcond
 310
 311
 312             /// Read reference value
 313             marked_ptr load(atomics::memory_order order) const CDS_NOEXCEPT
 314             {
 315                 return m_a.load(order);
 316             }
 317
 318             /// Store new value to reference
 319             void store( marked_ptr pNew, atomics::memory_order order ) CDS_NOEXCEPT
 320             {
 321                 before_store( pNew.ptr() );
 322                 marked_ptr pOld = m_a.exchange( pNew, order );
 323                 after_store( pOld.ptr(), pNew.ptr() );
 324             }
 325
 326             /// Store new value to reference
 327             void store( typename marked_ptr::pointer_type pNew, atomics::memory_order order ) CDS_NOEXCEPT
 328             {
 329                 before_store( pNew );
 330                 marked_ptr pOld = m_a.exchange( marked_ptr(pNew), order );
 331                 after_store( pOld.ptr(), pNew );
 332             }
 333
 334             /// Updates atomic reference from current value \p pOld to new value \p pNew (weak CAS)
 335             /**
 336                 May be used when concurrent updates are possible
 337
 338                 \p T - class derived from \ref hrc_gc_HRC_container_node "container_node" type
 339             */
 340             bool compare_exchange_weak( marked_ptr& pOld, marked_ptr pNew, atomics::memory_order mo_success, atomics::memory_order mo_fail ) CDS_NOEXCEPT
 341             {
 342                 before_cas( pNew.ptr() );
 343                 bool bSuccess = m_a.compare_exchange_weak( pOld, pNew, mo_success, mo_fail );
 344                 after_cas( bSuccess, pOld.ptr(), pNew.ptr() );
 345                 return bSuccess;
 346             }
 347             //@cond
 348             bool compare_exchange_weak( marked_ptr& pOld, marked_ptr pNew, atomics::memory_order mo_success ) CDS_NOEXCEPT
 349             {
 350                 before_cas( pNew.ptr() );
 351                 bool bSuccess = m_a.compare_exchange_weak( pOld, pNew, mo_success );
 352                 after_cas( bSuccess, pOld.ptr(), pNew.ptr() );
 353                 return bSuccess;
 354             }
 355             //@endcond
 356
 357             /// Updates atomic reference from current value \p pOld to new value \p pNew (strong CAS)
 358             /**
 359                 May be used when concurrent updates are possible
 360
 361                 \p T - class derived from \ref hrc_gc_HRC_container_node "container_node" type
 362             */
 363             bool compare_exchange_strong( marked_ptr& pOld, marked_ptr pNew, atomics::memory_order mo_success, atomics::memory_order mo_fail ) CDS_NOEXCEPT
 364             {
 365                 // protect pNew
 366                 before_cas( pNew.ptr() );
 367                 bool bSuccess = m_a.compare_exchange_strong( pOld, pNew, mo_success, mo_fail );
 368                 after_cas( bSuccess, pOld.ptr(), pNew.ptr() );
 369                 return bSuccess;
 370             }
 371             //@cond
 372             bool compare_exchange_strong( marked_ptr& pOld, marked_ptr pNew, atomics::memory_order mo_success ) CDS_NOEXCEPT
 373             {
 374                 before_cas( pNew.ptr() );
 375                 bool bSuccess = m_a.compare_exchange_strong( pOld, pNew, mo_success );
 376                 after_cas( bSuccess, pOld.ptr(), pNew.ptr() );
 377                 return bSuccess;
 378             }
 379             //@endcond
 380
 381         private:
 382             //@cond
 383             static void before_store( typename marked_ptr::pointer_type p ) CDS_NOEXCEPT
 384             {
 385                 if ( p )
 386                     ++p->m_RC;
 387             }
 388             static void after_store( typename marked_ptr::pointer_type pOld, typename marked_ptr::pointer_type pNew ) CDS_NOEXCEPT
 389             {
 390                 if ( pNew )
 391                     pNew->m_bTrace.store( false, atomics::memory_order_release );
 392                 if ( pOld )
 393                     --pOld->m_RC;
 394             }
 395             static void before_cas( typename marked_ptr::pointer_type p ) CDS_NOEXCEPT
 396             {
 397                 if ( p ) {
 398                     ++p->m_RC;
 399                     p->m_bTrace.store( false, atomics::memory_order_release );
 400                 }
 401             }
 402             static void after_cas( bool bSuccess, typename marked_ptr::pointer_type pOld, typename marked_ptr::pointer_type pNew ) CDS_NOEXCEPT
 403             {
 404                 if ( bSuccess ) {
 405                     if ( pOld )
 406                         --pOld->m_RC;
 407                 }
 408                 else {
 409                     if ( pNew )
 410                         --pNew->m_RC;
 411                 }
 412             }
 413             //@endcond
 414         };
 415
 416         /// HRC guard
 417         /**
 418             @headerfile cds/gc/hrc.h
 419             This class is a wrapper for hrc::AutoHPGuard.
 420         */
 421         class Guard: public hrc::AutoHPGuard
 422         {
 423             //@cond
 424             typedef hrc::AutoHPGuard base_class;
 425             //@endcond
 426
 427         public:
 428             /// Default constructor
 429             Guard() ;   // inline in hrc_impl.h
 430
 431             /// Protects atomic pointer
 432             /**
 433                 Return the value of \p toGuard
 434
 435                 The function tries to load \p toGuard and to store it
 436                 to the HP slot repeatedly until the guard's value equals \p toGuard
 437             */
 438             template <typename T>
 439             T * protect( atomic_ref<T> const& toGuard )
 440             {
 441                 T * pCur = toGuard.load(atomics::memory_order_relaxed);
 442                 T * pRet;
 443                 do {
 444                     pRet = assign( pCur );
 445                     pCur = toGuard.load(atomics::memory_order_acquire);
 446                 } while ( pRet != pCur );
 447                 return pCur;
 448             }
 449
 450             /// Protects a converted pointer of type \p atomic<T*>
 451             /**
 452                 Return the value of \p toGuard
 453
 454                 The function tries to load \p toGuard and to store result of \p f functor
 455                 to the HP slot repeatedly until the guard's value equals \p toGuard.
 456
 457                 The function is useful for intrusive containers when \p toGuard is a node pointer
 458                 that should be converted to a pointer to the value type before guarding.
 459                 The parameter \p f of type Func is a functor that makes this conversion:
 460                 \code
 461                     struct functor {
 462                         value_type * operator()( T * p );
 463                     };
 464                 \endcode
 465                 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
 466             */
 467             template <typename T, class Func>
 468             T * protect( atomic_ref<T> const& toGuard, Func f )
 469             {
 470                 T * pCur = toGuard.load(atomics::memory_order_relaxed);
 471                 T * pRet;
 472                 do {
 473                     pRet = pCur;
 474                     assign( f( pCur ) );
 475                     pCur = toGuard.load(atomics::memory_order_acquire);
 476                 } while ( pRet != pCur );
 477                 return pCur;
 478             }
 479
 480             /// Protects a atomic marked reference \p link
 481             /**
 482                 Returns current value of \p link.
 483
 484                 The function tries to load \p link and to store it
 485                 to the guard repeatedly until the guard's value equals \p link
 486             */
 487             template <typename T>
 488             typename atomic_marked_ptr<T>::marked_ptr protect( atomic_marked_ptr<T> const& link )
 489             {
 490                 typename atomic_marked_ptr<T>::marked_ptr p;
 491                 do {
 492                     assign( ( p = link.load(atomics::memory_order_relaxed)).ptr() );
 493                 } while ( p != link.load(atomics::memory_order_acquire) );
 494                 return p;
 495             }
 496
 497             /// Protects a atomic marked reference \p link
 498             /**
 499                 Returns current value of \p link.
 500
 501                 The function tries to load \p link and to store it
 502                 to the guard repeatedly until the guard's value equals \p link
 503
 504                 The function is useful for intrusive containers when \p link is a node pointer
 505                 that should be converted to a pointer to the value type before guarding.
 506                 The parameter \p f of type Func is a functor that makes this conversion:
 507                 \code
 508                     struct functor {
 509                         value_type * operator()( T p );
 510                     };
 511                 \endcode
 512                 Really, the result of <tt> f( link.load() ) </tt> is assigned to the hazard pointer.
 513             */
 514             template <typename T, typename Func>
 515             typename atomic_marked_ptr<T>::marked_ptr protect( atomic_marked_ptr<T> const& link, Func f )
 516             {
 517                 typename atomic_marked_ptr<T>::marked_ptr pCur;
 518                 do {
 519                     pCur = link.load(atomics::memory_order_relaxed);
 520                     assign( f( pCur ));
 521                 } while ( pCur != link.load(atomics::memory_order_acquire) );
 522                 return pCur;
 523             }
 524
 525             /// Stores \p p to the guard
 526             /**
 527                 The function equals to a simple assignment, no loop is performed.
 528                 Can be used for a pointer that cannot be changed concurrently.
 529             */
 530             template <typename T>
 531             T * assign( T * p )
 532             {
 533                 return base_class::operator =(p);
 534             }
 535
 536             /// Stores marked pointer \p p to the guard
 537             /**
 538                 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
 539                 Can be used for a marked pointer that cannot be changed concurrently.
 540             */
 541             template <typename T, int Bitmask>
 542             T * assign( cds::details::marked_ptr<T, Bitmask> p )
 543             {
 544                 return base_class::operator =( p.ptr() );
 545             }
 546
 547             /// Copy from \p src guard to \p this guard
 548             void copy( Guard const& src )
 549             {
 550                 assign( src.get_native() );
 551             }
 552
 553             /// Clear value of the guard
 554             void clear()
 555             {
 556                 base_class::clear();
 557             }
 558
 559             /// Get the value currently protected
 560             template <typename T>
 561             T * get() const
 562             {
 563                 return static_cast<T *>( get_native());
 564             }
 565
 566             /// Get native hazard pointer stored
 567             guarded_pointer get_native() const
 568             {
 569                 return base_class::get();
 570             }
 571         };
 572
 573         /// Array of guards
 574         /**
 575             @headerfile cds/gc/hrc.h
 576             This class is a wrapper for AutoHPArray template.
 577             Template parameter \p Limit defines the size of HP array.
 578         */
 579         template <size_t Limit>
 580         class GuardArray: public hrc::AutoHPArray<Limit>
 581         {
 582             //@cond
 583             typedef hrc::AutoHPArray<Limit> base_class;
 584             //@endcond
 585         public:
 586             /// Rebind array for other size \p OtherLimit
 587             template <size_t OtherLimit>
 588             struct rebind {
 589                 typedef GuardArray<OtherLimit>  other   ;   ///< rebinding result
 590             };
 591
 592         public:
 593             //@cond
 594             GuardArray()    ;   // inline in hrc_impl.h
 595             GuardArray( thread_gc_impl& threadGC )
 596                 : base_class( threadGC )
 597             {}
 598             //@endcond
 599
 600             /// Protects an atomic reference \p link in slot \p nIndex
 601             /**
 602                 Returns current value of \p link.
 603
 604                 The function tries to load \p pToGuard and to store it
 605                 to the slot \p nIndex repeatedly until the guard's value equals \p pToGuard
 606             */
 607             template <typename T>
 608             T * protect( size_t nIndex, atomic_ref<T> const& link )
 609             {
 610                 T * p;
 611                 do {
 612                     p = assign( nIndex, link.load(atomics::memory_order_relaxed) );
 613                 } while ( p != link.load(atomics::memory_order_acquire) );
 614                 return p;
 615             }
 616
 617             /// Protects a atomic marked reference \p link in slot \p nIndex
 618             /**
 619                 Returns current value of \p link.
 620
 621                 The function tries to load \p link and to store it
 622                 to the slot \p nIndex repeatedly until the guard's value equals \p link
 623             */
 624             template <typename T>
 625             typename atomic_marked_ptr<T>::marked_ptr protect( size_t nIndex, atomic_marked_ptr<T> const& link )
 626             {
 627                 typename atomic_marked_ptr<T>::marked_ptr p;
 628                 do {
 629                     assign( nIndex, ( p = link.load(atomics::memory_order_relaxed)).ptr() );
 630                 } while ( p != link.load(atomics::memory_order_acquire) );
 631                 return p;
 632             }
 633
 634             /// Protects a pointer of type \p atomic<T*>
 635             /**
 636                 Return the value of \p toGuard
 637
 638                 The function tries to load \p toGuard and to store it
 639                 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
 640
 641                 The function is useful for intrusive containers when \p toGuard is a node pointer
 642                 that should be converted to a pointer to the value type before guarding.
 643                 The parameter \p f of type Func is a functor that makes this conversion:
 644                 \code
 645                     struct functor {
 646                         value_type * operator()( T * p );
 647                     };
 648                 \endcode
 649                 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
 650             */
 651             template <typename T, class Func>
 652             T * protect(size_t nIndex, atomic_ref<T> const& toGuard, Func f )
 653             {
 654                 T * pRet;
 655                 do {
 656                     assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_relaxed) ));
 657                 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
 658
 659                 return pRet;
 660             }
 661
 662             /// Protects a atomic marked reference \p link in slot \p nIndex
 663             /**
 664                 Returns current value of \p link.
 665
 666                 The function tries to load \p link and to store it
 667                 to the slot \p nIndex repeatedly until the guard's value equals \p link
 668
 669                 The function is useful for intrusive containers when \p link is a node pointer
 670                 that should be converted to a pointer to the value type before guarding.
 671                 The parameter \p f of type Func is a functor that makes this conversion:
 672                 \code
 673                     struct functor {
 674                         value_type * operator()( T p );
 675                     };
 676                 \endcode
 677                 Really, the result of <tt> f( link.load() ) </tt> is assigned to the hazard pointer.
 678             */
 679             template <typename T, typename Func>
 680             typename atomic_marked_ptr<T>::marked_ptr protect( size_t nIndex, atomic_marked_ptr<T> const& link, Func f )
 681             {
 682                 typename atomic_marked_ptr<T>::marked_ptr p;
 683                 do {
 684                     p = link.load(atomics::memory_order_relaxed);
 685                     assign( nIndex, f( p ) );
 686                 } while ( p != link.load(atomics::memory_order_acquire) );
 687                 return p;
 688             }
 689
 690             /// Store \p to the slot \p nIndex
 691             /**
 692                 The function equals to a simple assignment, no loop is performed.
 693             */
 694             template <typename T>
 695             T * assign( size_t nIndex, T * p )
 696             {
 697                 base_class::set(nIndex, p);
 698                 return p;
 699             }
 700
 701             /// Store marked pointer \p p to the guard
 702             /**
 703                 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
 704                 Can be used for a marked pointer that cannot be changed concurrently.
 705             */
 706             template <typename T, int Bitmask>
 707             T * assign( size_t nIndex, cds::details::marked_ptr<T, Bitmask> p )
 708             {
 709                 return base_class::set( nIndex, p.ptr() );
 710             }
 711
 712             /// Copy guarded value from \p src guard to slot at index \p nIndex
 713             void copy( size_t nIndex, Guard const& src )
 714             {
 715                 assign( nIndex, src.get_native() );
 716             }
 717
 718             /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex
 719             void copy( size_t nDestIndex, size_t nSrcIndex )
 720             {
 721                 assign( nDestIndex, get_native( nSrcIndex ));
 722             }
 723
 724             /// Clear value of the slot \p nIndex
 725             void clear( size_t nIndex)
 726             {
 727                 base_class::clear( nIndex );
 728             }
 729
 730             /// Get current value of slot \p nIndex
 731             template <typename T>
 732             T * get( size_t nIndex) const
 733             {
 734                 return static_cast<T *>( get_native( nIndex ) );
 735             }
 736
 737             /// Get native hazard pointer stored
 738             guarded_pointer get_native( size_t nIndex ) const
 739             {
 740                 return base_class::operator[](nIndex).get();
 741             }
 742
 743             /// Capacity of the guard array
 744             static CDS_CONSTEXPR size_t capacity()
 745             {
 746                 return Limit;
 747             }
 748         };
 749
 750     public:
 751         /// Initializes hrc::GarbageCollector singleton
 752         /**
 753             The constructor calls hrc::GarbageCollector::Construct with passed parameters.
 754             See hrc::GarbageCollector::Construct for explanation of parameters meaning.
 755         */
 756         HRC(
 757             size_t nHazardPtrCount = 0,     ///< number of hazard pointers
 758             size_t nMaxThreadCount = 0,     ///< max threads count
 759             size_t nMaxNodeLinkCount = 0,   ///< max number of links a @ref hrc::ContainerNode can contain
 760             size_t nMaxTransientLinks = 0   ///< max number of links in live nodes that may transiently point to a deleted node
 761         )
 762         {
 763             hrc::GarbageCollector::Construct(
 764                 nHazardPtrCount,
 765                 nMaxThreadCount,
 766                 nMaxNodeLinkCount,
 767                 nMaxTransientLinks
 768             );
 769         }
 770
 771         /// Terminates hrc::GarbageCollector singleton
 772         /**
 773             The destructor calls \code hrc::GarbageCollector::Destruct() \endcode
 774         */
 775         ~HRC()
 776         {
 777             hrc::GarbageCollector::Destruct();
 778         }
 779
 780         /// Checks if count of hazard pointer is no less than \p nCountNeeded
 781         /**
 782             If \p bRaiseException is \p true (that is the default), the function raises an exception gc::too_few_hazard_pointers
 783             if \p nCountNeeded is more than the count of hazard pointer per thread.
 784         */
 785         static bool check_available_guards( size_t nCountNeeded, bool bRaiseException = true )
 786         {
 787             if ( hrc::GarbageCollector::instance().getHazardPointerCount() < nCountNeeded ) {
 788                 if ( bRaiseException )
 789                     throw cds::gc::too_few_hazard_pointers();
 790                 return false;
 791             }
 792             return true;
 793         }
 794
 795         /// Retire pointer \p p with function \p pFunc
 796         /**
 797             The function places pointer \p p to array of pointers ready for removing.
 798             (so called retired pointer array). The pointer can be safely removed when no guarded pointer points to it.
 799             Deleting the pointer is the function \p pFunc call.
 800         */
 801         template <typename T>
 802         static void retire( T * p, void (* pFunc)(T *) )    ;   // inline in hrc_impl.h
 803
 804         /// Retire pointer \p p with functor of type \p Disposer
 805         /**
 806             The function places pointer \p p to array of pointers ready for removing.
 807             (so called retired pointer array). The pointer can be safely removed when no guard points to it.
 808
 809             See gc::HP::retire for \p Disposer requirements.
 810         */
 811         template <class Disposer, typename T>
 812         static void retire( T * p ) ;   // inline in hrc_impl.h
 813
 814         /// Checks if HRC GC is constructed and may be used
 815         static bool isUsed()
 816         {
 817             return hrc::GarbageCollector::isUsed();
 818         }
 819
 820         /// Forced GC cycle call for current thread
 821         /**
 822             Usually, this function should not be called directly.
 823         */
 824         static void scan()  ;   // inline in hrc_impl.h
 825
 826         /// Synonym for \ref scan()
 827         static void force_dispose()
 828         {
 829             scan();
 830         }
 831     };
 832 }} // namespace cds::gc
 833
 834 #endif // #ifndef __CDS_GC_HRC_DECL_H