Mercurial > jdk8-mips64-public > langtools / file revision
src/share/classes/com/sun/tools/javac/util/Bits.java@2ca9e7d50136
src/share/classes/com/sun/tools/javac/util/Bits.java
Fri, 26 Apr 2013 10:17:01 +0100
- author
- vromero
- date
- Fri, 26 Apr 2013 10:17:01 +0100
- changeset 1713
- 2ca9e7d50136
- parent 1339
- 0e5899f09dab
- child 2027
- 4932bb04c4b8
- permissions
- -rw-r--r--
8008562: javac, a refactoring to Bits is necessary in order to provide a change history
Reviewed-by: mcimadamore
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 import static com.sun.tools.javac.util.Bits.BitsOpKind.*;
32 /** A class for extensible, mutable bit sets.
33 *
34 * <p><b>This is NOT part of any supported API.
35 * If you write code that depends on this, you do so at your own risk.
36 * This code and its internal interfaces are subject to change or
37 * deletion without notice.</b>
38 */
39 public class Bits {
41 public enum BitsOpKind {
42 INIT,
43 CLEAR,
44 INCL_BIT,
45 EXCL_BIT,
46 ASSIGN,
47 AND_SET,
48 OR_SET,
49 DIFF_SET,
50 XOR_SET,
51 INCL_RANGE,
52 EXCL_RANGE,
53 }
55 // ____________ reset _________
56 // / UNKNOWN \ <-------- / UNINIT \
57 // \____________/ | \_________/
58 // | | |
59 // |assign | | any
60 // | ___________ |
61 // ------> / NORMAL \ <----
62 // \___________/ |
63 // | |
64 // | |
65 // -----------
66 // any
67 private enum BitsState {
68 /* A Bits instance is in UNKNOWN state if it has been explicitly reset.
69 * It is possible to get to this state from any other by calling the
70 * reset method. An instance in the UNKNOWN state can pass to the
71 * NORMAL state after being assigned another Bits instance.
72 */
73 UNKNOWN,
74 /* A Bits instance is in UNINIT when it is created with the default
75 * constructor but it isn't explicitly reset. The main objective of this
76 * internal state is to save some memory.
77 */
78 UNINIT,
79 /* The normal state is reached after creating a Bits instance from an
80 * existing one or after applying any operation to an instance on UNINIT
81 * or NORMAL state. From this state a bits instance can pass to the
82 * UNKNOWN state by calling the reset method.
83 */
84 NORMAL;
86 static BitsState getState(int[] someBits, boolean reset) {
87 if (reset) {
88 return UNKNOWN;
89 } else {
90 if (someBits != unassignedBits) {
91 return NORMAL;
92 } else {
93 return UNINIT;
94 }
95 }
96 }
98 }
100 private final static int wordlen = 32;
101 private final static int wordshift = 5;
102 private final static int wordmask = wordlen - 1;
104 public int[] bits = null;
105 // This field will store last version of bits after every change.
106 public int[] oldBits = null;
108 public BitsOpKind lastOperation = null;
110 private static final int[] unassignedBits = new int[0];
112 private BitsState currentState;
114 /** Construct an initially empty set.
115 */
116 public Bits() {
117 this(false);
118 }
120 public Bits(Bits someBits) {
121 this(someBits.dup().bits, BitsState.getState(someBits.bits, false));
122 }
124 public Bits(boolean reset) {
125 this(unassignedBits, BitsState.getState(unassignedBits, reset));
126 }
128 /** Construct a set consisting initially of given bit vector.
129 */
130 private Bits(int[] bits, BitsState initState) {
131 this.bits = bits;
132 this.currentState = initState;
133 switch (initState) {
134 case UNKNOWN:
135 reset(); //this will also set current state;
136 break;
137 case NORMAL:
138 Assert.check(bits != unassignedBits);
139 lastOperation = INIT;
140 break;
141 }
142 }
144 /** This method will be called after any operation that causes a change to
145 * the bits. Subclasses can thus override it in order to extract information
146 * from the changes produced to the bits by the given operation.
147 */
148 public void changed() {}
150 private void sizeTo(int len) {
151 if (bits.length < len) {
152 bits = Arrays.copyOf(bits, len);
153 }
154 }
156 /** This set = {}.
157 */
158 public void clear() {
159 Assert.check(currentState != BitsState.UNKNOWN);
160 oldBits = bits;
161 lastOperation = CLEAR;
162 for (int i = 0; i < bits.length; i++) bits[i] = 0;
163 changed();
164 currentState = BitsState.NORMAL;
165 }
167 public void reset() {
168 bits = null;
169 oldBits = null;
170 currentState = BitsState.UNKNOWN;
171 }
173 public boolean isReset() {
174 return currentState == BitsState.UNKNOWN;
175 }
177 public Bits assign(Bits someBits) {
178 lastOperation = ASSIGN;
179 oldBits = bits;
180 bits = someBits.dup().bits;
181 changed();
182 currentState = BitsState.NORMAL;
183 return this;
184 }
186 /** Return a copy of this set.
187 */
188 private Bits dup() {
189 Assert.check(currentState != BitsState.UNKNOWN);
190 Bits tmp = new Bits();
191 if (currentState != BitsState.NORMAL) {
192 tmp.bits = bits;
193 } else {
194 tmp.bits = new int[bits.length];
195 System.arraycopy(bits, 0, tmp.bits, 0, bits.length);
196 }
197 currentState = BitsState.NORMAL;
198 return tmp;
199 }
201 /** Include x in this set.
202 */
203 public void incl(int x) {
204 Assert.check(currentState != BitsState.UNKNOWN);
205 Assert.check(x >= 0);
206 oldBits = bits;
207 lastOperation = INCL_BIT;
208 sizeTo((x >>> wordshift) + 1);
209 bits[x >>> wordshift] = bits[x >>> wordshift] |
210 (1 << (x & wordmask));
211 changed();
212 currentState = BitsState.NORMAL;
213 }
216 /** Include [start..limit) in this set.
217 */
218 public void inclRange(int start, int limit) {
219 Assert.check(currentState != BitsState.UNKNOWN);
220 oldBits = bits;
221 lastOperation = INCL_RANGE;
222 sizeTo((limit >>> wordshift) + 1);
223 for (int x = start; x < limit; x++) {
224 bits[x >>> wordshift] = bits[x >>> wordshift] |
225 (1 << (x & wordmask));
226 }
227 changed();
228 currentState = BitsState.NORMAL;
229 }
231 /** Exclude [start...end] from this set.
232 */
233 public void excludeFrom(int start) {
234 Assert.check(currentState != BitsState.UNKNOWN);
235 oldBits = bits;
236 lastOperation = EXCL_RANGE;
237 Bits temp = new Bits();
238 temp.sizeTo(bits.length);
239 temp.inclRange(0, start);
240 internalAndSet(temp);
241 changed();
242 currentState = BitsState.NORMAL;
243 }
245 /** Exclude x from this set.
246 */
247 public void excl(int x) {
248 Assert.check(currentState != BitsState.UNKNOWN);
249 Assert.check(x >= 0);
250 oldBits = bits;
251 lastOperation = EXCL_BIT;
252 sizeTo((x >>> wordshift) + 1);
253 bits[x >>> wordshift] = bits[x >>> wordshift] &
254 ~(1 << (x & wordmask));
255 changed();
256 currentState = BitsState.NORMAL;
257 }
259 /** Is x an element of this set?
260 */
261 public boolean isMember(int x) {
262 Assert.check(currentState != BitsState.UNKNOWN);
263 return
264 0 <= x && x < (bits.length << wordshift) &&
265 (bits[x >>> wordshift] & (1 << (x & wordmask))) != 0;
266 }
268 /** {@literal this set = this set & xs}.
269 */
270 public Bits andSet(Bits xs) {
271 Assert.check(currentState != BitsState.UNKNOWN);
272 oldBits = bits;
273 lastOperation = AND_SET;
274 internalAndSet(xs);
275 changed();
276 currentState = BitsState.NORMAL;
277 return this;
278 }
280 private void internalAndSet(Bits xs) {
281 Assert.check(currentState != BitsState.UNKNOWN);
282 sizeTo(xs.bits.length);
283 for (int i = 0; i < xs.bits.length; i++) {
284 bits[i] = bits[i] & xs.bits[i];
285 }
286 }
288 /** this set = this set | xs.
289 */
290 public Bits orSet(Bits xs) {
291 Assert.check(currentState != BitsState.UNKNOWN);
292 oldBits = bits;
293 lastOperation = OR_SET;
294 sizeTo(xs.bits.length);
295 for (int i = 0; i < xs.bits.length; i++) {
296 bits[i] = bits[i] | xs.bits[i];
297 }
298 changed();
299 currentState = BitsState.NORMAL;
300 return this;
301 }
303 /** this set = this set \ xs.
304 */
305 public Bits diffSet(Bits xs) {
306 Assert.check(currentState != BitsState.UNKNOWN);
307 oldBits = bits;
308 lastOperation = DIFF_SET;
309 for (int i = 0; i < bits.length; i++) {
310 if (i < xs.bits.length) {
311 bits[i] = bits[i] & ~xs.bits[i];
312 }
313 }
314 changed();
315 currentState = BitsState.NORMAL;
316 return this;
317 }
319 /** this set = this set ^ xs.
320 */
321 public Bits xorSet(Bits xs) {
322 Assert.check(currentState != BitsState.UNKNOWN);
323 oldBits = bits;
324 lastOperation = XOR_SET;
325 sizeTo(xs.bits.length);
326 for (int i = 0; i < xs.bits.length; i++) {
327 bits[i] = bits[i] ^ xs.bits[i];
328 }
329 changed();
330 currentState = BitsState.NORMAL;
331 return this;
332 }
334 /** Count trailing zero bits in an int. Algorithm from "Hacker's
335 * Delight" by Henry S. Warren Jr. (figure 5-13)
336 */
337 private static int trailingZeroBits(int x) {
338 Assert.check(wordlen == 32);
339 if (x == 0) return 32;
340 int n = 1;
341 if ((x & 0xffff) == 0) { n += 16; x >>>= 16; }
342 if ((x & 0x00ff) == 0) { n += 8; x >>>= 8; }
343 if ((x & 0x000f) == 0) { n += 4; x >>>= 4; }
344 if ((x & 0x0003) == 0) { n += 2; x >>>= 2; }
345 return n - (x&1);
346 }
348 /** Return the index of the least bit position ≥ x that is set.
349 * If none are set, returns -1. This provides a nice way to iterate
350 * over the members of a bit set:
351 * <pre>{@code
352 * for (int i = bits.nextBit(0); i>=0; i = bits.nextBit(i+1)) ...
353 * }</pre>
354 */
355 public int nextBit(int x) {
356 Assert.check(currentState != BitsState.UNKNOWN);
357 int windex = x >>> wordshift;
358 if (windex >= bits.length) return -1;
359 int word = bits[windex] & ~((1 << (x & wordmask))-1);
360 while (true) {
361 if (word != 0)
362 return (windex << wordshift) + trailingZeroBits(word);
363 windex++;
364 if (windex >= bits.length) return -1;
365 word = bits[windex];
366 }
367 }
369 /** a string representation of this set.
370 */
371 public String toString() {
372 if (bits.length > 0) {
373 char[] digits = new char[bits.length * wordlen];
374 for (int i = 0; i < bits.length * wordlen; i++)
375 digits[i] = isMember(i) ? '1' : '0';
376 return new String(digits);
377 } else {
378 return "[]";
379 }
380 }
382 /** Test Bits.nextBit(int). */
383 public static void main(String[] args) {
384 java.util.Random r = new java.util.Random();
385 Bits bits = new Bits();
386 for (int i=0; i<125; i++) {
387 int k;
388 do {
389 k = r.nextInt(250);
390 } while (bits.isMember(k));
391 System.out.println("adding " + k);
392 bits.incl(k);
393 }
394 int count = 0;
395 for (int i = bits.nextBit(0); i >= 0; i = bits.nextBit(i+1)) {
396 System.out.println("found " + i);
397 count ++;
398 }
399 if (count != 125) throw new Error();
400 }
401 }
