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             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 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 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::lock::Spinlock
  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 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         array()
 143             : m_arrLocks( nullptr )
 144             , m_nCapacity(0)
 145         {}
 146         array( select_cell_policy const& policy )
 147             : m_arrLocks( nullptr )
 148             , m_nCapacity(0)
 149             , m_SelectCellPolicy( policy )
 150         {}
 151         //@endcond
 152
 153     public:
 154         /// Constructs array of locks
 155         /**
 156             Allocates the array and initializes all locks as unlocked.
 157         */
 158         array(
 159             size_t nCapacity        ///< [in] Array size
 160         )
 161         : m_arrLocks( nullptr )
 162         , m_nCapacity( nCapacity )
 163         {
 164             m_arrLocks = create_lock_array( nCapacity );
 165         }
 166
 167         /// Constructs array of lock and copy cell selection policy
 168         /**
 169             Allocates the array and initializes all locks as unlocked.
 170         */
 171         array(
 172             size_t nCapacity,       ///< [in] Array size
 173             select_cell_policy const& policy    ///< Cell selection policy (copy-constructible)
 174         )
 175         : m_arrLocks( nullptr )
 176         , m_nCapacity( nCapacity )
 177         , m_SelectCellPolicy( policy )
 178         {
 179             m_arrLocks = create_lock_array( m_nCapacity );
 180         }
 181
 182         /// Constructs array of lock and move cell selection policy
 183         /**
 184             Allocates the array and initializes all locks as unlocked.
 185         */
 186         array(
 187             size_t nCapacity,       ///< [in] Array size
 188             select_cell_policy&& policy    ///< Cell selection policy (move-constructible)
 189         )
 190         : m_arrLocks( nullptr )
 191         , m_nCapacity( nCapacity )
 192         , m_SelectCellPolicy( std::forward<select_cell_policy>( policy ))
 193         {
 194             m_arrLocks = create_lock_array( m_nCapacity );
 195         }
 196
 197         /// Destructs array of locks and frees used memory
 198         ~array()
 199         {
 200             delete_lock_array( m_arrLocks, m_nCapacity );
 201         }
 202
 203         /// Locks a lock at cell \p hint
 204         /**
 205             To define real array's cell which should be locked, \ref select_cell_policy is used.
 206             The target cell is a result of <tt>select_cell_policy( hint, size() )</tt>.
 207
 208             Returns the index of locked lock.
 209         */
 210         template <typename Q>
 211         size_t lock( Q const& hint )
 212         {
 213             size_t nCell = m_SelectCellPolicy( hint, size() );
 214             assert( nCell < size() );
 215             m_arrLocks[nCell].lock();
 216             return nCell;
 217         }
 218
 219         /// Try lock a lock at cell \p hint
 220         /**
 221             To define real array's cell which should be locked, \ref select_cell_policy is used.
 222             The target cell is a result of <tt>select_cell_policy( hint, size() )</tt>.
 223
 224             Returns the index of locked lock if success, \ref c_nUnspecifiedCell constant otherwise.
 225         */
 226         template <typename Q>
 227         size_t try_lock( Q const& hint )
 228         {
 229             size_t nCell = m_SelectCellPolicy( hint, size() );
 230             assert( nCell < size() );
 231             if ( m_arrLocks[nCell].try_lock() )
 232                 return nCell;
 233             return c_nUnspecifiedCell;
 234         }
 235
 236         /// Unlock the lock specified by index \p nCell
 237         void unlock( size_t nCell )
 238         {
 239             assert( nCell < size() );
 240             m_arrLocks[nCell].unlock();
 241         }
 242
 243         /// Lock all
 244         void lock_all()
 245         {
 246             lock_type * pLock = m_arrLocks;
 247             for ( lock_type * pEnd = m_arrLocks + size(); pLock != pEnd; ++pLock )
 248                 pLock->lock();
 249         }
 250
 251         /// Unlock all
 252         void unlock_all()
 253         {
 254             lock_type * pLock = m_arrLocks;
 255             for ( lock_type * pEnd = m_arrLocks + size(); pLock != pEnd; ++pLock )
 256                 pLock->unlock();
 257         }
 258
 259         /// Get lock at cell \p nCell.
 260         /**
 261             Precondition: <tt>nCell < size()</tt>
 262         */
 263         lock_type& at( size_t nCell ) const
 264         {
 265             assert( nCell < size() );
 266             return m_arrLocks[ nCell ];
 267         }
 268
 269         /// Size of lock array.
 270         size_t size() const
 271         {
 272             return m_nCapacity;
 273         }
 274     };
 275
 276 }} // namespace cds::lock
 277
 278 //@cond
 279 namespace std {
 280
 281     /// Specialization \ref scoped_lock for lock::array
 282     template <typename Lock, typename SelectPolicy, class Alloc>
 283     class unique_lock< cds::lock::array< Lock, SelectPolicy, Alloc > >
 284     {
 285     public:
 286         typedef cds::lock::array< Lock, SelectPolicy, Alloc >   lock_array_type;   ///< Lock array type
 287
 288     private:
 289         lock_array_type&    m_arrLocks;
 290         size_t              m_nLockGuarded;
 291
 292         static const size_t c_nLockAll = ~size_t( 0 );
 293
 294     public:
 295         /// Onws the lock array \p arrLocks and locks a cell determined by \p hint parameter
 296         template <typename Q>
 297         unique_lock( lock_array_type& arrLocks, Q const& hint )
 298             : m_arrLocks( arrLocks )
 299             , m_nLockGuarded( arrLocks.lock( hint ) )
 300         {}
 301
 302         /// Locks all from \p arrLocks array
 303         unique_lock( lock_array_type& arrLocks )
 304             : m_arrLocks( arrLocks )
 305             , m_nLockGuarded( c_nLockAll )
 306         {
 307             arrLocks.lock_all();
 308         }
 309
 310         unique_lock() = delete;
 311         unique_lock( unique_lock const& ) = delete;
 312
 313         ~unique_lock()
 314         {
 315             if ( m_nLockGuarded == c_nLockAll )
 316                 m_arrLocks.unlock_all();
 317             else
 318                 m_arrLocks.unlock( m_nLockGuarded );
 319         }
 320     };
 321 } // namespace std
 322 //@endcond
 323
 324 #endif // #ifndef __CDS_LOCK_ARRAY_H