3 #ifndef CDSLIB_SYNC_LOCK_ARRAY_H
4 #define CDSLIB_SYNC_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 sync {
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 )
147 lock_array( select_cell_policy const& policy )
148 : m_arrLocks( nullptr )
150 , m_SelectCellPolicy( policy )
155 /// Constructs array of locks
157 Allocates the array and initializes all locks as unlocked.
160 size_t nCapacity ///< [in] Array size
162 : m_arrLocks( nullptr )
163 , m_nCapacity( nCapacity )
165 m_arrLocks = create_lock_array( nCapacity );
168 /// Constructs array of lock and copy cell selection policy
170 Allocates the array and initializes all locks as unlocked.
173 size_t nCapacity, ///< [in] Array size
174 select_cell_policy const& policy ///< Cell selection policy (copy-constructible)
176 : m_arrLocks( nullptr )
177 , m_nCapacity( nCapacity )
178 , m_SelectCellPolicy( policy )
180 m_arrLocks = create_lock_array( m_nCapacity );
183 /// Constructs array of lock and move cell selection policy
185 Allocates the array and initializes all locks as unlocked.
188 size_t nCapacity, ///< [in] Array size
189 select_cell_policy&& policy ///< Cell selection policy (move-constructible)
191 : m_arrLocks( nullptr )
192 , m_nCapacity( nCapacity )
193 , m_SelectCellPolicy( std::forward<select_cell_policy>( policy ))
195 m_arrLocks = create_lock_array( m_nCapacity );
198 /// Destructs array of locks and frees used memory
201 delete_lock_array( m_arrLocks, m_nCapacity );
204 /// Locks a lock at cell \p hint
206 To define real array's cell which should be locked, \ref select_cell_policy is used.
207 The target cell is a result of <tt>select_cell_policy( hint, size() )</tt>.
209 Returns the index of locked lock.
211 template <typename Q>
212 size_t lock( Q const& hint )
214 size_t nCell = m_SelectCellPolicy( hint, size() );
215 assert( nCell < size() );
216 m_arrLocks[nCell].lock();
220 /// Try lock a lock at cell \p hint
222 To define real array's cell which should be locked, \ref select_cell_policy is used.
223 The target cell is a result of <tt>select_cell_policy( hint, size() )</tt>.
225 Returns the index of locked lock if success, \ref c_nUnspecifiedCell constant otherwise.
227 template <typename Q>
228 size_t try_lock( Q const& hint )
230 size_t nCell = m_SelectCellPolicy( hint, size() );
231 assert( nCell < size() );
232 if ( m_arrLocks[nCell].try_lock() )
234 return c_nUnspecifiedCell;
237 /// Unlock the lock specified by index \p nCell
238 void unlock( size_t nCell )
240 assert( nCell < size() );
241 m_arrLocks[nCell].unlock();
247 lock_type * pLock = m_arrLocks;
248 for ( lock_type * pEnd = m_arrLocks + size(); pLock != pEnd; ++pLock )
255 lock_type * pLock = m_arrLocks;
256 for ( lock_type * pEnd = m_arrLocks + size(); pLock != pEnd; ++pLock )
260 /// Get lock at cell \p nCell.
262 Precondition: <tt>nCell < size()</tt>
264 lock_type& at( size_t nCell ) const
266 assert( nCell < size() );
267 return m_arrLocks[ nCell ];
270 /// Size of lock array.
277 }} // namespace cds::sync
282 /// Specialization \p std::unique_lock for \p sync::lock_array
283 template <typename Lock, typename SelectPolicy, class Alloc>
284 class unique_lock< cds::sync::lock_array< Lock, SelectPolicy, Alloc > >
287 typedef cds::sync::lock_array< Lock, SelectPolicy, Alloc > lock_array_type; ///< Lock array type
290 lock_array_type& m_arrLocks;
291 size_t m_nLockGuarded;
293 static const size_t c_nLockAll = ~size_t( 0 );
296 /// Onws the lock array \p arrLocks and locks a cell determined by \p hint parameter
297 template <typename Q>
298 unique_lock( lock_array_type& arrLocks, Q const& hint )
299 : m_arrLocks( arrLocks )
300 , m_nLockGuarded( arrLocks.lock( hint ) )
303 /// Locks all from \p arrLocks array
304 unique_lock( lock_array_type& arrLocks )
305 : m_arrLocks( arrLocks )
306 , m_nLockGuarded( c_nLockAll )
311 unique_lock() = delete;
312 unique_lock( unique_lock const& ) = delete;
316 if ( m_nLockGuarded == c_nLockAll )
317 m_arrLocks.unlock_all();
319 m_arrLocks.unlock( m_nLockGuarded );
325 #endif // #ifndef CDSLIB_SYNC_LOCK_ARRAY_H