cds/gc/hp.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_GC_HP_SMR_H
  32 #define CDSLIB_GC_HP_SMR_H
  33
  34 #include <exception>
  35 #include <cds/gc/details/hp_common.h>
  36 #include <cds/details/lib.h>
  37 #include <cds/threading/model.h>
  38 #include <cds/details/throw_exception.h>
  39 #include <cds/details/static_functor.h>
  40 #include <cds/details/marked_ptr.h>
  41 #include <cds/user_setup/cache_line.h>
  42
  43 /**
  44     @page cds_garbage_collectors_comparison Hazard Pointer SMR implementations
  45     @ingroup cds_garbage_collector
  46
  47     <table>
  48         <tr>
  49             <th>Feature</th>
  50             <th>%cds::gc::HP</th>
  51             <th>%cds::gc::DHP</th>
  52         </tr>
  53         <tr>
  54             <td>Max number of guarded (hazard) pointers per thread</td>
  55             <td>limited (specified at construction time)</td>
  56             <td>unlimited (dynamically allocated when needed)</td>
  57         </tr>
  58         <tr>
  59             <td>Max number of retired pointers<sup>1</sup></td>
  60             <td>bounded, specified at construction time</td>
  61             <td>bounded, adaptive, depends on current thread count and number of hazard pointer for each thread</td>
  62         </tr>
  63         <tr>
  64             <td>Thread count</td>
  65             <td>bounded, upper bound is specified at construction time</td>
  66             <td>unbounded</td>
  67         </tr>
  68     </table>
  69
  70     <sup>1</sup>Unbounded count of retired pointers means a possibility of memory exhaustion.
  71 */
  72
  73 namespace cds {
  74     /// @defgroup cds_garbage_collector Garbage collectors
  75
  76
  77     /// Different safe memory reclamation schemas (garbage collectors)
  78     /** @ingroup cds_garbage_collector
  79
  80         This namespace specifies different safe memory reclamation (SMR) algorithms.
  81         See \ref cds_garbage_collector "Garbage collectors"
  82     */
  83     namespace gc {
  84     } // namespace gc
  85
  86 } // namespace cds
  87
  88
  89 namespace cds { namespace gc {
  90     /// Hazard pointer implementation details
  91     namespace hp {
  92         using namespace cds::gc::hp::common;
  93
  94         /// Exception "Not enough Hazard Pointer"
  95         class not_enought_hazard_ptr: public std::length_error
  96         {
  97         //@cond
  98         public:
  99             not_enought_hazard_ptr()
 100                 : std::length_error( "Not enough Hazard Pointer" )
 101             {}
 102         //@endcond
 103         };
 104
 105         /// Exception "Hazard Pointer SMR is not initialized"
 106         class not_initialized: public std::runtime_error
 107         {
 108         //@cond
 109         public:
 110             not_initialized()
 111                 : std::runtime_error( "Global Hazard Pointer SMR object is not initialized" )
 112             {}
 113         //@endcond
 114         };
 115
 116         //@cond
 117         /// Per-thread hazard pointer storage
 118         class thread_hp_storage {
 119         public:
 120             thread_hp_storage( guard* arr, size_t nSize ) CDS_NOEXCEPT
 121                 : free_head_( arr )
 122                 , array_( arr )
 123                 , capacity_( nSize )
 124 #       ifdef CDS_ENABLE_HPSTAT
 125                 , alloc_guard_count_(0)
 126                 , free_guard_count_(0)
 127 #       endif
 128             {
 129                 // Initialize guards
 130                 new( arr ) guard[nSize];
 131
 132                 for ( guard* pEnd = arr + nSize - 1; arr < pEnd; ++arr )
 133                     arr->next_ = arr + 1;
 134                 arr->next_ = nullptr;
 135             }
 136
 137             thread_hp_storage() = delete;
 138             thread_hp_storage( thread_hp_storage const& ) = delete;
 139             thread_hp_storage( thread_hp_storage&& ) = delete;
 140
 141             size_t capacity() const CDS_NOEXCEPT
 142             {
 143                 return capacity_;
 144             }
 145
 146             bool full() const CDS_NOEXCEPT
 147             {
 148                 return free_head_ == nullptr;
 149             }
 150
 151             guard* alloc()
 152             {
 153 #       ifdef CDS_DISABLE_SMR_EXCEPTION
 154                 assert( !full());
 155 #       else
 156                 if ( full() )
 157                     CDS_THROW_EXCEPTION( not_enought_hazard_ptr());
 158 #       endif
 159                 guard* g = free_head_;
 160                 free_head_ = g->next_;
 161                 CDS_HPSTAT( ++alloc_guard_count_ );
 162                 return g;
 163             }
 164
 165             void free( guard* g ) CDS_NOEXCEPT
 166             {
 167                 assert( g >= array_ && g < array_ + capacity() );
 168
 169                 if ( g ) {
 170                     g->clear();
 171                     g->next_ = free_head_;
 172                     free_head_ = g;
 173                     CDS_HPSTAT( ++free_guard_count_ );
 174                 }
 175             }
 176
 177             template< size_t Capacity>
 178             size_t alloc( guard_array<Capacity>& arr )
 179             {
 180                 size_t i;
 181                 guard* g = free_head_;
 182                 for ( i = 0; i < Capacity && g; ++i ) {
 183                     arr.reset( i, g );
 184                     g = g->next_;
 185                 }
 186
 187 #       ifdef CDS_DISABLE_SMR_EXCEPTION
 188                 assert( i == Capacity );
 189 #       else
 190                 if ( i != Capacity )
 191                     CDS_THROW_EXCEPTION( not_enought_hazard_ptr());
 192 #       endif
 193                 free_head_ = g;
 194                 CDS_HPSTAT( alloc_guard_count_ += Capacity );
 195                 return i;
 196             }
 197
 198             template <size_t Capacity>
 199             void free( guard_array<Capacity>& arr ) CDS_NOEXCEPT
 200             {
 201                 guard* gList = free_head_;
 202                 for ( size_t i = 0; i < Capacity; ++i ) {
 203                     guard* g = arr[i];
 204                     if ( g ) {
 205                         g->clear();
 206                         g->next_ = gList;
 207                         gList = g;
 208                         CDS_HPSTAT( ++free_guard_count_ );
 209                     }
 210                 }
 211                 free_head_ = gList;
 212             }
 213
 214             // cppcheck-suppress functionConst
 215             void clear()
 216             {
 217                 for ( guard* cur = array_, *last = array_ + capacity(); cur < last; ++cur )
 218                     cur->clear();
 219             }
 220
 221             guard& operator[]( size_t idx )
 222             {
 223                 assert( idx < capacity() );
 224
 225                 return array_[idx];
 226             }
 227
 228             static size_t calc_array_size( size_t capacity )
 229             {
 230                 return sizeof( guard ) * capacity;
 231             }
 232
 233         private:
 234             guard*          free_head_; ///< Head of free guard list
 235             guard* const    array_;     ///< HP array
 236             size_t const    capacity_;  ///< HP array capacity
 237 #       ifdef CDS_ENABLE_HPSTAT
 238         public:
 239             size_t          alloc_guard_count_;
 240             size_t          free_guard_count_;
 241 #       endif
 242         };
 243         //@endcond
 244
 245         //@cond
 246         /// Per-thread retired array
 247         class retired_array
 248         {
 249         public:
 250             retired_array( retired_ptr* arr, size_t capacity ) CDS_NOEXCEPT
 251                 : current_( arr )
 252                 , last_( arr + capacity )
 253                 , retired_( arr )
 254 #       ifdef CDS_ENABLE_HPSTAT
 255                 , retire_call_count_(0)
 256 #       endif
 257             {}
 258
 259             retired_array() = delete;
 260             retired_array( retired_array const& ) = delete;
 261             retired_array( retired_array&& ) = delete;
 262
 263             size_t capacity() const CDS_NOEXCEPT
 264             {
 265                 return last_ - retired_;
 266             }
 267
 268             size_t size() const CDS_NOEXCEPT
 269             {
 270                 return current_ - retired_;
 271             }
 272
 273             bool push( retired_ptr&& p ) CDS_NOEXCEPT
 274             {
 275                 *current_ = p;
 276                 CDS_HPSTAT( ++retire_call_count_ );
 277                 return ++current_ < last_;
 278             }
 279
 280             retired_ptr* first() const CDS_NOEXCEPT
 281             {
 282                 return retired_;
 283             }
 284
 285             retired_ptr* last() const CDS_NOEXCEPT
 286             {
 287                 return current_;
 288             }
 289
 290             void reset( size_t nSize ) CDS_NOEXCEPT
 291             {
 292                 current_ = first() + nSize;
 293             }
 294
 295             bool full() const CDS_NOEXCEPT
 296             {
 297                 return current_ == last_;
 298             }
 299
 300             static size_t calc_array_size( size_t capacity )
 301             {
 302                 return sizeof( retired_ptr ) * capacity;
 303             }
 304
 305         private:
 306             retired_ptr*            current_;
 307             retired_ptr* const      last_;
 308             retired_ptr* const      retired_;
 309 #       ifdef CDS_ENABLE_HPSTAT
 310         public:
 311             size_t  retire_call_count_;
 312 #       endif
 313         };
 314         //@endcond
 315
 316         /// Internal statistics
 317         struct stat {
 318             size_t  guard_allocated;    ///< Count of allocated HP guards
 319             size_t  guard_freed;        ///< Count of freed HP guards
 320             size_t  retired_count;      ///< Count of retired pointers
 321             size_t  free_count;         ///< Count of free pointers
 322             size_t  scan_count;         ///< Count of \p scan() call
 323             size_t  help_scan_count;    ///< Count of \p help_scan() call
 324
 325             size_t  thread_rec_count;   ///< Count of thread records
 326
 327             /// Default ctor
 328             stat()
 329             {
 330                 clear();
 331             }
 332
 333             /// Clears all counters
 334             void clear()
 335             {
 336                 guard_allocated =
 337                     guard_freed =
 338                     retired_count =
 339                     free_count =
 340                     scan_count =
 341                     help_scan_count =
 342                     thread_rec_count = 0;
 343             }
 344         };
 345
 346         //@cond
 347         /// Per-thread data
 348         struct thread_data {
 349             thread_hp_storage   hazards_;   ///< Hazard pointers private to the thread
 350             retired_array       retired_;   ///< Retired data private to the thread
 351
 352             char pad1_[cds::c_nCacheLineSize];
 353             atomics::atomic<unsigned int> sync_; ///< dummy var to introduce synchronizes-with relationship between threads
 354             char pad2_[cds::c_nCacheLineSize];
 355
 356 #       ifdef CDS_ENABLE_HPSTAT
 357             // Internal statistics:
 358             size_t              free_count_;
 359             size_t              scan_count_;
 360             size_t              help_scan_count_;
 361 #       endif
 362
 363             // CppCheck warn: pad1_ and pad2_ is uninitialized in ctor
 364             // cppcheck-suppress uninitMemberVar
 365             thread_data( guard* guards, size_t guard_count, retired_ptr* retired_arr, size_t retired_capacity )
 366                 : hazards_( guards, guard_count )
 367                 , retired_( retired_arr, retired_capacity )
 368                 , sync_(0)
 369 #       ifdef CDS_ENABLE_HPSTAT
 370                 , free_count_(0)
 371                 , scan_count_(0)
 372                 , help_scan_count_(0)
 373 #       endif
 374             {}
 375
 376             thread_data() = delete;
 377             thread_data( thread_data const& ) = delete;
 378             thread_data( thread_data&& ) = delete;
 379
 380             void sync()
 381             {
 382                 sync_.fetch_add( 1, atomics::memory_order_acq_rel );
 383             }
 384         };
 385         //@endcond
 386
 387         /// \p smr::scan() strategy
 388         enum scan_type {
 389             classic,    ///< classic scan as described in Michael's works (see smr::classic_scan() )
 390             inplace     ///< inplace scan without allocation (see smr::inplace_scan() )
 391         };
 392
 393         //@cond
 394         /// Hazard Pointer SMR (Safe Memory Reclamation)
 395         class smr
 396         {
 397             struct thread_record;
 398
 399         public:
 400             /// Returns the instance of Hazard Pointer \ref smr
 401             static smr& instance()
 402             {
 403 #       ifdef CDS_DISABLE_SMR_EXCEPTION
 404                 assert( instance_ != nullptr );
 405 #       else
 406                 if ( !instance_ )
 407                     CDS_THROW_EXCEPTION( not_initialized());
 408 #       endif
 409                 return *instance_;
 410             }
 411
 412             /// Creates Hazard Pointer SMR singleton
 413             /**
 414                 Hazard Pointer SMR is a singleton. If HP instance is not initialized then the function creates the instance.
 415                 Otherwise it does nothing.
 416
 417                 The Michael's HP reclamation schema depends of three parameters:
 418                 - \p nHazardPtrCount - HP pointer count per thread. Usually it is small number (2-4) depending from
 419                     the data structure algorithms. By default, if \p nHazardPtrCount = 0,
 420                     the function uses maximum of HP count for CDS library
 421                 - \p nMaxThreadCount - max count of thread with using HP GC in your application. Default is 100.
 422                 - \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than
 423                     <tt> nHazardPtrCount * nMaxThreadCount </tt>
 424                     Default is <tt>2 * nHazardPtrCount * nMaxThreadCount</tt>
 425             */
 426             static CDS_EXPORT_API void construct(
 427                 size_t nHazardPtrCount = 0,     ///< Hazard pointer count per thread
 428                 size_t nMaxThreadCount = 0,     ///< Max count of simultaneous working thread in your application
 429                 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
 430                 scan_type nScanType = inplace   ///< Scan type (see \ref scan_type enum)
 431             );
 432
 433             // for back-copatibility
 434             static void Construct(
 435                 size_t nHazardPtrCount = 0,     ///< Hazard pointer count per thread
 436                 size_t nMaxThreadCount = 0,     ///< Max count of simultaneous working thread in your application
 437                 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
 438                 scan_type nScanType = inplace   ///< Scan type (see \ref scan_type enum)
 439             )
 440             {
 441                 construct( nHazardPtrCount, nMaxThreadCount, nMaxRetiredPtrCount, nScanType );
 442             }
 443
 444             /// Destroys global instance of \ref smr
 445             /**
 446                 The parameter \p bDetachAll should be used carefully: if its value is \p true,
 447                 then the object destroyed automatically detaches all attached threads. This feature
 448                 can be useful when you have no control over the thread termination, for example,
 449                 when \p libcds is injected into existing external thread.
 450             */
 451             static CDS_EXPORT_API void destruct(
 452                 bool bDetachAll = false     ///< Detach all threads
 453             );
 454
 455             // for back-compatibility
 456             static void Destruct(
 457                 bool bDetachAll = false     ///< Detach all threads
 458             )
 459             {
 460                 destruct( bDetachAll );
 461             }
 462
 463             /// Checks if global SMR object is constructed and may be used
 464             static bool isUsed() CDS_NOEXCEPT
 465             {
 466                 return instance_ != nullptr;
 467             }
 468
 469             /// Set memory management functions
 470             /**
 471                 @note This function may be called <b>BEFORE</b> creating an instance
 472                 of Hazard Pointer SMR
 473
 474                 SMR object allocates some memory for thread-specific data and for
 475                 creating SMR object.
 476                 By default, a standard \p new and \p delete operators are used for this.
 477             */
 478             static CDS_EXPORT_API void set_memory_allocator(
 479                 void* ( *alloc_func )( size_t size ),
 480                 void (*free_func )( void * p )
 481             );
 482
 483             /// Returns max Hazard Pointer count per thread
 484             size_t get_hazard_ptr_count() const CDS_NOEXCEPT
 485             {
 486                 return hazard_ptr_count_;
 487             }
 488
 489             /// Returns max thread count
 490             size_t get_max_thread_count() const CDS_NOEXCEPT
 491             {
 492                 return max_thread_count_;
 493             }
 494
 495             /// Returns max size of retired objects array
 496             size_t get_max_retired_ptr_count() const CDS_NOEXCEPT
 497             {
 498                 return max_retired_ptr_count_;
 499             }
 500
 501             /// Get current scan strategy
 502             scan_type get_scan_type() const
 503             {
 504                 return scan_type_;
 505             }
 506
 507             /// Checks that required hazard pointer count \p nRequiredCount is less or equal then max hazard pointer count
 508             /**
 509                 If <tt> nRequiredCount > get_hazard_ptr_count()</tt> then the exception \p not_enought_hazard_ptr is thrown
 510             */
 511             static void check_hazard_ptr_count( size_t nRequiredCount )
 512             {
 513                 if ( instance().get_hazard_ptr_count() < nRequiredCount ) {
 514 #       ifdef CDS_DISABLE_SMR_EXCEPTION
 515                     assert( false );    // not enough hazard ptr
 516 #       else
 517                     CDS_THROW_EXCEPTION( not_enought_hazard_ptr() );
 518 #       endif
 519                 }
 520             }
 521
 522             /// Returns thread-local data for the current thread
 523             static CDS_EXPORT_API thread_data* tls();
 524
 525             static CDS_EXPORT_API void attach_thread();
 526             static CDS_EXPORT_API void detach_thread();
 527
 528             /// Get internal statistics
 529             CDS_EXPORT_API void statistics( stat& st );
 530
 531         public: // for internal use only
 532             /// The main garbage collecting function
 533             /**
 534                 This function is called internally when upper bound of thread's list of reclaimed pointers
 535                 is reached.
 536
 537                 There are the following scan algorithm:
 538                 - \ref hzp_gc_classic_scan "classic_scan" allocates memory for internal use
 539                 - \ref hzp_gc_inplace_scan "inplace_scan" does not allocate any memory
 540
 541                 Use \p set_scan_type() member function to setup appropriate scan algorithm.
 542             */
 543             void scan( thread_data* pRec )
 544             {
 545                 ( this->*scan_func_ )( pRec );
 546             }
 547
 548             /// Helper scan routine
 549             /**
 550                 The function guarantees that every node that is eligible for reuse is eventually freed, barring
 551                 thread failures. To do so, after executing \p scan(), a thread executes a \p %help_scan(),
 552                 where it checks every HP record. If an HP record is inactive, the thread moves all "lost" reclaimed pointers
 553                 to thread's list of reclaimed pointers.
 554
 555                 The function is called internally by \p scan().
 556             */
 557             CDS_EXPORT_API void help_scan( thread_data* pThis );
 558
 559         private:
 560             CDS_EXPORT_API smr(
 561                 size_t nHazardPtrCount,     ///< Hazard pointer count per thread
 562                 size_t nMaxThreadCount,     ///< Max count of simultaneous working thread in your application
 563                 size_t nMaxRetiredPtrCount, ///< Capacity of the array of retired objects for the thread
 564                 scan_type nScanType         ///< Scan type (see \ref scan_type enum)
 565             );
 566
 567             CDS_EXPORT_API ~smr();
 568
 569             CDS_EXPORT_API void detach_all_thread();
 570
 571             /// Classic scan algorithm
 572             /** @anchor hzp_gc_classic_scan
 573                 Classical scan algorithm as described in Michael's paper.
 574
 575                 A scan includes four stages. The first stage involves scanning the array HP for non-null values.
 576                 Whenever a non-null value is encountered, it is inserted in a local list of currently protected pointer.
 577                 Only stage 1 accesses shared variables. The following stages operate only on private variables.
 578
 579                 The second stage of a scan involves sorting local list of protected pointers to allow
 580                 binary search in the third stage.
 581
 582                 The third stage of a scan involves checking each reclaimed node
 583                 against the pointers in local list of protected pointers. If the binary search yields
 584                 no match, the node is freed. Otherwise, it cannot be deleted now and must kept in thread's list
 585                 of reclaimed pointers.
 586
 587                 The forth stage prepares new thread's private list of reclaimed pointers
 588                 that could not be freed during the current scan, where they remain until the next scan.
 589
 590                 This algorithm allocates memory for internal HP array.
 591
 592                 This function is called internally by ThreadGC object when upper bound of thread's list of reclaimed pointers
 593                 is reached.
 594             */
 595             CDS_EXPORT_API void classic_scan( thread_data* pRec );
 596
 597             /// In-place scan algorithm
 598             /** @anchor hzp_gc_inplace_scan
 599                 Unlike the \p classic_scan() algorithm, \p %inplace_scan() does not allocate any memory.
 600                 All operations are performed in-place.
 601             */
 602             CDS_EXPORT_API void inplace_scan( thread_data* pRec );
 603
 604         private:
 605             CDS_EXPORT_API thread_record* create_thread_data();
 606             static CDS_EXPORT_API void destroy_thread_data( thread_record* pRec );
 607
 608             /// Allocates Hazard Pointer SMR thread private data
 609             CDS_EXPORT_API thread_record* alloc_thread_data();
 610
 611             /// Free HP SMR thread-private data
 612             CDS_EXPORT_API void free_thread_data( thread_record* pRec );
 613
 614         private:
 615             static CDS_EXPORT_API smr* instance_;
 616
 617             atomics::atomic< thread_record*>    thread_list_;   ///< Head of thread list
 618
 619             size_t const    hazard_ptr_count_;      ///< max count of thread's hazard pointer
 620             size_t const    max_thread_count_;      ///< max count of thread
 621             size_t const    max_retired_ptr_count_; ///< max count of retired ptr per thread
 622             scan_type const scan_type_;             ///< scan type (see \ref scan_type enum)
 623             void ( smr::*scan_func_ )( thread_data* pRec );
 624         };
 625         //@endcond
 626
 627         //@cond
 628         // for backward compatibility
 629         typedef smr GarbageCollector;
 630         //@endcond
 631
 632     } // namespace hp
 633
 634     /// Hazard Pointer SMR (Safe Memory Reclamation)
 635     /**  @ingroup cds_garbage_collector
 636
 637         Implementation of classic Hazard Pointer SMR
 638
 639         Sources:
 640             - [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
 641             - [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
 642             - [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
 643
 644         Hazard Pointer SMR is a singleton. The main user-level part of Hazard Pointer schema is
 645         \p %cds::gc::HP class and its nested classes. Before use any HP-related class you must initialize \p %HP
 646         by contructing \p %cds::gc::HP object in beginning of your \p main().
 647         See \ref cds_how_to_use "How to use" section for details how to apply SMR schema.
 648     */
 649     class HP
 650     {
 651     public:
 652         /// Native guarded pointer type
 653         typedef hp::hazard_ptr guarded_pointer;
 654
 655         /// Atomic reference
 656         template <typename T> using atomic_ref = atomics::atomic<T *>;
 657
 658         /// Atomic marked pointer
 659         template <typename MarkedPtr> using atomic_marked_ptr = atomics::atomic<MarkedPtr>;
 660
 661         /// Atomic type
 662         template <typename T> using atomic_type = atomics::atomic<T>;
 663
 664         /// Exception "Not enough Hazard Pointer"
 665         typedef hp::not_enought_hazard_ptr not_enought_hazard_ptr_exception;
 666
 667         /// Internal statistics
 668         typedef hp::stat stat;
 669
 670         /// Hazard Pointer guard
 671         /**
 672             A guard is a hazard pointer.
 673             Additionally, the \p %Guard class manages allocation and deallocation of the hazard pointer.
 674
 675             \p %Guard object is movable but not copyable.
 676
 677             The guard object can be in two states:
 678             - unlinked - the guard is not linked with any internal hazard pointer.
 679               In this state no operation except \p link() and move assignment is supported.
 680             - linked (default) - the guard allocates an internal hazard pointer and completely operable.
 681
 682             Due to performance reason the implementation does not check state of the guard in runtime.
 683
 684             @warning Move assignment transfers the guard in unlinked state, use with care.
 685         */
 686         class Guard
 687         {
 688         public:
 689             /// Default ctor allocates a guard (hazard pointer) from thread-private storage
 690             /**
 691                 @warning Can throw \p too_many_hazard_ptr_exception if internal hazard pointer objects are exhausted.
 692             */
 693             Guard()
 694                 : guard_( hp::smr::tls()->hazards_.alloc() )
 695             {}
 696
 697             /// Initilalizes an unlinked guard i.e. the guard contains no hazard pointer. Used for move semantics support
 698             explicit Guard( std::nullptr_t ) CDS_NOEXCEPT
 699                 : guard_( nullptr )
 700             {}
 701
 702             /// Move ctor - \p src guard becomes unlinked (transfer internal guard ownership)
 703             Guard( Guard&& src ) CDS_NOEXCEPT
 704                 : guard_( src.guard_ )
 705             {
 706                 src.guard_ = nullptr;
 707             }
 708
 709             /// Move assignment: the internal guards are swapped between \p src and \p this
 710             /**
 711                 @warning \p src will become in unlinked state if \p this was unlinked on entry.
 712             */
 713             Guard& operator=( Guard&& src ) CDS_NOEXCEPT
 714             {
 715                 std::swap( guard_, src.guard_ );
 716                 return *this;
 717             }
 718
 719             /// Copy ctor is prohibited - the guard is not copyable
 720             Guard( Guard const& ) = delete;
 721
 722             /// Copy assignment is prohibited
 723             Guard& operator=( Guard const& ) = delete;
 724
 725             /// Frees the internal hazard pointer if the guard is in linked state
 726             ~Guard()
 727             {
 728                 unlink();
 729             }
 730
 731             /// Checks if the guard object linked with any internal hazard pointer
 732             bool is_linked() const
 733             {
 734                 return guard_ != nullptr;
 735             }
 736
 737             /// Links the guard with internal hazard pointer if the guard is in unlinked state
 738             /**
 739                 @warning Can throw \p not_enought_hazard_ptr_exception if internal hazard pointer array is exhausted.
 740             */
 741             void link()
 742             {
 743                 if ( !guard_ )
 744                     guard_ = hp::smr::tls()->hazards_.alloc();
 745             }
 746
 747             /// Unlinks the guard from internal hazard pointer; the guard becomes in unlinked state
 748             void unlink()
 749             {
 750                 if ( guard_ ) {
 751                     hp::smr::tls()->hazards_.free( guard_ );
 752                     guard_ = nullptr;
 753                 }
 754             }
 755
 756             /// Protects a pointer of type \p atomic<T*>
 757             /**
 758                 Return the value of \p toGuard
 759
 760                 The function tries to load \p toGuard and to store it
 761                 to the HP slot repeatedly until the guard's value equals \p toGuard
 762
 763                 @warning The guad object should be in linked state, otherwise the result is undefined
 764             */
 765             template <typename T>
 766             T protect( atomics::atomic<T> const& toGuard )
 767             {
 768                 assert( guard_ != nullptr );
 769
 770                 T pCur = toGuard.load(atomics::memory_order_acquire);
 771                 T pRet;
 772                 do {
 773                     pRet = assign( pCur );
 774                     pCur = toGuard.load(atomics::memory_order_acquire);
 775                 } while ( pRet != pCur );
 776                 return pCur;
 777             }
 778
 779             /// Protects a converted pointer of type \p atomic<T*>
 780             /**
 781                 Return the value of \p toGuard
 782
 783                 The function tries to load \p toGuard and to store result of \p f functor
 784                 to the HP slot repeatedly until the guard's value equals \p toGuard.
 785
 786                 The function is useful for intrusive containers when \p toGuard is a node pointer
 787                 that should be converted to a pointer to the value before protecting.
 788                 The parameter \p f of type Func is a functor that makes this conversion:
 789                 \code
 790                     struct functor {
 791                         value_type * operator()( T * p );
 792                     };
 793                 \endcode
 794                 Actually, the result of <tt> f( toGuard.load()) </tt> is assigned to the hazard pointer.
 795
 796                 @warning The guad object should be in linked state, otherwise the result is undefined
 797             */
 798             template <typename T, class Func>
 799             T protect( atomics::atomic<T> const& toGuard, Func f )
 800             {
 801                 assert( guard_ != nullptr );
 802
 803                 T pCur = toGuard.load(atomics::memory_order_acquire);
 804                 T pRet;
 805                 do {
 806                     pRet = pCur;
 807                     assign( f( pCur ));
 808                     pCur = toGuard.load(atomics::memory_order_acquire);
 809                 } while ( pRet != pCur );
 810                 return pCur;
 811             }
 812
 813             /// Store \p p to the guard
 814             /**
 815                 The function equals to a simple assignment the value \p p to guard, no loop is performed.
 816                 Can be used for a pointer that cannot be changed concurrently or if the pointer is already
 817                 guarded by another guard.
 818
 819                 @warning The guad object should be in linked state, otherwise the result is undefined
 820             */
 821             template <typename T>
 822             T * assign( T* p )
 823             {
 824                 assert( guard_ != nullptr );
 825
 826                 guard_->set( p );
 827                 hp::smr::tls()->sync();
 828                 return p;
 829             }
 830
 831             //@cond
 832             std::nullptr_t assign( std::nullptr_t )
 833             {
 834                 assert( guard_ != nullptr );
 835
 836                 guard_->clear();
 837                 return nullptr;
 838             }
 839             //@endcond
 840
 841             /// Copy a value guarded from \p src guard to \p this guard (valid only in linked state)
 842             void copy( Guard const& src )
 843             {
 844                 assign( src.get_native());
 845             }
 846
 847             /// Store marked pointer \p p to the guard
 848             /**
 849                 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
 850                 Can be used for a marked pointer that cannot be changed concurrently or if the marked pointer
 851                 is already guarded by another guard.
 852
 853                 @warning The guard object should be in linked state, otherwise the result is undefined
 854             */
 855             template <typename T, int BITMASK>
 856             T * assign( cds::details::marked_ptr<T, BITMASK> p )
 857             {
 858                 return assign( p.ptr());
 859             }
 860
 861             /// Clear value of the guard (valid only in linked state)
 862             void clear()
 863             {
 864                 assign( nullptr );
 865             }
 866
 867             /// Get the value currently protected (valid only in linked state)
 868             template <typename T>
 869             T * get() const
 870             {
 871                 assert( guard_ != nullptr );
 872                 return guard_->get_as<T>();
 873             }
 874
 875             /// Get native hazard pointer stored (valid only in linked state)
 876             guarded_pointer get_native() const
 877             {
 878                 assert( guard_ != nullptr );
 879                 return guard_->get();
 880             }
 881
 882             //@cond
 883             hp::guard* release()
 884             {
 885                 hp::guard* g = guard_;
 886                 guard_ = nullptr;
 887                 return g;
 888             }
 889
 890             hp::guard*& guard_ref()
 891             {
 892                 return guard_;
 893             }
 894             //@endcond
 895
 896         private:
 897             //@cond
 898             hp::guard* guard_;
 899             //@endcond
 900         };
 901
 902         /// Array of Hazard Pointer guards
 903         /**
 904             The class is intended for allocating an array of hazard pointer guards.
 905             Template parameter \p Count defines the size of the array.
 906         */
 907         template <size_t Count>
 908         class GuardArray
 909         {
 910         public:
 911             /// Rebind array for other size \p Count2
 912             template <size_t Count2>
 913             struct rebind {
 914                 typedef GuardArray<Count2>  other;   ///< rebinding result
 915             };
 916
 917             /// Array capacity
 918             static CDS_CONSTEXPR const size_t c_nCapacity = Count;
 919
 920         public:
 921             /// Default ctor allocates \p Count hazard pointers
 922             GuardArray()
 923             {
 924                 hp::smr::tls()->hazards_.alloc( guards_ );
 925             }
 926
 927             /// Move ctor is prohibited
 928             GuardArray( GuardArray&& ) = delete;
 929
 930             /// Move assignment is prohibited
 931             GuardArray& operator=( GuardArray&& ) = delete;
 932
 933             /// Copy ctor is prohibited
 934             GuardArray( GuardArray const& ) = delete;
 935
 936             /// Copy assignment is prohibited
 937             GuardArray& operator=( GuardArray const& ) = delete;
 938
 939             /// Frees allocated hazard pointers
 940             ~GuardArray()
 941             {
 942                 hp::smr::tls()->hazards_.free( guards_ );
 943             }
 944
 945             /// Protects a pointer of type \p atomic<T*>
 946             /**
 947                 Return the value of \p toGuard
 948
 949                 The function tries to load \p toGuard and to store it
 950                 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
 951             */
 952             template <typename T>
 953             T protect( size_t nIndex, atomics::atomic<T> const& toGuard )
 954             {
 955                 assert( nIndex < capacity());
 956
 957                 T pRet;
 958                 do {
 959                     pRet = assign( nIndex, toGuard.load(atomics::memory_order_acquire));
 960                 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
 961
 962                 return pRet;
 963             }
 964
 965             /// Protects a pointer of type \p atomic<T*>
 966             /**
 967                 Return the value of \p toGuard
 968
 969                 The function tries to load \p toGuard and to store it
 970                 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
 971
 972                 The function is useful for intrusive containers when \p toGuard is a node pointer
 973                 that should be converted to a pointer to the value type before guarding.
 974                 The parameter \p f of type Func is a functor that makes this conversion:
 975                 \code
 976                     struct functor {
 977                         value_type * operator()( T * p );
 978                     };
 979                 \endcode
 980                 Really, the result of <tt> f( toGuard.load()) </tt> is assigned to the hazard pointer.
 981             */
 982             template <typename T, class Func>
 983             T protect( size_t nIndex, atomics::atomic<T> const& toGuard, Func f )
 984             {
 985                 assert( nIndex < capacity());
 986
 987                 T pRet;
 988                 do {
 989                     assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_acquire)));
 990                 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
 991
 992                 return pRet;
 993             }
 994
 995             /// Store \p to the slot \p nIndex
 996             /**
 997                 The function equals to a simple assignment, no loop is performed.
 998             */
 999             template <typename T>
1000             T * assign( size_t nIndex, T * p )
1001             {
1002                 assert( nIndex < capacity() );
1003
1004                 guards_.set( nIndex, p );
1005                 hp::smr::tls()->sync();
1006                 return p;
1007             }
1008
1009             /// Store marked pointer \p p to the guard
1010             /**
1011                 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
1012                 Can be used for a marked pointer that cannot be changed concurrently.
1013             */
1014             template <typename T, int BITMASK>
1015             T * assign( size_t nIndex, cds::details::marked_ptr<T, BITMASK> p )
1016             {
1017                 return assign( nIndex, p.ptr());
1018             }
1019
1020             /// Copy guarded value from \p src guard to slot at index \p nIndex
1021             void copy( size_t nIndex, Guard const& src )
1022             {
1023                 assign( nIndex, src.get_native());
1024             }
1025
1026             /// Copy guarded value from slot \p nSrcIndex to the slot \p nDestIndex
1027             void copy( size_t nDestIndex, size_t nSrcIndex )
1028             {
1029                 assign( nDestIndex, get_native( nSrcIndex ));
1030             }
1031
1032             /// Clear value of the slot \p nIndex
1033             void clear( size_t nIndex )
1034             {
1035                 guards_.clear( nIndex );
1036             }
1037
1038             /// Get current value of slot \p nIndex
1039             template <typename T>
1040             T * get( size_t nIndex ) const
1041             {
1042                 assert( nIndex < capacity() );
1043                 return guards_[nIndex]->template get_as<T>();
1044             }
1045
1046             /// Get native hazard pointer stored
1047             guarded_pointer get_native( size_t nIndex ) const
1048             {
1049                 assert( nIndex < capacity());
1050                 return guards_[nIndex]->get();
1051             }
1052
1053             //@cond
1054             hp::guard* release( size_t nIndex ) CDS_NOEXCEPT
1055             {
1056                 return guards_.release( nIndex );
1057             }
1058             //@endcond
1059
1060             /// Capacity of the guard array
1061             static CDS_CONSTEXPR size_t capacity()
1062             {
1063                 return c_nCapacity;
1064             }
1065
1066         private:
1067             //@cond
1068             hp::guard_array<c_nCapacity> guards_;
1069             //@endcond
1070         };
1071
1072         /// Guarded pointer
1073         /**
1074             A guarded pointer is a pair of a pointer and GC's guard.
1075             Usually, it is used for returning a pointer to an element of a lock-free container.
1076             The guard prevents the pointer to be early disposed (freed) by SMR.
1077             After destructing \p %guarded_ptr object the pointer can be disposed (freed) automatically at any time.
1078
1079             Template arguments:
1080             - \p GuardedType - a type which the guard stores
1081             - \p ValueType - a value type
1082             - \p Cast - a functor for converting <tt>GuardedType*</tt> to <tt>ValueType*</tt>. Default is \p void (no casting).
1083
1084             For intrusive containers, \p GuardedType is the same as \p ValueType and no casting is needed.
1085             In such case the \p %guarded_ptr is:
1086             @code
1087             typedef cds::gc::HP::guarded_ptr< foo > intrusive_guarded_ptr;
1088             @endcode
1089
1090             For standard (non-intrusive) containers \p GuardedType is not the same as \p ValueType and casting is needed.
1091             For example:
1092             @code
1093             struct foo {
1094                 int const   key;
1095                 std::string value;
1096             };
1097
1098             struct value_accessor {
1099                 std::string* operator()( foo* pFoo ) const
1100                 {
1101                     return &(pFoo->value);
1102                 }
1103             };
1104
1105             // Guarded ptr
1106             typedef cds::gc::HP::guarded_ptr< Foo, std::string, value_accessor > nonintrusive_guarded_ptr;
1107             @endcode
1108
1109             You don't need use this class directly.
1110             All set/map container classes from \p libcds declare the typedef for \p %guarded_ptr with appropriate casting functor.
1111         */
1112         template <typename GuardedType, typename ValueType=GuardedType, typename Cast=void >
1113         class guarded_ptr
1114         {
1115             //@cond
1116             struct trivial_cast {
1117                 ValueType * operator()( GuardedType * p ) const
1118                 {
1119                     return p;
1120                 }
1121             };
1122
1123             template <typename GT, typename VT, typename C> friend class guarded_ptr;
1124             //@endcond
1125
1126         public:
1127             typedef GuardedType guarded_type; ///< Guarded type
1128             typedef ValueType   value_type;   ///< Value type
1129
1130             /// Functor for casting \p guarded_type to \p value_type
1131             typedef typename std::conditional< std::is_same<Cast, void>::value, trivial_cast, Cast >::type value_cast;
1132
1133         public:
1134             /// Creates empty guarded pointer
1135             guarded_ptr() CDS_NOEXCEPT
1136                 : guard_(nullptr)
1137             {}
1138
1139             //@cond
1140             explicit guarded_ptr( hp::guard* g ) CDS_NOEXCEPT
1141                 : guard_( g )
1142             {}
1143
1144             /// Initializes guarded pointer with \p p
1145             explicit guarded_ptr( guarded_type* p ) CDS_NOEXCEPT
1146                 : guard_( nullptr )
1147             {
1148                 reset(p);
1149             }
1150             explicit guarded_ptr( std::nullptr_t ) CDS_NOEXCEPT
1151                 : guard_( nullptr )
1152             {}
1153             //@endcond
1154
1155             /// Move ctor
1156             guarded_ptr( guarded_ptr&& gp ) CDS_NOEXCEPT
1157                 : guard_( gp.guard_ )
1158             {
1159                 gp.guard_ = nullptr;
1160             }
1161
1162             /// Move ctor
1163             template <typename GT, typename VT, typename C>
1164             guarded_ptr( guarded_ptr<GT, VT, C>&& gp ) CDS_NOEXCEPT
1165                 : guard_( gp.guard_ )
1166             {
1167                 gp.guard_ = nullptr;
1168             }
1169
1170             /// Ctor from \p Guard
1171             explicit guarded_ptr( Guard&& g ) CDS_NOEXCEPT
1172                 : guard_( g.release())
1173             {}
1174
1175             /// The guarded pointer is not copy-constructible
1176             guarded_ptr( guarded_ptr const& gp ) = delete;
1177
1178             /// Clears the guarded pointer
1179             /**
1180                 \ref release() is called if guarded pointer is not \ref empty()
1181             */
1182             ~guarded_ptr() CDS_NOEXCEPT
1183             {
1184                 release();
1185             }
1186
1187             /// Move-assignment operator
1188             guarded_ptr& operator=( guarded_ptr&& gp ) CDS_NOEXCEPT
1189             {
1190                 std::swap( guard_, gp.guard_ );
1191                 return *this;
1192             }
1193
1194             /// Move-assignment from \p Guard
1195             guarded_ptr& operator=( Guard&& g ) CDS_NOEXCEPT
1196             {
1197                 std::swap( guard_, g.guard_ref());
1198                 return *this;
1199             }
1200
1201             /// The guarded pointer is not copy-assignable
1202             guarded_ptr& operator=(guarded_ptr const& gp) = delete;
1203
1204             /// Returns a pointer to guarded value
1205             value_type * operator ->() const CDS_NOEXCEPT
1206             {
1207                 assert( !empty());
1208                 return value_cast()( guard_->get_as<guarded_type>());
1209             }
1210
1211             /// Returns a reference to guarded value
1212             value_type& operator *() CDS_NOEXCEPT
1213             {
1214                 assert( !empty());
1215                 return *value_cast()( guard_->get_as<guarded_type>());
1216             }
1217
1218             /// Returns const reference to guarded value
1219             value_type const& operator *() const CDS_NOEXCEPT
1220             {
1221                 assert( !empty());
1222                 return *value_cast()( guard_->get_as<guarded_type>());
1223             }
1224
1225             /// Checks if the guarded pointer is \p nullptr
1226             bool empty() const CDS_NOEXCEPT
1227             {
1228                 return !guard_ || guard_->get( atomics::memory_order_relaxed ) == nullptr;
1229             }
1230
1231             /// \p bool operator returns <tt>!empty()</tt>
1232             explicit operator bool() const CDS_NOEXCEPT
1233             {
1234                 return !empty();
1235             }
1236
1237             /// Clears guarded pointer
1238             /**
1239                 If the guarded pointer has been released, the pointer can be disposed (freed) at any time.
1240                 Dereferncing the guarded pointer after \p release() is dangerous.
1241             */
1242             void release() CDS_NOEXCEPT
1243             {
1244                 free_guard();
1245             }
1246
1247             //@cond
1248             // For internal use only!!!
1249             void reset(guarded_type * p) CDS_NOEXCEPT
1250             {
1251                 alloc_guard();
1252                 assert( guard_ );
1253                 guard_->set(p);
1254             }
1255             //@endcond
1256
1257         private:
1258             //@cond
1259             void alloc_guard()
1260             {
1261                 if ( !guard_ )
1262                     guard_ = hp::smr::tls()->hazards_.alloc();
1263             }
1264
1265             void free_guard()
1266             {
1267                 if ( guard_ ) {
1268                     hp::smr::tls()->hazards_.free( guard_ );
1269                     guard_ = nullptr;
1270                 }
1271             }
1272             //@endcond
1273
1274         private:
1275             //@cond
1276             hp::guard* guard_;
1277             //@endcond
1278         };
1279
1280     public:
1281         /// \p scan() type
1282         enum class scan_type {
1283             classic = hp::classic,    ///< classic scan as described in Michael's papers
1284             inplace = hp::inplace     ///< inplace scan without allocation
1285         };
1286
1287         /// Initializes %HP singleton
1288         /**
1289             The constructor initializes Hazard Pointer SMR singleton with passed parameters.
1290             If the instance does not yet exist then the function creates the instance.
1291             Otherwise it does nothing.
1292
1293             The Michael's %HP reclamation schema depends of three parameters:
1294             - \p nHazardPtrCount - hazard pointer count per thread. Usually it is small number (up to 10) depending from
1295                 the data structure algorithms. If \p nHazardPtrCount = 0, the defaul value 8 is used
1296             - \p nMaxThreadCount - max count of thread with using Hazard Pointer GC in your application. Default is 100.
1297             - \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than
1298                 <tt> nHazardPtrCount * nMaxThreadCount </tt>. Default is <tt>2 * nHazardPtrCount * nMaxThreadCount </tt>.
1299         */
1300         HP(
1301             size_t nHazardPtrCount = 0,     ///< Hazard pointer count per thread
1302             size_t nMaxThreadCount = 0,     ///< Max count of simultaneous working thread in your application
1303             size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
1304             scan_type nScanType = scan_type::inplace   ///< Scan type (see \p scan_type enum)
1305         )
1306         {
1307             hp::smr::construct(
1308                 nHazardPtrCount,
1309                 nMaxThreadCount,
1310                 nMaxRetiredPtrCount,
1311                 static_cast<hp::scan_type>(nScanType)
1312             );
1313         }
1314
1315         /// Terminates GC singleton
1316         /**
1317             The destructor destroys %HP global object. After calling of this function you may \b NOT
1318             use CDS data structures based on \p %cds::gc::HP.
1319             Usually, %HP object is destroyed at the end of your \p main().
1320         */
1321         ~HP()
1322         {
1323             hp::smr::destruct( true );
1324         }
1325
1326         /// Checks that required hazard pointer count \p nCountNeeded is less or equal then max hazard pointer count
1327         /**
1328             If <tt> nRequiredCount > get_hazard_ptr_count()</tt> then the exception \p not_enought_hazard_ptr is thrown
1329         */
1330         static void check_available_guards( size_t nCountNeeded )
1331         {
1332             hp::smr::check_hazard_ptr_count( nCountNeeded );
1333         }
1334
1335         /// Set memory management functions
1336         /**
1337             @note This function may be called <b>BEFORE</b> creating an instance
1338             of Hazard Pointer SMR
1339
1340             SMR object allocates some memory for thread-specific data and for
1341             creating SMR object.
1342             By default, a standard \p new and \p delete operators are used for this.
1343         */
1344         static void set_memory_allocator(
1345             void* ( *alloc_func )( size_t size ),   ///< \p malloc() function
1346             void( *free_func )( void * p )          ///< \p free() function
1347         )
1348         {
1349             hp::smr::set_memory_allocator( alloc_func, free_func );
1350         }
1351
1352         /// Returns max Hazard Pointer count
1353         static size_t max_hazard_count()
1354         {
1355             return hp::smr::instance().get_hazard_ptr_count();
1356         }
1357
1358         /// Returns max count of thread
1359         static size_t max_thread_count()
1360         {
1361             return hp::smr::instance().get_max_thread_count();
1362         }
1363
1364         /// Returns capacity of retired pointer array
1365         static size_t retired_array_capacity()
1366         {
1367             return hp::smr::instance().get_max_retired_ptr_count();
1368         }
1369
1370         /// Retire pointer \p p with function \p func
1371         /**
1372             The function places pointer \p p to array of pointers ready for removing.
1373             (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
1374             \p func is a disposer: when \p p can be safely removed, \p func is called.
1375         */
1376         template <typename T>
1377         static void retire( T * p, void( *func )( void * ))
1378         {
1379             hp::thread_data* rec = hp::smr::tls();
1380             if ( !rec->retired_.push( hp::retired_ptr( p, func )))
1381                 hp::smr::instance().scan( rec );
1382         }
1383
1384         /// Retire pointer \p p with functor of type \p Disposer
1385         /**
1386             The function places pointer \p p to array of pointers ready for removing.
1387             (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
1388
1389             Deleting the pointer is an invocation of some object of type \p Disposer; the interface of \p Disposer is:
1390             \code
1391             template <typename T>
1392             struct disposer {
1393                 void operator()( T * p )    ;   // disposing operator
1394             };
1395             \endcode
1396             Since the functor call can happen at any time after \p retire() call, additional restrictions are imposed to \p Disposer type:
1397             - it should be stateless functor
1398             - it should be default-constructible
1399             - the result of functor call with argument \p p should not depend on where the functor will be called.
1400
1401             \par Examples:
1402             Operator \p delete functor:
1403             \code
1404             template <typename T>
1405             struct disposer {
1406                 void operator ()( T * p ) {
1407                     delete p;
1408                 }
1409             };
1410
1411             // How to call HP::retire method
1412             int * p = new int;
1413
1414             // ... use p in lock-free manner
1415
1416             cds::gc::HP::retire<disposer>( p ) ;   // place p to retired pointer array of HP GC
1417             \endcode
1418
1419             Functor based on \p std::allocator :
1420             \code
1421             template <typename Alloc = std::allocator<int> >
1422             struct disposer {
1423                 template <typename T>
1424                 void operator()( T * p ) {
1425                     typedef typename Alloc::templare rebind<T>::other alloc_t;
1426                     alloc_t a;
1427                     a.destroy( p );
1428                     a.deallocate( p, 1 );
1429                 }
1430             };
1431             \endcode
1432         */
1433         template <class Disposer, typename T>
1434         static void retire( T * p )
1435         {
1436             if ( !hp::smr::tls()->retired_.push( hp::retired_ptr( p, cds::details::static_functor<Disposer, T>::call )))
1437                 scan();
1438         }
1439
1440         /// Get current scan strategy
1441         static scan_type getScanType()
1442         {
1443             return static_cast<scan_type>( hp::smr::instance().get_scan_type());
1444         }
1445
1446         /// Checks if Hazard Pointer GC is constructed and may be used
1447         static bool isUsed()
1448         {
1449             return hp::smr::isUsed();
1450         }
1451
1452         /// Forces SMR call for current thread
1453         /**
1454             Usually, this function should not be called directly.
1455         */
1456         static void scan()
1457         {
1458             hp::smr::instance().scan( hp::smr::tls());
1459         }
1460
1461         /// Synonym for \p scan()
1462         static void force_dispose()
1463         {
1464             scan();
1465         }
1466
1467         /// Returns internal statistics
1468         /**
1469             The function clears \p st before gathering statistics.
1470
1471             @note Internal statistics is available only if you compile
1472             \p libcds and your program with \p -DCDS_ENABLE_HPSTAT.
1473         */
1474         static void statistics( stat& st )
1475         {
1476             hp::smr::instance().statistics( st );
1477         }
1478
1479         /// Returns post-mortem statistics
1480         /**
1481             Post-mortem statistics is gathered in the \p %HP object destructor
1482             and can be accessible after destructing the global \p %HP object.
1483
1484             @note Internal statistics is available only if you compile
1485             \p libcds and your program with \p -DCDS_ENABLE_HPSTAT.
1486
1487             Usage:
1488             \code
1489             int main()
1490             {
1491                 cds::Initialize();
1492                 {
1493                     // Initialize HP SMR
1494                     cds::gc::HP hp;
1495
1496                     // deal with HP-based data structured
1497                     // ...
1498                 }
1499
1500                 // HP object destroyed
1501                 // Get total post-mortem statistics
1502                 cds::gc::HP::stat const& st = cds::gc::HP::postmortem_statistics();
1503
1504                 printf( "HP statistics:\n"
1505                     "  thread count           = %llu\n"
1506                     "  guard allocated        = %llu\n"
1507                     "  guard freed            = %llu\n"
1508                     "  retired data count     = %llu\n"
1509                     "  free data count        = %llu\n"
1510                     "  scan() call count      = %llu\n"
1511                     "  help_scan() call count = %llu\n",
1512                     st.thread_rec_count,
1513                     st.guard_allocated, st.guard_freed,
1514                     st.retired_count, st.free_count,
1515                     st.scan_count, st.help_scan_count
1516                 );
1517
1518                 cds::Terminate();
1519             }
1520             \endcode
1521         */
1522         CDS_EXPORT_API static stat const& postmortem_statistics();
1523     };
1524
1525 }} // namespace cds::gc
1526
1527 #endif // #ifndef CDSLIB_GC_HP_SMR_H
1528