3 #ifndef __CDS_LOCK_ARRAY_H
4 #define __CDS_LOCK_ARRAY_H
6 #include <mutex> //unique_lock
7 #include <cds/details/allocator.h>
8 #include <cds/algo/int_algo.h>
9 #include <boost/mpl/if.hpp>
11 namespace cds { namespace lock {
13 /// Trivial lock \ref array selection policy
14 struct trivial_select_policy
17 size_t operator()( size_t nWhat, size_t nCapacity ) const
19 assert( nWhat < 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 )
30 /// The lock \ref array cell selection policy "division by modulo"
31 struct mod_select_policy
33 /// Returns <tt> nWhat % nCapacity </tt>
34 size_t operator()( size_t nWhat, size_t nCapacity ) const
36 return nWhat % nCapacity;
39 /// Checks if \p nCapacity is acceptable by policy. For modulo policy, any positive \p nCapacity is accepted.
40 static bool is_capacity_accepted( size_t nCapacity )
46 /// The lock \ref array cell selection policy "division by modulo of power of 2"
48 This policy may be used if the size of lock array is equal to power of two.
50 struct pow2_select_policy
56 /// Ctor. \p nCapacity must be power of two.
57 pow2_select_policy( size_t nCapacity )
58 : m_nMask( nCapacity - 1 )
60 assert( is_capacity_accepted( nCapacity ));
64 pow2_select_policy( pow2_select_policy const& src )
65 : m_nMask( src.m_nMask )
69 pow2_select_policy( pow2_select_policy&& src )
70 : m_nMask( src.m_nMask )
73 /// Returns <tt>nWhat & (nPow2 - 1)</tt>
74 size_t operator()( size_t nWhat, size_t ) const
76 return nWhat & m_nMask;
79 /// Checks if \p nCapacity is acceptable by policy. \p nCapacity must be power of two
80 static bool is_capacity_accepted( size_t nCapacity )
82 return cds::beans::is_power2( nCapacity );
88 The lock array is useful for building fine-grained lock-based data structure
89 based on striping technique. Instead of locking access to data struct (a hash map, for example)
90 at whole, the striping locks only part of the map (a bucket). So, access to different buckets
94 - \p Lock - lock type, for example, \p boost::mutex, \p cds::lock::Spinlock
95 - \p SelectPolicy - array cell selection policy, the default is \ref mod_select_policy
96 Available policies: \ref trivial_select_policy, \ref pow2_select_policy, \ref mod_select_policy.
97 - \p Alloc - memory allocator for array
99 To determine array's cell the selection policy \p SelectPolicy functor is used. Two arguments
100 are passed to the policy:
101 \code size_t operator()( size_t nHint, size_t nCapacity ) const \endcode
102 - \p nHint - a hint to calculate cell index in the lock array. Usually, it is a hash value.
103 - \p nCapacity - the size of the lock array
104 The functor should return the index in the lock array.
106 Note that the type of \p nHint parameter can be any.
108 template <typename Lock
109 , typename SelectPolicy = mod_select_policy
110 , class Alloc = CDS_DEFAULT_ALLOCATOR
115 typedef ::cds::details::Allocator< Lock, Alloc > cxx_allocator;
118 typedef Lock lock_type ; ///< lock type
119 typedef SelectPolicy select_cell_policy ; ///< Cell selection policy functor
120 static size_t const c_nUnspecifiedCell = (size_t) -1 ; ///< failed \ref try_lock call result
123 lock_type * m_arrLocks ; ///< lock array
124 size_t const m_nCapacity ; ///< array capacity
126 select_cell_policy m_SelectCellPolicy ; ///< Cell selection policy
130 static lock_type * create_lock_array( size_t nCapacity )
132 return cxx_allocator().NewArray( nCapacity );
134 static void delete_lock_array( lock_type * pArr, size_t nCapacity )
137 cxx_allocator().Delete( pArr, nCapacity );
140 // Only for internal use!!!
142 : m_arrLocks( nullptr )
145 array( select_cell_policy const& policy )
146 : m_arrLocks( nullptr )
148 , m_SelectCellPolicy( policy )
153 /// Constructs array of locks
155 Allocates the array and initializes all locks as unlocked.
158 size_t nCapacity ///< [in] Array size
160 : m_arrLocks( nullptr )
161 , m_nCapacity( nCapacity )
163 m_arrLocks = create_lock_array( nCapacity );
166 /// Constructs array of lock and copy cell selection policy
168 Allocates the array and initializes all locks as unlocked.
171 size_t nCapacity, ///< [in] Array size
172 select_cell_policy const& policy ///< Cell selection policy (copy-constructible)
174 : m_arrLocks( nullptr )
175 , m_nCapacity( nCapacity )
176 , m_SelectCellPolicy( policy )
178 m_arrLocks = create_lock_array( m_nCapacity );
181 /// Constructs array of lock and move cell selection policy
183 Allocates the array and initializes all locks as unlocked.
186 size_t nCapacity, ///< [in] Array size
187 select_cell_policy&& policy ///< Cell selection policy (move-constructible)
189 : m_arrLocks( nullptr )
190 , m_nCapacity( nCapacity )
191 , m_SelectCellPolicy( std::forward<select_cell_policy>( policy ))
193 m_arrLocks = create_lock_array( m_nCapacity );
196 /// Destructs array of locks and frees used memory
199 delete_lock_array( m_arrLocks, m_nCapacity );
202 /// Locks a lock at cell \p hint
204 To define real array's cell which should be locked, \ref select_cell_policy is used.
205 The target cell is a result of <tt>select_cell_policy( hint, size() )</tt>.
207 Returns the index of locked lock.
209 template <typename Q>
210 size_t lock( Q const& hint )
212 size_t nCell = m_SelectCellPolicy( hint, size() );
213 assert( nCell < size() );
214 m_arrLocks[nCell].lock();
218 /// Try lock a lock at cell \p hint
220 To define real array's cell which should be locked, \ref select_cell_policy is used.
221 The target cell is a result of <tt>select_cell_policy( hint, size() )</tt>.
223 Returns the index of locked lock if success, \ref c_nUnspecifiedCell constant otherwise.
225 template <typename Q>
226 size_t try_lock( Q const& hint )
228 size_t nCell = m_SelectCellPolicy( hint, size() );
229 assert( nCell < size() );
230 if ( m_arrLocks[nCell].try_lock() )
232 return c_nUnspecifiedCell;
235 /// Unlock the lock specified by index \p nCell
236 void unlock( size_t nCell )
238 assert( nCell < size() );
239 m_arrLocks[nCell].unlock();
245 lock_type * pLock = m_arrLocks;
246 for ( lock_type * pEnd = m_arrLocks + size(); pLock != pEnd; ++pLock )
253 lock_type * pLock = m_arrLocks;
254 for ( lock_type * pEnd = m_arrLocks + size(); pLock != pEnd; ++pLock )
258 /// Get lock at cell \p nCell.
260 Precondition: <tt>nCell < size()</tt>
262 lock_type& at( size_t nCell ) const
264 assert( nCell < size() );
265 return m_arrLocks[ nCell ];
268 /// Size of lock array.
275 }} // namespace cds::lock
280 /// Specialization \ref scoped_lock for lock::array
281 template <typename Lock, typename SelectPolicy, class Alloc>
282 class unique_lock< cds::lock::array< Lock, SelectPolicy, Alloc > >
285 typedef cds::lock::array< Lock, SelectPolicy, Alloc > lock_array_type; ///< Lock array type
288 lock_array_type& m_arrLocks;
289 size_t m_nLockGuarded;
291 static const size_t c_nLockAll = ~size_t( 0 );
294 /// Onws the lock array \p arrLocks and locks a cell determined by \p hint parameter
295 template <typename Q>
296 unique_lock( lock_array_type& arrLocks, Q const& hint )
297 : m_arrLocks( arrLocks )
298 , m_nLockGuarded( arrLocks.lock( hint ) )
301 /// Locks all from \p arrLocks array
302 unique_lock( lock_array_type& arrLocks )
303 : m_arrLocks( arrLocks )
304 , m_nLockGuarded( c_nLockAll )
309 unique_lock() = delete;
310 unique_lock( unique_lock const& ) = delete;
314 if ( m_nLockGuarded == c_nLockAll )
315 m_arrLocks.unlock_all();
317 m_arrLocks.unlock( m_nLockGuarded );
323 #endif // #ifndef __CDS_LOCK_ARRAY_H