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/algo/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         /// 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 boost::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             lock_type& l = m_arrLocks[ nCell ];
 216             l.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             lock_type& l = m_arrLocks[ nCell ];
 233             if ( l.try_lock() )
 234                 return nCell;
 235             return c_nUnspecifiedCell;
 236         }
 237
 238         /// Unlock the lock specified by index \p nCell
 239         void unlock( size_t nCell )
 240         {
 241             assert( nCell < size() );
 242             m_arrLocks[nCell].unlock();
 243         }
 244
 245         /// Lock all
 246         void lock_all()
 247         {
 248             lock_type * pLock = m_arrLocks;
 249             for ( size_t i = 0; i < size(); ++i, ++pLock )
 250                 pLock->lock();
 251         }
 252
 253         /// Unlock all
 254         void unlock_all()
 255         {
 256             lock_type * pLock = m_arrLocks;
 257             for ( size_t i = 0; i < size(); ++i, ++pLock )
 258                 pLock->unlock();
 259         }
 260
 261         /// Get lock at cell \p nCell.
 262         /**
 263             Precondition: <tt>nCell < size()</tt>
 264         */
 265         lock_type& at( size_t nCell ) const
 266         {
 267             assert( nCell < size() );
 268             return m_arrLocks[ nCell ];
 269         }
 270
 271         /// Size of lock array.
 272         size_t size() const
 273         {
 274             return m_nCapacity;
 275         }
 276     };
 277
 278     /// Specialization \ref scoped_lock for lock::array
 279     template <typename Lock, typename SelectPolicy, class Alloc>
 280     class scoped_lock< cds::lock::array< Lock, SelectPolicy, Alloc > >: public cds::details::noncopyable
 281     {
 282     public:
 283         typedef cds::lock::array< Lock, SelectPolicy, Alloc >   lock_array_type ;   ///< Lock array type
 284
 285     private:
 286         //@cond
 287         lock_array_type&    m_arrLocks;
 288         size_t              m_nLockGuarded;
 289
 290         static const size_t c_nLockAll = ~size_t(0);
 291         //@endcond
 292
 293     public:
 294         /// Onws the lock array \p arrLocks and locks a cell determined by \p hint parameter
 295         template <typename Q>
 296         scoped_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         scoped_lock( lock_array_type& arrLocks )
 303             : m_arrLocks( arrLocks )
 304             , m_nLockGuarded( c_nLockAll )
 305         {
 306             arrLocks.lock_all();
 307         }
 308
 309         ~scoped_lock()
 310         {
 311             if ( m_nLockGuarded == c_nLockAll )
 312                 m_arrLocks.unlock_all();
 313             else
 314                 m_arrLocks.unlock( m_nLockGuarded );
 315         }
 316     };
 317
 318 }} // namespace cds::lock
 319
 320 #endif // #ifndef __CDS_LOCK_ARRAY_H