Line data Source code
1 : /* Functions to support fixed-length bitmaps.
2 : Copyright (C) 2024-2026 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 1333667010 : 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 1200300309 : (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 1333667010 : static constexpr bool non_zero(const Arg &x)
57 : {
58 1333667010 : return (bool) x.val[M - 1]
59 622377938 : || 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 1066933608 : static constexpr Result from_index(int index, Rest ...rest)
77 : {
78 : return bbitmap_operators<M - 1>::template from_index<Result>
79 1066933608 : (index,
80 1066933608 : uint64_t ((index - (M - 1) * 64) == (index & 63)) << (index & 63),
81 1066933608 : 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 44455567 : static constexpr Result binary(Operator, const Arg, const Arg,
93 : Rest ...rest)
94 : {
95 44455567 : 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 44455567 : static constexpr Result from_index(int, Rest ...rest)
118 : {
119 44455567 : 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 1333667010 : 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 24987608 : 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 41606789 : bbitmap<N> operator|=(const bbitmap<N> other)
150 : {
151 1289810459 : for (int i = 0; i < N; i++)
152 1248203670 : val[i] |= other.val[i];
153 :
154 41606789 : return this;
155 : }
156 :
157 44455567 : constexpr bbitmap<N> operator&(const bbitmap<N> other) const
158 : {
159 : return bbitmap_operators<N>::template binary<bbitmap<N>>
160 44455567 : (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 44455567 : constexpr explicit operator bool() const
196 : {
197 44455567 : 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 44455567 : static constexpr bbitmap<N> from_index (int index)
213 : {
214 44455567 : 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
|
