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 
getState(int[] someBits, boolean reset)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 final static int wordlen = 32;
88     private final static int wordshift = 5;
89     private final static 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      */
Bits()99     public Bits() {
100         this(false);
101     }
102 
Bits(Bits someBits)103     public Bits(Bits someBits) {
104         this(someBits.dup().bits, BitsState.getState(someBits.bits, false));
105     }
106 
Bits(boolean reset)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      */
Bits(int[] bits, BitsState initState)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 
sizeTo(int len)126     protected void sizeTo(int len) {
127         if (bits.length < len) {
128             bits = Arrays.copyOf(bits, len);
129         }
130     }
131 
132     /** This set = {}.
133      */
clear()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 
reset()142     public void reset() {
143         internalReset();
144     }
145 
internalReset()146     protected void internalReset() {
147         bits = null;
148         currentState = BitsState.UNKNOWN;
149     }
150 
isReset()151     public boolean isReset() {
152         return currentState == BitsState.UNKNOWN;
153     }
154 
assign(Bits someBits)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      */
dup()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 
dupBits()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      */
incl(int x)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      */
inclRange(int start, int limit)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      */
excludeFrom(int start)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      */
excl(int x)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      */
isMember(int x)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      */
andSet(Bits xs)239     public Bits andSet(Bits xs) {
240         Assert.check(currentState != BitsState.UNKNOWN);
241         internalAndSet(xs);
242         currentState = BitsState.NORMAL;
243         return this;
244     }
245 
internalAndSet(Bits xs)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      */
orSet(Bits xs)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      */
diffSet(Bits xs)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      */
xorSet(Bits xs)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      */
trailingZeroBits(int x)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 &ge; 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      */
nextBit(int x)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
toString()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 }
349