1 /*
2 * Copyright (c) 1999, 2015, 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 public int[] bits = null;
92 // This field will store last version of bits after every change.
93 private static final int[] unassignedBits = new int[0];
94
95 protected BitsState currentState;
96
97 /** Construct an initially empty set.
98 */
99 public Bits() {
100 this(false);
101 }
102
103 public Bits(Bits someBits) {
104 this(someBits.dup().bits, BitsState.getState(someBits.bits, false));
105 }
106
107 public Bits(boolean reset) {
108 this(unassignedBits, BitsState.getState(unassignedBits, reset));
109 }
110
111 /** Construct a set consisting initially of given bit vector.
112 */
113 protected Bits(int[] bits, BitsState initState) {
114 this.bits = bits;
115 this.currentState = initState;
116 switch (initState) {
117 case UNKNOWN:
118 this.bits = null;
119 break;
120 case NORMAL:
121 Assert.check(bits != unassignedBits);
122 break;
123 }
124 }
125
126 protected void sizeTo(int len) {
127 if (bits.length < len) {
128 bits = Arrays.copyOf(bits, len);
129 }
130 }
131
132 /** This set = {}.
133 */
134 public void clear() {
135 Assert.check(currentState != BitsState.UNKNOWN);
136 for (int i = 0; i < bits.length; i++) {
137 bits[i] = 0;
138 }
139 currentState = BitsState.NORMAL;
140 }
141
142 public void reset() {
143 internalReset();
144 }
145
146 protected void internalReset() {
147 bits = null;
148 currentState = BitsState.UNKNOWN;
149 }
150
151 public boolean isReset() {
152 return currentState == BitsState.UNKNOWN;
153 }
154
155 public Bits assign(Bits someBits) {
156 bits = someBits.dup().bits;
157 currentState = BitsState.NORMAL;
158 return this;
159 }
160
161 /** Return a copy of this set.
162 */
163 public Bits dup() {
164 Assert.check(currentState != BitsState.UNKNOWN);
165 Bits tmp = new Bits();
166 tmp.bits = dupBits();
167 currentState = BitsState.NORMAL;
168 return tmp;
169 }
170
171 protected int[] dupBits() {
172 int [] result;
173 if (currentState != BitsState.NORMAL) {
174 result = bits;
175 } else {
176 result = new int[bits.length];
177 System.arraycopy(bits, 0, result, 0, bits.length);
178 }
179 return result;
180 }
181
182 /** Include x in this set.
183 */
184 public void incl(int x) {
185 Assert.check(currentState != BitsState.UNKNOWN);
186 Assert.check(x >= 0);
187 sizeTo((x >>> wordshift) + 1);
188 bits[x >>> wordshift] = bits[x >>> wordshift] |
189 (1 << (x & wordmask));
190 currentState = BitsState.NORMAL;
191 }
192
193
194 /** Include [start..limit) in this set.
195 */
196 public void inclRange(int start, int limit) {
197 Assert.check(currentState != BitsState.UNKNOWN);
198 sizeTo((limit >>> wordshift) + 1);
199 for (int x = start; x < limit; x++) {
200 bits[x >>> wordshift] = bits[x >>> wordshift] |
201 (1 << (x & wordmask));
202 }
203 currentState = BitsState.NORMAL;
204 }
205
206 /** Exclude [start...end] from this set.
207 */
208 public void excludeFrom(int start) {
209 Assert.check(currentState != BitsState.UNKNOWN);
210 Bits temp = new Bits();
211 temp.sizeTo(bits.length);
212 temp.inclRange(0, start);
213 internalAndSet(temp);
214 currentState = BitsState.NORMAL;
215 }
216
217 /** Exclude x from this set.
218 */
219 public void excl(int x) {
220 Assert.check(currentState != BitsState.UNKNOWN);
221 Assert.check(x >= 0);
222 sizeTo((x >>> wordshift) + 1);
223 bits[x >>> wordshift] = bits[x >>> wordshift] &
224 ~(1 << (x & wordmask));
225 currentState = BitsState.NORMAL;
226 }
227
228 /** Is x an element of this set?
229 */
230 public boolean isMember(int x) {
231 Assert.check(currentState != BitsState.UNKNOWN);
232 return
233 0 <= x && x < (bits.length << wordshift) &&
234 (bits[x >>> wordshift] & (1 << (x & wordmask))) != 0;
235 }
236
237 /** {@literal this set = this set & xs}.
238 */
239 public Bits andSet(Bits xs) {
240 Assert.check(currentState != BitsState.UNKNOWN);
241 internalAndSet(xs);
242 currentState = BitsState.NORMAL;
243 return this;
244 }
245
246 protected void internalAndSet(Bits xs) {
247 Assert.check(currentState != BitsState.UNKNOWN);
248 sizeTo(xs.bits.length);
249 for (int i = 0; i < xs.bits.length; i++) {
250 bits[i] = bits[i] & xs.bits[i];
251 }
252 }
253
254 /** this set = this set | xs.
255 */
256 public Bits orSet(Bits xs) {
257 Assert.check(currentState != BitsState.UNKNOWN);
258 sizeTo(xs.bits.length);
259 for (int i = 0; i < xs.bits.length; i++) {
260 bits[i] = bits[i] | xs.bits[i];
261 }
262 currentState = BitsState.NORMAL;
263 return this;
264 }
265
266 /** this set = this set \ xs.
267 */
268 public Bits diffSet(Bits xs) {
269 Assert.check(currentState != BitsState.UNKNOWN);
270 for (int i = 0; i < bits.length; i++) {
271 if (i < xs.bits.length) {
272 bits[i] = bits[i] & ~xs.bits[i];
273 }
274 }
275 currentState = BitsState.NORMAL;
276 return this;
277 }
278
279 /** this set = this set ^ xs.
280 */
281 public Bits xorSet(Bits xs) {
282 Assert.check(currentState != BitsState.UNKNOWN);
283 sizeTo(xs.bits.length);
284 for (int i = 0; i < xs.bits.length; i++) {
285 bits[i] = bits[i] ^ xs.bits[i];
286 }
287 currentState = BitsState.NORMAL;
288 return this;
289 }
290
291 /** Count trailing zero bits in an int. Algorithm from "Hacker's
292 * Delight" by Henry S. Warren Jr. (figure 5-13)
293 */
294 private static int trailingZeroBits(int x) {
295 Assert.check(wordlen == 32);
296 if (x == 0) {
297 return 32;
298 }
299 int n = 1;
300 if ((x & 0xffff) == 0) { n += 16; x >>>= 16; }
301 if ((x & 0x00ff) == 0) { n += 8; x >>>= 8; }
302 if ((x & 0x000f) == 0) { n += 4; x >>>= 4; }
303 if ((x & 0x0003) == 0) { n += 2; x >>>= 2; }
304 return n - (x&1);
305 }
306
307 /** Return the index of the least bit position ≥ x that is set.
308 * If none are set, returns -1. This provides a nice way to iterate
309 * over the members of a bit set:
310 * <pre>{@code
311 * for (int i = bits.nextBit(0); i>=0; i = bits.nextBit(i+1)) ...
312 * }</pre>
313 */
314 public int nextBit(int x) {
315 Assert.check(currentState != BitsState.UNKNOWN);
316 int windex = x >>> wordshift;
317 if (windex >= bits.length) {
318 return -1;
319 }
320 int word = bits[windex] & ~((1 << (x & wordmask))-1);
321 while (true) {
322 if (word != 0) {
323 return (windex << wordshift) + trailingZeroBits(word);
324 }
325 windex++;
326 if (windex >= bits.length) {
327 return -1;
328 }
329 word = bits[windex];
330 }
331 }
332
333 /** a string representation of this set.
334 */
335 @Override
336 public String toString() {
337 if (bits != null && bits.length > 0) {
338 char[] digits = new char[bits.length * wordlen];
339 for (int i = 0; i < bits.length * wordlen; i++) {
340 digits[i] = isMember(i) ? '1' : '0';
341 }
342 return new String(digits);
343 } else {
344 return "[]";
345 }
346 }
347
348 }