cds/gc/hrc/details/hrc_retired.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_GC_HRC_SCHEMA_RETIRED_H
   4 #define __CDS_GC_HRC_SCHEMA_RETIRED_H
   5
   6 #include <cds/gc/hrc/details/hrc_fwd.h>
   7 #include <cds/gc/details/retired_ptr.h>
   8 #include <cds/cxx11_atomic.h>
   9 #include <cds/details/bounded_array.h>
  10
  11 namespace cds { namespace gc { namespace hrc {
  12     namespace details {
  13
  14         /// Pointer to function to free (destruct and deallocate) retired pointer of specific type
  15         typedef gc::details::free_retired_ptr_func free_retired_ptr_func;
  16
  17         /// Retired node descriptor
  18         struct retired_node {
  19             CDS_ATOMIC::atomic<ContainerNode *> m_pNode        ;    ///< node to destroy
  20             free_retired_ptr_func               m_funcFree     ;    ///< pointer to the destructor function
  21             size_t                              m_nNextFree    ;    ///< Next free item in retired array
  22             CDS_ATOMIC::atomic<unsigned int>    m_nClaim       ;    ///< Access to reclaimed node
  23             CDS_ATOMIC::atomic<bool>            m_bDone        ;    ///< the record is in work (concurrent access flag)
  24
  25             /// Default ctor
  26             retired_node()
  27                 : m_pNode( null_ptr<ContainerNode *>() )
  28                 , m_funcFree( null_ptr<free_retired_ptr_func>() )
  29                 , m_nNextFree(0)
  30                 , m_nClaim(0)
  31                 , m_bDone( false )
  32             {}
  33
  34             /// Assignment ctor
  35             retired_node(
  36                 ContainerNode * pNode           ///< Node to retire
  37                 ,free_retired_ptr_func func     ///< Destructor function
  38                 )
  39                 : m_pNode( pNode )
  40                 , m_funcFree( func )
  41                 , m_nClaim(0)
  42                 , m_bDone( false )
  43             {}
  44
  45             /// Compares two \ref retired_node
  46             static bool Less( const retired_node& p1, const retired_node& p2 )
  47             {
  48                 return p1.m_pNode.load( CDS_ATOMIC::memory_order_relaxed ) < p2.m_pNode.load( CDS_ATOMIC::memory_order_relaxed );
  49             }
  50
  51             /// Assignment operator
  52             retired_node& set( ContainerNode * pNode, free_retired_ptr_func func )
  53             {
  54                 m_bDone.store( false, CDS_ATOMIC::memory_order_relaxed );
  55                 m_nClaim.store( 0, CDS_ATOMIC::memory_order_relaxed );
  56                 m_funcFree = func;
  57                 m_pNode.store( pNode, CDS_ATOMIC::memory_order_release );
  58                 CDS_COMPILER_RW_BARRIER;
  59                 return *this;
  60             }
  61
  62             /// Invokes destructor function for the pointer
  63             void free()
  64             {
  65                 assert( m_funcFree != null_ptr<free_retired_ptr_func>() );
  66                 m_funcFree( m_pNode.load( CDS_ATOMIC::memory_order_relaxed ));
  67             }
  68         };
  69
  70         /// Compare two retired node
  71         /**
  72             This comparison operator is needed for sorting pointers on
  73             deallocation step
  74         */
  75         static inline bool operator <( const retired_node& p1, const retired_node& p2 )
  76         {
  77             return retired_node::Less( p1, p2 );
  78         }
  79
  80         /// Array of ready for destroying pointers
  81         /**
  82             The array object is belonged to one thread: only owner thread may write to this array,
  83             any other thread can read one.
  84         */
  85         class retired_vector
  86         {
  87             typedef cds::details::bounded_array<retired_node> vector_type  ;   ///< type of vector of retired pointer (implicit CDS_DEFAULT_ALLOCATOR dependency)
  88
  89             //@cond
  90             static const size_t m_nEndFreeList = size_t(0) -  1 ;    ///< End of free list
  91             //@endcond
  92             size_t          m_nFreeList ; ///< Index of first free item in m_arr
  93             vector_type     m_arr       ; ///< Array of retired pointers (implicit \ref CDS_DEFAULT_ALLOCATOR dependence)
  94
  95         public:
  96             /// Iterator over retired pointer vector
  97             typedef vector_type::iterator                       iterator;
  98             /// Const iterator type
  99             typedef vector_type::const_iterator                 const_iterator;
 100
 101         public:
 102             /// Ctor
 103             retired_vector( const GarbageCollector& mgr )    ;    // inline
 104             ~retired_vector()
 105             {}
 106
 107             ///@anchor hrc_gc_retired_vector_capacity Capacity (max available size) of array
 108             size_t capacity() const
 109             {
 110                 return m_arr.capacity();
 111             }
 112
 113             /// Returns count of retired node in array. This function is intended for debug purposes only
 114             size_t retiredNodeCount() const
 115             {
 116                 size_t nCount = 0;
 117                 const size_t nCapacity = capacity();
 118                 for ( size_t i = 0; i < nCapacity; ++i ) {
 119                     if ( m_arr[i].m_pNode.load( CDS_ATOMIC::memory_order_relaxed ) != null_ptr<ContainerNode *>() )
 120                         ++nCount;
 121                 }
 122                 return nCount;
 123             }
 124
 125             /// Push a new item into the array
 126             void push( ContainerNode * p, free_retired_ptr_func pFunc )
 127             {
 128                 assert( !isFull());
 129
 130                 size_t n = m_nFreeList;
 131                 assert( m_arr[n].m_pNode.load( CDS_ATOMIC::memory_order_relaxed ) == null_ptr<ContainerNode *>() );
 132                 m_nFreeList = m_arr[n].m_nNextFree;
 133                 CDS_DEBUG_DO( m_arr[n].m_nNextFree = m_nEndFreeList ; )
 134                 m_arr[n].set( p, pFunc );
 135             }
 136
 137             /// Pops the item by index \p n from the array
 138             void pop( size_t n )
 139             {
 140                 assert( n < capacity() );
 141                 m_arr[n].m_pNode.store( null_ptr<ContainerNode *>(), CDS_ATOMIC::memory_order_release );
 142                 m_arr[n].m_nNextFree = m_nFreeList;
 143                 m_nFreeList = n;
 144             }
 145
 146             /// Checks if array is full
 147             bool isFull() const
 148             {
 149                 return m_nFreeList == m_nEndFreeList;
 150             }
 151
 152             /// Get the item by index \p i
 153             retired_node& operator []( size_t i )
 154             {
 155                 assert( i < capacity() );
 156                 return m_arr[i];
 157             }
 158
 159             /// Returns a random-access iterator to the first element in the retired pointer vector
 160             /**
 161                 If the vector is empty, end() == begin().
 162             */
 163             iterator begin()
 164             {
 165                 return m_arr.begin();
 166             }
 167
 168             /// Const version of begin()
 169             const_iterator begin() const
 170             {
 171                 return m_arr.begin();
 172             }
 173
 174             /// A random-access iterator to the end of the vector object.
 175             /**
 176                 If the vector is empty, end() == begin().
 177             */
 178             iterator end()
 179             {
 180                 return m_arr.end();
 181             }
 182
 183             /// Const version of end()
 184             const_iterator end() const
 185             {
 186                 return m_arr.end();
 187             }
 188         };
 189
 190     }    // namespace details
 191 }}}    // namespace cds::gc::hrc
 192
 193 #endif // #ifndef __CDS_GC_HRC_SCHEMA_RETIRED_H