--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
+
+ Source code repo: http://github.com/khizmax/libcds/
+ Download: http://sourceforge.net/projects/libcds/files/
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions are met:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef CDSLIB_SYNC_LOCK_ARRAY_H
+#define CDSLIB_SYNC_LOCK_ARRAY_H
+
+#include <mutex> //unique_lock
+#include <cds/details/allocator.h>
+#include <cds/algo/int_algo.h>
+
+namespace cds { namespace sync {
+
+ /// Trivial lock \ref lock_array selection policy
+ struct trivial_select_policy
+ {
+ /// Returns \p nWhat
+ size_t operator()( size_t nWhat, size_t nCapacity ) const
+ {
+ assert( nWhat < nCapacity );
+ CDS_UNUSED( nCapacity );
+ return nWhat;
+ }
+
+ /// Checks if \p nCapacity is acceptable by policy. For trivial policy, any \p nCapacity is accepted.
+ static bool is_capacity_accepted( size_t nCapacity )
+ {
+ CDS_UNUSED( nCapacity );
+ return true;
+ }
+ };
+
+ /// The lock \ref lock_array cell selection policy "division by modulo"
+ struct mod_select_policy
+ {
+ /// Returns <tt> nWhat % nCapacity </tt>
+ size_t operator()( size_t nWhat, size_t nCapacity ) const
+ {
+ return nWhat % nCapacity;
+ }
+
+ /// Checks if \p nCapacity is acceptable by policy. For modulo policy, any positive \p nCapacity is accepted.
+ static bool is_capacity_accepted( size_t nCapacity )
+ {
+ return nCapacity > 0;
+ }
+ };
+
+ /// The lock \ref lock_array cell selection policy "division by modulo of power of 2"
+ /**
+ This policy may be used if the size of lock array is equal to power of two.
+ */
+ struct pow2_select_policy
+ {
+ //@cond
+ const size_t m_nMask;
+ //@endcond
+
+ /// Ctor. \p nCapacity must be power of two.
+ pow2_select_policy( size_t nCapacity )
+ : m_nMask( nCapacity - 1 )
+ {
+ assert( is_capacity_accepted( nCapacity ));
+ }
+
+ /// Copy constructor
+ pow2_select_policy( pow2_select_policy const& src )
+ : m_nMask( src.m_nMask )
+ {}
+
+ /// Move constructor
+ pow2_select_policy( pow2_select_policy&& src )
+ : m_nMask( src.m_nMask )
+ {}
+
+ /// Returns <tt>nWhat & (nPow2 - 1)</tt>
+ size_t operator()( size_t nWhat, size_t ) const
+ {
+ return nWhat & m_nMask;
+ }
+
+ /// Checks if \p nCapacity is acceptable by policy. \p nCapacity must be power of two
+ static bool is_capacity_accepted( size_t nCapacity )
+ {
+ return cds::beans::is_power2( nCapacity );
+ }
+ };
+
+ /// Array of locks
+ /**
+ The lock array is useful for building fine-grained lock-based data structure
+ based on striping technique. Instead of locking access to data struct (a hash map, for example)
+ at whole, the striping locks only part of the map (a bucket). So, access to different buckets
+ can be simultaneous.
+
+ Template arguments:
+ - \p Lock - lock type, for example, \p std::mutex, \p cds::sync::spin_lock
+ - \p SelectPolicy - array cell selection policy, the default is \ref mod_select_policy
+ Available policies: \ref trivial_select_policy, \ref pow2_select_policy, \ref mod_select_policy.
+ - \p Alloc - memory allocator for array
+
+ To determine array's cell the selection policy \p SelectPolicy functor is used. Two arguments
+ are passed to the policy:
+ \code size_t operator()( size_t nHint, size_t nCapacity ) const \endcode
+ - \p nHint - a hint to calculate cell index in the lock array. Usually, it is a hash value.
+ - \p nCapacity - the size of the lock array
+ The functor should return the index in the lock array.
+
+ Note that the type of \p nHint parameter can be any.
+ */
+ template <typename Lock
+ , typename SelectPolicy = mod_select_policy
+ , class Alloc = CDS_DEFAULT_ALLOCATOR
+ >
+ class lock_array
+ {
+ //@cond
+ typedef ::cds::details::Allocator< Lock, Alloc > cxx_allocator;
+ //@endcond
+ public:
+ typedef Lock lock_type ; ///< lock type
+ typedef SelectPolicy select_cell_policy ; ///< Cell selection policy functor
+ static size_t const c_nUnspecifiedCell = (size_t) -1 ; ///< failed \ref try_lock call result
+
+ protected:
+ lock_type * m_arrLocks ; ///< lock array
+ size_t const m_nCapacity ; ///< array capacity
+
+ select_cell_policy m_SelectCellPolicy ; ///< Cell selection policy
+
+ protected:
+ //@cond
+ static lock_type * create_lock_array( size_t nCapacity )
+ {
+ return cxx_allocator().NewArray( nCapacity );
+ }
+ static void delete_lock_array( lock_type * pArr, size_t nCapacity )
+ {
+ if ( pArr )
+ cxx_allocator().Delete( pArr, nCapacity );
+ }
+
+ // Only for internal use!!!
+ lock_array()
+ : m_arrLocks( nullptr )
+ , m_nCapacity(0)
+ {}
+
+ lock_array( select_cell_policy const& policy )
+ : m_arrLocks( nullptr )
+ , m_nCapacity(0)
+ , m_SelectCellPolicy( policy )
+ {}
+ //@endcond
+
+ public:
+ /// Constructs array of locks
+ /**
+ Allocates the array and initializes all locks as unlocked.
+ */
+ lock_array(
+ size_t nCapacity ///< [in] Array size
+ )
+ : m_arrLocks( nullptr )
+ , m_nCapacity( nCapacity )
+ {
+ m_arrLocks = create_lock_array( nCapacity );
+ }
+
+ /// Constructs array of lock and copy cell selection policy
+ /**
+ Allocates the array and initializes all locks as unlocked.
+ */
+ lock_array(
+ size_t nCapacity, ///< [in] Array size
+ select_cell_policy const& policy ///< Cell selection policy (copy-constructible)
+ )
+ : m_arrLocks( nullptr )
+ , m_nCapacity( nCapacity )
+ , m_SelectCellPolicy( policy )
+ {
+ m_arrLocks = create_lock_array( m_nCapacity );
+ }
+
+ /// Constructs array of lock and move cell selection policy
+ /**
+ Allocates the array and initializes all locks as unlocked.
+ */
+ lock_array(
+ size_t nCapacity, ///< [in] Array size
+ select_cell_policy&& policy ///< Cell selection policy (move-constructible)
+ )
+ : m_arrLocks( nullptr )
+ , m_nCapacity( nCapacity )
+ , m_SelectCellPolicy( std::forward<select_cell_policy>( policy ))
+ {
+ m_arrLocks = create_lock_array( m_nCapacity );
+ }
+
+ /// Destructs array of locks and frees used memory
+ ~lock_array()
+ {
+ delete_lock_array( m_arrLocks, m_nCapacity );
+ }
+
+ /// Locks a lock at cell \p hint
+ /**
+ To define real array's cell which should be locked, \ref select_cell_policy is used.
+ The target cell is a result of <tt>select_cell_policy( hint, size())</tt>.
+
+ Returns the index of locked lock.
+ */
+ template <typename Q>
+ size_t lock( Q const& hint )
+ {
+ size_t nCell = m_SelectCellPolicy( hint, size());
+ assert( nCell < size());
+ m_arrLocks[nCell].lock();
+ return nCell;
+ }
+
+ /// Try lock a lock at cell \p hint
+ /**
+ To define real array's cell which should be locked, \ref select_cell_policy is used.
+ The target cell is a result of <tt>select_cell_policy( hint, size())</tt>.
+
+ Returns the index of locked lock if success, \ref c_nUnspecifiedCell constant otherwise.
+ */
+ template <typename Q>
+ size_t try_lock( Q const& hint )
+ {
+ size_t nCell = m_SelectCellPolicy( hint, size());
+ assert( nCell < size());
+ if ( m_arrLocks[nCell].try_lock())
+ return nCell;
+ return c_nUnspecifiedCell;
+ }
+
+ /// Unlock the lock specified by index \p nCell
+ void unlock( size_t nCell )
+ {
+ assert( nCell < size());
+ m_arrLocks[nCell].unlock();
+ }
+
+ /// Lock all
+ void lock_all()
+ {
+ lock_type * pLock = m_arrLocks;
+ for ( lock_type * pEnd = m_arrLocks + size(); pLock != pEnd; ++pLock )
+ pLock->lock();
+ }
+
+ /// Unlock all
+ void unlock_all()
+ {
+ lock_type * pLock = m_arrLocks;
+ for ( lock_type * pEnd = m_arrLocks + size(); pLock != pEnd; ++pLock )
+ pLock->unlock();
+ }
+
+ /// Get lock at cell \p nCell.
+ /**
+ Precondition: <tt>nCell < size()</tt>
+ */
+ lock_type& at( size_t nCell ) const
+ {
+ assert( nCell < size());
+ return m_arrLocks[ nCell ];
+ }
+
+ /// Size of lock array.
+ size_t size() const
+ {
+ return m_nCapacity;
+ }
+ };
+
+}} // namespace cds::sync
+
+//@cond
+namespace std {
+
+ /// Specialization \p std::unique_lock for \p sync::lock_array
+ template <typename Lock, typename SelectPolicy, class Alloc>
+ class unique_lock< cds::sync::lock_array< Lock, SelectPolicy, Alloc > >
+ {
+ public:
+ typedef cds::sync::lock_array< Lock, SelectPolicy, Alloc > lock_array_type; ///< Lock array type
+
+ private:
+ lock_array_type& m_arrLocks;
+ size_t m_nLockGuarded;
+
+ static const size_t c_nLockAll = ~size_t( 0 );
+
+ public:
+ /// Onws the lock array \p arrLocks and locks a cell determined by \p hint parameter
+ template <typename Q>
+ unique_lock( lock_array_type& arrLocks, Q const& hint )
+ : m_arrLocks( arrLocks )
+ , m_nLockGuarded( arrLocks.lock( hint ))
+ {}
+
+ /// Locks all from \p arrLocks array
+ unique_lock( lock_array_type& arrLocks )
+ : m_arrLocks( arrLocks )
+ , m_nLockGuarded( c_nLockAll )
+ {
+ arrLocks.lock_all();
+ }
+
+ unique_lock() = delete;
+ unique_lock( unique_lock const& ) = delete;
+
+ ~unique_lock()
+ {
+ if ( m_nLockGuarded == c_nLockAll )
+ m_arrLocks.unlock_all();
+ else
+ m_arrLocks.unlock( m_nLockGuarded );
+ }
+ };
+} // namespace std
+//@endcond
+
+#endif // #ifndef CDSLIB_SYNC_LOCK_ARRAY_H
projects / c11concurrency-benchmarks.git / blobdiff