This class provides a constant-size bitmap that can be used as almost a
drop-in replacement for bitmaps stored in integer types. The
implementation is entirely within the header file and uses recursive
templated operations to support effective optimisation and usage in
constexpr expressions.
This initial implementation hardcodes the choice of uint64_t elements
for storage and initialisation, but this could instead be specified via
a second template parameter.
gcc/ChangeLog:
* bbitmap.h: New file.
diff --git a/gcc/bbitmap.h b/gcc/bbitmap.h
new file mode 100644
index
0000000000000000000000000000000000000000..108ac1bf9e6042f5ae16988bc1688fe0045a3293
--- /dev/null
+++ b/gcc/bbitmap.h
@@ -0,0 +1,238 @@
+/* Functions to support fixed-length bitmaps.
+ Copyright (C) 2024 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+#ifndef GCC_BBITMAP_H
+#define GCC_BBITMAP_H
+
+/* Implementation of bounded (fixed length) bitmaps.
+
+ This provides a drop-in replacement for bitmaps that have outgrown the
+ storage capacity of a single integer.
+
+ Sets are stored as a fixed length array of uint64_t elements. The length of
+ this array is given as a template parameter. */
+
+template<int M>
+struct bbitmap_operators
+{
+ template<typename Result, typename Operator, typename Arg, typename ...Rest>
+ static constexpr Result binary(Operator op, const Arg &x, const Arg &y,
+ Rest ...rest)
+ {
+ return bbitmap_operators<M - 1>::template binary<Result, Operator, Arg>
+ (op, x, y, op (x.val[M - 1], y.val[M - 1]), rest...);
+ }
+
+ template<typename Operator, typename Arg, typename ...Rest>
+ static void compound(Operator op, Arg &x, const Arg &y)
+ {
+ bbitmap_operators<M - 1>::template compound<Operator, Arg> (op, x, y);
+ x.val[M - 1] = op (x.val[M - 1], y.val[M - 1]);
+ }
+
+ template<typename Result, typename Arg, typename ...Rest>
+ static constexpr Result bit_not(const Arg &x, Rest ...rest)
+ {
+ return bbitmap_operators<M - 1>::template bit_not<Result, Arg>
+ (x, ~(x.val[M - 1]), rest...);
+ }
+
+ template<typename Arg>
+ static constexpr bool non_zero(const Arg &x)
+ {
+ return (bool) x.val[M - 1]
+ || bbitmap_operators<M - 1>::template non_zero<Arg> (x);
+ }
+
+ template<typename Arg>
+ static constexpr bool equal(const Arg &x, const Arg &y)
+ {
+ return x.val[M - 1] == y.val[M - 1]
+ && bbitmap_operators<M - 1>::template equal<Arg> (x, y);
+ }
+
+#define SUB_INDEX(i) (i - (M - 1) * 64)
+#define IN_SUB_RANGE(i) (SUB_INDEX (i) >= 0 && SUB_INDEX (i) < 64)
+
+ template<typename Result, typename ...Rest>
+ static constexpr Result from_index(int index, Rest ...rest)
+ {
+ return bbitmap_operators<M - 1>::template from_index<Result>
+ (index,
+ (IN_SUB_RANGE (index)
+ ? (uint64_t (1) << (IN_SUB_RANGE (index) ? SUB_INDEX (index) : 0))
+ : uint64_t (0)),
+ rest...);
+ }
+
+#undef IN_SUB_RANGE
+#undef SUB_INDEX
+
+};
+
+template<>
+struct bbitmap_operators<0>
+{
+ template<typename Result, typename Operator, typename Arg, typename ...Rest>
+ static constexpr Result binary(Operator, const Arg, const Arg,
+ Rest ...rest)
+ {
+ return Result { rest... };
+ }
+
+ template<typename Operator, typename Arg, typename ...Rest>
+ static void compound(Operator, Arg, const Arg)
+ {
+ return;
+ }
+
+ template<typename Result, typename Arg, typename ...Rest>
+ static constexpr Result bit_not(const Arg, Rest ...rest)
+ {
+ return Result { rest... };
+ }
+
+ template<typename Arg>
+ static constexpr bool non_zero(const Arg)
+ {
+ return false;
+ }
+
+ template<typename Arg>
+ static constexpr bool equal(const Arg, const Arg)
+ {
+ return true;
+ }
+
+ template<typename Result, typename ...Rest>
+ static constexpr Result from_index(int, Rest ...rest)
+ {
+ return Result { rest... };
+ }
+};
+
+template<typename T>
+constexpr T bbitmap_element_or(T x, T y) { return x | y;}
+
+template<typename T>
+constexpr T bbitmap_element_and(T x, T y) { return x & y;}
+
+template<typename T>
+constexpr T bbitmap_element_xor(T x, T y) { return x ^ y;}
+
+
+
+template <int N>
+class GTY((user)) bbitmap
+{
+public:
+ uint64_t val[N];
+
+ template<typename... Rest>
+ constexpr bbitmap(Rest ...rest) : val{(uint64_t) rest...} {}
+
+ constexpr bbitmap<N> operator|(const bbitmap<N> other) const
+ {
+ return bbitmap_operators<N>::template
binary<bbitmap<N>>(bbitmap_element_or<uint64_t>,
+ *this, other);
+ }
+
+ bbitmap<N> operator|=(const bbitmap<N> other)
+ {
+ bbitmap_operators<N>::template compound (bbitmap_element_or<uint64_t>,
+ *this, other);
+ return this;
+ }
+
+ constexpr bbitmap<N> operator&(const bbitmap<N> other) const
+ {
+ return bbitmap_operators<N>::template
binary<bbitmap<N>>(bbitmap_element_and<uint64_t>,
+ *this, other);
+ }
+
+ bbitmap<N> operator&=(const bbitmap<N> other)
+ {
+ bbitmap_operators<N>::template compound (bbitmap_element_and<uint64_t>,
+ *this, other);
+ return this;
+ }
+
+ constexpr bbitmap<N> operator^(const bbitmap<N> other) const
+ {
+ return bbitmap_operators<N>::template
binary<bbitmap<N>>(bbitmap_element_xor<uint64_t>,
+ *this, other);
+ }
+
+ bbitmap<N> operator^=(const bbitmap<N> other)
+ {
+ bbitmap_operators<N>::template compound (bbitmap_element_xor<uint64_t>,
+ *this, other);
+ return this;
+ }
+
+ constexpr bbitmap<N> operator~() const
+ {
+ return bbitmap_operators<N>::template bit_not<bbitmap<N>>(*this);
+ }
+
+ constexpr bool operator!() const
+ {
+ return !(bbitmap_operators<N>::template non_zero<bbitmap<N>>(*this));
+ }
+
+ constexpr explicit operator bool() const
+ {
+ return bbitmap_operators<N>::template non_zero<bbitmap<N>>(*this);
+ }
+
+ constexpr bool operator==(const bbitmap<N> other) const
+ {
+ return bbitmap_operators<N>::template equal<bbitmap<N>>(*this, other);
+ }
+
+ constexpr bool operator!=(const bbitmap<N> other) const
+ {
+ return !(bbitmap_operators<N>::template equal<bbitmap<N>>(*this, other));
+ }
+
+ static constexpr bbitmap<N> from_index (int index)
+ {
+ return bbitmap_operators<N>::template from_index<bbitmap<N>> (index);
+ }
+};
+
+template<int N>
+void
+gt_ggc_mx (bbitmap<N> *)
+{
+}
+
+template<int N>
+void
+gt_pch_nx (bbitmap<N> *)
+{
+}
+
+template<int N>
+void
+gt_pch_nx (bbitmap<N> *, gt_pointer_operator, void *)
+{
+}
+
+#endif
