/**
* Various low-level, bit-manipulation routines.
*
- * findFirstSet(x)
+ * findFirstSet(x) [constexpr]
* find first (least significant) bit set in a value of an integral type,
* 1-based (like ffs()). 0 = no bits are set (x == 0)
*
- * findLastSet(x)
+ * findLastSet(x) [constexpr]
* find last (most significant) bit set in a value of an integral type,
* 1-based. 0 = no bits are set (x == 0)
* for x != 0, findLastSet(x) == 1 + floor(log2(x))
*
+ * nextPowTwo(x) [constexpr]
+ * Finds the next power of two >= x.
+ *
+ * isPowTwo(x) [constexpr]
+ * return true iff x is a power of two
+ *
* popcount(x)
* return the number of 1 bits in x
*
- * nextPowTwo(x)
- * Finds the next power of two >= x.
- *
* Endian
* convert between native, big, and little endian representation
* Endian::big(x) big <-> native
#include <byteswap.h>
#include <cassert>
#include <cinttypes>
-#include <cstring> // for ffs, ffsl, ffsll
#include <endian.h>
#include <iterator>
#include <limits>
namespace folly {
// Generate overloads for findFirstSet as wrappers around
-// appropriate ffs, ffsl, ffsll functions from glibc.
-// We first define these overloads for signed types (because ffs, ffsl, ffsll
-// take int, long, and long long as arguments, respectively) and then
-// define an overload for unsigned that forwards to the overload for the
-// corresponding signed type.
+// appropriate ffs, ffsl, ffsll gcc builtins
template <class T>
+inline constexpr
typename std::enable_if<
(std::is_integral<T>::value &&
- std::is_signed<T>::value &&
- (std::numeric_limits<T>::digits <= std::numeric_limits<int>::digits)),
+ std::is_unsigned<T>::value &&
+ sizeof(T) <= sizeof(unsigned int)),
unsigned int>::type
findFirstSet(T x) {
- return ::ffs(static_cast<int>(x));
+ return __builtin_ffs(x);
}
template <class T>
+inline constexpr
typename std::enable_if<
(std::is_integral<T>::value &&
- std::is_signed<T>::value &&
- (std::numeric_limits<T>::digits > std::numeric_limits<int>::digits) &&
- (std::numeric_limits<T>::digits <= std::numeric_limits<long>::digits)),
+ std::is_unsigned<T>::value &&
+ sizeof(T) > sizeof(unsigned int) &&
+ sizeof(T) <= sizeof(unsigned long)),
unsigned int>::type
findFirstSet(T x) {
- return ::ffsl(static_cast<long>(x));
+ return __builtin_ffsl(x);
}
-#ifdef FOLLY_HAVE_FFSLL
-
template <class T>
+inline constexpr
typename std::enable_if<
(std::is_integral<T>::value &&
- std::is_signed<T>::value &&
- (std::numeric_limits<T>::digits > std::numeric_limits<long>::digits) &&
- (std::numeric_limits<T>::digits <= std::numeric_limits<long long>::digits)),
+ std::is_unsigned<T>::value &&
+ sizeof(T) > sizeof(unsigned long) &&
+ sizeof(T) <= sizeof(unsigned long long)),
unsigned int>::type
findFirstSet(T x) {
- return ::ffsll(static_cast<long long>(x));
+ return __builtin_ffsll(x);
}
-#endif
-
template <class T>
+inline constexpr
typename std::enable_if<
- (std::is_integral<T>::value &&
- !std::is_signed<T>::value),
+ (std::is_integral<T>::value && std::is_signed<T>::value),
unsigned int>::type
findFirstSet(T x) {
- // Note that conversion from an unsigned type to the corresponding signed
+ // Note that conversion from a signed type to the corresponding unsigned
// type is technically implementation-defined, but will likely work
// on any impementation that uses two's complement.
- return findFirstSet(static_cast<typename std::make_signed<T>::type>(x));
+ return findFirstSet(static_cast<typename std::make_unsigned<T>::type>(x));
}
// findLastSet: return the 1-based index of the highest bit set
// for x > 0, findLastSet(x) == 1 + floor(log2(x))
template <class T>
+inline constexpr
typename std::enable_if<
(std::is_integral<T>::value &&
std::is_unsigned<T>::value &&
- (std::numeric_limits<T>::digits <=
- std::numeric_limits<unsigned int>::digits)),
+ sizeof(T) <= sizeof(unsigned int)),
unsigned int>::type
findLastSet(T x) {
return x ? 8 * sizeof(unsigned int) - __builtin_clz(x) : 0;
}
template <class T>
+inline constexpr
typename std::enable_if<
(std::is_integral<T>::value &&
std::is_unsigned<T>::value &&
- (std::numeric_limits<T>::digits >
- std::numeric_limits<unsigned int>::digits) &&
- (std::numeric_limits<T>::digits <=
- std::numeric_limits<unsigned long>::digits)),
+ sizeof(T) > sizeof(unsigned int) &&
+ sizeof(T) <= sizeof(unsigned long)),
unsigned int>::type
findLastSet(T x) {
return x ? 8 * sizeof(unsigned long) - __builtin_clzl(x) : 0;
}
template <class T>
+inline constexpr
typename std::enable_if<
(std::is_integral<T>::value &&
std::is_unsigned<T>::value &&
- (std::numeric_limits<T>::digits >
- std::numeric_limits<unsigned long>::digits) &&
- (std::numeric_limits<T>::digits <=
- std::numeric_limits<unsigned long long>::digits)),
+ sizeof(T) > sizeof(unsigned long) &&
+ sizeof(T) <= sizeof(unsigned long long)),
unsigned int>::type
findLastSet(T x) {
return x ? 8 * sizeof(unsigned long long) - __builtin_clzll(x) : 0;
}
template <class T>
+inline constexpr
typename std::enable_if<
(std::is_integral<T>::value &&
std::is_signed<T>::value),
}
template <class T>
-inline
+inline constexpr
typename std::enable_if<
std::is_integral<T>::value && std::is_unsigned<T>::value,
T>::type
nextPowTwo(T v) {
- if (UNLIKELY(v == 0)) {
- return 1;
- }
- return 1ul << findLastSet(v - 1);
+ return v ? (1ul << findLastSet(v - 1)) : 1;
+}
+
+template <class T>
+inline constexpr
+typename std::enable_if<
+ std::is_integral<T>::value && std::is_unsigned<T>::value,
+ bool>::type
+isPowTwo(T v) {
+ return (v != 0) && !(v & (v - 1));
}
/**
struct Unaligned<
T,
typename std::enable_if<std::is_pod<T>::value>::type> {
- Unaligned() { } // uninitialized
+ Unaligned() = default; // uninitialized
/* implicit */ Unaligned(T v) : value(v) { }
T value;
} __attribute__((packed));
projects / folly.git / blobdiff