3 #ifndef __CDS_LOCK_ARRAY_H
4 #define __CDS_LOCK_ARRAY_H
6 #include <cds/details/allocator.h>
7 #include <cds/lock/scoped_lock.h>
8 #include <cds/algo/int_algo.h>
10 #include <boost/mpl/if.hpp>
12 namespace cds { namespace lock {
14 /// Trivial lock \ref array selection policy
15 struct trivial_select_policy
18 size_t operator()( size_t nWhat, size_t nCapacity ) const
20 assert( nWhat < nCapacity );
24 /// Checks if \p nCapacity is acceptable by policy. For trivial policy, any \p nCapacity is accepted.
25 static bool is_capacity_accepted( size_t 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 )
69 # ifdef CDS_RVALUE_SUPPORT
71 pow2_select_policy( pow2_select_policy&& src )
72 : m_nMask( src.m_nMask )
76 /// Returns <tt>nWhat & (nPow2 - 1)</tt>
77 size_t operator()( size_t nWhat, size_t ) const
79 return nWhat & m_nMask;
82 /// Checks if \p nCapacity is acceptable by policy. \p nCapacity must be power of two
83 static bool is_capacity_accepted( size_t nCapacity )
85 return cds::beans::is_power2( nCapacity );
91 The lock array is useful for building fine-grained lock-based data structure
92 based on striping technique. Instead of locking access to data struct (a hash map, for example)
93 at whole, the striping locks only part of the map (a bucket). So, access to different buckets
97 - \p Lock - lock type, for example, \p boost::mutex, \p cds::lock::Spinlock
98 - \p SelectPolicy - array cell selection policy, the default is \ref mod_select_policy
99 Available policies: \ref trivial_select_policy, \ref pow2_select_policy, \ref mod_select_policy.
100 - \p Alloc - memory allocator for array
102 To determine array's cell the selection policy \p SelectPolicy functor is used. Two arguments
103 are passed to the policy:
104 \code size_t operator()( size_t nHint, size_t nCapacity ) const \endcode
105 - \p nHint - a hint to calculate cell index in the lock array. Usually, it is a hash value.
106 - \p nCapacity - the size of the lock array
107 The functor should return the index in the lock array.
109 Note that the type of \p nHint parameter can be any.
111 template <typename Lock
112 , typename SelectPolicy = mod_select_policy
113 , class Alloc = CDS_DEFAULT_ALLOCATOR
118 typedef ::cds::details::Allocator< Lock, Alloc > cxx_allocator;
121 typedef Lock lock_type ; ///< lock type
122 typedef SelectPolicy select_cell_policy ; ///< Cell selection policy functor
123 static size_t const c_nUnspecifiedCell = (size_t) -1 ; ///< failed \ref try_lock call result
126 lock_type * m_arrLocks ; ///< lock array
127 size_t const m_nCapacity ; ///< array capacity
129 select_cell_policy m_SelectCellPolicy ; ///< Cell selection policy
133 static lock_type * create_lock_array( size_t nCapacity )
135 return cxx_allocator().NewArray( nCapacity );
137 static void delete_lock_array( lock_type * pArr, size_t nCapacity )
140 cxx_allocator().Delete( pArr, nCapacity );
143 // Only for internal use!!!
145 : m_arrLocks( nullptr )
148 array( select_cell_policy const& policy )
149 : m_arrLocks( nullptr )
151 , m_SelectCellPolicy( policy )
156 /// Constructs array of locks
158 Allocates the array and initializes all locks as unlocked.
161 size_t nCapacity ///< [in] Array size
163 : m_arrLocks( nullptr )
164 , m_nCapacity( nCapacity )
166 m_arrLocks = create_lock_array( nCapacity );
169 /// Constructs array of lock and copy cell selection policy
171 Allocates the array and initializes all locks as unlocked.
174 size_t nCapacity, ///< [in] Array size
175 select_cell_policy const& policy ///< Cell selection policy (copy-constructible)
177 : m_arrLocks( nullptr )
178 , m_nCapacity( nCapacity )
179 , m_SelectCellPolicy( policy )
181 m_arrLocks = create_lock_array( m_nCapacity );
184 # ifdef CDS_RVALUE_SUPPORT
185 /// Constructs array of lock and move cell selection policy
187 Allocates the array and initializes all locks as unlocked.
190 size_t nCapacity, ///< [in] Array size
191 select_cell_policy&& policy ///< Cell selection policy (move-constructible)
193 : m_arrLocks( nullptr )
194 , m_nCapacity( nCapacity )
195 , m_SelectCellPolicy( std::forward<select_cell_policy>( policy ))
197 m_arrLocks = create_lock_array( m_nCapacity );
201 /// Destructs array of locks and frees used memory
204 delete_lock_array( m_arrLocks, m_nCapacity );
207 /// Locks a lock at cell \p hint
209 To define real array's cell which should be locked, \ref select_cell_policy is used.
210 The target cell is a result of <tt>select_cell_policy( hint, size() )</tt>.
212 Returns the index of locked lock.
214 template <typename Q>
215 size_t lock( Q const& hint )
217 size_t nCell = m_SelectCellPolicy( hint, size() );
218 assert( nCell < size() );
219 lock_type& l = m_arrLocks[ nCell ];
224 /// Try lock a lock at cell \p hint
226 To define real array's cell which should be locked, \ref select_cell_policy is used.
227 The target cell is a result of <tt>select_cell_policy( hint, size() )</tt>.
229 Returns the index of locked lock if success, \ref c_nUnspecifiedCell constant otherwise.
231 template <typename Q>
232 size_t try_lock( Q const& hint )
234 size_t nCell = m_SelectCellPolicy( hint, size() );
235 assert( nCell < size() );
236 lock_type& l = m_arrLocks[ nCell ];
239 return c_nUnspecifiedCell;
242 /// Unlock the lock specified by index \p nCell
243 void unlock( size_t nCell )
245 assert( nCell < size() );
246 m_arrLocks[nCell].unlock();
252 lock_type * pLock = m_arrLocks;
253 for ( size_t i = 0; i < size(); ++i, ++pLock )
260 lock_type * pLock = m_arrLocks;
261 for ( size_t i = 0; i < size(); ++i, ++pLock )
265 /// Get lock at cell \p nCell.
267 Precondition: <tt>nCell < size()</tt>
269 lock_type& at( size_t nCell ) const
271 assert( nCell < size() );
272 return m_arrLocks[ nCell ];
275 /// Size of lock array.
282 /// Specialization \ref scoped_lock for lock::array
283 template <typename Lock, typename SelectPolicy, class Alloc>
284 class scoped_lock< cds::lock::array< Lock, SelectPolicy, Alloc > >: public cds::details::noncopyable
287 typedef cds::lock::array< Lock, SelectPolicy, Alloc > lock_array_type ; ///< Lock array type
291 lock_array_type& m_arrLocks;
292 size_t m_nLockGuarded;
294 static const size_t c_nLockAll = ~size_t(0);
298 /// Onws the lock array \p arrLocks and locks a cell determined by \p hint parameter
299 template <typename Q>
300 scoped_lock( lock_array_type& arrLocks, Q const& hint )
301 : m_arrLocks( arrLocks )
302 , m_nLockGuarded( arrLocks.lock( hint ))
305 /// Locks all from \p arrLocks array
306 scoped_lock( lock_array_type& arrLocks )
307 : m_arrLocks( arrLocks )
308 , m_nLockGuarded( c_nLockAll )
315 if ( m_nLockGuarded == c_nLockAll )
316 m_arrLocks.unlock_all();
318 m_arrLocks.unlock( m_nLockGuarded );
322 }} // namespace cds::lock
324 #endif // #ifndef __CDS_LOCK_ARRAY_H