25 |
25 |
26 package com.sun.tools.javac.util; |
26 package com.sun.tools.javac.util; |
27 |
27 |
28 import java.util.Arrays; |
28 import java.util.Arrays; |
29 |
29 |
|
30 import static com.sun.tools.javac.util.Bits.BitsOpKind.*; |
|
31 |
30 /** A class for extensible, mutable bit sets. |
32 /** A class for extensible, mutable bit sets. |
31 * |
33 * |
32 * <p><b>This is NOT part of any supported API. |
34 * <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. |
35 * 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 |
36 * This code and its internal interfaces are subject to change or |
35 * deletion without notice.</b> |
37 * deletion without notice.</b> |
36 */ |
38 */ |
37 public class Bits { |
39 public class Bits { |
38 |
40 |
|
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 } |
|
54 |
|
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; |
|
85 |
|
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 } |
|
97 |
|
98 } |
39 |
99 |
40 private final static int wordlen = 32; |
100 private final static int wordlen = 32; |
41 private final static int wordshift = 5; |
101 private final static int wordshift = 5; |
42 private final static int wordmask = wordlen - 1; |
102 private final static int wordmask = wordlen - 1; |
43 |
103 |
44 private int[] bits; |
104 public int[] bits = null; |
|
105 // This field will store last version of bits after every change. |
|
106 public int[] oldBits = null; |
|
107 |
|
108 public BitsOpKind lastOperation = null; |
|
109 |
|
110 private static final int[] unassignedBits = new int[0]; |
|
111 |
|
112 private BitsState currentState; |
45 |
113 |
46 /** Construct an initially empty set. |
114 /** Construct an initially empty set. |
47 */ |
115 */ |
48 public Bits() { |
116 public Bits() { |
49 this(new int[1]); |
117 this(false); |
|
118 } |
|
119 |
|
120 public Bits(Bits someBits) { |
|
121 this(someBits.dup().bits, BitsState.getState(someBits.bits, false)); |
|
122 } |
|
123 |
|
124 public Bits(boolean reset) { |
|
125 this(unassignedBits, BitsState.getState(unassignedBits, reset)); |
50 } |
126 } |
51 |
127 |
52 /** Construct a set consisting initially of given bit vector. |
128 /** Construct a set consisting initially of given bit vector. |
53 */ |
129 */ |
54 public Bits(int[] bits) { |
130 private Bits(int[] bits, BitsState initState) { |
55 this.bits = bits; |
131 this.bits = bits; |
56 } |
132 this.currentState = initState; |
57 |
133 switch (initState) { |
58 /** Construct a set consisting initially of given range. |
134 case UNKNOWN: |
59 */ |
135 reset(); //this will also set current state; |
60 public Bits(int start, int limit) { |
136 break; |
61 this(); |
137 case NORMAL: |
62 inclRange(start, limit); |
138 Assert.check(bits != unassignedBits); |
63 } |
139 lastOperation = INIT; |
|
140 break; |
|
141 } |
|
142 } |
|
143 |
|
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() {} |
64 |
149 |
65 private void sizeTo(int len) { |
150 private void sizeTo(int len) { |
66 if (bits.length < len) { |
151 if (bits.length < len) { |
67 bits = Arrays.copyOf(bits, len); |
152 bits = Arrays.copyOf(bits, len); |
68 } |
153 } |
69 } |
154 } |
70 |
155 |
71 /** This set = {}. |
156 /** This set = {}. |
72 */ |
157 */ |
73 public void clear() { |
158 public void clear() { |
|
159 Assert.check(currentState != BitsState.UNKNOWN); |
|
160 oldBits = bits; |
|
161 lastOperation = CLEAR; |
74 for (int i = 0; i < bits.length; i++) bits[i] = 0; |
162 for (int i = 0; i < bits.length; i++) bits[i] = 0; |
|
163 changed(); |
|
164 currentState = BitsState.NORMAL; |
|
165 } |
|
166 |
|
167 public void reset() { |
|
168 bits = null; |
|
169 oldBits = null; |
|
170 currentState = BitsState.UNKNOWN; |
|
171 } |
|
172 |
|
173 public boolean isReset() { |
|
174 return currentState == BitsState.UNKNOWN; |
|
175 } |
|
176 |
|
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; |
75 } |
184 } |
76 |
185 |
77 /** Return a copy of this set. |
186 /** Return a copy of this set. |
78 */ |
187 */ |
79 public Bits dup() { |
188 private Bits dup() { |
80 int[] newbits = new int[bits.length]; |
189 Assert.check(currentState != BitsState.UNKNOWN); |
81 System.arraycopy(bits, 0, newbits, 0, bits.length); |
190 Bits tmp = new Bits(); |
82 return new Bits(newbits); |
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; |
83 } |
199 } |
84 |
200 |
85 /** Include x in this set. |
201 /** Include x in this set. |
86 */ |
202 */ |
87 public void incl(int x) { |
203 public void incl(int x) { |
|
204 Assert.check(currentState != BitsState.UNKNOWN); |
88 Assert.check(x >= 0); |
205 Assert.check(x >= 0); |
|
206 oldBits = bits; |
|
207 lastOperation = INCL_BIT; |
89 sizeTo((x >>> wordshift) + 1); |
208 sizeTo((x >>> wordshift) + 1); |
90 bits[x >>> wordshift] = bits[x >>> wordshift] | |
209 bits[x >>> wordshift] = bits[x >>> wordshift] | |
91 (1 << (x & wordmask)); |
210 (1 << (x & wordmask)); |
|
211 changed(); |
|
212 currentState = BitsState.NORMAL; |
92 } |
213 } |
93 |
214 |
94 |
215 |
95 /** Include [start..limit) in this set. |
216 /** Include [start..limit) in this set. |
96 */ |
217 */ |
97 public void inclRange(int start, int limit) { |
218 public void inclRange(int start, int limit) { |
|
219 Assert.check(currentState != BitsState.UNKNOWN); |
|
220 oldBits = bits; |
|
221 lastOperation = INCL_RANGE; |
98 sizeTo((limit >>> wordshift) + 1); |
222 sizeTo((limit >>> wordshift) + 1); |
99 for (int x = start; x < limit; x++) |
223 for (int x = start; x < limit; x++) { |
100 bits[x >>> wordshift] = bits[x >>> wordshift] | |
224 bits[x >>> wordshift] = bits[x >>> wordshift] | |
101 (1 << (x & wordmask)); |
225 (1 << (x & wordmask)); |
|
226 } |
|
227 changed(); |
|
228 currentState = BitsState.NORMAL; |
102 } |
229 } |
103 |
230 |
104 /** Exclude [start...end] from this set. |
231 /** Exclude [start...end] from this set. |
105 */ |
232 */ |
106 public void excludeFrom(int start) { |
233 public void excludeFrom(int start) { |
|
234 Assert.check(currentState != BitsState.UNKNOWN); |
|
235 oldBits = bits; |
|
236 lastOperation = EXCL_RANGE; |
107 Bits temp = new Bits(); |
237 Bits temp = new Bits(); |
108 temp.sizeTo(bits.length); |
238 temp.sizeTo(bits.length); |
109 temp.inclRange(0, start); |
239 temp.inclRange(0, start); |
110 andSet(temp); |
240 internalAndSet(temp); |
|
241 changed(); |
|
242 currentState = BitsState.NORMAL; |
111 } |
243 } |
112 |
244 |
113 /** Exclude x from this set. |
245 /** Exclude x from this set. |
114 */ |
246 */ |
115 public void excl(int x) { |
247 public void excl(int x) { |
|
248 Assert.check(currentState != BitsState.UNKNOWN); |
116 Assert.check(x >= 0); |
249 Assert.check(x >= 0); |
|
250 oldBits = bits; |
|
251 lastOperation = EXCL_BIT; |
117 sizeTo((x >>> wordshift) + 1); |
252 sizeTo((x >>> wordshift) + 1); |
118 bits[x >>> wordshift] = bits[x >>> wordshift] & |
253 bits[x >>> wordshift] = bits[x >>> wordshift] & |
119 ~(1 << (x & wordmask)); |
254 ~(1 << (x & wordmask)); |
|
255 changed(); |
|
256 currentState = BitsState.NORMAL; |
120 } |
257 } |
121 |
258 |
122 /** Is x an element of this set? |
259 /** Is x an element of this set? |
123 */ |
260 */ |
124 public boolean isMember(int x) { |
261 public boolean isMember(int x) { |
|
262 Assert.check(currentState != BitsState.UNKNOWN); |
125 return |
263 return |
126 0 <= x && x < (bits.length << wordshift) && |
264 0 <= x && x < (bits.length << wordshift) && |
127 (bits[x >>> wordshift] & (1 << (x & wordmask))) != 0; |
265 (bits[x >>> wordshift] & (1 << (x & wordmask))) != 0; |
128 } |
266 } |
129 |
267 |
130 /** {@literal this set = this set & xs}. |
268 /** {@literal this set = this set & xs}. |
131 */ |
269 */ |
132 public Bits andSet(Bits xs) { |
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 } |
|
279 |
|
280 private void internalAndSet(Bits xs) { |
|
281 Assert.check(currentState != BitsState.UNKNOWN); |
133 sizeTo(xs.bits.length); |
282 sizeTo(xs.bits.length); |
134 for (int i = 0; i < xs.bits.length; i++) |
283 for (int i = 0; i < xs.bits.length; i++) { |
135 bits[i] = bits[i] & xs.bits[i]; |
284 bits[i] = bits[i] & xs.bits[i]; |
|
285 } |
|
286 } |
|
287 |
|
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; |
136 return this; |
300 return this; |
137 } |
301 } |
138 |
302 |
139 /** this set = this set | xs. |
|
140 */ |
|
141 public Bits orSet(Bits xs) { |
|
142 sizeTo(xs.bits.length); |
|
143 for (int i = 0; i < xs.bits.length; i++) |
|
144 bits[i] = bits[i] | xs.bits[i]; |
|
145 return this; |
|
146 } |
|
147 |
|
148 /** this set = this set \ xs. |
303 /** this set = this set \ xs. |
149 */ |
304 */ |
150 public Bits diffSet(Bits xs) { |
305 public Bits diffSet(Bits xs) { |
|
306 Assert.check(currentState != BitsState.UNKNOWN); |
|
307 oldBits = bits; |
|
308 lastOperation = DIFF_SET; |
151 for (int i = 0; i < bits.length; i++) { |
309 for (int i = 0; i < bits.length; i++) { |
152 if (i < xs.bits.length) { |
310 if (i < xs.bits.length) { |
153 bits[i] = bits[i] & ~xs.bits[i]; |
311 bits[i] = bits[i] & ~xs.bits[i]; |
154 } |
312 } |
155 } |
313 } |
|
314 changed(); |
|
315 currentState = BitsState.NORMAL; |
156 return this; |
316 return this; |
157 } |
317 } |
158 |
318 |
159 /** this set = this set ^ xs. |
319 /** this set = this set ^ xs. |
160 */ |
320 */ |
161 public Bits xorSet(Bits xs) { |
321 public Bits xorSet(Bits xs) { |
|
322 Assert.check(currentState != BitsState.UNKNOWN); |
|
323 oldBits = bits; |
|
324 lastOperation = XOR_SET; |
162 sizeTo(xs.bits.length); |
325 sizeTo(xs.bits.length); |
163 for (int i = 0; i < xs.bits.length; i++) |
326 for (int i = 0; i < xs.bits.length; i++) { |
164 bits[i] = bits[i] ^ xs.bits[i]; |
327 bits[i] = bits[i] ^ xs.bits[i]; |
|
328 } |
|
329 changed(); |
|
330 currentState = BitsState.NORMAL; |
165 return this; |
331 return this; |
166 } |
332 } |
167 |
333 |
168 /** Count trailing zero bits in an int. Algorithm from "Hacker's |
334 /** Count trailing zero bits in an int. Algorithm from "Hacker's |
169 * Delight" by Henry S. Warren Jr. (figure 5-13) |
335 * Delight" by Henry S. Warren Jr. (figure 5-13) |