cds/sync/lock_array.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_SYNC_LOCK_ARRAY_H
   4 #define CDSLIB_SYNC_LOCK_ARRAY_H
   5
   6 #include <mutex>    //unique_lock
   7 #include <cds/details/allocator.h>
   8 #include <cds/algo/int_algo.h>
   9
  10 namespace cds { namespace sync {
  11
  12     /// Trivial lock \ref lock_array selection policy
  13     struct trivial_select_policy
  14     {
  15         /// Returns \p nWhat
  16         size_t operator()( size_t nWhat, size_t nCapacity ) const
  17         {
  18             assert( nWhat < nCapacity );
  19             CDS_UNUSED( nCapacity );
  20             return nWhat;
  21         }
  22
  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 )
  25         {
  26             CDS_UNUSED( nCapacity );
  27             return true;
  28         }
  29     };
  30
  31     /// The lock \ref lock_array cell selection policy "division by modulo"
  32     struct mod_select_policy
  33     {
  34         /// Returns <tt> nWhat % nCapacity </tt>
  35         size_t operator()( size_t nWhat, size_t nCapacity ) const
  36         {
  37             return nWhat % nCapacity;
  38         }
  39
  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 )
  42         {
  43             return nCapacity > 0;
  44         }
  45     };
  46
  47     /// The lock \ref lock_array cell selection policy "division by modulo of power of 2"
  48     /**
  49         This policy may be used if the size of lock array is equal to power of two.
  50     */
  51     struct pow2_select_policy
  52     {
  53         //@cond
  54         const size_t    m_nMask;
  55         //@endcond
  56
  57         /// Ctor. \p nCapacity must be power of two.
  58         pow2_select_policy( size_t nCapacity )
  59             : m_nMask( nCapacity - 1 )
  60         {
  61             assert( is_capacity_accepted( nCapacity ));
  62         }
  63
  64         /// Copy constructor
  65         pow2_select_policy( pow2_select_policy const& src )
  66             : m_nMask( src.m_nMask )
  67         {}
  68
  69         /// Move constructor
  70         pow2_select_policy( pow2_select_policy&& src )
  71             : m_nMask( src.m_nMask )
  72         {}
  73
  74         /// Returns <tt>nWhat & (nPow2 - 1)</tt>
  75         size_t operator()( size_t nWhat, size_t ) const
  76         {
  77             return nWhat & m_nMask;
  78         }
  79
  80         /// Checks if \p nCapacity is acceptable by policy. \p nCapacity must be power of two
  81         static bool is_capacity_accepted( size_t nCapacity )
  82         {
  83             return cds::beans::is_power2( nCapacity );
  84         }
  85     };
  86
  87     /// Array of locks
  88     /**
  89         The lock array is useful for building fine-grained lock-based data structure
  90         based on striping technique. Instead of locking access to data struct (a hash map, for example)
  91         at whole, the striping locks only part of the map (a bucket). So, access to different buckets
  92         can be simultaneous.
  93
  94         Template arguments:
  95         - \p Lock - lock type, for example, \p std::mutex, \p cds::sync::spin_lock
  96         - \p SelectPolicy - array cell selection policy, the default is \ref mod_select_policy
  97              Available policies: \ref trivial_select_policy, \ref pow2_select_policy, \ref mod_select_policy.
  98         - \p Alloc - memory allocator for array
  99
 100         To determine array's cell the selection policy \p SelectPolicy functor is used. Two arguments
 101         are passed to the policy:
 102         \code size_t operator()( size_t nHint, size_t nCapacity ) const \endcode
 103         - \p nHint - a hint to calculate cell index in the lock array. Usually, it is a hash value.
 104         - \p nCapacity - the size of the lock array
 105         The functor should return the index in the lock array.
 106
 107         Note that the type of \p nHint parameter can be any.
 108     */
 109     template <typename Lock
 110         , typename SelectPolicy = mod_select_policy
 111         , class Alloc = CDS_DEFAULT_ALLOCATOR
 112     >
 113     class lock_array
 114     {
 115         //@cond
 116         typedef ::cds::details::Allocator< Lock, Alloc > cxx_allocator;
 117         //@endcond
 118     public:
 119         typedef Lock            lock_type           ;   ///< lock type
 120         typedef SelectPolicy    select_cell_policy  ;   ///< Cell selection policy functor
 121         static size_t const     c_nUnspecifiedCell = (size_t) -1 ;  ///< failed \ref try_lock call result
 122
 123     protected:
 124         lock_type *         m_arrLocks  ;   ///< lock array
 125         size_t const        m_nCapacity ;   ///< array capacity
 126
 127         select_cell_policy  m_SelectCellPolicy  ;   ///< Cell selection policy
 128
 129     protected:
 130         //@cond
 131         static lock_type * create_lock_array( size_t nCapacity )
 132         {
 133             return cxx_allocator().NewArray( nCapacity );
 134         }
 135         static void delete_lock_array( lock_type * pArr, size_t nCapacity )
 136         {
 137             if ( pArr )
 138                 cxx_allocator().Delete( pArr, nCapacity );
 139         }
 140
 141         // Only for internal use!!!
 142         lock_array()
 143             : m_arrLocks( nullptr )
 144             , m_nCapacity(0)
 145         {}
 146
 147         lock_array( select_cell_policy const& policy )
 148             : m_arrLocks( nullptr )
 149             , m_nCapacity(0)
 150             , m_SelectCellPolicy( policy )
 151         {}
 152         //@endcond
 153
 154     public:
 155         /// Constructs array of locks
 156         /**
 157             Allocates the array and initializes all locks as unlocked.
 158         */
 159         lock_array(
 160             size_t nCapacity        ///< [in] Array size
 161         )
 162         : m_arrLocks( nullptr )
 163         , m_nCapacity( nCapacity )
 164         {
 165             m_arrLocks = create_lock_array( nCapacity );
 166         }
 167
 168         /// Constructs array of lock and copy cell selection policy
 169         /**
 170             Allocates the array and initializes all locks as unlocked.
 171         */
 172         lock_array(
 173             size_t nCapacity,       ///< [in] Array size
 174             select_cell_policy const& policy    ///< Cell selection policy (copy-constructible)
 175         )
 176         : m_arrLocks( nullptr )
 177         , m_nCapacity( nCapacity )
 178         , m_SelectCellPolicy( policy )
 179         {
 180             m_arrLocks = create_lock_array( m_nCapacity );
 181         }
 182
 183         /// Constructs array of lock and move cell selection policy
 184         /**
 185             Allocates the array and initializes all locks as unlocked.
 186         */
 187         lock_array(
 188             size_t nCapacity,       ///< [in] Array size
 189             select_cell_policy&& policy    ///< Cell selection policy (move-constructible)
 190         )
 191         : m_arrLocks( nullptr )
 192         , m_nCapacity( nCapacity )
 193         , m_SelectCellPolicy( std::forward<select_cell_policy>( policy ))
 194         {
 195             m_arrLocks = create_lock_array( m_nCapacity );
 196         }
 197
 198         /// Destructs array of locks and frees used memory
 199         ~lock_array()
 200         {
 201             delete_lock_array( m_arrLocks, m_nCapacity );
 202         }
 203
 204         /// Locks a lock at cell \p hint
 205         /**
 206             To define real array's cell which should be locked, \ref select_cell_policy is used.
 207             The target cell is a result of <tt>select_cell_policy( hint, size() )</tt>.
 208
 209             Returns the index of locked lock.
 210         */
 211         template <typename Q>
 212         size_t lock( Q const& hint )
 213         {
 214             size_t nCell = m_SelectCellPolicy( hint, size() );
 215             assert( nCell < size() );
 216             m_arrLocks[nCell].lock();
 217             return nCell;
 218         }
 219
 220         /// Try lock a lock at cell \p hint
 221         /**
 222             To define real array's cell which should be locked, \ref select_cell_policy is used.
 223             The target cell is a result of <tt>select_cell_policy( hint, size() )</tt>.
 224
 225             Returns the index of locked lock if success, \ref c_nUnspecifiedCell constant otherwise.
 226         */
 227         template <typename Q>
 228         size_t try_lock( Q const& hint )
 229         {
 230             size_t nCell = m_SelectCellPolicy( hint, size() );
 231             assert( nCell < size() );
 232             if ( m_arrLocks[nCell].try_lock() )
 233                 return nCell;
 234             return c_nUnspecifiedCell;
 235         }
 236
 237         /// Unlock the lock specified by index \p nCell
 238         void unlock( size_t nCell )
 239         {
 240             assert( nCell < size() );
 241             m_arrLocks[nCell].unlock();
 242         }
 243
 244         /// Lock all
 245         void lock_all()
 246         {
 247             lock_type * pLock = m_arrLocks;
 248             for ( lock_type * pEnd = m_arrLocks + size(); pLock != pEnd; ++pLock )
 249                 pLock->lock();
 250         }
 251
 252         /// Unlock all
 253         void unlock_all()
 254         {
 255             lock_type * pLock = m_arrLocks;
 256             for ( lock_type * pEnd = m_arrLocks + size(); pLock != pEnd; ++pLock )
 257                 pLock->unlock();
 258         }
 259
 260         /// Get lock at cell \p nCell.
 261         /**
 262             Precondition: <tt>nCell < size()</tt>
 263         */
 264         lock_type& at( size_t nCell ) const
 265         {
 266             assert( nCell < size() );
 267             return m_arrLocks[ nCell ];
 268         }
 269
 270         /// Size of lock array.
 271         size_t size() const
 272         {
 273             return m_nCapacity;
 274         }
 275     };
 276
 277 }} // namespace cds::sync
 278
 279 //@cond
 280 namespace std {
 281
 282     /// Specialization \p std::unique_lock for \p sync::lock_array
 283     template <typename Lock, typename SelectPolicy, class Alloc>
 284     class unique_lock< cds::sync::lock_array< Lock, SelectPolicy, Alloc > >
 285     {
 286     public:
 287         typedef cds::sync::lock_array< Lock, SelectPolicy, Alloc >   lock_array_type;   ///< Lock array type
 288
 289     private:
 290         lock_array_type&    m_arrLocks;
 291         size_t              m_nLockGuarded;
 292
 293         static const size_t c_nLockAll = ~size_t( 0 );
 294
 295     public:
 296         /// Onws the lock array \p arrLocks and locks a cell determined by \p hint parameter
 297         template <typename Q>
 298         unique_lock( lock_array_type& arrLocks, Q const& hint )
 299             : m_arrLocks( arrLocks )
 300             , m_nLockGuarded( arrLocks.lock( hint ) )
 301         {}
 302
 303         /// Locks all from \p arrLocks array
 304         unique_lock( lock_array_type& arrLocks )
 305             : m_arrLocks( arrLocks )
 306             , m_nLockGuarded( c_nLockAll )
 307         {
 308             arrLocks.lock_all();
 309         }
 310
 311         unique_lock() = delete;
 312         unique_lock( unique_lock const& ) = delete;
 313
 314         ~unique_lock()
 315         {
 316             if ( m_nLockGuarded == c_nLockAll )
 317                 m_arrLocks.unlock_all();
 318             else
 319                 m_arrLocks.unlock( m_nLockGuarded );
 320         }
 321     };
 322 } // namespace std
 323 //@endcond
 324
 325 #endif // #ifndef CDSLIB_SYNC_LOCK_ARRAY_H