folly::Bits< T, Traits > Struct Template Reference

#include <Bits.h>

Public Types
typedef Traits::UnderlyingType	UnderlyingType
typedef T	type

Static Public Member Functions
static constexpr size_t	blockIndex (size_t bit)
static constexpr size_t	bitOffset (size_t bit)
static constexpr size_t	blockCount (size_t nbits)
static void	set (T *p, size_t bit)
static void	clear (T *p, size_t bit)
static bool	test (const T *p, size_t bit)
static void	set (T *p, size_t bitStart, size_t count, UnderlyingType value)
static UnderlyingType	get (const T *p, size_t bitStart, size_t count)
static size_t	count (const T *begin, const T *end)

Static Public Attributes
static constexpr size_t	bitsPerBlock

Private Types
using	UnsignedType = typename std::make_unsigned< UnderlyingType >::type

Static Private Member Functions
static void	innerSet (T *p, size_t bitStart, size_t count, UnderlyingType value)
static UnderlyingType	innerGet (const T *p, size_t bitStart, size_t count)
static constexpr UnderlyingType	ones (size_t count)

Static Private Attributes
static constexpr UnderlyingType	zero = UnderlyingType(0)
static constexpr UnderlyingType	one = UnderlyingType(1)

Detailed Description

template<class T, class Traits = detail::BitsTraits<T>>
struct folly::Bits< T, Traits >

Wrapper class with static methods for various bit-level operations, treating an array of T as an array of bits (in little-endian order). (T is either an unsigned integral type or Unaligned<X>, where X is an unsigned integral type)

Definition at line 125 of file Bits.h.

Member Typedef Documentation

template<class T, class Traits = detail::BitsTraits<T>>

typedef T folly::Bits< T, Traits >::type

Definition at line 127 of file Bits.h.

template<class T, class Traits = detail::BitsTraits<T>>

typedef Traits::UnderlyingType folly::Bits< T, Traits >::UnderlyingType

Definition at line 126 of file Bits.h.

template<class T, class Traits = detail::BitsTraits<T>>

using folly::Bits< T, Traits >::UnsignedType = typename std::make_unsigned<UnderlyingType>::type

private

Definition at line 205 of file Bits.h.

Member Function Documentation

template<class T, class Traits = detail::BitsTraits<T>>

static constexpr size_t folly::Bits< T, Traits >::bitOffset ( size_t  bit )

inlinestatic

Offset in block of the given bit.

Definition at line 146 of file Bits.h.

                                                {
    return bit % bitsPerBlock;
  }

template<class T, class Traits = detail::BitsTraits<T>>

static constexpr size_t folly::Bits< T, Traits >::blockCount ( size_t  nbits )

inlinestatic

Number of blocks used by the given number of bits.

Definition at line 153 of file Bits.h.

References folly::test::begin(), count, folly::test::end(), folly::T, test(), and folly::value().

                                                   {
    return nbits / bitsPerBlock + (nbits % bitsPerBlock != 0);
  }

template<class T, class Traits = detail::BitsTraits<T>>

static constexpr size_t folly::Bits< T, Traits >::blockIndex ( size_t  bit )

inlinestatic

Byte index of the given bit.

Definition at line 139 of file Bits.h.

                                                 {
    return bit / bitsPerBlock;
  }

template<class T , class Traits >

void folly::Bits< T, Traits >::clear ( T *  p, size_t  bit  )

inlinestatic

Clear the given bit.

Definition at line 226 of file Bits.h.

References folly::T.

Referenced by runSimpleTest64(), and runSimpleTest8().

                                                   {
  T& block = p[blockIndex(bit)];
  Traits::store(block, Traits::loadRMW(block) & ~(one << bitOffset(bit)));
}

template<class T , class Traits >

size_t folly::Bits< T, Traits >::count ( const T *  begin, const T *  end  )

inlinestatic

Count the number of bits set in a range of blocks.

Definition at line 319 of file Bits.h.

References folly::test::begin(), folly::test::end(), deadlock::load(), and folly::popcount().

                                                                 {
  size_t n = 0;
  for (; begin != end; ++begin) {
    n += popcount(Traits::load(*begin));
  }
  return n;
}

template<class T , class Traits >

auto folly::Bits< T, Traits >::get ( const T *  p, size_t  bitStart, size_t  count  )

inlinestatic

Get count contiguous bits starting at bitStart. Precondition: count <= sizeof(T) * 8

Definition at line 285 of file Bits.h.

References count, and value.

Referenced by benchmarkGet(), and TEST().

                      {
  if (count == 0) {
    return UnderlyingType{};
  }

  DCHECK_LE(count, sizeof(UnderlyingType) * 8);
  size_t idx = blockIndex(bitStart);
  size_t offset = bitOffset(bitStart);
  UnderlyingType ret;
  if (offset + count <= bitsPerBlock) {
    ret = innerGet(p + idx, offset, count);
  } else {
    size_t countInThisBlock = bitsPerBlock - offset;
    size_t countInNextBlock = count - countInThisBlock;
    UnderlyingType thisBlockValue = innerGet(p + idx, offset, countInThisBlock);
    UnderlyingType nextBlockValue = innerGet(p + idx + 1, 0, countInNextBlock);
    ret = (nextBlockValue << countInThisBlock) | thisBlockValue;
  }
  if (std::is_signed<UnderlyingType>::value) {
    size_t emptyBits = bitsPerBlock - count;
    ret <<= emptyBits;
    ret >>= emptyBits;
  }
  return ret;
}

