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