util/bitset: Support larger ranges in BITSET_TEST/CLEAR_RANGE

Reviewed-by: Karol Herbst <kherbst@redhat.com>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/15988>

1 files changed, 40 insertions, 2 deletions

diff --git a/src/util/bitset.h b/src/util/bitset.h
index d8ec1af67ad..c1a3848f78d 100644
--- a/src/util/bitset.h
+++ b/src/util/bitset.h
@@ -192,7 +192,7 @@ __bitset_shl(BITSET_WORD *x, unsigned amount, unsigned n)
 
 /* bit range operations
  */
-#define BITSET_TEST_RANGE(x, b, e) \
+#define BITSET_TEST_RANGE_INSIDE_WORD(x, b, e) \
    (BITSET_BITWORD(b) == BITSET_BITWORD(e) ? \
    (((x)[BITSET_BITWORD(b)] & BITSET_RANGE(b, e)) != 0) : \
    (assert (!"BITSET_TEST_RANGE: bit range crosses word boundary"), 0))
@@ -200,11 +200,30 @@ __bitset_shl(BITSET_WORD *x, unsigned amount, unsigned n)
    (BITSET_BITWORD(b) == BITSET_BITWORD(e) ? \
    ((x)[BITSET_BITWORD(b)] |= BITSET_RANGE(b, e)) : \
    (assert (!"BITSET_SET_RANGE_INSIDE_WORD: bit range crosses word boundary"), 0))
-#define BITSET_CLEAR_RANGE(x, b, e) \
+#define BITSET_CLEAR_RANGE_INSIDE_WORD(x, b, e) \
    (BITSET_BITWORD(b) == BITSET_BITWORD(e) ? \
    ((x)[BITSET_BITWORD(b)] &= ~BITSET_RANGE(b, e)) : \
    (assert (!"BITSET_CLEAR_RANGE: bit range crosses word boundary"), 0))
 
+static inline bool
+__bitset_test_range(BITSET_WORD *r, unsigned start, unsigned end)
+{
+   const unsigned size = end - start + 1;
+   const unsigned start_mod = start % BITSET_WORDBITS;
+
+   if (start_mod + size <= BITSET_WORDBITS) {
+      return BITSET_TEST_RANGE_INSIDE_WORD(r, start, end);
+   } else {
+      const unsigned first_size = BITSET_WORDBITS - start_mod;
+
+      return __bitset_test_range(r, start, start + first_size - 1) ||
+             __bitset_test_range(r, start + first_size, end);
+   }
+}
+
+#define BITSET_TEST_RANGE(x, b, e) \
+   __bitset_test_range(x, b, e)
+
 static inline void
 __bitset_set_range(BITSET_WORD *r, unsigned start, unsigned end)
 {
@@ -224,6 +243,25 @@ __bitset_set_range(BITSET_WORD *r, unsigned start, unsigned end)
 #define BITSET_SET_RANGE(x, b, e) \
    __bitset_set_range(x, b, e)
 
+static inline void
+__bitclear_clear_range(BITSET_WORD *r, unsigned start, unsigned end)
+{
+   const unsigned size = end - start + 1;
+   const unsigned start_mod = start % BITSET_WORDBITS;
+
+   if (start_mod + size <= BITSET_WORDBITS) {
+      BITSET_CLEAR_RANGE_INSIDE_WORD(r, start, end);
+   } else {
+      const unsigned first_size = BITSET_WORDBITS - start_mod;
+
+      __bitclear_clear_range(r, start, start + first_size - 1);
+      __bitclear_clear_range(r, start + first_size, end);
+   }
+}
+
+#define BITSET_CLEAR_RANGE(x, b, e) \
+   __bitclear_clear_range(x, b, e)
+
 static inline unsigned
 __bitset_prefix_sum(const BITSET_WORD *x, unsigned b, unsigned n)
 {