template<class T , class Traits >

auto folly::Bits< T, Traits >::innerGet ( const T *  p, size_t  bitStart, size_t  count  )

inlinestaticprivate

Definition at line 313 of file Bits.h.

References count, and deadlock::load().

                      {
  return (Traits::load(*p) >> offset) & ones(count);
}

template<class T , class Traits >

void folly::Bits< T, Traits >::innerSet ( T *  p, size_t  bitStart, size_t  count, UnderlyingType  value  )

inlinestaticprivate

Definition at line 265 of file Bits.h.

References FOLLY_POP_WARNING.

                          {
  // Mask out bits and set new value
  UnderlyingType v = Traits::loadRMW(*p);
  v &= ~(ones(count) << offset);
  v |= (value << offset);
  Traits::store(*p, v);
}

template<class T, class Traits = detail::BitsTraits<T>>

static constexpr UnderlyingType folly::Bits< T, Traits >::ones ( size_t  count )

inlinestaticprivate

Definition at line 206 of file Bits.h.

References count, FOLLY_GCC_DISABLE_WARNING, FOLLY_GNU_DISABLE_WARNING, and FOLLY_PUSH_WARNING.

                                                     {
    return (count < bitsPerBlock)
        ? static_cast<UnderlyingType>((UnsignedType{1} << count) - 1)
        : ~zero;
  }

template<class T , class Traits >

FOLLY_PUSH_WARNING void folly::Bits< T, Traits >::set ( T *  p, size_t  bit  )

inlinestatic

Set the given bit.

Definition at line 220 of file Bits.h.

References folly::T.

Referenced by benchmarkSet(), runMultiBitTest64(), runMultiBitTest8(), runSignedMultiBitTest8(), runSimpleTest64(), runSimpleTest8(), and TEST().

                                                 {
  T& block = p[blockIndex(bit)];
  Traits::store(block, Traits::loadRMW(block) | (one << bitOffset(bit)));
}

template<class T , class Traits >

void folly::Bits< T, Traits >::set ( T *  p, size_t  bitStart, size_t  count, UnderlyingType  value  )

inlinestatic

Set count contiguous bits starting at bitStart to the values from the least significant count bits of value; little endian. (value & 1 becomes the bit at bitStart, etc) Precondition: count <= sizeof(T) * 8 Precondition: value can fit in 'count' bits

Definition at line 232 of file Bits.h.

References count, type, and value.

                          {
  DCHECK_LE(count, sizeof(UnderlyingType) * 8);
  size_t cut = bitsPerBlock - count;
  if (cut != 8 * sizeof(UnderlyingType)) {
    using U = typename std::make_unsigned<UnderlyingType>::type;
    DCHECK_EQ(value, UnderlyingType(U(value) << cut) >> cut);
  }
  size_t idx = blockIndex(bitStart);
  size_t offset = bitOffset(bitStart);
  if (std::is_signed<UnderlyingType>::value) {
    value &= ones(count);
  }
  if (offset + count <= bitsPerBlock) {
    innerSet(p + idx, offset, count, value);
  } else {
    size_t countInThisBlock = bitsPerBlock - offset;
    size_t countInNextBlock = count - countInThisBlock;

    UnderlyingType thisBlock = UnderlyingType(value & ones(countInThisBlock));
    UnderlyingType nextBlock = UnderlyingType(value >> countInThisBlock);
    if (std::is_signed<UnderlyingType>::value) {
      nextBlock &= ones(countInNextBlock);
    }
    innerSet(p + idx, offset, countInThisBlock, thisBlock);
    innerSet(p + idx + 1, 0, countInNextBlock, nextBlock);
  }
}

template<class T , class Traits >

FOLLY_POP_WARNING bool folly::Bits< T, Traits >::test ( const T *  p, size_t  bit  )

inlinestatic

Test the given bit.

Definition at line 280 of file Bits.h.

References deadlock::load().

                                                        {
  return Traits::load(p[blockIndex(bit)]) & (one << bitOffset(bit));
}

Member Data Documentation

template<class T, class Traits = detail::BitsTraits<T>>

constexpr size_t folly::Bits< T, Traits >::bitsPerBlock

static

Initial value:

= std::numeric_limits<
      typename std::make_unsigned<UnderlyingType>::type>::digits

Number of bits in a block.

Definition at line 133 of file Bits.h.

template<class T, class Traits = detail::BitsTraits<T>>

constexpr UnderlyingType folly::Bits< T, Traits >::one = UnderlyingType(1)

staticprivate

Definition at line 203 of file Bits.h.

template<class T, class Traits = detail::BitsTraits<T>>

constexpr UnderlyingType folly::Bits< T, Traits >::zero = UnderlyingType(0)

staticprivate

Definition at line 202 of file Bits.h.

---

The documentation for this struct was generated from the following file:

• proxygen/folly/folly/experimental/Bits.h