Mercurial > jdk8-mips64-public > langtools / file revision
src/share/classes/com/sun/tools/javac/util/Bits.java@d4051d4f5daf
src/share/classes/com/sun/tools/javac/util/Bits.java
Wed, 10 Jun 2015 14:22:04 -0700
- author
- mfang
- date
- Wed, 10 Jun 2015 14:22:04 -0700
- changeset 2815
- d4051d4f5daf
- parent 2566
- 58e7e71b302e
- child 2702
- 9ca8d8713094
- child 2820
- 7f6d6b80a58b
- permissions
- -rw-r--r--
8083601: jdk8u60 l10n resource file translation update 2
Reviewed-by: ksrini, yhuang
1 /*
2 * Copyright (c) 1999, 2013, 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 */
26 package com.sun.tools.javac.util;
28 import java.util.Arrays;
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 {
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;
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 }
85 }
87 public enum BitsOpKind {
88 INIT,
89 CLEAR,
90 INCL_BIT,
91 EXCL_BIT,
92 ASSIGN,
93 AND_SET,
94 OR_SET,
95 DIFF_SET,
96 XOR_SET,
97 INCL_RANGE,
98 EXCL_RANGE,
99 }
101 private final static int wordlen = 32;
102 private final static int wordshift = 5;
103 private final static int wordmask = wordlen - 1;
105 public int[] bits = null;
106 // This field will store last version of bits after every change.
107 private static final int[] unassignedBits = new int[0];
109 protected BitsState currentState;
111 /** Construct an initially empty set.
112 */
113 public Bits() {
114 this(false);
115 }
117 public Bits(Bits someBits) {
118 this(someBits.dup().bits, BitsState.getState(someBits.bits, false));
119 }
121 public Bits(boolean reset) {
122 this(unassignedBits, BitsState.getState(unassignedBits, reset));
123 }
125 /** Construct a set consisting initially of given bit vector.
126 */
127 protected Bits(int[] bits, BitsState initState) {
128 this.bits = bits;
129 this.currentState = initState;
130 switch (initState) {
131 case UNKNOWN:
132 this.bits = null;
133 break;
134 case NORMAL:
135 Assert.check(bits != unassignedBits);
136 break;
137 }
138 }
140 protected void sizeTo(int len) {
141 if (bits.length < len) {
142 bits = Arrays.copyOf(bits, len);
143 }
144 }
146 /** This set = {}.
147 */
148 public void clear() {
149 Assert.check(currentState != BitsState.UNKNOWN);
150 for (int i = 0; i < bits.length; i++) {
151 bits[i] = 0;
152 }
153 currentState = BitsState.NORMAL;
154 }
156 public void reset() {
157 internalReset();
158 }
160 protected void internalReset() {
161 bits = null;
162 currentState = BitsState.UNKNOWN;
163 }
165 public boolean isReset() {
166 return currentState == BitsState.UNKNOWN;
167 }
169 public Bits assign(Bits someBits) {
170 bits = someBits.dup().bits;
171 currentState = BitsState.NORMAL;
172 return this;
173 }
175 /** Return a copy of this set.
176 */
177 public Bits dup() {
178 Assert.check(currentState != BitsState.UNKNOWN);
179 Bits tmp = new Bits();
180 tmp.bits = dupBits();
181 currentState = BitsState.NORMAL;
182 return tmp;
183 }
185 protected int[] dupBits() {
186 int [] result;
187 if (currentState != BitsState.NORMAL) {
188 result = bits;
189 } else {
190 result = new int[bits.length];
191 System.arraycopy(bits, 0, result, 0, bits.length);
192 }
193 return result;
194 }
196 /** Include x in this set.
197 */
198 public void incl(int x) {
199 Assert.check(currentState != BitsState.UNKNOWN);
200 Assert.check(x >= 0, "Value of x " + x);
201 sizeTo((x >>> wordshift) + 1);
202 bits[x >>> wordshift] = bits[x >>> wordshift] |
203 (1 << (x & wordmask));
204 currentState = BitsState.NORMAL;
205 }
208 /** Include [start..limit) in this set.
209 */
210 public void inclRange(int start, int limit) {
211 Assert.check(currentState != BitsState.UNKNOWN);
212 sizeTo((limit >>> wordshift) + 1);
213 for (int x = start; x < limit; x++) {
214 bits[x >>> wordshift] = bits[x >>> wordshift] |
215 (1 << (x & wordmask));
216 }
217 currentState = BitsState.NORMAL;
218 }
220 /** Exclude [start...end] from this set.
221 */
222 public void excludeFrom(int start) {
223 Assert.check(currentState != BitsState.UNKNOWN);
224 Bits temp = new Bits();
225 temp.sizeTo(bits.length);
226 temp.inclRange(0, start);
227 internalAndSet(temp);
228 currentState = BitsState.NORMAL;
229 }
231 /** Exclude x from this set.
232 */
233 public void excl(int x) {
234 Assert.check(currentState != BitsState.UNKNOWN);
235 Assert.check(x >= 0);
236 sizeTo((x >>> wordshift) + 1);
237 bits[x >>> wordshift] = bits[x >>> wordshift] &
238 ~(1 << (x & wordmask));
239 currentState = BitsState.NORMAL;
240 }
242 /** Is x an element of this set?
243 */
244 public boolean isMember(int x) {
245 Assert.check(currentState != BitsState.UNKNOWN);
246 return
247 0 <= x && x < (bits.length << wordshift) &&
248 (bits[x >>> wordshift] & (1 << (x & wordmask))) != 0;
249 }
251 /** {@literal this set = this set & xs}.
252 */
253 public Bits andSet(Bits xs) {
254 Assert.check(currentState != BitsState.UNKNOWN);
255 internalAndSet(xs);
256 currentState = BitsState.NORMAL;
257 return this;
258 }
260 protected void internalAndSet(Bits xs) {
261 Assert.check(currentState != BitsState.UNKNOWN);
262 sizeTo(xs.bits.length);
263 for (int i = 0; i < xs.bits.length; i++) {
264 bits[i] = bits[i] & xs.bits[i];
265 }
266 }
268 /** this set = this set | xs.
269 */
270 public Bits orSet(Bits xs) {
271 Assert.check(currentState != BitsState.UNKNOWN);
272 sizeTo(xs.bits.length);
273 for (int i = 0; i < xs.bits.length; i++) {
274 bits[i] = bits[i] | xs.bits[i];
275 }
276 currentState = BitsState.NORMAL;
277 return this;
278 }
280 /** this set = this set \ xs.
281 */
282 public Bits diffSet(Bits xs) {
283 Assert.check(currentState != BitsState.UNKNOWN);
284 for (int i = 0; i < bits.length; i++) {
285 if (i < xs.bits.length) {
286 bits[i] = bits[i] & ~xs.bits[i];
287 }
288 }
289 currentState = BitsState.NORMAL;
290 return this;
291 }
293 /** this set = this set ^ xs.
294 */
295 public Bits xorSet(Bits xs) {
296 Assert.check(currentState != BitsState.UNKNOWN);
297 sizeTo(xs.bits.length);
298 for (int i = 0; i < xs.bits.length; i++) {
299 bits[i] = bits[i] ^ xs.bits[i];
300 }
301 currentState = BitsState.NORMAL;
302 return this;
303 }
305 /** Count trailing zero bits in an int. Algorithm from "Hacker's
306 * Delight" by Henry S. Warren Jr. (figure 5-13)
307 */
308 private static int trailingZeroBits(int x) {
309 Assert.check(wordlen == 32);
310 if (x == 0) {
311 return 32;
312 }
313 int n = 1;
314 if ((x & 0xffff) == 0) { n += 16; x >>>= 16; }
315 if ((x & 0x00ff) == 0) { n += 8; x >>>= 8; }
316 if ((x & 0x000f) == 0) { n += 4; x >>>= 4; }
317 if ((x & 0x0003) == 0) { n += 2; x >>>= 2; }
318 return n - (x&1);
319 }
321 /** Return the index of the least bit position ≥ x that is set.
322 * If none are set, returns -1. This provides a nice way to iterate
323 * over the members of a bit set:
324 * <pre>{@code
325 * for (int i = bits.nextBit(0); i>=0; i = bits.nextBit(i+1)) ...
326 * }</pre>
327 */
328 public int nextBit(int x) {
329 Assert.check(currentState != BitsState.UNKNOWN);
330 int windex = x >>> wordshift;
331 if (windex >= bits.length) {
332 return -1;
333 }
334 int word = bits[windex] & ~((1 << (x & wordmask))-1);
335 while (true) {
336 if (word != 0) {
337 return (windex << wordshift) + trailingZeroBits(word);
338 }
339 windex++;
340 if (windex >= bits.length) {
341 return -1;
342 }
343 word = bits[windex];
344 }
345 }
347 /** a string representation of this set.
348 */
349 @Override
350 public String toString() {
351 if (bits != null && bits.length > 0) {
352 char[] digits = new char[bits.length * wordlen];
353 for (int i = 0; i < bits.length * wordlen; i++) {
354 digits[i] = isMember(i) ? '1' : '0';
355 }
356 return new String(digits);
357 } else {
358 return "[]";
359 }
360 }
362 /** Test Bits.nextBit(int). */
363 public static void main(String[] args) {
364 java.util.Random r = new java.util.Random();
365 Bits bits = new Bits();
366 for (int i=0; i<125; i++) {
367 int k;
368 do {
369 k = r.nextInt(250);
370 } while (bits.isMember(k));
371 System.out.println("adding " + k);
372 bits.incl(k);
373 }
374 int count = 0;
375 for (int i = bits.nextBit(0); i >= 0; i = bits.nextBit(i+1)) {
376 System.out.println("found " + i);
377 count ++;
378 }
379 if (count != 125) {
380 throw new Error();
381 }
382 }
383 }
