tdb2: cleanups for tdbtorture, add more debugging and -S flag.
[ccan] / ccan / ilog / ilog.h
index ed91f4eaf830de7192cf27c84a51b145eb899f2c..55dd009885a73c488cb41280f64a319e84ed6233 100644 (file)
@@ -2,30 +2,8 @@
 # define _ilog_H (1)
 # include "config.h"
 # include <stdint.h>
-# include <ccan/compiler/compiler.h>
 # include <limits.h>
-/*Note the casts to (int) below: this prevents CLZ{32|64}_OFFS from "upgrading"
-   the type of an entire expression to an (unsigned) size_t.*/
-# if HAVE_BUILTIN_CLZ && INT_MAX>=2147483647
-#  define CLZ32_OFFS ((int)sizeof(unsigned)*CHAR_BIT)
-#  define CLZ32(_x) (__builtin_clz(_x))
-# elif HAVE_BUILTIN_CLZL && LONG_MAX>=2147483647L
-#  define CLZ32_OFFS ((int)sizeof(unsigned long)*CHAR_BIT)
-#  define CLZ32(_x) (__builtin_clzl(_x))
-# endif
-
-# if HAVE_BUILTIN_CLZ && INT_MAX>=9223372036854775807LL
-#  define CLZ64_OFFS ((int)sizeof(unsigned)*CHAR_BIT)
-#  define CLZ64(_x) (__builtin_clz(_x))
-# elif HAVE_BUILTIN_CLZL && LONG_MAX>=9223372036854775807LL
-#  define CLZ64_OFFS ((int)sizeof(unsigned long)*CHAR_BIT)
-#  define CLZ64(_x) (__builtin_clzl(_x))
-# elif HAVE_BUILTIN_CLZLL /* long long must be >= 64 bits according to ISO C */
-#  define CLZ64_OFFS ((int)sizeof(unsigned long long)*CHAR_BIT)
-#  define CLZ64(_x) (__builtin_clzll(_x))
-# endif
-
-
+# include <ccan/compiler/compiler.h>
 
 /**
  * ilog32 - Integer binary logarithm of a 32-bit value.
  * Returns floor(log2(_v))+1, or 0 if _v==0.
  * This is the number of bits that would be required to represent _v in two's
  *  complement notation with all of the leading zeros stripped.
- * The ILOG_32() or ILOGNZ_32() macros may be able to use a builtin function
- *  instead, which should be faster.
+ * Note that many uses will resolve to the fast macro version instead.
+ *
+ * See Also:
+ *     ilog32_nz(), ilog64()
+ *
+ * Example:
+ *     // Rounds up to next power of 2 (if not a power of 2).
+ *     static uint32_t round_up32(uint32_t i)
+ *     {
+ *             assert(i != 0);
+ *             return 1U << ilog32(i-1);
+ *     }
  */
-int ilog32(uint32_t _v) IDEMPOTENT_ATTRIBUTE;
+int ilog32(uint32_t _v) IDEMPOTENT;
+
 /**
- * ilog64 - Integer binary logarithm of a 64-bit value.
- * @_v: A 64-bit value.
- * Returns floor(log2(_v))+1, or 0 if _v==0.
+ * ilog32_nz - Integer binary logarithm of a non-zero 32-bit value.
+ * @_v: A 32-bit value.
+ * Returns floor(log2(_v))+1, or undefined if _v==0.
  * This is the number of bits that would be required to represent _v in two's
  *  complement notation with all of the leading zeros stripped.
- * The ILOG_64() or ILOGNZ_64() macros may be able to use a builtin function
- *  instead, which should be faster.
+ * Note that many uses will resolve to the fast macro version instead.
+ * See Also:
+ *     ilog32(), ilog64_nz()
+ * Example:
+ *     // Find Last Set (ie. highest bit set, 0 to 31).
+ *     static uint32_t fls32(uint32_t i)
+ *     {
+ *             assert(i != 0);
+ *             return ilog32_nz(i) - 1;
+ *     }
  */
-int ilog64(uint64_t _v) IDEMPOTENT_ATTRIBUTE;
-
+int ilog32_nz(uint32_t _v) IDEMPOTENT;
 
