gcc/bbitmap.h

   1 /* Functions to support fixed-length bitmaps.
   2    Copyright (C) 2024 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #ifndef GCC_BBITMAP_H
  21 #define GCC_BBITMAP_H
  22
  23 /* Implementation of bounded (fixed length) bitmaps.
  24
  25    This provides a drop-in replacement for bitmaps that have outgrown the
  26    storage capacity of a single integer.
  27
  28    Sets are stored as a fixed length array of uint64_t elements.  The length of
  29    this array is given as a template parameter.  */
  30
  31 /* Use recusive templated functions to define constexpr operations.  */
  32 template<int M>
  33 struct bbitmap_operators
  34 {
  35   /* Return a result that maps binary operator OP to elements [0, M) of
  36      X and Y, and takes the remaining elements from REST.  */
  37   template<typename Result, typename Operator, typename Arg, typename ...Rest>
  38   static constexpr Result binary(Operator op, const Arg &x, const Arg &y,
  39                                  Rest ...rest)
  40   {
  41     return bbitmap_operators<M - 1>::template binary<Result, Operator, Arg>
  42       (op, x, y, op (x.val[M - 1], y.val[M - 1]), rest...);
  43   }
  44
  45   /* Return a result that contains the bitwise inverse of elements [0, M) of X,
  46      and takes the remaining elements from REST.  */
  47   template<typename Result, typename Arg, typename ...Rest>
  48   static constexpr Result bit_not(const Arg &x, Rest ...rest)
  49   {
  50     return bbitmap_operators<M - 1>::template bit_not<Result, Arg>
  51       (x, ~(x.val[M - 1]), rest...);
  52   }
  53
  54   /* Return true if any element [0, M) of X is nonzero.  */
  55   template<typename Arg>
  56   static constexpr bool non_zero(const Arg &x)
  57   {
  58     return (bool) x.val[M - 1]
  59       || bbitmap_operators<M - 1>::template non_zero<Arg> (x);
  60   }
  61
  62   /* Return true if elements [0, M) of X are all equal to the corresponding
  63      elements of Y.  */
  64   template<typename Arg>
  65   static constexpr bool equal(const Arg &x, const Arg &y)
  66   {
  67     return x.val[M - 1] == y.val[M - 1]
  68       && bbitmap_operators<M - 1>::template equal<Arg> (x, y);
  69   }
  70
  71   /* If bit index INDEX selects a bit in the first M elements, return a
  72      Result with that bit set and the other bits of the leading M elements
  73      clear.  Clear the leading M elements otherwise.  Take the remaining
  74      elements of the Result from REST.  */
  75   template<typename Result, typename ...Rest>
  76   static constexpr Result from_index(int index, Rest ...rest)
  77   {
  78     return bbitmap_operators<M - 1>::template from_index<Result>
  79       (index,
  80        uint64_t ((index - (M - 1) * 64) == (index & 63)) << (index & 63),
  81        rest...);
  82   }
  83 };
  84
  85 /* These functions form the base for the recursive functions above.  They
  86    return either bitmap containing the elements passed in REST, or a default
  87    bool result.  */
  88 template<>
  89 struct bbitmap_operators<0>
  90 {
  91   template<typename Result, typename Operator, typename Arg, typename ...Rest>
  92   static constexpr Result binary(Operator, const Arg, const Arg,
  93                                  Rest ...rest)
  94   {
  95     return Result { rest... };
  96   }
  97
  98   template<typename Result, typename Arg, typename ...Rest>
  99   static constexpr Result bit_not(const Arg, Rest ...rest)
 100   {
 101     return Result { rest... };
 102   }
 103
 104   template<typename Arg>
 105   static constexpr bool non_zero(const Arg)
 106   {
 107     return false;
 108   }
 109
 110   template<typename Arg>
 111   static constexpr bool equal(const Arg, const Arg)
 112   {
 113     return true;
 114   }
 115
 116   template<typename Result, typename ...Rest>
 117   static constexpr Result from_index(int, Rest ...rest)
 118   {
 119     return Result { rest... };
 120   }
 121 };
 122
 123 template<typename T>
 124 constexpr T bbitmap_element_or(T x, T y) { return x | y;}
 125
 126 template<typename T>
 127 constexpr T bbitmap_element_and(T x, T y) { return x & y;}
 128
 129 template<typename T>
 130 constexpr T bbitmap_element_xor(T x, T y) { return x ^ y;}
 131
 132
 133
 134 template <int N>
 135 class GTY((user)) bbitmap
 136 {
 137 public:
 138   uint64_t val[N];
 139
 140   template<typename... Rest>
 141   constexpr bbitmap(Rest ...rest) : val{(uint64_t) rest...} {}
 142
 143   constexpr bbitmap<N> operator|(const bbitmap<N> other) const
 144   {
 145     return bbitmap_operators<N>::template binary<bbitmap<N>>
 146       (bbitmap_element_or<uint64_t>, *this, other);
 147   }
 148
 149   bbitmap<N> operator|=(const bbitmap<N> other)
 150   {
 151     for (int i = 0; i < N; i++)
 152       val[i] |= other.val[i];
 153
 154     return this;
 155   }
 156
 157   constexpr bbitmap<N> operator&(const bbitmap<N> other) const
 158   {
 159     return bbitmap_operators<N>::template binary<bbitmap<N>>
 160       (bbitmap_element_and<uint64_t>, *this, other);
 161   }
 162
 163   bbitmap<N> operator&=(const bbitmap<N> other)
 164   {
 165     for (int i = 0; i < N; i++)
 166       val[i] &= other.val[i];
 167
 168     return this;
 169   }
 170
 171   constexpr bbitmap<N> operator^(const bbitmap<N> other) const
 172   {
 173     return bbitmap_operators<N>::template binary<bbitmap<N>>
 174       (bbitmap_element_xor<uint64_t>, *this, other);
 175   }
 176
 177   bbitmap<N> operator^=(const bbitmap<N> other)
 178   {
 179     for (int i = 0; i < N; i++)
 180       val[i] ^= other.val[i];
 181
 182     return this;
 183   }
 184
 185   constexpr bbitmap<N> operator~() const
 186   {
 187     return bbitmap_operators<N>::template bit_not<bbitmap<N>>(*this);
 188   }
 189
 190   constexpr bool operator!() const
 191   {
 192     return !(bbitmap_operators<N>::template non_zero<bbitmap<N>>(*this));
 193   }
 194
 195   constexpr explicit operator bool() const
 196   {
 197     return bbitmap_operators<N>::template non_zero<bbitmap<N>>(*this);
 198   }
 199
 200   constexpr bool operator==(const bbitmap<N> other) const
 201   {
 202     return bbitmap_operators<N>::template equal<bbitmap<N>>(*this, other);
 203   }
 204
 205   constexpr bool operator!=(const bbitmap<N> other) const
 206   {
 207     return !(bbitmap_operators<N>::template equal<bbitmap<N>>(*this, other));
 208   }
 209
 210   /* Return a bitmap with bit INDEX set and all other bits clear.  */
 211
 212   static constexpr bbitmap<N> from_index (int index)
 213   {
 214     return bbitmap_operators<N>::template from_index<bbitmap<N>> (index);
 215   }
 216 };
 217
 218 template<int N>
 219 void
 220 gt_ggc_mx (bbitmap<N> *)
 221 {
 222 }
 223
 224 template<int N>
 225 void
 226 gt_pch_nx (bbitmap<N> *)
 227 {
 228 }
 229
 230 template<int N>
 231 void
 232 gt_pch_nx (bbitmap<N> *, gt_pointer_operator, void *)
 233 {
 234 }
 235
 236 #endif