cds/sync/lock_array.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  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.
  18
  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.
  29 */
  30
  31 #ifndef CDSLIB_SYNC_LOCK_ARRAY_H
  32 #define CDSLIB_SYNC_LOCK_ARRAY_H
  33
  34 #include <mutex>    //unique_lock
  35 #include <cds/details/allocator.h>
  36 #include <cds/algo/int_algo.h>
  37
  38 namespace cds { namespace sync {
  39
  40     /// Trivial lock \ref lock_array selection policy
  41     struct trivial_select_policy
  42     {
  43         /// Returns \p nWhat
  44         size_t operator()( size_t nWhat, size_t nCapacity ) const
  45         {
  46             assert( nWhat < nCapacity );
  47             CDS_UNUSED( nCapacity );
  48             return nWhat;
  49         }
  50
  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 )
  53         {
  54             CDS_UNUSED( nCapacity );
  55             return true;
  56         }
  57     };
  58
  59     /// The lock \ref lock_array cell selection policy "division by modulo"
  60     struct mod_select_policy
  61     {
  62         /// Returns <tt> nWhat % nCapacity </tt>
  63         size_t operator()( size_t nWhat, size_t nCapacity ) const
  64         {
  65             return nWhat % nCapacity;
  66         }
  67
  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 )
  70         {
  71             return nCapacity > 0;
  72         }
  73     };
  74
  75     /// The lock \ref lock_array cell selection policy "division by modulo of power of 2"
  76     /**
  77         This policy may be used if the size of lock array is equal to power of two.
  78     */
  79     struct pow2_select_policy
  80     {
  81         //@cond
  82         const size_t    m_nMask;
  83         //@endcond
  84
  85         /// Ctor. \p nCapacity must be power of two.
  86         pow2_select_policy( size_t nCapacity )
  87             : m_nMask( nCapacity - 1 )
  88         {
  89             assert( is_capacity_accepted( nCapacity ));
  90         }
  91
  92         /// Copy constructor
  93         pow2_select_policy( pow2_select_policy const& src )
  94             : m_nMask( src.m_nMask )
  95         {}
  96
  97         /// Move constructor
  98         pow2_select_policy( pow2_select_policy&& src )
  99             : m_nMask( src.m_nMask )
 100         {}
 101
 102         /// Returns <tt>nWhat & (nPow2 - 1)</tt>
 103         size_t operator()( size_t nWhat, size_t ) const
 104         {
 105             return nWhat & m_nMask;
 106         }
 107
 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 )
 110         {
 111             return cds::beans::is_power2( nCapacity );
 112         }
 113     };
 114
 115     /// Array of locks
 116     /**
 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
 120         can be simultaneous.
 121
 122         Template arguments:
 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
 127
 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.
 134
 135         Note that the type of \p nHint parameter can be any.
 136     */
 137     template <typename Lock
 138         , typename SelectPolicy = mod_select_policy
 139         , class Alloc = CDS_DEFAULT_ALLOCATOR
 140     >
 141     class lock_array
 142     {
 143         //@cond
 144         typedef ::cds::details::Allocator< Lock, Alloc > cxx_allocator;
 145         //@endcond
 146     public:
 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
 150
 151     protected:
 152         lock_type *         m_arrLocks  ;   ///< lock array
 153         size_t const        m_nCapacity ;   ///< array capacity
 154
 155         select_cell_policy  m_SelectCellPolicy  ;   ///< Cell selection policy
 156
 157     protected:
 158         //@cond
 159         static lock_type * create_lock_array( size_t nCapacity )
 160         {
 161             return cxx_allocator().NewArray( nCapacity );
 162         }
 163         static void delete_lock_array( lock_type * pArr, size_t nCapacity )
 164         {
 165             if ( pArr )
 166                 cxx_allocator().Delete( pArr, nCapacity );
 167         }
 168
 169         // Only for internal use!!!
 170         lock_array()
 171             : m_arrLocks( nullptr )
 172             , m_nCapacity(0)
 173         {}
 174
 175         lock_array( select_cell_policy const& policy )
 176             : m_arrLocks( nullptr )
 177             , m_nCapacity(0)
 178             , m_SelectCellPolicy( policy )
 179         {}
 180         //@endcond
 181
 182     public:
 183         /// Constructs array of locks
 184         /**
 185             Allocates the array and initializes all locks as unlocked.
 186         */
 187         lock_array(
 188             size_t nCapacity        ///< [in] Array size
 189         )
 190         : m_arrLocks( nullptr )
 191         , m_nCapacity( nCapacity )
 192         {
 193             m_arrLocks = create_lock_array( nCapacity );
 194         }
 195
 196         /// Constructs array of lock and copy cell selection policy
 197         /**
 198             Allocates the array and initializes all locks as unlocked.
 199         */
 200         lock_array(
 201             size_t nCapacity,       ///< [in] Array size
 202             select_cell_policy const& policy    ///< Cell selection policy (copy-constructible)
 203         )
 204         : m_arrLocks( nullptr )
 205         , m_nCapacity( nCapacity )
 206         , m_SelectCellPolicy( policy )
 207         {
 208             m_arrLocks = create_lock_array( m_nCapacity );
 209         }
 210
 211         /// Constructs array of lock and move cell selection policy
 212         /**
 213             Allocates the array and initializes all locks as unlocked.
 214         */
 215         lock_array(
 216             size_t nCapacity,       ///< [in] Array size
 217             select_cell_policy&& policy    ///< Cell selection policy (move-constructible)
 218         )
 219         : m_arrLocks( nullptr )
 220         , m_nCapacity( nCapacity )
 221         , m_SelectCellPolicy( std::forward<select_cell_policy>( policy ))
 222         {
 223             m_arrLocks = create_lock_array( m_nCapacity );
 224         }
 225
 226         /// Destructs array of locks and frees used memory
 227         ~lock_array()
 228         {
 229             delete_lock_array( m_arrLocks, m_nCapacity );
 230         }
 231
 232         /// Locks a lock at cell \p hint
 233         /**
 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>.
 236
 237             Returns the index of locked lock.
 238         */
 239         template <typename Q>
 240         size_t lock( Q const& hint )
 241         {
 242             size_t nCell = m_SelectCellPolicy( hint, size() );
 243             assert( nCell < size() );
 244             m_arrLocks[nCell].lock();
 245             return nCell;
 246         }
 247
 248         /// Try lock a lock at cell \p hint
 249         /**
 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>.
 252
 253             Returns the index of locked lock if success, \ref c_nUnspecifiedCell constant otherwise.
 254         */
 255         template <typename Q>
 256         size_t try_lock( Q const& hint )
 257         {
 258             size_t nCell = m_SelectCellPolicy( hint, size() );
 259             assert( nCell < size() );
 260             if ( m_arrLocks[nCell].try_lock() )
 261                 return nCell;
 262             return c_nUnspecifiedCell;
 263         }
 264
 265         /// Unlock the lock specified by index \p nCell
 266         void unlock( size_t nCell )
 267         {
 268             assert( nCell < size() );
 269             m_arrLocks[nCell].unlock();
 270         }
 271
 272         /// Lock all
 273         void lock_all()
 274         {
 275             lock_type * pLock = m_arrLocks;
 276             for ( lock_type * pEnd = m_arrLocks + size(); pLock != pEnd; ++pLock )
 277                 pLock->lock();
 278         }
 279
 280         /// Unlock all
 281         void unlock_all()
 282         {
 283             lock_type * pLock = m_arrLocks;
 284             for ( lock_type * pEnd = m_arrLocks + size(); pLock != pEnd; ++pLock )
 285                 pLock->unlock();
 286         }
 287
 288         /// Get lock at cell \p nCell.
 289         /**
 290             Precondition: <tt>nCell < size()</tt>
 291         */
 292         lock_type& at( size_t nCell ) const
 293         {
 294             assert( nCell < size() );
 295             return m_arrLocks[ nCell ];
 296         }
 297
 298         /// Size of lock array.
 299         size_t size() const
 300         {
 301             return m_nCapacity;
 302         }
 303     };
 304
 305 }} // namespace cds::sync
 306
 307 //@cond
 308 namespace std {
 309
 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 > >
 313     {
 314     public:
 315         typedef cds::sync::lock_array< Lock, SelectPolicy, Alloc >   lock_array_type;   ///< Lock array type
 316
 317     private:
 318         lock_array_type&    m_arrLocks;
 319         size_t              m_nLockGuarded;
 320
 321         static const size_t c_nLockAll = ~size_t( 0 );
 322
 323     public:
 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 ) )
 329         {}
 330
 331         /// Locks all from \p arrLocks array
 332         unique_lock( lock_array_type& arrLocks )
 333             : m_arrLocks( arrLocks )
 334             , m_nLockGuarded( c_nLockAll )
 335         {
 336             arrLocks.lock_all();
 337         }
 338
 339         unique_lock() = delete;
 340         unique_lock( unique_lock const& ) = delete;
 341
 342         ~unique_lock()
 343         {
 344             if ( m_nLockGuarded == c_nLockAll )
 345                 m_arrLocks.unlock_all();
 346             else
 347                 m_arrLocks.unlock( m_nLockGuarded );
 348         }
 349     };
 350 } // namespace std
 351 //@endcond
 352
 353 #endif // #ifndef CDSLIB_SYNC_LOCK_ARRAY_H