2 * Copyright 2015 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #ifndef FOLLY_ATOMICBITSET_H_
18 #define FOLLY_ATOMICBITSET_H_
26 #include <boost/noncopyable.hpp>
28 #include <folly/Portability.h>
33 * An atomic bitset of fixed size (specified at compile time).
36 class AtomicBitSet : private boost::noncopyable {
39 * Construct an AtomicBitSet; all bits are initially false.
44 * Set bit idx to true, using the given memory order. Returns the
45 * previous value of the bit.
47 * Note that the operation is a read-modify-write operation due to the use
50 bool set(size_t idx, std::memory_order order = std::memory_order_seq_cst);
53 * Set bit idx to false, using the given memory order. Returns the
54 * previous value of the bit.
56 * Note that the operation is a read-modify-write operation due to the use
59 bool reset(size_t idx, std::memory_order order = std::memory_order_seq_cst);
62 * Set bit idx to the given value, using the given memory order. Returns
63 * the previous value of the bit.
65 * Note that the operation is a read-modify-write operation due to the use
66 * of fetch_and or fetch_or.
68 * Yes, this is an overload of set(), to keep as close to std::bitset's
69 * interface as possible.
73 std::memory_order order = std::memory_order_seq_cst);
79 std::memory_order order = std::memory_order_seq_cst) const;
82 * Same as test() with the default memory order.
84 bool operator[](size_t idx) const;
87 * Return the size of the bitset.
89 constexpr size_t size() const {
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;
100 // Even if not lock free, what can we do?
101 typedef unsigned int BlockType;
103 typedef std::atomic<BlockType> AtomicBlockType;
105 static constexpr size_t kBitsPerBlock =
106 std::numeric_limits<BlockType>::digits;
108 static constexpr size_t blockIndex(size_t bit) {
109 return bit / kBitsPerBlock;
112 static constexpr size_t bitOffset(size_t bit) {
113 return bit % kBitsPerBlock;
117 static constexpr BlockType kOne = 1;
119 std::array<AtomicBlockType, N> data_;
122 // value-initialize to zero
124 inline AtomicBitSet<N>::AtomicBitSet() : data_() {
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;
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;
142 inline bool AtomicBitSet<N>::set(size_t idx,
144 std::memory_order order) {
145 return value ? set(idx, order) : reset(idx, order);
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;
156 inline bool AtomicBitSet<N>::operator[](size_t idx) const {
162 #endif /* FOLLY_ATOMICBITSET_H_ */