-# if defined(CLZ32)
 /**
- * ILOGNZ_32 - Integer binary logarithm of a non-zero 32-bit value.
- * @_v: A non-zero 32-bit value.
- * Returns floor(log2(_v))+1.
+ * ilog64 - Integer binary logarithm of a 64-bit value.
+ * @_v: A 64-bit value.
+ * Returns floor(log2(_v))+1, or 0 if _v==0.
  * This is the number of bits that would be required to represent _v in two's
  *  complement notation with all of the leading zeros stripped.
- * If _v is zero, the return value is undefined; use ILOG_32() instead.
+ * Note that many uses will resolve to the fast macro version instead.
+ * See Also:
+ *     ilog64_nz(), ilog32()
  */
-#  define ILOGNZ_32(_v) (CLZ32_OFFS-CLZ32(_v))
+int ilog64(uint64_t _v) IDEMPOTENT;
+
 /**
- * ILOG_32 - Integer binary logarithm of a 32-bit value.
- * @_v: A 32-bit value.
- * Returns floor(log2(_v))+1, or 0 if _v==0.
+ * ilog64_nz - Integer binary logarithm of a non-zero 64-bit value.
+ * @_v: A 64-bit value.
+ * Returns floor(log2(_v))+1, or undefined if _v==0.
  * This is the number of bits that would be required to represent _v in two's
  *  complement notation with all of the leading zeros stripped.
+ * Note that many uses will resolve to the fast macro version instead.
+ * See Also:
+ *     ilog64(), ilog32_nz()
  */
-#  define ILOG_32(_v)   (ILOGNZ_32(_v)&-!!(_v))
-# else
-#  define ILOGNZ_32(_v) (ilog32(_v))
-#  define ILOG_32(_v)   (ilog32(_v))
-# endif
+int ilog64_nz(uint64_t _v) IDEMPOTENT;
 
-# if defined(CLZ64)
 /**
- * ILOGNZ_64 - Integer binary logarithm of a non-zero 64-bit value.
- * @_v: A non-zero 64-bit value.
- * Returns floor(log2(_v))+1.
+ * STATIC_ILOG_32 - The integer logarithm of an (unsigned, 32-bit) constant.
+ * @_v: A non-negative 32-bit constant.
+ * Returns floor(log2(_v))+1, or 0 if _v==0.
  * This is the number of bits that would be required to represent _v in two's
  *  complement notation with all of the leading zeros stripped.
- * If _v is zero, the return value is undefined; use ILOG_64() instead.
+ * This macro should only be used when you need a compile-time constant,
+ * otherwise ilog32 or ilog32_nz are just as fast and more flexible.
+ *
+ * Example:
+ *     #define MY_PAGE_SIZE    4096
+ *     #define MY_PAGE_BITS    (STATIC_ILOG_32(PAGE_SIZE) - 1)
  */
-#  define ILOGNZ_64(_v) (CLZ64_OFFS-CLZ64(_v))
+#define STATIC_ILOG_32(_v) (STATIC_ILOG5((uint32_t)(_v)))
+
 /**
- * ILOG_64 - Integer binary logarithm of a 64-bit value.
- * @_v: A 64-bit value.
+ * STATIC_ILOG_64 - The integer logarithm of an (unsigned, 64-bit) constant.
+ * @_v: A non-negative 64-bit constant.
  * Returns floor(log2(_v))+1, or 0 if _v==0.
  * This is the number of bits that would be required to represent _v in two's
  *  complement notation with all of the leading zeros stripped.
+ * This macro should only be used when you need a compile-time constant,
+ * otherwise ilog64 or ilog64_nz are just as fast and more flexible.
  */
