3 #ifndef __CDS_GC_HZP_DETAILS_HP_ALLOC_H
4 #define __CDS_GC_HZP_DETAILS_HP_ALLOC_H
6 #include <cds/cxx11_atomic.h>
7 #include <cds/details/allocator.h>
8 #include <cds/gc/hzp/details/hp_fwd.h>
9 #include <cds/gc/hzp/details/hp_type.h>
13 namespace gc { namespace hzp {
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 CDS_ATOMIC::atomic<HazardPointer>
29 typedef HazardPointer hazard_ptr ; ///< Hazard pointer type
32 typedef CDS_ATOMIC::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), CDS_ATOMIC::memory_order_release );
59 /// Returns current value of hazard pointer
61 Loading has acquire semantics
63 operator hazard_ptr() const CDS_NOEXCEPT
68 /// Returns current value of hazard pointer
70 Loading has acquire semantics
72 hazard_ptr get() const CDS_NOEXCEPT
74 return base_class::load( CDS_ATOMIC::memory_order_acquire );
79 Clearing has relaxed semantics.
81 void clear() CDS_NOEXCEPT
83 // memory order is not necessary here
84 base_class::store( nullptr, CDS_ATOMIC::memory_order_relaxed );
85 //CDS_COMPILER_RW_BARRIER;
89 /// Specialization of HPGuardT for hazard_pointer type
90 typedef HPGuardT<hazard_pointer> HPGuard;
92 /// Array of hazard pointers.
94 Array of hazard-pointer. Placing a pointer into this array guards the pointer against reclamation.
95 Template parameter \p Count defines the size of hazard pointer array. \p Count parameter should not exceed
96 GarbageCollector::getHazardPointerCount().
98 It is unsafe to use this class directly. Instead, the AutoHPArray should be used.
100 While creating the object of HPArray class an array of size \p Count of hazard pointers is reserved by
101 the HP Manager of current thread. The object's destructor cleans all of reserved hazard pointer and
102 returns reserved HP to the HP pool of ThreadGC.
104 Usually, it is not necessary to create an object of this class. The object of class ThreadGC contains
105 the HPArray object and implements interface for HP setting and freeing.
108 \li HazardPointer - type of hazard pointer. It is hazard_pointer usually
109 \li Count - capacity of array
112 template <typename HazardPointer, size_t Count>
116 typedef HazardPointer hazard_ptr_type ; ///< Hazard pointer type
117 typedef HPGuardT<hazard_ptr_type> atomic_hazard_ptr ; ///< Element type of the array
118 static const size_t c_nCapacity = Count ; ///< Capacity of the array
122 atomic_hazard_ptr * m_arr ; ///< Hazard pointer array of size = \p Count
123 template <typename OtherHazardPointer, class Allocator> friend class HPAllocator;
127 /// Constructs uninitialized array.
128 HPArrayT() CDS_NOEXCEPT
132 ~HPArrayT() CDS_NOEXCEPT
135 /// Returns max count of hazard pointer for this array
136 CDS_CONSTEXPR size_t capacity() const
141 /// Set hazard pointer \p nIndex. 0 <= \p nIndex < \p Count
142 void set( size_t nIndex, hazard_ptr_type hzPtr ) CDS_NOEXCEPT
144 assert( nIndex < capacity() );
145 m_arr[nIndex] = hzPtr;
148 /// Returns reference to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count)
149 atomic_hazard_ptr& operator []( size_t nIndex ) CDS_NOEXCEPT
151 assert( nIndex < capacity() );
152 return m_arr[nIndex];
155 /// Returns reference to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count) [const version]
156 atomic_hazard_ptr& operator []( size_t nIndex ) const CDS_NOEXCEPT
158 assert( nIndex < capacity() );
159 return m_arr[nIndex];
162 /// Clears (sets to NULL) hazard pointer \p nIndex
163 void clear( size_t nIndex ) CDS_NOEXCEPT
165 assert( nIndex < capacity() );
166 m_arr[ nIndex ].clear();
170 /// Specialization of HPArrayT class for hazard_pointer type
171 #ifdef CDS_CXX11_TEMPLATE_ALIAS_SUPPORT
172 template <size_t Count> using HPArray = HPArrayT<hazard_pointer, Count >;
174 template <size_t Count>
175 class HPArray: public HPArrayT<hazard_pointer, Count>
179 /// Allocator of hazard pointers for the thread
181 The hazard pointer array is the free-list of unused hazard pointer for the thread.
182 The array is managed as a stack.
183 The max size (capacity) of array is defined at ctor time and cannot be changed during object's lifetime
185 Each allocator object is thread-private.
188 \li HazardPointer - type of hazard pointer (hazard_pointer usually)
189 \li Allocator - memory allocator class, default is \ref CDS_DEFAULT_ALLOCATOR
191 This helper class should not be used directly.
193 template < typename HazardPointer, class Allocator = CDS_DEFAULT_ALLOCATOR >
197 typedef HazardPointer hazard_ptr_type ; ///< type of hazard pointer
198 typedef HPGuardT<hazard_ptr_type> atomic_hazard_ptr ; ///< Atomic hazard pointer type
199 typedef Allocator allocator_type ; ///< allocator type
203 typedef cds::details::Allocator< atomic_hazard_ptr, allocator_type > allocator_impl;
205 atomic_hazard_ptr * m_arrHazardPtr ; ///< Array of hazard pointers
206 size_t m_nTop ; ///< The top of stack
207 const size_t m_nCapacity ; ///< Array capacity
213 explicit HPAllocator(
214 size_t nCapacity ///< max count of hazard pointer per thread
216 : m_arrHazardPtr( alloc_array( nCapacity ) )
217 , m_nCapacity( nCapacity )
225 allocator_impl().Delete( m_arrHazardPtr, capacity() );
228 /// Get capacity of array
229 size_t capacity() const CDS_NOEXCEPT
234 /// Get size of array. The size is equal to the capacity of array
235 size_t size() const CDS_NOEXCEPT
240 /// Checks if all items are allocated
241 bool isFull() const CDS_NOEXCEPT
246 /// Allocates hazard pointer
247 atomic_hazard_ptr& alloc() CDS_NOEXCEPT
249 assert( m_nTop > 0 );
251 return m_arrHazardPtr[m_nTop];
254 /// Frees previously allocated hazard pointer
255 void free( atomic_hazard_ptr& hp ) CDS_NOEXCEPT
257 assert( m_nTop < capacity() );
260 CDS_COMPILER_RW_BARRIER ; // ???
263 /// Allocates hazard pointers array
265 Allocates \p Count hazard pointers from array \p m_arrHazardPtr
266 Returns initialized object \p arr
268 template <size_t Count>
269 void alloc( HPArrayT<hazard_ptr_type, Count>& arr ) CDS_NOEXCEPT
271 assert( m_nTop >= Count );
273 arr.m_arr = m_arrHazardPtr + m_nTop;
276 /// Frees hazard pointer array
278 Frees the array of hazard pointers allocated by previous call \p this->alloc.
280 template <size_t Count>
281 void free( const HPArrayT<hazard_ptr_type, Count>& arr ) CDS_NOEXCEPT
283 assert( m_nTop + Count <= capacity());
284 for ( size_t i = m_nTop; i < m_nTop + Count; ++i )
285 m_arrHazardPtr[ i ].clear();
289 /// Makes all HP free
290 void clear() CDS_NOEXCEPT
295 /// Returns to i-th hazard pointer
296 atomic_hazard_ptr& operator []( size_t i ) CDS_NOEXCEPT
298 assert( i < capacity() );
299 return m_arrHazardPtr[i];
304 void make_free() CDS_NOEXCEPT
306 for ( size_t i = 0; i < capacity(); ++i )
307 m_arrHazardPtr[ i ].clear();
311 atomic_hazard_ptr * alloc_array( size_t nCapacity )
313 return allocator_impl().NewArray( nCapacity );
318 }}} // namespace gc::hzp::details
322 #endif // #ifndef __CDS_GC_HZP_DETAILS_HP_ALLOC_H