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 #   ifdef CDS_CXX11_EXPLICITLY_DEFAULTED_FUNCTION_SUPPORT
 149             atomic_ref() = default;
 150 #   else
 151             atomic_ref() CDS_NOEXCEPT
 152                 : base_class()
 153             {}
 154 #   endif
 155             explicit CDS_CONSTEXPR atomic_ref(T * p) CDS_NOEXCEPT
 156                 : base_class( p )
 157             {}
 158             //@endcond
 159
 160             /// Read reference value
 161             T * load( atomics::memory_order order ) const CDS_NOEXCEPT
 162             {
 163                 return base_class::load( order );
 164             }
 165             //@cond
 166             T * load( atomics::memory_order order ) const volatile CDS_NOEXCEPT
 167             {
 168                 return base_class::load( order );
 169             }
 170             //@endcond
 171
 172             /// Store new value to reference
 173             void store( T * pNew, atomics::memory_order order ) CDS_NOEXCEPT
 174             {
 175                 before_store( pNew );
 176                 T * pOld = base_class::exchange( pNew, order );
 177                 after_store( pOld, pNew );
 178             }
 179             //@cond
 180             void store( T * pNew, atomics::memory_order order ) volatile CDS_NOEXCEPT
 181             {
 182                 before_store( pNew );
 183                 T * pOld = base_class::exchange( pNew, order );
 184                 after_store( pOld, pNew );
 185             }
 186             //@endcond
 187
 188             /// Updates atomic reference from current value \p pOld to new value \p pNew (strong CAS)
 189             /**
 190                 May be used when concurrent updates are possible
 191
 192                 \p T - class derived from \ref hrc_gc_HRC_container_node "container_node" type
 193             */
 194             bool compare_exchange_strong( T *& pOld, T * pNew, atomics::memory_order mo_success, atomics::memory_order mo_fail ) CDS_NOEXCEPT
 195             {
 196                 before_cas( pNew );
 197                 bool bSuccess = base_class::compare_exchange_strong( pOld, pNew, mo_success, mo_fail );
 198                 after_cas( bSuccess, pOld, pNew );
 199                 return bSuccess;
 200             }
 201             //@cond
 202             bool compare_exchange_strong( T *& pOld, T * pNew, atomics::memory_order mo_success, atomics::memory_order mo_fail ) volatile CDS_NOEXCEPT
 203             {
 204                 before_cas( pNew );
 205                 bool bSuccess = base_class::compare_exchange_strong( pOld, pNew, mo_success, mo_fail );
 206                 after_cas( bSuccess, pOld, pNew );
 207                 return bSuccess;
 208             }
 209             bool compare_exchange_strong( T *& pOld, T * pNew, atomics::memory_order mo_success ) CDS_NOEXCEPT
 210             {
 211                 return compare_exchange_strong( pOld, pNew, mo_success, atomics::memory_order_relaxed );
 212             }
 213             bool compare_exchange_strong( T *& pOld, T * pNew, atomics::memory_order mo_success ) volatile CDS_NOEXCEPT
 214             {
 215                 return compare_exchange_strong( pOld, pNew, mo_success, atomics::memory_order_relaxed );
 216             }
 217             //@endcond
 218
 219             /// Updates atomic reference from current value \p pOld to new value \p pNew (weak CAS)
 220             /**
 221                 May be used when concurrent updates are possible
 222
 223                 \p T - class derived from \ref hrc_gc_HRC_container_node "container_node" type
 224             */
 225             bool compare_exchange_weak( T *& pOld, T * pNew, atomics::memory_order mo_success, atomics::memory_order mo_fail ) CDS_NOEXCEPT
 226             {
 227                 before_cas( pNew );
 228                 bool bSuccess = base_class::compare_exchange_weak( pOld, pNew, mo_success, mo_fail );
 229                 after_cas( bSuccess, pOld, pNew );
 230                 return bSuccess;
 231             }
 232             //@cond
 233             bool compare_exchange_weak( T *& pOld, T * pNew, atomics::memory_order mo_success, atomics::memory_order mo_fail ) volatile CDS_NOEXCEPT
 234             {
 235                 before_cas( pNew );
 236                 bool bSuccess = base_class::compare_exchange_weak( pOld, pNew, mo_success, mo_fail );
 237                 after_cas( bSuccess, pOld, pNew );
 238                 return bSuccess;
 239             }
 240             bool compare_exchange_weak( T *& pOld, T * pNew, atomics::memory_order mo_success ) CDS_NOEXCEPT
 241             {
 242                 return compare_exchange_weak( pOld, pNew, mo_success, atomics::memory_order_relaxed );
 243             }
 244             bool compare_exchange_weak( T *& pOld, T * pNew, atomics::memory_order mo_success ) volatile CDS_NOEXCEPT
 245             {
 246                 return compare_exchange_weak( pOld, pNew, mo_success, atomics::memory_order_relaxed );
 247             }
 248             //@endcond
 249
 250         private:
 251             //@cond
 252             static void before_store( T * pNew ) CDS_NOEXCEPT
 253             {
 254                 if ( pNew )
 255                     ++pNew->m_RC;
 256             }
 257             static void after_store( T * pOld, T * pNew ) CDS_NOEXCEPT
 258             {
 259                 if ( pNew )
 260                     pNew->m_bTrace.store( false, atomics::memory_order_release );
 261                 if ( pOld )
 262                     --pOld->m_RC;
 263             }
 264             static void before_cas( T * p ) CDS_NOEXCEPT
 265             {
 266                 if ( p ) {
 267                     ++p->m_RC;
 268                     p->m_bTrace.store( false, atomics::memory_order_release );
 269                 }
 270             }
 271             static void after_cas( bool bSuccess, T * pOld, T * pNew ) CDS_NOEXCEPT
 272             {
 273                 if ( bSuccess ) {
 274                     if ( pOld )
 275                         --pOld->m_RC;
 276                 }
 277                 else {
 278                     if ( pNew )
 279                         --pNew->m_RC;
 280                 }
 281             }
 282             //@endcond
 283         };
 284
 285         /// Atomic marked pointer
 286         /**
 287             @headerfile cds/gc/hrc.h
 288         */
 289         template <typename MarkedPtr>
 290         class atomic_marked_ptr
 291         {
 292             //@cond
 293             atomics::atomic< MarkedPtr >     m_a;
 294             //@endcond
 295         public:
 296             /// Marked pointer type
 297             typedef MarkedPtr    marked_ptr;
 298
 299             //@cond
 300             atomic_marked_ptr() CDS_NOEXCEPT
 301                 : m_a( marked_ptr() )
 302             {}
 303
 304             explicit CDS_CONSTEXPR atomic_marked_ptr( typename marked_ptr::value_type * p ) CDS_NOEXCEPT
 305                 : m_a( marked_ptr(p) )
 306             {}
 307
 308             atomic_marked_ptr( typename marked_ptr::value_type * ptr, int nMask ) CDS_NOEXCEPT
 309                 : m_a( marked_ptr(ptr, nMask) )
 310             {}
 311
 312             explicit atomic_marked_ptr( marked_ptr const&  ptr ) CDS_NOEXCEPT
 313                 : m_a( ptr )
 314             {}
 315             //@endcond
 316
 317
 318             /// Read reference value
 319             marked_ptr load(atomics::memory_order order) const CDS_NOEXCEPT
 320             {
 321                 return m_a.load(order);
 322             }
 323
 324             /// Store new value to reference
 325             void store( marked_ptr pNew, atomics::memory_order order ) CDS_NOEXCEPT
 326             {
 327                 before_store( pNew.ptr() );
 328                 marked_ptr pOld = m_a.exchange( pNew, order );
 329                 after_store( pOld.ptr(), pNew.ptr() );
 330             }
 331
 332             /// Store new value to reference
 333             void store( typename marked_ptr::pointer_type pNew, atomics::memory_order order ) CDS_NOEXCEPT
 334             {
 335                 before_store( pNew );
 336                 marked_ptr pOld = m_a.exchange( marked_ptr(pNew), order );
 337                 after_store( pOld.ptr(), pNew );
 338             }
 339
 340             /// Updates atomic reference from current value \p pOld to new value \p pNew (weak CAS)
 341             /**
 342                 May be used when concurrent updates are possible
 343
 344                 \p T - class derived from \ref hrc_gc_HRC_container_node "container_node" type
 345             */
 346             bool compare_exchange_weak( marked_ptr& pOld, marked_ptr pNew, atomics::memory_order mo_success, atomics::memory_order mo_fail ) CDS_NOEXCEPT
 347             {
 348                 before_cas( pNew.ptr() );
 349                 bool bSuccess = m_a.compare_exchange_weak( pOld, pNew, mo_success, mo_fail );
 350                 after_cas( bSuccess, pOld.ptr(), pNew.ptr() );
 351                 return bSuccess;
 352             }
 353             //@cond
 354             bool compare_exchange_weak( marked_ptr& pOld, marked_ptr pNew, atomics::memory_order mo_success ) CDS_NOEXCEPT
 355             {
 356                 before_cas( pNew.ptr() );
 357                 bool bSuccess = m_a.compare_exchange_weak( pOld, pNew, mo_success );
 358                 after_cas( bSuccess, pOld.ptr(), pNew.ptr() );
 359                 return bSuccess;
 360             }
 361             //@endcond
 362
 363             /// Updates atomic reference from current value \p pOld to new value \p pNew (strong CAS)
 364             /**
 365                 May be used when concurrent updates are possible
 366
 367                 \p T - class derived from \ref hrc_gc_HRC_container_node "container_node" type
 368             */
 369             bool compare_exchange_strong( marked_ptr& pOld, marked_ptr pNew, atomics::memory_order mo_success, atomics::memory_order mo_fail ) CDS_NOEXCEPT
 370             {
 371                 // protect pNew
 372                 before_cas( pNew.ptr() );
 373                 bool bSuccess = m_a.compare_exchange_strong( pOld, pNew, mo_success, mo_fail );
 374                 after_cas( bSuccess, pOld.ptr(), pNew.ptr() );
 375                 return bSuccess;
 376             }
 377             //@cond
 378             bool compare_exchange_strong( marked_ptr& pOld, marked_ptr pNew, atomics::memory_order mo_success ) CDS_NOEXCEPT
 379             {
 380                 before_cas( pNew.ptr() );
 381                 bool bSuccess = m_a.compare_exchange_strong( pOld, pNew, mo_success );
 382                 after_cas( bSuccess, pOld.ptr(), pNew.ptr() );
 383                 return bSuccess;
 384             }
 385             //@endcond
 386
 387         private:
 388             //@cond
 389             static void before_store( typename marked_ptr::pointer_type p ) CDS_NOEXCEPT
 390             {
 391                 if ( p )
 392                     ++p->m_RC;
 393             }
 394             static void after_store( typename marked_ptr::pointer_type pOld, typename marked_ptr::pointer_type pNew ) CDS_NOEXCEPT
 395             {
 396                 if ( pNew )
 397                     pNew->m_bTrace.store( false, atomics::memory_order_release );
 398                 if ( pOld )
 399                     --pOld->m_RC;
 400             }
 401             static void before_cas( typename marked_ptr::pointer_type p ) CDS_NOEXCEPT
 402             {
 403                 if ( p ) {
 404                     ++p->m_RC;
 405                     p->m_bTrace.store( false, atomics::memory_order_release );
 406                 }
 407             }
 408             static void after_cas( bool bSuccess, typename marked_ptr::pointer_type pOld, typename marked_ptr::pointer_type pNew ) CDS_NOEXCEPT
 409             {
 410                 if ( bSuccess ) {
 411                     if ( pOld )
 412                         --pOld->m_RC;
 413                 }
 414                 else {
 415                     if ( pNew )
 416                         --pNew->m_RC;
 417                 }
 418             }
 419             //@endcond
 420         };
 421
 422         /// HRC guard
 423         /**
 424             @headerfile cds/gc/hrc.h
 425             This class is a wrapper for hrc::AutoHPGuard.
 426         */
 427         class Guard: public hrc::AutoHPGuard
 428         {
 429             //@cond
 430             typedef hrc::AutoHPGuard base_class;
 431             //@endcond
 432
 433         public:
 434             /// Default constructor
 435             Guard() ;   // inline in hrc_impl.h
 436
 437             /// Protects atomic pointer
 438             /**
 439                 Return the value of \p toGuard
 440
 441                 The function tries to load \p toGuard and to store it
 442                 to the HP slot repeatedly until the guard's value equals \p toGuard
 443             */
 444             template <typename T>
 445             T * protect( atomic_ref<T> const& toGuard )
 446             {
 447                 T * pCur = toGuard.load(atomics::memory_order_relaxed);
 448                 T * pRet;
 449                 do {
 450                     pRet = assign( pCur );
 451                     pCur = toGuard.load(atomics::memory_order_acquire);
 452                 } while ( pRet != pCur );
 453                 return pCur;
 454             }
 455
 456             /// Protects a converted pointer of type \p atomic<T*>
 457             /**
 458                 Return the value of \p toGuard
 459
 460                 The function tries to load \p toGuard and to store result of \p f functor
 461                 to the HP slot repeatedly until the guard's value equals \p toGuard.
 462
 463                 The function is useful for intrusive containers when \p toGuard is a node pointer
 464                 that should be converted to a pointer to the value type before guarding.
 465                 The parameter \p f of type Func is a functor that makes this conversion:
 466                 \code
 467                     struct functor {
 468                         value_type * operator()( T * p );
 469                     };
 470                 \endcode
 471                 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
 472             */
 473             template <typename T, class Func>
 474             T * protect( atomic_ref<T> const& toGuard, Func f )
 475             {
 476                 T * pCur = toGuard.load(atomics::memory_order_relaxed);
 477                 T * pRet;
 478                 do {
 479                     pRet = pCur;
 480                     assign( f( pCur ) );
 481                     pCur = toGuard.load(atomics::memory_order_acquire);
 482                 } while ( pRet != pCur );
 483                 return pCur;
 484             }
 485
 486             /// Protects a atomic marked reference \p link
 487             /**
 488                 Returns current value of \p link.
 489
 490                 The function tries to load \p link and to store it
 491                 to the guard repeatedly until the guard's value equals \p link
 492             */
 493             template <typename T>
 494             typename atomic_marked_ptr<T>::marked_ptr protect( atomic_marked_ptr<T> const& link )
 495             {
 496                 typename atomic_marked_ptr<T>::marked_ptr p;
 497                 do {
 498                     assign( ( p = link.load(atomics::memory_order_relaxed)).ptr() );
 499                 } while ( p != link.load(atomics::memory_order_acquire) );
 500                 return p;
 501             }
 502
 503             /// Protects a atomic marked reference \p link
 504             /**
 505                 Returns current value of \p link.
 506
 507                 The function tries to load \p link and to store it
 508                 to the guard repeatedly until the guard's value equals \p link
 509
 510                 The function is useful for intrusive containers when \p link is a node pointer
 511                 that should be converted to a pointer to the value type before guarding.
 512                 The parameter \p f of type Func is a functor that makes this conversion:
 513                 \code
 514                     struct functor {
 515                         value_type * operator()( T p );
 516                     };
 517                 \endcode
 518                 Really, the result of <tt> f( link.load() ) </tt> is assigned to the hazard pointer.
 519             */
 520             template <typename T, typename Func>
 521             typename atomic_marked_ptr<T>::marked_ptr protect( atomic_marked_ptr<T> const& link, Func f )
 522             {
 523                 typename atomic_marked_ptr<T>::marked_ptr pCur;
 524                 do {
 525                     pCur = link.load(atomics::memory_order_relaxed);
 526                     assign( f( pCur ));
 527                 } while ( pCur != link.load(atomics::memory_order_acquire) );
 528                 return pCur;
 529             }
 530
 531             /// Stores \p p to the guard
 532             /**
 533                 The function equals to a simple assignment, no loop is performed.
 534                 Can be used for a pointer that cannot be changed concurrently.
 535             */
 536             template <typename T>
 537             T * assign( T * p )
 538             {
 539                 return base_class::operator =(p);
 540             }
 541
 542             /// Stores marked pointer \p p to the guard
 543             /**
 544                 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
 545                 Can be used for a marked pointer that cannot be changed concurrently.
 546             */
 547             template <typename T, int Bitmask>
 548             T * assign( cds::details::marked_ptr<T, Bitmask> p )
 549             {
 550                 return base_class::operator =( p.ptr() );
 551             }
 552
 553             /// Copy from \p src guard to \p this guard
 554             void copy( Guard const& src )
 555             {
 556                 assign( src.get_native() );
 557             }
 558
 559             /// Clear value of the guard
 560             void clear()
 561             {
 562                 base_class::clear();
 563             }
 564
 565             /// Get the value currently protected
 566             template <typename T>
 567             T * get() const
 568             {
 569                 return static_cast<T *>( get_native());
 570             }
 571
 572             /// Get native hazard pointer stored
 573             guarded_pointer get_native() const
 574             {
 575                 return base_class::get();
 576             }
 577         };
 578
 579         /// Array of guards
 580         /**
 581             @headerfile cds/gc/hrc.h
 582             This class is a wrapper for AutoHPArray template.
 583             Template parameter \p Limit defines the size of HP array.
 584         */
 585         template <size_t Limit>
 586         class GuardArray: public hrc::AutoHPArray<Limit>
 587         {
 588             //@cond
 589             typedef hrc::AutoHPArray<Limit> base_class;
 590             //@endcond
 591         public:
 592             /// Rebind array for other size \p OtherLimit
 593             template <size_t OtherLimit>
 594             struct rebind {
 595                 typedef GuardArray<OtherLimit>  other   ;   ///< rebinding result
 596             };
 597
 598         public:
 599             //@cond
 600             GuardArray()    ;   // inline in hrc_impl.h
 601             GuardArray( thread_gc_impl& threadGC )
 602                 : base_class( threadGC )
 603             {}
 604             //@endcond
 605
 606             /// Protects an atomic reference \p link in slot \p nIndex
 607             /**
 608                 Returns current value of \p link.
 609
 610                 The function tries to load \p pToGuard and to store it
 611                 to the slot \p nIndex repeatedly until the guard's value equals \p pToGuard
 612             */
 613             template <typename T>
 614             T * protect( size_t nIndex, atomic_ref<T> const& link )
 615             {
 616                 T * p;
 617                 do {
 618                     p = assign( nIndex, link.load(atomics::memory_order_relaxed) );
 619                 } while ( p != link.load(atomics::memory_order_acquire) );
 620                 return p;
 621             }
 622
 623             /// Protects a atomic marked reference \p link in slot \p nIndex
 624             /**
 625                 Returns current value of \p link.
 626
 627                 The function tries to load \p link and to store it
 628                 to the slot \p nIndex repeatedly until the guard's value equals \p link
 629             */
 630             template <typename T>
 631             typename atomic_marked_ptr<T>::marked_ptr protect( size_t nIndex, atomic_marked_ptr<T> const& link )
 632             {
 633                 typename atomic_marked_ptr<T>::marked_ptr p;
 634                 do {
 635                     assign( nIndex, ( p = link.load(atomics::memory_order_relaxed)).ptr() );
 636                 } while ( p != link.load(atomics::memory_order_acquire) );
 637                 return p;
 638             }
 639
 640             /// Protects a pointer of type \p atomic<T*>
 641             /**
 642                 Return the value of \p toGuard
 643
 644                 The function tries to load \p toGuard and to store it
 645                 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
 646
 647                 The function is useful for intrusive containers when \p toGuard is a node pointer
 648                 that should be converted to a pointer to the value type before guarding.
 649                 The parameter \p f of type Func is a functor that makes this conversion:
 650                 \code
 651                     struct functor {
 652                         value_type * operator()( T * p );
 653                     };
 654                 \endcode
 655                 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
 656             */
 657             template <typename T, class Func>
 658             T * protect(size_t nIndex, atomic_ref<T> const& toGuard, Func f )
 659             {
 660                 T * pRet;
 661                 do {
 662                     assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_relaxed) ));
 663                 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
 664
 665                 return pRet;
 666             }
 667
 668             /// Protects a atomic marked reference \p link in slot \p nIndex
 669             /**
 670                 Returns current value of \p link.
 671
 672                 The function tries to load \p link and to store it
 673                 to the slot \p nIndex repeatedly until the guard's value equals \p link
 674
 675                 The function is useful for intrusive containers when \p link is a node pointer
 676                 that should be converted to a pointer to the value type before guarding.
 677                 The parameter \p f of type Func is a functor that makes this conversion:
 678                 \code
 679                     struct functor {
 680                         value_type * operator()( T p );
 681                     };
 682                 \endcode
 683                 Really, the result of <tt> f( link.load() ) </tt> is assigned to the hazard pointer.
 684             */
 685             template <typename T, typename Func>
 686             typename atomic_marked_ptr<T>::marked_ptr protect( size_t nIndex, atomic_marked_ptr<T> const& link, Func f )
 687             {
 688                 typename atomic_marked_ptr<T>::marked_ptr p;
 689                 do {
 690                     p = link.load(atomics::memory_order_relaxed);
 691                     assign( nIndex, f( p ) );
 692                 } while ( p != link.load(atomics::memory_order_acquire) );
 693                 return p;
 694             }
 695
 696             /// Store \p to the slot \p nIndex
 697             /**
 698                 The function equals to a simple assignment, no loop is performed.
 699             */
 700             template <typename T>
 701             T * assign( size_t nIndex, T * p )
 702             {
 703                 base_class::set(nIndex, p);
 704                 return p;
 705             }
 706
 707             /// Store marked pointer \p p to the guard
 708             /**
 709                 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
 710                 Can be used for a marked pointer that cannot be changed concurrently.
 711             */
 712             template <typename T, int Bitmask>
 713             T * assign( size_t nIndex, cds::details::marked_ptr<T, Bitmask> p )
 714             {
 715                 return base_class::set( nIndex, p.ptr() );
 716             }
 717
 718             /// Copy guarded value from \p src guard to slot at index \p nIndex
 719             void copy( size_t nIndex, Guard const& src )
 720             {
 721                 assign( nIndex, src.get_native() );
 722             }
 723
 724             /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex
 725             void copy( size_t nDestIndex, size_t nSrcIndex )
 726             {
 727                 assign( nDestIndex, get_native( nSrcIndex ));
 728             }
 729
 730             /// Clear value of the slot \p nIndex
 731             void clear( size_t nIndex)
 732             {
 733                 base_class::clear( nIndex );
 734             }
 735
 736             /// Get current value of slot \p nIndex
 737             template <typename T>
 738             T * get( size_t nIndex) const
 739             {
 740                 return static_cast<T *>( get_native( nIndex ) );
 741             }
 742
 743             /// Get native hazard pointer stored
 744             guarded_pointer get_native( size_t nIndex ) const
 745             {
 746                 return base_class::operator[](nIndex).get();
 747             }
 748
 749             /// Capacity of the guard array
 750             static CDS_CONSTEXPR size_t capacity()
 751             {
 752                 return Limit;
 753             }
 754         };
 755
 756     public:
 757         /// Initializes hrc::GarbageCollector singleton
 758         /**
 759             The constructor calls hrc::GarbageCollector::Construct with passed parameters.
 760             See hrc::GarbageCollector::Construct for explanation of parameters meaning.
 761         */
 762         HRC(
 763             size_t nHazardPtrCount = 0,     ///< number of hazard pointers
 764             size_t nMaxThreadCount = 0,     ///< max threads count
 765             size_t nMaxNodeLinkCount = 0,   ///< max number of links a @ref hrc::ContainerNode can contain
 766             size_t nMaxTransientLinks = 0   ///< max number of links in live nodes that may transiently point to a deleted node
 767         )
 768         {
 769             hrc::GarbageCollector::Construct(
 770                 nHazardPtrCount,
 771                 nMaxThreadCount,
 772                 nMaxNodeLinkCount,
 773                 nMaxTransientLinks
 774             );
 775         }
 776
 777         /// Terminates hrc::GarbageCollector singleton
 778         /**
 779             The destructor calls \code hrc::GarbageCollector::Destruct() \endcode
 780         */
 781         ~HRC()
 782         {
 783             hrc::GarbageCollector::Destruct();
 784         }
 785
 786         /// Checks if count of hazard pointer is no less than \p nCountNeeded
 787         /**
 788             If \p bRaiseException is \p true (that is the default), the function raises an exception gc::too_few_hazard_pointers
 789             if \p nCountNeeded is more than the count of hazard pointer per thread.
 790         */
 791         static bool check_available_guards( size_t nCountNeeded, bool bRaiseException = true )
 792         {
 793             if ( hrc::GarbageCollector::instance().getHazardPointerCount() < nCountNeeded ) {
 794                 if ( bRaiseException )
 795                     throw cds::gc::too_few_hazard_pointers();
 796                 return false;
 797             }
 798             return true;
 799         }
 800
 801         /// Retire pointer \p p with function \p pFunc
 802         /**
 803             The function places pointer \p p to array of pointers ready for removing.
 804             (so called retired pointer array). The pointer can be safely removed when no guarded pointer points to it.
 805             Deleting the pointer is the function \p pFunc call.
 806         */
 807         template <typename T>
 808         static void retire( T * p, void (* pFunc)(T *) )    ;   // inline in hrc_impl.h
 809
 810         /// Retire pointer \p p with functor of type \p Disposer
 811         /**
 812             The function places pointer \p p to array of pointers ready for removing.
 813             (so called retired pointer array). The pointer can be safely removed when no guard points to it.
 814
 815             See gc::HP::retire for \p Disposer requirements.
 816         */
 817         template <class Disposer, typename T>
 818         static void retire( T * p ) ;   // inline in hrc_impl.h
 819
 820         /// Checks if HRC GC is constructed and may be used
 821         static bool isUsed()
 822         {
 823             return hrc::GarbageCollector::isUsed();
 824         }
 825
 826         /// Forced GC cycle call for current thread
 827         /**
 828             Usually, this function should not be called directly.
 829         */
 830         static void scan()  ;   // inline in hrc_impl.h
 831
 832         /// Synonym for \ref scan()
 833         static void force_dispose()
 834         {
 835             scan();
 836         }
 837     };
 838 }} // namespace cds::gc
 839
 840 #endif // #ifndef __CDS_GC_HRC_DECL_H