1 /*
2 * Copyright (c) 1999, 2025, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package com.sun.tools.javac.util;
27
28 import java.util.Arrays;
29
30 /** A class for extensible, mutable bit sets.
31 *
32 * <p><b>This is NOT part of any supported API.
33 * If you write code that depends on this, you do so at your own risk.
34 * This code and its internal interfaces are subject to change or
35 * deletion without notice.</b>
36 */
37 public class Bits {
38
39 // ____________ reset _________
40 // / UNKNOWN \ <-------- / UNINIT \
41 // \____________/ | \_________/
42 // | | |
43 // |assign | | any
44 // | ___________ |
45 // ------> / NORMAL \ <----
46 // \___________/ |
47 // | |
48 // | |
49 // -----------
50 // any
51 protected enum BitsState {
52 /* A Bits instance is in UNKNOWN state if it has been explicitly reset.
53 * It is possible to get to this state from any other by calling the
54 * reset method. An instance in the UNKNOWN state can pass to the
55 * NORMAL state after being assigned another Bits instance.
56 *
57 * Bits instances are final fields in Flow so the UNKNOWN state models
58 * the null assignment.
59 */
60 UNKNOWN,
61 /* A Bits instance is in UNINIT when it is created with the default
62 * constructor but it isn't explicitly reset. The main objective of this
63 * internal state is to save some memory.
64 */
65 UNINIT,
66 /* The normal state is reached after creating a Bits instance from an
67 * existing one or after applying any operation to an instance on UNINIT
68 * or NORMAL state. From this state a bits instance can pass to the
69 * UNKNOWN state by calling the reset method.
70 */
71 NORMAL;
72
73 static BitsState getState(int[] someBits, boolean reset) {
74 if (reset) {
75 return UNKNOWN;
76 } else {
77 if (someBits != unassignedBits) {
78 return NORMAL;
79 } else {
80 return UNINIT;
81 }
82 }
83 }
84
85 }
86
87 private static final int wordlen = 32;
88 private static final int wordshift = 5;
89 private static final int wordmask = wordlen - 1;
90
91 /* every int in the bits array is used to represent 32 bits, so the bits array will have
92 * length == 1 until we need to represent the 33rd bit and so on.
93 */
94 private int[] bits = null;
95 // This field will store last version of bits after every change.
96 private static final int[] unassignedBits = new int[0];
97
98 protected BitsState currentState;
99
100 /** Construct an initially empty set.
101 */
102 public Bits() {
103 this(false);
104 }
105
106 public Bits(Bits someBits) {
107 this(someBits.dup().bits, BitsState.getState(someBits.bits, false));
108 }
109
110 public Bits(boolean reset) {
111 this(unassignedBits, BitsState.getState(unassignedBits, reset));
112 }
113
114 /** Construct a set consisting initially of given bit vector.
115 */
116 protected Bits(int[] bits, BitsState initState) {
117 this.bits = bits;
118 this.currentState = initState;
119 switch (initState) {
120 case UNKNOWN:
121 this.bits = null;
122 break;
123 case NORMAL:
124 Assert.check(bits != unassignedBits);
125 break;
126 }
127 }
128
129 protected void sizeTo(int len) {
130 if (bits.length < len) {
131 bits = Arrays.copyOf(bits, len);
132 }
133 }
134
135 /** This set = {}.
136 */
137 public void clear() {
138 Assert.check(currentState != BitsState.UNKNOWN);
139 for (int i = 0; i < bits.length; i++) {
140 bits[i] = 0;
141 }
142 currentState = BitsState.NORMAL;
143 }
144
145 public void reset() {
146 internalReset();
147 }
148
149 protected void internalReset() {
150 bits = null;
151 currentState = BitsState.UNKNOWN;
152 }
153
154 public boolean isReset() {
155 return currentState == BitsState.UNKNOWN;
156 }
157
158 public Bits assign(Bits someBits) {
159 bits = someBits.dup().bits;
160 currentState = BitsState.NORMAL;
161 return this;
162 }
163
164 /** Return a copy of this set.
165 */
166 public Bits dup() {
167 Assert.check(currentState != BitsState.UNKNOWN);
168 Bits tmp = new Bits();
169 tmp.bits = dupBits();
170 currentState = BitsState.NORMAL;
171 return tmp;
172 }
173
174 protected int[] dupBits() {
175 int [] result;
176 if (currentState != BitsState.NORMAL) {
177 result = bits;
178 } else {
179 result = new int[bits.length];
180 System.arraycopy(bits, 0, result, 0, bits.length);
181 }
182 return result;
183 }
184
185 /** Include x in this set.
186 */
187 public void incl(int x) {
188 Assert.check(currentState != BitsState.UNKNOWN);
189 Assert.check(x >= 0);
190 sizeTo((x >>> wordshift) + 1);
191 bits[x >>> wordshift] = bits[x >>> wordshift] |
192 (1 << (x & wordmask));
193 currentState = BitsState.NORMAL;
194 }
195
196
197 /** Include [start..limit) in this set.
198 */
199 public void inclRange(int start, int limit) {
200 Assert.check(currentState != BitsState.UNKNOWN);
201 sizeTo((limit >>> wordshift) + 1);
202 for (int x = start; x < limit; x++) {
203 bits[x >>> wordshift] = bits[x >>> wordshift] |
204 (1 << (x & wordmask));
205 }
206 currentState = BitsState.NORMAL;
207 }
208
209 /** Exclude [start...end] from this set.
210 */
211 public void excludeFrom(int start) {
212 Assert.check(currentState != BitsState.UNKNOWN);
213 Bits temp = new Bits();
214 temp.sizeTo(bits.length);
215 temp.inclRange(0, start);
216 internalAndSet(temp);
217 currentState = BitsState.NORMAL;
218 }
219
220 /** Exclude x from this set.
221 */
222 public void excl(int x) {
223 Assert.check(currentState != BitsState.UNKNOWN);
224 Assert.check(x >= 0);
225 sizeTo((x >>> wordshift) + 1);
226 bits[x >>> wordshift] = bits[x >>> wordshift] &
227 ~(1 << (x & wordmask));
228 currentState = BitsState.NORMAL;
229 }
230
231 /** Is x an element of this set?
232 */
233 public boolean isMember(int x) {
234 Assert.check(currentState != BitsState.UNKNOWN);
235 return
236 0 <= x && x < (bits.length << wordshift) &&
237 (bits[x >>> wordshift] & (1 << (x & wordmask))) != 0;
238 }
239
240 /** {@literal this set = this set & xs}.
241 */
242 public Bits andSet(Bits xs) {
243 Assert.check(currentState != BitsState.UNKNOWN);
244 internalAndSet(xs);
245 currentState = BitsState.NORMAL;
246 return this;
247 }
248
249 protected void internalAndSet(Bits xs) {
250 Assert.check(currentState != BitsState.UNKNOWN);
251 sizeTo(xs.bits.length);
252 for (int i = 0; i < xs.bits.length; i++) {
253 bits[i] = bits[i] & xs.bits[i];
254 }
255 }
256
257 /** this set = this set | xs.
258 */
259 public Bits orSet(Bits xs) {
260 Assert.check(currentState != BitsState.UNKNOWN);
261 sizeTo(xs.bits.length);
262 for (int i = 0; i < xs.bits.length; i++) {
263 bits[i] = bits[i] | xs.bits[i];
264 }
265 currentState = BitsState.NORMAL;
266 return this;
267 }
268
269 /** this set = this set \ xs.
270 */
271 public Bits diffSet(Bits xs) {
272 Assert.check(currentState != BitsState.UNKNOWN);
273 for (int i = 0; i < bits.length; i++) {
274 if (i < xs.bits.length) {
275 bits[i] = bits[i] & ~xs.bits[i];
276 }
277 }
278 currentState = BitsState.NORMAL;
279 return this;
280 }
281
282 /** this set = this set ^ xs.
283 */
284 public Bits xorSet(Bits xs) {
285 Assert.check(currentState != BitsState.UNKNOWN);
286 sizeTo(xs.bits.length);
287 for (int i = 0; i < xs.bits.length; i++) {
288 bits[i] = bits[i] ^ xs.bits[i];
289 }
290 currentState = BitsState.NORMAL;
291 return this;
292 }
293
294 /** Count trailing zero bits in an int. Algorithm from "Hacker's
295 * Delight" by Henry S. Warren Jr. (figure 5-13)
296 */
297 private static int trailingZeroBits(int x) {
298 Assert.check(wordlen == 32);
299 if (x == 0) {
300 return 32;
301 }
302 int n = 1;
303 if ((x & 0xffff) == 0) { n += 16; x >>>= 16; }
304 if ((x & 0x00ff) == 0) { n += 8; x >>>= 8; }
305 if ((x & 0x000f) == 0) { n += 4; x >>>= 4; }
306 if ((x & 0x0003) == 0) { n += 2; x >>>= 2; }
307 return n - (x&1);
308 }
309
310 /** Return the index of the least bit position ≥ x that is set.
311 * If none are set, returns -1. This provides a nice way to iterate
312 * over the members of a bit set:
313 * <pre>{@code
314 * for (int i = bits.nextBit(0); i>=0; i = bits.nextBit(i+1)) ...
315 * }</pre>
316 */
317 public int nextBit(int x) {
318 Assert.check(currentState != BitsState.UNKNOWN);
319 int windex = x >>> wordshift;
320 if (windex >= bits.length) {
321 return -1;
322 }
323 int word = bits[windex] & ~((1 << (x & wordmask))-1);
324 while (true) {
325 if (word != 0) {
326 return (windex << wordshift) + trailingZeroBits(word);
327 }
328 windex++;
329 if (windex >= bits.length) {
330 return -1;
331 }
332 word = bits[windex];
333 }
334 }
335
336 /** a string representation of this set.
337 */
338 @Override
339 public String toString() {
340 if (bits != null && bits.length > 0) {
341 char[] digits = new char[bits.length * wordlen];
342 for (int i = 0; i < bits.length * wordlen; i++) {
343 digits[i] = isMember(i) ? '1' : '0';
344 }
345 return new String(digits);
346 } else {
347 return "[]";
348 }
349 }
350
351 }