3 #ifndef CDSLIB_GC_DETAILS_HP_ALLOC_H
4 #define CDSLIB_GC_DETAILS_HP_ALLOC_H
6 #include <cds/algo/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()
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() );
249 /// Allocates hazard pointers array
251 Allocates \p Count hazard pointers from array \p m_arrHazardPtr
252 Returns initialized object \p arr
254 template <size_t Count>
255 void alloc( hp_array<Count>& arr )
257 assert( m_nTop >= Count );
259 arr.m_arr = m_arrHazardPtr + m_nTop;
262 /// Frees hazard pointer array
264 Frees the array of hazard pointers allocated by previous call \p this->alloc.
266 template <size_t Count>
267 void free( hp_array<Count> const& arr ) CDS_NOEXCEPT
271 assert( m_nTop + Count <= capacity());
272 for ( size_t i = m_nTop; i < m_nTop + Count; ++i )
273 m_arrHazardPtr[i].clear();
277 /// Makes all HP free
278 void clear() CDS_NOEXCEPT
283 /// Returns to i-th hazard pointer
284 atomic_hazard_ptr& operator []( size_t i ) CDS_NOEXCEPT
286 assert( i < capacity() );
287 return m_arrHazardPtr[i];
291 void make_free() CDS_NOEXCEPT
293 for ( size_t i = 0; i < capacity(); ++i )
294 m_arrHazardPtr[i].clear();
298 atomic_hazard_ptr * alloc_array( size_t nCapacity )
300 return allocator_impl().NewArray( nCapacity );
304 }}} // namespace gc::hp::details
308 #endif // #ifndef CDSLIB_GC_DETAILS_HP_ALLOC_H