cds/lock/array.h

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