folly/AtomicBitSet.h

   1 /*
   2  * Copyright 2014 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 namespace folly {
  29
  30 /**
  31  * An atomic bitset of fixed size (specified at compile time).
  32  */
  33 template <size_t N>
  34 class AtomicBitSet : private boost::noncopyable {
  35  public:
  36   /**
  37    * Construct an AtomicBitSet; all bits are initially false.
  38    */
  39   AtomicBitSet();
  40
  41   /**
  42    * Set bit idx to true, using the given memory order. Returns the
  43    * previous value of the bit.
  44    *
  45    * Note that the operation is a read-modify-write operation due to the use
  46    * of fetch_or.
  47    */
  48   bool set(size_t idx, std::memory_order order = std::memory_order_seq_cst);
  49
  50   /**
  51    * Set bit idx to false, using the given memory order. Returns the
  52    * previous value of the bit.
  53    *
  54    * Note that the operation is a read-modify-write operation due to the use
  55    * of fetch_and.
  56    */
  57   bool reset(size_t idx, std::memory_order order = std::memory_order_seq_cst);
  58
  59   /**
  60    * Set bit idx to the given value, using the given memory order. Returns
  61    * the previous value of the bit.
  62    *
  63    * Note that the operation is a read-modify-write operation due to the use
  64    * of fetch_and or fetch_or.
  65    *
  66    * Yes, this is an overload of set(), to keep as close to std::bitset's
  67    * interface as possible.
  68    */
  69   bool set(size_t idx,
  70            bool value,
  71            std::memory_order order = std::memory_order_seq_cst);
  72
  73   /**
  74    * Read bit idx.
  75    */
  76   bool test(size_t idx,
  77             std::memory_order order = std::memory_order_seq_cst) const;
  78
  79   /**
  80    * Same as test() with the default memory order.
  81    */
  82   bool operator[](size_t idx) const;
  83
  84   /**
  85    * Return the size of the bitset.
  86    */
  87   constexpr size_t size() const {
  88     return N;
  89   }
  90
  91  private:
  92   // Pick the largest lock-free type available
  93 #if (ATOMIC_LLONG_LOCK_FREE == 2)
  94   typedef unsigned long long BlockType;
  95 #elif (ATOMIC_LONG_LOCK_FREE == 2)
  96   typedef unsigned long BlockType;
  97 #else
  98   // Even if not lock free, what can we do?
  99   typedef unsigned int BlockType;
 100 #endif
 101   typedef std::atomic<BlockType> AtomicBlockType;
 102
 103   static constexpr size_t kBitsPerBlock =
 104     std::numeric_limits<BlockType>::digits;
 105
 106   static constexpr size_t blockIndex(size_t bit) {
 107     return bit / kBitsPerBlock;
 108   }
 109
 110   static constexpr size_t bitOffset(size_t bit) {
 111     return bit % kBitsPerBlock;
 112   }
 113
 114   // avoid casts
 115   static constexpr BlockType kOne = 1;
 116
 117   std::array<AtomicBlockType, N> data_;
 118 };
 119
 120 // value-initialize to zero
 121 template <size_t N>
 122 inline AtomicBitSet<N>::AtomicBitSet() : data_() {
 123 }
 124
 125 template <size_t N>
 126 inline bool AtomicBitSet<N>::set(size_t idx, std::memory_order order) {
 127   assert(idx < N * kBitsPerBlock);
 128   BlockType mask = kOne << bitOffset(idx);
 129   return data_[blockIndex(idx)].fetch_or(mask, order) & mask;
 130 }
 131
 132 template <size_t N>
 133 inline bool AtomicBitSet<N>::reset(size_t idx, std::memory_order order) {
 134   assert(idx < N * kBitsPerBlock);
 135   BlockType mask = kOne << bitOffset(idx);
 136   return data_[blockIndex(idx)].fetch_and(~mask, order) & mask;
 137 }
 138
 139 template <size_t N>
 140 inline bool AtomicBitSet<N>::set(size_t idx,
 141                                  bool value,
 142                                  std::memory_order order) {
 143   return value ? set(idx, order) : reset(idx, order);
 144 }
 145
 146 template <size_t N>
 147 inline bool AtomicBitSet<N>::test(size_t idx, std::memory_order order) const {
 148   assert(idx < N * kBitsPerBlock);
 149   BlockType mask = kOne << bitOffset(idx);
 150   return data_[blockIndex(idx)].load(order) & mask;
 151 }
 152
 153 template <size_t N>
 154 inline bool AtomicBitSet<N>::operator[](size_t idx) const {
 155   return test(idx);
 156 }
 157
 158 }  // namespaces
 159
 160 #endif /* FOLLY_ATOMICBITSET_H_ */
 161