Sync AVL tree code from project

[wimlib] / include / wimlib / bitops.h

diff --git a/include/wimlib/bitops.h b/include/wimlib/bitops.h
index 70e6c611a888c68feb76ddbb627c57a4d2b89c54..1fc30f6c69a1b9a03e0987e215ffe5abe5900340 100644 (file)
--- a/include/wimlib/bitops.h
+++ b/include/wimlib/bitops.h
@@ -24,13 +24,17 @@
 #include "wimlib/compiler.h"
 #include "wimlib/types.h"
 
-/* Find Last Set bit   */
+/*
+ * Bit Scan Reverse (BSR) - find the 0-based index (relative to the least
+ * significant bit) of the *most* significant 1 bit in the input value.  The
+ * input value must be nonzero!
+ */
 
-static inline unsigned
-fls32(u32 v)
+static forceinline unsigned
+bsr32(u32 v)
 {
-#ifdef compiler_fls32
-       return compiler_fls32(v);
+#ifdef compiler_bsr32
+       return compiler_bsr32(v);
 #else
        unsigned bit = 0;
        while ((v >>= 1) != 0)
@@ -39,11 +43,11 @@ fls32(u32 v)
 #endif
 }
 
-static inline unsigned
-fls64(u64 v)
+static forceinline unsigned
+bsr64(u64 v)
 {
-#ifdef compiler_fls64
-       return compiler_fls64(v);
+#ifdef compiler_bsr64
+       return compiler_bsr64(v);
 #else
        unsigned bit = 0;
        while ((v >>= 1) != 0)
@@ -52,23 +56,27 @@ fls64(u64 v)
 #endif
 }
 
-static inline unsigned
-flsw(machine_word_t v)
+static forceinline unsigned
+bsrw(machine_word_t v)
 {
-       STATIC_ASSERT(WORDSIZE == 4 || WORDSIZE == 8);
-       if (WORDSIZE == 4)
-               return fls32(v);
+       STATIC_ASSERT(WORDBITS == 32 || WORDBITS == 64);
+       if (WORDBITS == 32)
+               return bsr32(v);
        else
-               return fls64(v);
+               return bsr64(v);
 }
 
-/* Find First Set bit   */
+/*
+ * Bit Scan Forward (BSF) - find the 0-based index (relative to the least
+ * significant bit) of the *least* significant 1 bit in the input value.  The
+ * input value must be nonzero!
+ */
 
-static inline unsigned
-ffs32(u32 v)
+static forceinline unsigned
+bsf32(u32 v)
 {
-#ifdef compiler_ffs32
-       return compiler_ffs32(v);
+#ifdef compiler_bsf32
+       return compiler_bsf32(v);
 #else
        unsigned bit;
        for (bit = 0; !(v & 1); bit++, v >>= 1)
@@ -77,11 +85,11 @@ ffs32(u32 v)
 #endif
 }
 
-static inline unsigned
-ffs64(u64 v)
+static forceinline unsigned
+bsf64(u64 v)
 {
-#ifdef compiler_ffs64
-       return compiler_ffs64(v);
+#ifdef compiler_bsf64
+       return compiler_bsf64(v);
 #else
        unsigned bit;
        for (bit = 0; !(v & 1); bit++, v >>= 1)
@@ -90,24 +98,30 @@ ffs64(u64 v)
 #endif
 }
 
-static inline unsigned
-ffsw(machine_word_t v)
+static forceinline unsigned
+bsfw(machine_word_t v)
 {
-       STATIC_ASSERT(WORDSIZE == 4 || WORDSIZE == 8);
-       if (WORDSIZE == 4)
-               return ffs32(v);
+       STATIC_ASSERT(WORDBITS == 32 || WORDBITS == 64);
+       if (WORDBITS == 32)
+               return bsf32(v);
        else
-               return ffs64(v);
+               return bsf64(v);
 }
 
-/* Round up to nearest power of 2  */
+/* Return the log base 2 of 'n', rounded up to the nearest integer. */
+static forceinline unsigned
+ilog2_ceil(size_t n)
+{
+        if (n <= 1)
+                return 0;
+        return 1 + bsrw(n - 1);
+}
 
-static inline size_t
+/* Round 'n' up to the nearest power of 2 */
+static forceinline size_t
 roundup_pow_of_2(size_t n)
 {
-       if (n <= 1)
-               return 1;
-       return (size_t)1 << (1 + flsw(n - 1));
+       return (size_t)1 << ilog2_ceil(n);
 }
 
 #endif /* _WIMLIB_BITOPS_H */