21 #include <type_traits> 23 #include <glog/logging.h> 45 template <
class T,
class Enable =
void>
55 typename
std::enable_if<(std::is_integral<T>::value)>
::type> {
76 typename
std::enable_if<(std::is_integral<T>::value)>
::type> {
99 typename
std::enable_if<(std::is_integral<T>::value)>
::type> {
124 template <
class T,
class Traits = detail::BitsTraits<T>>
128 static_assert(
sizeof(
T) ==
sizeof(UnderlyingType),
"Size mismatch");
133 static constexpr
size_t bitsPerBlock = std::numeric_limits<
140 return bit / bitsPerBlock;
147 return bit % bitsPerBlock;
154 return nbits / bitsPerBlock + (nbits % bitsPerBlock != 0);
160 static void set(
T* p,
size_t bit);
165 static void clear(
T* p,
size_t bit);
170 static bool test(
const T* p,
size_t bit);
179 static void set(
T* p,
size_t bitStart,
size_t count, UnderlyingType
value);
185 static UnderlyingType
get(
const T* p,
size_t bitStart,
size_t count);
196 innerSet(
T* p,
size_t bitStart,
size_t count, UnderlyingType
value);
200 static UnderlyingType innerGet(
const T* p,
size_t bitStart,
size_t count);
202 static constexpr UnderlyingType zero = UnderlyingType(0);
203 static constexpr UnderlyingType one = UnderlyingType(1);
206 static constexpr UnderlyingType
ones(
size_t count) {
207 return (count < bitsPerBlock)
219 template <
class T,
class Traits>
221 T& block = p[blockIndex(bit)];
222 Traits::store(block, Traits::loadRMW(block) | (one << bitOffset(bit)));
225 template <
class T,
class Traits>
227 T& block = p[blockIndex(bit)];
228 Traits::store(block, Traits::loadRMW(block) & ~(one << bitOffset(bit)));
231 template <
class T,
class Traits>
236 UnderlyingType
value) {
237 DCHECK_LE(count,
sizeof(UnderlyingType) * 8);
238 size_t cut = bitsPerBlock -
count;
239 if (cut != 8 *
sizeof(UnderlyingType)) {
241 DCHECK_EQ(value, UnderlyingType(U(value) << cut) >> cut);
243 size_t idx = blockIndex(bitStart);
244 size_t offset = bitOffset(bitStart);
246 value &= ones(count);
248 if (offset + count <= bitsPerBlock) {
249 innerSet(p + idx, offset, count, value);
251 size_t countInThisBlock = bitsPerBlock - offset;
252 size_t countInNextBlock = count - countInThisBlock;
254 UnderlyingType thisBlock = UnderlyingType(value & ones(countInThisBlock));
255 UnderlyingType nextBlock = UnderlyingType(value >> countInThisBlock);
257 nextBlock &= ones(countInNextBlock);
259 innerSet(p + idx, offset, countInThisBlock, thisBlock);
260 innerSet(p + idx + 1, 0, countInNextBlock, nextBlock);
264 template <
class T,
class Traits>
269 UnderlyingType
value) {
271 UnderlyingType
v = Traits::loadRMW(*p);
272 v &= ~(ones(count) << offset);
273 v |= (value << offset);
274 Traits::store(*p, v);
279 template <
class T,
class Traits>
281 return Traits::load(p[blockIndex(bit)]) & (one << bitOffset(bit));
284 template <
class T,
class Traits>
288 return UnderlyingType{};
291 DCHECK_LE(
count,
sizeof(UnderlyingType) * 8);
292 size_t idx = blockIndex(bitStart);
293 size_t offset = bitOffset(bitStart);
295 if (offset +
count <= bitsPerBlock) {
296 ret = innerGet(p + idx, offset,
count);
298 size_t countInThisBlock = bitsPerBlock - offset;
299 size_t countInNextBlock =
count - countInThisBlock;
300 UnderlyingType thisBlockValue = innerGet(p + idx, offset, countInThisBlock);
301 UnderlyingType nextBlockValue = innerGet(p + idx + 1, 0, countInNextBlock);
302 ret = (nextBlockValue << countInThisBlock) | thisBlockValue;
305 size_t emptyBits = bitsPerBlock -
count;
312 template <
class T,
class Traits>
318 template <
class T,
class Traits>
constexpr unsigned int popcount(T const v)
static T load(const T &x)
static T FOLLY_DISABLE_ADDRESS_SANITIZER load(const UnalignedNoASan< T > &x)
#define FOLLY_GNU_DISABLE_WARNING(warningName)
#define FOLLY_DISABLE_ADDRESS_SANITIZER
#define FOLLY_POP_WARNING
static void set(T *p, size_t bit)
#define FOLLY_PUSH_WARNING
static UnderlyingType get(const T *p, size_t bitStart, size_t count)
static constexpr UnderlyingType ones(size_t count)
static uint64_t test(std::string name, bool fc_, bool dedicated_, bool tc_, bool syncops_, uint64_t base)
static constexpr size_t blockCount(size_t nbits)
auto begin(TestAdlIterable &instance)
—— Concurrent Priority Queue Implementation ——
static UnderlyingType innerGet(const T *p, size_t bitStart, size_t count)
static void innerSet(T *p, size_t bitStart, size_t count, UnderlyingType value)
typename std::make_unsigned< UnderlyingType >::type UnsignedType
Traits::UnderlyingType UnderlyingType
static T loadRMW(const T &x)
auto end(TestAdlIterable &instance)
static void FOLLY_DISABLE_ADDRESS_SANITIZER store(UnalignedNoASan< T > &x, T v)
static size_t count(const T *begin, const T *end)
static void clear(T *p, size_t bit)
static bool test(const T *p, size_t bit)
static const char *const value
static void store(Unaligned< T > &x, T v)
static T load(const Unaligned< T > &x)
static constexpr size_t blockIndex(size_t bit)
static T loadRMW(const Unaligned< T > &x)
static T FOLLY_DISABLE_ADDRESS_SANITIZER loadRMW(const UnalignedNoASan< T > &x)
uint64_t value(const typename LockFreeRingBuffer< T, Atom >::Cursor &rbcursor)
static constexpr size_t bitOffset(size_t bit)
static void store(T &x, T v)
#define FOLLY_GCC_DISABLE_WARNING(warningName)