3 #ifndef __CDS_GC_HP_DETAILS_HP_ALLOC_H
4 #define __CDS_GC_HP_DETAILS_HP_ALLOC_H
6 #include <cds/cxx11_atomic.h>
7 #include <cds/details/allocator.h>
8 #include <cds/gc/hp/details/hp_fwd.h>
9 #include <cds/gc/hp/details/hp_type.h>
13 namespace gc { namespace hp {
14 /// Hazard Pointer schema implementation details
17 /// Hazard pointer guard
19 It is unsafe to use this class directly.
20 Instead, the AutoHPGuard class should be used.
23 \li HazardPointer - type of hazard pointer. It is \ref hazard_pointer for Michael's Hazard Pointer reclamation schema
25 template <typename HazardPointer>
26 class HPGuardT: protected atomics::atomic<HazardPointer>
29 typedef HazardPointer hazard_ptr ; ///< Hazard pointer type
32 typedef atomics::atomic<hazard_ptr> base_class;
37 template <typename OtherHazardPointer, class Allocator> friend class HPAllocator;
41 HPGuardT() CDS_NOEXCEPT
42 : base_class( nullptr )
44 ~HPGuardT() CDS_NOEXCEPT
47 /// Sets HP value. Guards pointer \p p from reclamation.
49 Storing has release semantics.
52 T * operator =( T * p ) CDS_NOEXCEPT
54 // We use atomic store with explicit memory order because other threads may read this hazard pointer concurrently
55 base_class::store( reinterpret_cast<hazard_ptr>(p), atomics::memory_order_release );
60 std::nullptr_t operator=( std::nullptr_t ) CDS_NOEXCEPT
67 /// Returns current value of hazard pointer
69 Loading has acquire semantics
71 operator hazard_ptr() const CDS_NOEXCEPT
76 /// Returns current value of hazard pointer
78 Loading has acquire semantics
80 hazard_ptr get() const CDS_NOEXCEPT
82 return base_class::load( atomics::memory_order_acquire );
87 Clearing has relaxed semantics.
89 void clear() CDS_NOEXCEPT
91 // memory order is not necessary here
92 base_class::store( nullptr, atomics::memory_order_relaxed );
93 //CDS_COMPILER_RW_BARRIER;
97 /// Specialization of HPGuardT for hazard_pointer type
98 typedef HPGuardT<hazard_pointer> HPGuard;
100 /// Array of hazard pointers.
102 Array of hazard-pointer. Placing a pointer into this array guards the pointer against reclamation.
103 Template parameter \p Count defines the size of hazard pointer array. \p Count parameter should not exceed
104 GarbageCollector::getHazardPointerCount().
106 It is unsafe to use this class directly. Instead, the AutoHPArray should be used.
108 While creating the object of HPArray class an array of size \p Count of hazard pointers is reserved by
109 the HP Manager of current thread. The object's destructor cleans all of reserved hazard pointer and
110 returns reserved HP to the HP pool of ThreadGC.
112 Usually, it is not necessary to create an object of this class. The object of class ThreadGC contains
113 the HPArray object and implements interface for HP setting and freeing.
116 \li HazardPointer - type of hazard pointer. It is hazard_pointer usually
117 \li Count - capacity of array
120 template <typename HazardPointer, size_t Count>
124 typedef HazardPointer hazard_ptr_type ; ///< Hazard pointer type
125 typedef HPGuardT<hazard_ptr_type> atomic_hazard_ptr ; ///< Element type of the array
126 static const size_t c_nCapacity = Count ; ///< Capacity of the array
130 atomic_hazard_ptr * m_arr ; ///< Hazard pointer array of size = \p Count
131 template <typename OtherHazardPointer, class Allocator> friend class HPAllocator;
135 /// Constructs uninitialized array.
136 HPArrayT() CDS_NOEXCEPT
140 ~HPArrayT() CDS_NOEXCEPT
143 /// Returns max count of hazard pointer for this array
144 CDS_CONSTEXPR size_t capacity() const
149 /// Set hazard pointer \p nIndex. 0 <= \p nIndex < \p Count
150 void set( size_t nIndex, hazard_ptr_type hzPtr ) CDS_NOEXCEPT
152 assert( nIndex < capacity() );
153 m_arr[nIndex] = hzPtr;
156 /// Returns reference to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count)
157 atomic_hazard_ptr& operator []( size_t nIndex ) CDS_NOEXCEPT
159 assert( nIndex < capacity() );
160 return m_arr[nIndex];
163 /// Returns reference to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count) [const version]
164 atomic_hazard_ptr& operator []( size_t nIndex ) const CDS_NOEXCEPT
166 assert( nIndex < capacity() );
167 return m_arr[nIndex];
170 /// Clears (sets to \p nullptr) hazard pointer \p nIndex
171 void clear( size_t nIndex ) CDS_NOEXCEPT
173 assert( nIndex < capacity() );
174 m_arr[ nIndex ].clear();
178 /// Specialization of HPArrayT class for hazard_pointer type
179 template <size_t Count> using HPArray = HPArrayT<hazard_pointer, Count >;
181 /// Allocator of hazard pointers for the thread
183 The hazard pointer array is the free-list of unused hazard pointer for the thread.
184 The array is managed as a stack.
185 The max size (capacity) of array is defined at ctor time and cannot be changed during object's lifetime
187 Each allocator object is thread-private.
190 \li HazardPointer - type of hazard pointer (hazard_pointer usually)
191 \li Allocator - memory allocator class, default is \ref CDS_DEFAULT_ALLOCATOR
193 This helper class should not be used directly.
195 template < typename HazardPointer, class Allocator = CDS_DEFAULT_ALLOCATOR >
199 typedef HazardPointer hazard_ptr_type ; ///< type of hazard pointer
200 typedef HPGuardT<hazard_ptr_type> atomic_hazard_ptr ; ///< Atomic hazard pointer type
201 typedef Allocator allocator_type ; ///< allocator type
205 typedef cds::details::Allocator< atomic_hazard_ptr, allocator_type > allocator_impl;
207 atomic_hazard_ptr * m_arrHazardPtr ; ///< Array of hazard pointers
208 size_t m_nTop ; ///< The top of stack
209 const size_t m_nCapacity ; ///< Array capacity
215 explicit HPAllocator(
216 size_t nCapacity ///< max count of hazard pointer per thread
218 : m_arrHazardPtr( alloc_array( nCapacity ) )
219 , m_nCapacity( nCapacity )
227 allocator_impl().Delete( m_arrHazardPtr, capacity() );
230 /// Get capacity of array
231 size_t capacity() const CDS_NOEXCEPT
236 /// Get size of array. The size is equal to the capacity of array
237 size_t size() const CDS_NOEXCEPT
242 /// Checks if all items are allocated
243 bool isFull() const CDS_NOEXCEPT
248 /// Allocates hazard pointer
249 atomic_hazard_ptr& alloc() CDS_NOEXCEPT
251 assert( m_nTop > 0 );
253 return m_arrHazardPtr[m_nTop];
256 /// Frees previously allocated hazard pointer
257 void free( atomic_hazard_ptr& hp ) CDS_NOEXCEPT
259 assert( m_nTop < capacity() );
262 CDS_COMPILER_RW_BARRIER ; // ???
265 /// Allocates hazard pointers array
267 Allocates \p Count hazard pointers from array \p m_arrHazardPtr
268 Returns initialized object \p arr
270 template <size_t Count>
271 void alloc( HPArrayT<hazard_ptr_type, Count>& arr ) CDS_NOEXCEPT
273 assert( m_nTop >= Count );
275 arr.m_arr = m_arrHazardPtr + m_nTop;
278 /// Frees hazard pointer array
280 Frees the array of hazard pointers allocated by previous call \p this->alloc.
282 template <size_t Count>
283 void free( const HPArrayT<hazard_ptr_type, Count>& arr ) CDS_NOEXCEPT
285 assert( m_nTop + Count <= capacity());
286 for ( size_t i = m_nTop; i < m_nTop + Count; ++i )
287 m_arrHazardPtr[ i ].clear();
291 /// Makes all HP free
292 void clear() CDS_NOEXCEPT
297 /// Returns to i-th hazard pointer
298 atomic_hazard_ptr& operator []( size_t i ) CDS_NOEXCEPT
300 assert( i < capacity() );
301 return m_arrHazardPtr[i];
306 void make_free() CDS_NOEXCEPT
308 for ( size_t i = 0; i < capacity(); ++i )
309 m_arrHazardPtr[ i ].clear();
313 atomic_hazard_ptr * alloc_array( size_t nCapacity )
315 return allocator_impl().NewArray( nCapacity );
320 }}} // namespace gc::hp::details
324 #endif // #ifndef __CDS_GC_HP_DETAILS_HP_ALLOC_H