folly/AtomicBitSet.h

   1 /*
   2  * Copyright 2015 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #ifndef FOLLY_ATOMICBITSET_H_
  18 #define FOLLY_ATOMICBITSET_H_
  19
  20 #include <array>
  21 #include <atomic>
  22 #include <cassert>
  23 #include <cstddef>
  24 #include <limits>
  25
  26 #include <boost/noncopyable.hpp>
  27
  28 #include <folly/Portability.h>
  29
  30 namespace folly {
  31
  32 /**
  33  * An atomic bitset of fixed size (specified at compile time).
  34  */
  35 template <size_t N>
  36 class AtomicBitSet : private boost::noncopyable {
  37  public:
  38   /**
  39    * Construct an AtomicBitSet; all bits are initially false.
  40    */
  41   AtomicBitSet();
  42
  43   /**
  44    * Set bit idx to true, using the given memory order. Returns the
  45    * previous value of the bit.
  46    *
  47    * Note that the operation is a read-modify-write operation due to the use
  48    * of fetch_or.
  49    */
  50   bool set(size_t idx, std::memory_order order = std::memory_order_seq_cst);
  51
  52   /**
  53    * Set bit idx to false, using the given memory order. Returns the
  54    * previous value of the bit.
  55    *
  56    * Note that the operation is a read-modify-write operation due to the use
  57    * of fetch_and.
  58    */
  59   bool reset(size_t idx, std::memory_order order = std::memory_order_seq_cst);
  60
  61   /**
  62    * Set bit idx to the given value, using the given memory order. Returns
  63    * the previous value of the bit.
  64    *
  65    * Note that the operation is a read-modify-write operation due to the use
  66    * of fetch_and or fetch_or.
  67    *
  68    * Yes, this is an overload of set(), to keep as close to std::bitset's
  69    * interface as possible.
  70    */
  71   bool set(size_t idx,
  72            bool value,
  73            std::memory_order order = std::memory_order_seq_cst);
  74
  75   /**
  76    * Read bit idx.
  77    */
  78   bool test(size_t idx,
  79             std::memory_order order = std::memory_order_seq_cst) const;
  80
  81   /**
  82    * Same as test() with the default memory order.
  83    */
  84   bool operator[](size_t idx) const;
  85
  86   /**
  87    * Return the size of the bitset.
  88    */
  89   constexpr size_t size() const {
  90     return N;
  91   }
  92
  93  private:
  94   // Pick the largest lock-free type available
  95 #if (ATOMIC_LLONG_LOCK_FREE == 2)
  96   typedef unsigned long long BlockType;
  97 #elif (ATOMIC_LONG_LOCK_FREE == 2)
  98   typedef unsigned long BlockType;
  99 #else
 100   // Even if not lock free, what can we do?
 101   typedef unsigned int BlockType;
 102 #endif
 103   typedef std::atomic<BlockType> AtomicBlockType;
 104
 105   static constexpr size_t kBitsPerBlock =
 106     std::numeric_limits<BlockType>::digits;
 107
 108   static constexpr size_t blockIndex(size_t bit) {
 109     return bit / kBitsPerBlock;
 110   }
 111
 112   static constexpr size_t bitOffset(size_t bit) {
 113     return bit % kBitsPerBlock;
 114   }
 115
 116   // avoid casts
 117   static constexpr BlockType kOne = 1;
 118
 119   std::array<AtomicBlockType, N> data_;
 120 };
 121
 122 // value-initialize to zero
 123 template <size_t N>
 124 inline AtomicBitSet<N>::AtomicBitSet() : data_() {
 125 }
 126
 127 template <size_t N>
 128 inline bool AtomicBitSet<N>::set(size_t idx, std::memory_order order) {
 129   assert(idx < N * kBitsPerBlock);
 130   BlockType mask = kOne << bitOffset(idx);
 131   return data_[blockIndex(idx)].fetch_or(mask, order) & mask;
 132 }
 133
 134 template <size_t N>
 135 inline bool AtomicBitSet<N>::reset(size_t idx, std::memory_order order) {
 136   assert(idx < N * kBitsPerBlock);
 137   BlockType mask = kOne << bitOffset(idx);
 138   return data_[blockIndex(idx)].fetch_and(~mask, order) & mask;
 139 }
 140
 141 template <size_t N>
 142 inline bool AtomicBitSet<N>::set(size_t idx,
 143                                  bool value,
 144                                  std::memory_order order) {
 145   return value ? set(idx, order) : reset(idx, order);
 146 }
 147
 148 template <size_t N>
 149 inline bool AtomicBitSet<N>::test(size_t idx, std::memory_order order) const {
 150   assert(idx < N * kBitsPerBlock);
 151   BlockType mask = kOne << bitOffset(idx);
 152   return data_[blockIndex(idx)].load(order) & mask;
 153 }
 154
 155 template <size_t N>
 156 inline bool AtomicBitSet<N>::operator[](size_t idx) const {
 157   return test(idx);
 158 }
 159
 160 }  // namespaces
 161
 162 #endif /* FOLLY_ATOMICBITSET_H_ */