3 #ifndef __CDS_GC_DETAILS_HP_ALLOC_H
4 #define __CDS_GC_DETAILS_HP_ALLOC_H
6 #include <cds/cxx11_atomic.h>
7 #include <cds/details/allocator.h>
8 #include <cds/gc/details/hp_type.h>
12 namespace gc { namespace hp {
14 class GarbageCollector;
17 /// Hazard Pointer schema implementation details
20 /// Hazard pointer guard
22 It is unsafe to use this class directly.
23 Instead, the \p hp::guard class should be used.
25 class hp_guard : protected atomics::atomic < hazard_pointer >
28 typedef hazard_pointer hazard_ptr; ///< Hazard pointer type
31 typedef atomics::atomic<hazard_ptr> base_class;
36 template <class Allocator> friend class hp_allocator;
40 hp_guard() CDS_NOEXCEPT
41 : base_class( nullptr )
43 ~hp_guard() CDS_NOEXCEPT
46 /// Sets HP value. Guards pointer \p p from reclamation.
48 Storing has release semantics.
51 T * operator =(T * p) CDS_NOEXCEPT
53 // We use atomic store with explicit memory order because other threads may read this hazard pointer concurrently
59 std::nullptr_t operator=(std::nullptr_t) CDS_NOEXCEPT
66 /// Returns current value of hazard pointer
68 Loading has acquire semantics
70 operator hazard_ptr() const CDS_NOEXCEPT
75 /// Returns current value of hazard pointer
77 Loading has acquire semantics
79 hazard_ptr get( atomics::memory_order order = atomics::memory_order_acquire ) const CDS_NOEXCEPT
81 return base_class::load( order );
85 void set( T * p, atomics::memory_order order = atomics::memory_order_release ) CDS_NOEXCEPT
87 base_class::store( reinterpret_cast<hazard_ptr>(p), order );
92 Clearing has relaxed semantics.
94 void clear( atomics::memory_order order = atomics::memory_order_relaxed ) CDS_NOEXCEPT
96 // memory order is not necessary here
97 base_class::store( nullptr, order );
101 /// Array of hazard pointers.
103 Array of hazard-pointer. Placing a pointer into this array guards the pointer against reclamation.
104 Template parameter \p Count defines the size of hazard pointer array. \p Count parameter should not exceed
105 GarbageCollector::getHazardPointerCount().
107 It is unsafe to use this class directly. Instead, the \p hp::array should be used.
109 While creating the object of \p hp_array class an array of size \p Count of hazard pointers is reserved by
110 the HP Manager of current thread. The object's destructor cleans all of reserved hazard pointer and
111 returns reserved HP to the HP pool of ThreadGC.
113 Usually, it is not necessary to create an object of this class. The object of class ThreadGC contains
114 the \p hp_array object and implements interface for HP setting and freeing.
117 \li Count - capacity of array
120 template <size_t Count>
124 typedef hazard_pointer hazard_ptr_type; ///< Hazard pointer type
125 typedef hp_guard atomic_hazard_ptr; ///< Element type of the array
126 static CDS_CONSTEXPR 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 <class Allocator> friend class hp_allocator;
135 /// Constructs uninitialized array.
136 hp_array() CDS_NOEXCEPT
140 ~hp_array() 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 /// Allocator of hazard pointers for the thread
180 The hazard pointer array is the free-list of unused hazard pointer for the thread.
181 The array is managed as a stack.
182 The max size (capacity) of array is defined at ctor time and cannot be changed during object's lifetime
184 Each allocator object is thread-private.
187 \li Allocator - memory allocator class, default is \ref CDS_DEFAULT_ALLOCATOR
189 This helper class should not be used directly.
191 template <class Allocator = CDS_DEFAULT_ALLOCATOR >
195 typedef hazard_pointer hazard_ptr_type; ///< type of hazard pointer
196 typedef hp_guard atomic_hazard_ptr; ///< Atomic hazard pointer type
197 typedef Allocator allocator_type; ///< allocator type
201 typedef cds::details::Allocator< atomic_hazard_ptr, allocator_type > allocator_impl;
203 atomic_hazard_ptr * m_arrHazardPtr ; ///< Array of hazard pointers
204 size_t m_nTop ; ///< The top of stack
205 const size_t m_nCapacity ; ///< Array capacity
211 explicit hp_allocator(
212 size_t nCapacity ///< max count of hazard pointer per thread
214 : m_arrHazardPtr( alloc_array( nCapacity ) )
215 , m_nCapacity( nCapacity )
223 allocator_impl().Delete( m_arrHazardPtr, capacity() );
226 /// Get capacity of array
227 size_t capacity() const CDS_NOEXCEPT
232 /// Get size of array. The size is equal to the capacity of array
233 size_t size() const CDS_NOEXCEPT
238 /// Checks if all items are allocated
239 bool isFull() const CDS_NOEXCEPT
244 /// Allocates hazard pointer
245 atomic_hazard_ptr& alloc() CDS_NOEXCEPT
247 assert( m_nTop > 0 );
249 return m_arrHazardPtr[m_nTop];
252 /// Frees previously allocated hazard pointer
253 void free( atomic_hazard_ptr& hp ) CDS_NOEXCEPT
255 assert( m_nTop < capacity() );
258 CDS_COMPILER_RW_BARRIER ; // ???
261 /// Allocates hazard pointers array
263 Allocates \p Count hazard pointers from array \p m_arrHazardPtr
264 Returns initialized object \p arr
266 template <size_t Count>
267 void alloc( hp_array<Count>& arr ) CDS_NOEXCEPT
269 assert( m_nTop >= Count );
271 arr.m_arr = m_arrHazardPtr + m_nTop;
274 /// Frees hazard pointer array
276 Frees the array of hazard pointers allocated by previous call \p this->alloc.
278 template <size_t Count>
279 void free( hp_array<Count> const& arr ) CDS_NOEXCEPT
281 assert( m_nTop + Count <= capacity());
282 for ( size_t i = m_nTop; i < m_nTop + Count; ++i )
283 m_arrHazardPtr[ i ].clear();
287 /// Makes all HP free
288 void clear() CDS_NOEXCEPT
293 /// Returns to i-th hazard pointer
294 atomic_hazard_ptr& operator []( size_t i ) CDS_NOEXCEPT
296 assert( i < capacity() );
297 return m_arrHazardPtr[i];
302 void make_free() CDS_NOEXCEPT
304 for ( size_t i = 0; i < capacity(); ++i )
305 m_arrHazardPtr[ i ].clear();
309 atomic_hazard_ptr * alloc_array( size_t nCapacity )
311 return allocator_impl().NewArray( nCapacity );
316 }}} // namespace gc::hp::details
320 #endif // #ifndef __CDS_GC_DETAILS_HP_ALLOC_H