util: add BITSET_LAST_BIT() helper

[mesa.git] / src / util / bitset.h

diff --git a/src/util/bitset.h b/src/util/bitset.h
index 7bb5f3c83cfdb811e00d426d6ef0a7ab6dee41a3..012764afc42a725fd8722d136117734a1e20dfaa 100644 (file)
--- a/src/util/bitset.h
+++ b/src/util/bitset.h
@@ -31,7 +31,8 @@
 #ifndef BITSET_H
 #define BITSET_H
 
-#include "util/u_math.h"
+#include "util/bitscan.h"
+#include "util/macros.h"
 
 /****************************************************************************
  * generic bitset implementation
@@ -53,22 +54,22 @@
 #define BITSET_ONES(x) memset( (x), 0xff, sizeof (x) )
 
 #define BITSET_BITWORD(b) ((b) / BITSET_WORDBITS)
-#define BITSET_BIT(b) (1 << ((b) % BITSET_WORDBITS))
+#define BITSET_BIT(b) (1u << ((b) % BITSET_WORDBITS))
 
 /* single bit operations
  */
-#define BITSET_TEST(x, b) ((x)[BITSET_BITWORD(b)] & BITSET_BIT(b))
+#define BITSET_TEST(x, b) (((x)[BITSET_BITWORD(b)] & BITSET_BIT(b)) != 0)
 #define BITSET_SET(x, b) ((x)[BITSET_BITWORD(b)] |= BITSET_BIT(b))
 #define BITSET_CLEAR(x, b) ((x)[BITSET_BITWORD(b)] &= ~BITSET_BIT(b))
 
-#define BITSET_MASK(b) ((b) == BITSET_WORDBITS ? ~0 : BITSET_BIT(b) - 1)
-#define BITSET_RANGE(b, e) (BITSET_MASK((e) + 1) & ~BITSET_MASK(b))
+#define BITSET_MASK(b) (((b) % BITSET_WORDBITS == 0) ? ~0 : BITSET_BIT(b) - 1)
+#define BITSET_RANGE(b, e) ((BITSET_MASK((e) + 1)) & ~(BITSET_BIT(b) - 1))
 
 /* bit range operations
  */
 #define BITSET_TEST_RANGE(x, b, e) \
    (BITSET_BITWORD(b) == BITSET_BITWORD(e) ? \
-   ((x)[BITSET_BITWORD(b)] & BITSET_RANGE(b, e)) : \
+   (((x)[BITSET_BITWORD(b)] & BITSET_RANGE(b, e)) != 0) : \
    (assert (!"BITSET_TEST_RANGE: bit range crosses word boundary"), 0))
 #define BITSET_SET_RANGE(x, b, e) \
    (BITSET_BITWORD(b) == BITSET_BITWORD(e) ? \
@@ -94,7 +95,21 @@ __bitset_ffs(const BITSET_WORD *x, int n)
    return 0;
 }
 
+/* Get the last bit set in a bitset.
+ */
+static inline int
+__bitset_last_bit(const BITSET_WORD *x, int n)
+{
+   for (int i = n - 1; i >= 0; i--) {
+      if (x[i])
+         return util_last_bit(x[i]) + BITSET_WORDBITS * i;
+   }
+
+   return 0;
+}
+
 #define BITSET_FFS(x) __bitset_ffs(x, ARRAY_SIZE(x))
+#define BITSET_LAST_BIT(x, size) __bitset_last_bit(x, size)
 
 static inline unsigned
 __bitset_next_set(unsigned i, BITSET_WORD *tmp,
@@ -128,9 +143,17 @@ __bitset_next_set(unsigned i, BITSET_WORD *tmp,
    return word * BITSET_WORDBITS + bit;
 }
 
-#define BITSET_FOREACH_SET(__i, __tmp, __set, __size) \
-   for (__tmp = *(__set), __i = 0; \
-        (__i = __bitset_next_set(__i, &__tmp, __set, __size)) < __size;)
+/**
+ * Iterates over each set bit in a set
+ *
+ * @param __i    iteration variable, bit number
+ * @param __set  the bitset to iterate (will not be modified)
+ * @param __size number of bits in the set to consider
+ */
+#define BITSET_FOREACH_SET(__i, __set, __size) \
+   for (BITSET_WORD __tmp = *(__set), *__foo = &__tmp; __foo != NULL; __foo = NULL) \
+      for (__i = 0; \
+           (__i = __bitset_next_set(__i, &__tmp, __set, __size)) < __size;)
 
 #ifdef __cplusplus
 
@@ -142,23 +165,6 @@ __bitset_next_set(unsigned i, BITSET_WORD *tmp,
  * it as, and N is the number of bits in the bitset.
  */
 #define DECLARE_BITSET_T(T, N) struct T {                       \
-      /* XXX - Replace this with an implicitly-defined          \
-       * constructor when support for C++11 defaulted           \
-       * constructors can be assumed (available on GCC 4.4 and  \
-       * later) in order to make the object trivially           \
-       * constructible like a fundamental integer type for      \
-       * convenience.                                           \
-       */                                                       \
-      T()                                                       \
-      {                                                         \
-      }                                                         \
-                                                                \
-      T(BITSET_WORD x)                                          \
-      {                                                         \
-         for (unsigned i = 0; i < BITSET_WORDS(N); i++, x = 0)  \
-            words[i] = x;                                       \
-      }                                                         \
-                                                                \
       EXPLICIT_CONVERSION                                       \
       operator bool() const                                     \
       {                                                         \
@@ -168,6 +174,13 @@ __bitset_next_set(unsigned i, BITSET_WORD *tmp,
          return false;                                          \
       }                                                         \
                                                                 \
+      T &                                                       \
+      operator=(int x)                                          \
+      {                                                         \
+         const T c = {{ (BITSET_WORD)x }};                      \
+         return *this = c;                                      \
+      }                                                         \
+                                                                \
       friend bool                                               \
       operator==(const T &b, const T &c)                        \
       {                                                         \
@@ -180,6 +193,19 @@ __bitset_next_set(unsigned i, BITSET_WORD *tmp,
          return !(b == c);                                      \
       }                                                         \
                                                                 \
+      friend bool                                               \
+      operator==(const T &b, int x)                             \
+      {                                                         \
+         const T c = {{ (BITSET_WORD)x }};                      \
+         return b == c;                                         \
+      }                                                         \
+                                                                \
+      friend bool                                               \
+      operator!=(const T &b, int x)                             \
+      {                                                         \
+         return !(b == x);                                      \
+      }                                                         \
+                                                                \
       friend T                                                  \
       operator~(const T &b)                                     \
       {                                                         \