-#  define ILOG_64(_v)   (ILOGNZ_64(_v)&-!!(_v))
-# else
-#  define ILOGNZ_64(_v) (ilog64(_v))
-#  define ILOG_64(_v)   (ilog64(_v))
-# endif
+#define STATIC_ILOG_64(_v) (STATIC_ILOG6((uint64_t)(_v)))
+
+/* Private implementation details */
+
+/*Note the casts to (int) below: this prevents "upgrading"
+   the type of an entire expression to an (unsigned) size_t.*/
+#if INT_MAX>=2147483647 && HAVE_BUILTIN_CLZ
+#define builtin_ilog32_nz(v) \
+       (((int)sizeof(unsigned)*CHAR_BIT) - __builtin_clz(v))
+#elif LONG_MAX>=2147483647L && HAVE_BUILTIN_CLZL
+#define builtin_ilog32_nz(v) \
+       (((int)sizeof(unsigned)*CHAR_BIT) - __builtin_clzl(v))
+#endif
+
+#if INT_MAX>=9223372036854775807LL && HAVE_BUILTIN_CLZ
+#define builtin_ilog64_nz(v) \
+       (((int)sizeof(unsigned)*CHAR_BIT) - __builtin_clz(v))
+#elif LONG_MAX>=9223372036854775807LL && HAVE_BUILTIN_CLZL
+#define builtin_ilog64_nz(v) \
+       (((int)sizeof(unsigned long)*CHAR_BIT) - __builtin_clzl(v))
+#elif HAVE_BUILTIN_CLZLL
+#define builtin_ilog64_nz(v) \
+       (((int)sizeof(unsigned long long)*CHAR_BIT) - __builtin_clzll(v))
+#endif
+
+#ifdef builtin_ilog32_nz
+#define ilog32(_v) (builtin_ilog32_nz(_v)&-!!(_v))
+#define ilog32_nz(_v) builtin_ilog32_nz(_v)
+#else
+#define ilog32_nz(_v) ilog32(_v)
+#define ilog32(_v) (IS_COMPILE_CONSTANT(_v) ? STATIC_ILOG_32(_v) : ilog32(_v))
+#endif /* builtin_ilog32_nz */
+
+#ifdef builtin_ilog64_nz
+#define ilog64(_v) (builtin_ilog64_nz(_v)&-!!(_v))
+#define ilog64_nz(_v) builtin_ilog64_nz(_v)
+#else
+#define ilog64_nz(_v) ilog64(_v)
+#define ilog64(_v) (IS_COMPILE_CONSTANT(_v) ? STATIC_ILOG_64(_v) : ilog64(_v))
+#endif /* builtin_ilog64_nz */
 
+/* Macros for evaluating compile-time constant ilog. */
 # define STATIC_ILOG0(_v) (!!(_v))
 # define STATIC_ILOG1(_v) (((_v)&0x2)?2:STATIC_ILOG0(_v))
 # define STATIC_ILOG2(_v) (((_v)&0xC)?2+STATIC_ILOG1((_v)>>2):STATIC_ILOG1(_v))
@@ -106,27 +146,5 @@ int ilog64(uint64_t _v) IDEMPOTENT_ATTRIBUTE;
  (((_v)&0xFFFF0000)?16+STATIC_ILOG4((_v)>>16):STATIC_ILOG4(_v))
 # define STATIC_ILOG6(_v) \
  (((_v)&0xFFFFFFFF00000000ULL)?32+STATIC_ILOG5((_v)>>32):STATIC_ILOG5(_v))
-/**
- * STATIC_ILOG_32 - The integer logarithm of an (unsigned, 32-bit) constant.
- * @_v: A non-negative 32-bit constant.
- * Returns floor(log2(_v))+1, or 0 if _v==0.
- * This is the number of bits that would be required to represent _v in two's
- *  complement notation with all of the leading zeros stripped.
- * This macro is suitable for evaluation at compile time, but it should not be
- *  used on values that can change at runtime, as it operates via exhaustive
- *  search.
- */
-# define STATIC_ILOG_32(_v) (STATIC_ILOG5((uint32_t)(_v)))
-/**
- * STATIC_ILOG_64 - The integer logarithm of an (unsigned, 64-bit) constant.
- * @_v: A non-negative 64-bit constant.
- * Returns floor(log2(_v))+1, or 0 if _v==0.
- * This is the number of bits that would be required to represent _v in two's
- *  complement notation with all of the leading zeros stripped.
- * This macro is suitable for evaluation at compile time, but it should not be
- *  used on values that can change at runtime, as it operates via exhaustive
- *  search.
- */
-# define STATIC_ILOG_64(_v) (STATIC_ILOG6((uint64_t)(_v)))
 
-#endif
+#endif /* _ilog_H */