X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FBits.h;h=a88e6349254dd30269447b34ec587d7136124007;hb=86d219c38847965714df9eba03b07fa2f6e30ecc;hp=4d4656d20e784938b5d87278a21648506ed1151b;hpb=7fd87e7e86bb78dc693da2111bf915761346d540;p=folly.git

diff --git a/folly/Bits.h b/folly/Bits.h
index 4d4656d2..a88e6349 100644
--- a/folly/Bits.h
+++ b/folly/Bits.h
@@ -17,21 +17,24 @@
 /**
  * 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
@@ -69,7 +72,6 @@
 #include <byteswap.h>
 #include <cassert>
 #include <cinttypes>
-#include <cstring>  // for ffs, ffsl, ffsll
 #include <endian.h>
 #include <iterator>
 #include <limits>
@@ -80,99 +82,93 @@
 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),
@@ -182,15 +178,21 @@ typename std::enable_if<
 }
 
 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));
 }
 
 /**
@@ -496,7 +498,7 @@ template <class T>
 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));