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
30 typedef atomics::atomic<hazard_ptr> base_class;
33 template <class Allocator> friend class hp_allocator;
36 hp_guard() CDS_NOEXCEPT
37 : base_class( nullptr )
39 ~hp_guard() CDS_NOEXCEPT
42 /// Sets HP value. Guards pointer \p p from reclamation.
44 Storing has release semantics.
47 T * operator =(T * p) CDS_NOEXCEPT
49 // We use atomic store with explicit memory order because other threads may read this hazard pointer concurrently
54 std::nullptr_t operator=(std::nullptr_t) CDS_NOEXCEPT
60 /// Returns current value of hazard pointer
62 Loading has acquire semantics
64 operator hazard_ptr() const CDS_NOEXCEPT
69 /// Returns current value of hazard pointer
71 Loading has acquire semantics
73 hazard_ptr get( atomics::memory_order order = atomics::memory_order_acquire ) const CDS_NOEXCEPT
75 return base_class::load( order );
79 void set( T * p, atomics::memory_order order = atomics::memory_order_release ) CDS_NOEXCEPT
81 base_class::store( reinterpret_cast<hazard_ptr>(p), order );
86 Clearing has relaxed semantics.
88 void clear( atomics::memory_order order = atomics::memory_order_relaxed ) CDS_NOEXCEPT
90 // memory order is not necessary here
91 base_class::store( nullptr, order );
95 /// Array of hazard pointers.
97 Array of hazard-pointer. Placing a pointer into this array guards the pointer against reclamation.
98 Template parameter \p Count defines the size of hazard pointer array. \p Count parameter should not exceed
99 GarbageCollector::getHazardPointerCount().
101 It is unsafe to use this class directly. Instead, the \p hp::array should be used.
103 While creating the object of \p hp_array class an array of size \p Count of hazard pointers is reserved by
104 the HP Manager of current thread. The object's destructor cleans all of reserved hazard pointer and
105 returns reserved HP to the HP pool of ThreadGC.
107 Usually, it is not necessary to create an object of this class. The object of class ThreadGC contains
108 the \p hp_array object and implements interface for HP setting and freeing.
111 \li Count - capacity of array
114 template <size_t Count>
118 typedef hazard_pointer hazard_ptr_type; ///< Hazard pointer type
119 typedef hp_guard atomic_hazard_ptr; ///< Element type of the array
120 static CDS_CONSTEXPR const size_t c_nCapacity = Count ; ///< Capacity of the array
123 atomic_hazard_ptr * m_arr ; ///< Hazard pointer array of size = \p Count
124 template <class Allocator> friend class hp_allocator;
127 /// Constructs uninitialized array.
128 hp_array() CDS_NOEXCEPT
132 ~hp_array() 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 \p nullptr) hazard pointer \p nIndex
163 void clear( size_t nIndex ) CDS_NOEXCEPT
165 assert( nIndex < capacity() );
166 m_arr[ nIndex ].clear();
170 /// Allocator of hazard pointers for the thread
172 The hazard pointer array is the free-list of unused hazard pointer for the thread.
173 The array is managed as a stack.
174 The max size (capacity) of array is defined at ctor time and cannot be changed during object's lifetime
176 Each allocator object is thread-private.
179 \li Allocator - memory allocator class, default is \ref CDS_DEFAULT_ALLOCATOR
181 This helper class should not be used directly.
183 template <class Allocator = CDS_DEFAULT_ALLOCATOR >
187 typedef hazard_pointer hazard_ptr_type; ///< type of hazard pointer
188 typedef hp_guard atomic_hazard_ptr; ///< Atomic hazard pointer type
189 typedef Allocator allocator_type; ///< allocator type
192 typedef cds::details::Allocator< atomic_hazard_ptr, allocator_type > allocator_impl;
194 atomic_hazard_ptr * m_arrHazardPtr ; ///< Array of hazard pointers
195 size_t m_nTop ; ///< The top of stack
196 const size_t m_nCapacity ; ///< Array capacity
200 explicit hp_allocator(
201 size_t nCapacity ///< max count of hazard pointer per thread
203 : m_arrHazardPtr( alloc_array( nCapacity ) )
204 , m_nCapacity( nCapacity )
212 allocator_impl().Delete( m_arrHazardPtr, capacity() );
215 /// Get capacity of array
216 size_t capacity() const CDS_NOEXCEPT
221 /// Get size of array. The size is equal to the capacity of array
222 size_t size() const CDS_NOEXCEPT
227 /// Checks if all items are allocated
228 bool isFull() const CDS_NOEXCEPT
233 /// Allocates hazard pointer
234 atomic_hazard_ptr& alloc() CDS_NOEXCEPT
236 assert( m_nTop > 0 );
238 return m_arrHazardPtr[m_nTop];
241 /// Frees previously allocated hazard pointer
242 void free( atomic_hazard_ptr& hp ) CDS_NOEXCEPT
244 assert( m_nTop < capacity() );
247 CDS_COMPILER_RW_BARRIER ; // ???
250 /// Allocates hazard pointers array
252 Allocates \p Count hazard pointers from array \p m_arrHazardPtr
253 Returns initialized object \p arr
255 template <size_t Count>
256 void alloc( hp_array<Count>& arr ) CDS_NOEXCEPT
258 assert( m_nTop >= Count );
260 arr.m_arr = m_arrHazardPtr + m_nTop;
263 /// Frees hazard pointer array
265 Frees the array of hazard pointers allocated by previous call \p this->alloc.
267 template <size_t Count>
268 void free( hp_array<Count> const& arr ) CDS_NOEXCEPT
270 assert( m_nTop + Count <= capacity());
271 for ( size_t i = m_nTop; i < m_nTop + Count; ++i )
272 m_arrHazardPtr[ i ].clear();
276 /// Makes all HP free
277 void clear() CDS_NOEXCEPT
282 /// Returns to i-th hazard pointer
283 atomic_hazard_ptr& operator []( size_t i ) CDS_NOEXCEPT
285 assert( i < capacity() );
286 return m_arrHazardPtr[i];
290 void make_free() CDS_NOEXCEPT
292 for ( size_t i = 0; i < capacity(); ++i )
293 m_arrHazardPtr[ i ].clear();
297 atomic_hazard_ptr * alloc_array( size_t nCapacity )
299 return allocator_impl().NewArray( nCapacity );
303 }}} // namespace gc::hp::details
307 #endif // #ifndef __CDS_GC_DETAILS_HP_ALLOC_H