2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_SYNC_LOCK_ARRAY_H
32 #define CDSLIB_SYNC_LOCK_ARRAY_H
34 #include <mutex> //unique_lock
35 #include <cds/details/allocator.h>
36 #include <cds/algo/int_algo.h>
38 namespace cds { namespace sync {
40 /// Trivial lock \ref lock_array selection policy
41 struct trivial_select_policy
44 size_t operator()( size_t nWhat, size_t nCapacity ) const
46 assert( nWhat < nCapacity );
47 CDS_UNUSED( nCapacity );
51 /// Checks if \p nCapacity is acceptable by policy. For trivial policy, any \p nCapacity is accepted.
52 static bool is_capacity_accepted( size_t nCapacity )
54 CDS_UNUSED( nCapacity );
59 /// The lock \ref lock_array cell selection policy "division by modulo"
60 struct mod_select_policy
62 /// Returns <tt> nWhat % nCapacity </tt>
63 size_t operator()( size_t nWhat, size_t nCapacity ) const
65 return nWhat % nCapacity;
68 /// Checks if \p nCapacity is acceptable by policy. For modulo policy, any positive \p nCapacity is accepted.
69 static bool is_capacity_accepted( size_t nCapacity )
75 /// The lock \ref lock_array cell selection policy "division by modulo of power of 2"
77 This policy may be used if the size of lock array is equal to power of two.
79 struct pow2_select_policy
85 /// Ctor. \p nCapacity must be power of two.
86 pow2_select_policy( size_t nCapacity )
87 : m_nMask( nCapacity - 1 )
89 assert( is_capacity_accepted( nCapacity ));
93 pow2_select_policy( pow2_select_policy const& src )
94 : m_nMask( src.m_nMask )
98 pow2_select_policy( pow2_select_policy&& src )
99 : m_nMask( src.m_nMask )
102 /// Returns <tt>nWhat & (nPow2 - 1)</tt>
103 size_t operator()( size_t nWhat, size_t ) const
105 return nWhat & m_nMask;
108 /// Checks if \p nCapacity is acceptable by policy. \p nCapacity must be power of two
109 static bool is_capacity_accepted( size_t nCapacity )
111 return cds::beans::is_power2( nCapacity );
117 The lock array is useful for building fine-grained lock-based data structure
118 based on striping technique. Instead of locking access to data struct (a hash map, for example)
119 at whole, the striping locks only part of the map (a bucket). So, access to different buckets
123 - \p Lock - lock type, for example, \p std::mutex, \p cds::sync::spin_lock
124 - \p SelectPolicy - array cell selection policy, the default is \ref mod_select_policy
125 Available policies: \ref trivial_select_policy, \ref pow2_select_policy, \ref mod_select_policy.
126 - \p Alloc - memory allocator for array
128 To determine array's cell the selection policy \p SelectPolicy functor is used. Two arguments
129 are passed to the policy:
130 \code size_t operator()( size_t nHint, size_t nCapacity ) const \endcode
131 - \p nHint - a hint to calculate cell index in the lock array. Usually, it is a hash value.
132 - \p nCapacity - the size of the lock array
133 The functor should return the index in the lock array.
135 Note that the type of \p nHint parameter can be any.
137 template <typename Lock
138 , typename SelectPolicy = mod_select_policy
139 , class Alloc = CDS_DEFAULT_ALLOCATOR
144 typedef ::cds::details::Allocator< Lock, Alloc > cxx_allocator;
147 typedef Lock lock_type ; ///< lock type
148 typedef SelectPolicy select_cell_policy ; ///< Cell selection policy functor
149 static size_t const c_nUnspecifiedCell = (size_t) -1 ; ///< failed \ref try_lock call result
152 lock_type * m_arrLocks ; ///< lock array
153 size_t const m_nCapacity ; ///< array capacity
155 select_cell_policy m_SelectCellPolicy ; ///< Cell selection policy
159 static lock_type * create_lock_array( size_t nCapacity )
161 return cxx_allocator().NewArray( nCapacity );
163 static void delete_lock_array( lock_type * pArr, size_t nCapacity )
166 cxx_allocator().Delete( pArr, nCapacity );
169 // Only for internal use!!!
171 : m_arrLocks( nullptr )
175 lock_array( select_cell_policy const& policy )
176 : m_arrLocks( nullptr )
178 , m_SelectCellPolicy( policy )
183 /// Constructs array of locks
185 Allocates the array and initializes all locks as unlocked.
188 size_t nCapacity ///< [in] Array size
190 : m_arrLocks( nullptr )
191 , m_nCapacity( nCapacity )
193 m_arrLocks = create_lock_array( nCapacity );
196 /// Constructs array of lock and copy cell selection policy
198 Allocates the array and initializes all locks as unlocked.
201 size_t nCapacity, ///< [in] Array size
202 select_cell_policy const& policy ///< Cell selection policy (copy-constructible)
204 : m_arrLocks( nullptr )
205 , m_nCapacity( nCapacity )
206 , m_SelectCellPolicy( policy )
208 m_arrLocks = create_lock_array( m_nCapacity );
211 /// Constructs array of lock and move cell selection policy
213 Allocates the array and initializes all locks as unlocked.
216 size_t nCapacity, ///< [in] Array size
217 select_cell_policy&& policy ///< Cell selection policy (move-constructible)
219 : m_arrLocks( nullptr )
220 , m_nCapacity( nCapacity )
221 , m_SelectCellPolicy( std::forward<select_cell_policy>( policy ))
223 m_arrLocks = create_lock_array( m_nCapacity );
226 /// Destructs array of locks and frees used memory
229 delete_lock_array( m_arrLocks, m_nCapacity );
232 /// Locks a lock at cell \p hint
234 To define real array's cell which should be locked, \ref select_cell_policy is used.
235 The target cell is a result of <tt>select_cell_policy( hint, size() )</tt>.
237 Returns the index of locked lock.
239 template <typename Q>
240 size_t lock( Q const& hint )
242 size_t nCell = m_SelectCellPolicy( hint, size() );
243 assert( nCell < size() );
244 m_arrLocks[nCell].lock();
248 /// Try lock a lock at cell \p hint
250 To define real array's cell which should be locked, \ref select_cell_policy is used.
251 The target cell is a result of <tt>select_cell_policy( hint, size() )</tt>.
253 Returns the index of locked lock if success, \ref c_nUnspecifiedCell constant otherwise.
255 template <typename Q>
256 size_t try_lock( Q const& hint )
258 size_t nCell = m_SelectCellPolicy( hint, size() );
259 assert( nCell < size() );
260 if ( m_arrLocks[nCell].try_lock() )
262 return c_nUnspecifiedCell;
265 /// Unlock the lock specified by index \p nCell
266 void unlock( size_t nCell )
268 assert( nCell < size() );
269 m_arrLocks[nCell].unlock();
275 lock_type * pLock = m_arrLocks;
276 for ( lock_type * pEnd = m_arrLocks + size(); pLock != pEnd; ++pLock )
283 lock_type * pLock = m_arrLocks;
284 for ( lock_type * pEnd = m_arrLocks + size(); pLock != pEnd; ++pLock )
288 /// Get lock at cell \p nCell.
290 Precondition: <tt>nCell < size()</tt>
292 lock_type& at( size_t nCell ) const
294 assert( nCell < size() );
295 return m_arrLocks[ nCell ];
298 /// Size of lock array.
305 }} // namespace cds::sync
310 /// Specialization \p std::unique_lock for \p sync::lock_array
311 template <typename Lock, typename SelectPolicy, class Alloc>
312 class unique_lock< cds::sync::lock_array< Lock, SelectPolicy, Alloc > >
315 typedef cds::sync::lock_array< Lock, SelectPolicy, Alloc > lock_array_type; ///< Lock array type
318 lock_array_type& m_arrLocks;
319 size_t m_nLockGuarded;
321 static const size_t c_nLockAll = ~size_t( 0 );
324 /// Onws the lock array \p arrLocks and locks a cell determined by \p hint parameter
325 template <typename Q>
326 unique_lock( lock_array_type& arrLocks, Q const& hint )
327 : m_arrLocks( arrLocks )
328 , m_nLockGuarded( arrLocks.lock( hint ) )
331 /// Locks all from \p arrLocks array
332 unique_lock( lock_array_type& arrLocks )
333 : m_arrLocks( arrLocks )
334 , m_nLockGuarded( c_nLockAll )
339 unique_lock() = delete;
340 unique_lock( unique_lock const& ) = delete;
344 if ( m_nLockGuarded == c_nLockAll )
345 m_arrLocks.unlock_all();
347 m_arrLocks.unlock( m_nLockGuarded );
353 #endif // #ifndef CDSLIB_SYNC_LOCK_ARRAY_H