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