3 #ifndef CDSLIB_LOCK_ARRAY_H
4 #define CDSLIB_LOCK_ARRAY_H
6 #include <mutex> //unique_lock
7 #include <cds/details/allocator.h>
8 #include <cds/algo/int_algo.h>
10 namespace cds { namespace lock {
12 /// Trivial lock \ref array selection policy
13 struct trivial_select_policy
16 size_t operator()( size_t nWhat, size_t nCapacity ) const
18 assert( nWhat < nCapacity );
19 CDS_UNUSED( nCapacity );
23 /// Checks if \p nCapacity is acceptable by policy. For trivial policy, any \p nCapacity is accepted.
24 static bool is_capacity_accepted( size_t nCapacity )
26 CDS_UNUSED( nCapacity );
31 /// The lock \ref array cell selection policy "division by modulo"
32 struct mod_select_policy
34 /// Returns <tt> nWhat % nCapacity </tt>
35 size_t operator()( size_t nWhat, size_t nCapacity ) const
37 return nWhat % nCapacity;
40 /// Checks if \p nCapacity is acceptable by policy. For modulo policy, any positive \p nCapacity is accepted.
41 static bool is_capacity_accepted( size_t nCapacity )
47 /// The lock \ref array cell selection policy "division by modulo of power of 2"
49 This policy may be used if the size of lock array is equal to power of two.
51 struct pow2_select_policy
57 /// Ctor. \p nCapacity must be power of two.
58 pow2_select_policy( size_t nCapacity )
59 : m_nMask( nCapacity - 1 )
61 assert( is_capacity_accepted( nCapacity ));
65 pow2_select_policy( pow2_select_policy const& src )
66 : m_nMask( src.m_nMask )
70 pow2_select_policy( pow2_select_policy&& src )
71 : m_nMask( src.m_nMask )
74 /// Returns <tt>nWhat & (nPow2 - 1)</tt>
75 size_t operator()( size_t nWhat, size_t ) const
77 return nWhat & m_nMask;
80 /// Checks if \p nCapacity is acceptable by policy. \p nCapacity must be power of two
81 static bool is_capacity_accepted( size_t nCapacity )
83 return cds::beans::is_power2( nCapacity );
89 The lock array is useful for building fine-grained lock-based data structure
90 based on striping technique. Instead of locking access to data struct (a hash map, for example)
91 at whole, the striping locks only part of the map (a bucket). So, access to different buckets
95 - \p Lock - lock type, for example, \p std::mutex, \p cds::sync::spin_lock
96 - \p SelectPolicy - array cell selection policy, the default is \ref mod_select_policy
97 Available policies: \ref trivial_select_policy, \ref pow2_select_policy, \ref mod_select_policy.
98 - \p Alloc - memory allocator for array
100 To determine array's cell the selection policy \p SelectPolicy functor is used. Two arguments
101 are passed to the policy:
102 \code size_t operator()( size_t nHint, size_t nCapacity ) const \endcode
103 - \p nHint - a hint to calculate cell index in the lock array. Usually, it is a hash value.
104 - \p nCapacity - the size of the lock array
105 The functor should return the index in the lock array.
107 Note that the type of \p nHint parameter can be any.
109 template <typename Lock
110 , typename SelectPolicy = mod_select_policy
111 , class Alloc = CDS_DEFAULT_ALLOCATOR
116 typedef ::cds::details::Allocator< Lock, Alloc > cxx_allocator;
119 typedef Lock lock_type ; ///< lock type
120 typedef SelectPolicy select_cell_policy ; ///< Cell selection policy functor
121 static size_t const c_nUnspecifiedCell = (size_t) -1 ; ///< failed \ref try_lock call result
124 lock_type * m_arrLocks ; ///< lock array
125 size_t const m_nCapacity ; ///< array capacity
127 select_cell_policy m_SelectCellPolicy ; ///< Cell selection policy
131 static lock_type * create_lock_array( size_t nCapacity )
133 return cxx_allocator().NewArray( nCapacity );
135 static void delete_lock_array( lock_type * pArr, size_t nCapacity )
138 cxx_allocator().Delete( pArr, nCapacity );
141 // Only for internal use!!!
143 : m_arrLocks( nullptr )
146 array( select_cell_policy const& policy )
147 : m_arrLocks( nullptr )
149 , m_SelectCellPolicy( policy )
154 /// Constructs array of locks
156 Allocates the array and initializes all locks as unlocked.
159 size_t nCapacity ///< [in] Array size
161 : m_arrLocks( nullptr )
162 , m_nCapacity( nCapacity )
164 m_arrLocks = create_lock_array( nCapacity );
167 /// Constructs array of lock and copy cell selection policy
169 Allocates the array and initializes all locks as unlocked.
172 size_t nCapacity, ///< [in] Array size
173 select_cell_policy const& policy ///< Cell selection policy (copy-constructible)
175 : m_arrLocks( nullptr )
176 , m_nCapacity( nCapacity )
177 , m_SelectCellPolicy( policy )
179 m_arrLocks = create_lock_array( m_nCapacity );
182 /// Constructs array of lock and move cell selection policy
184 Allocates the array and initializes all locks as unlocked.
187 size_t nCapacity, ///< [in] Array size
188 select_cell_policy&& policy ///< Cell selection policy (move-constructible)
190 : m_arrLocks( nullptr )
191 , m_nCapacity( nCapacity )
192 , m_SelectCellPolicy( std::forward<select_cell_policy>( policy ))
194 m_arrLocks = create_lock_array( m_nCapacity );
197 /// Destructs array of locks and frees used memory
200 delete_lock_array( m_arrLocks, m_nCapacity );
203 /// Locks a lock at cell \p hint
205 To define real array's cell which should be locked, \ref select_cell_policy is used.
206 The target cell is a result of <tt>select_cell_policy( hint, size() )</tt>.
208 Returns the index of locked lock.
210 template <typename Q>
211 size_t lock( Q const& hint )
213 size_t nCell = m_SelectCellPolicy( hint, size() );
214 assert( nCell < size() );
215 m_arrLocks[nCell].lock();
219 /// Try lock a lock at cell \p hint
221 To define real array's cell which should be locked, \ref select_cell_policy is used.
222 The target cell is a result of <tt>select_cell_policy( hint, size() )</tt>.
224 Returns the index of locked lock if success, \ref c_nUnspecifiedCell constant otherwise.
226 template <typename Q>
227 size_t try_lock( Q const& hint )
229 size_t nCell = m_SelectCellPolicy( hint, size() );
230 assert( nCell < size() );
231 if ( m_arrLocks[nCell].try_lock() )
233 return c_nUnspecifiedCell;
236 /// Unlock the lock specified by index \p nCell
237 void unlock( size_t nCell )
239 assert( nCell < size() );
240 m_arrLocks[nCell].unlock();
246 lock_type * pLock = m_arrLocks;
247 for ( lock_type * pEnd = m_arrLocks + size(); pLock != pEnd; ++pLock )
254 lock_type * pLock = m_arrLocks;
255 for ( lock_type * pEnd = m_arrLocks + size(); pLock != pEnd; ++pLock )
259 /// Get lock at cell \p nCell.
261 Precondition: <tt>nCell < size()</tt>
263 lock_type& at( size_t nCell ) const
265 assert( nCell < size() );
266 return m_arrLocks[ nCell ];
269 /// Size of lock array.
276 }} // namespace cds::lock
281 /// Specialization \ref scoped_lock for lock::array
282 template <typename Lock, typename SelectPolicy, class Alloc>
283 class unique_lock< cds::lock::array< Lock, SelectPolicy, Alloc > >
286 typedef cds::lock::array< Lock, SelectPolicy, Alloc > lock_array_type; ///< Lock array type
289 lock_array_type& m_arrLocks;
290 size_t m_nLockGuarded;
292 static const size_t c_nLockAll = ~size_t( 0 );
295 /// Onws the lock array \p arrLocks and locks a cell determined by \p hint parameter
296 template <typename Q>
297 unique_lock( lock_array_type& arrLocks, Q const& hint )
298 : m_arrLocks( arrLocks )
299 , m_nLockGuarded( arrLocks.lock( hint ) )
302 /// Locks all from \p arrLocks array
303 unique_lock( lock_array_type& arrLocks )
304 : m_arrLocks( arrLocks )
305 , m_nLockGuarded( c_nLockAll )
310 unique_lock() = delete;
311 unique_lock( unique_lock const& ) = delete;
315 if ( m_nLockGuarded == c_nLockAll )
316 m_arrLocks.unlock_all();
318 m_arrLocks.unlock( m_nLockGuarded );
324 #endif // #ifndef CDSLIB_LOCK_ARRAY_H