Bits.java revision 2827:5e500700b168 
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
26package com.sun.tools.javac.util;
27
28import 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 */
37public 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 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     */
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 &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     */
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}
349