cds/lock/array.h

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