Bits.java revision 2633:0d89f8b94872 
1/*
2 * Copyright (c) 1999, 2014, 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    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    }
100
101    private final static int wordlen = 32;
102    private final static int wordshift = 5;
103    private final static int wordmask = wordlen - 1;
104
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];
108
109    protected BitsState currentState;
110
111    /** Construct an initially empty set.
112     */
113    public Bits() {
114        this(false);
115    }
116
117    public Bits(Bits someBits) {
118        this(someBits.dup().bits, BitsState.getState(someBits.bits, false));
119    }
120
121    public Bits(boolean reset) {
122        this(unassignedBits, BitsState.getState(unassignedBits, reset));
123    }
124
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    }
139
140    protected void sizeTo(int len) {
141        if (bits.length < len) {
142            bits = Arrays.copyOf(bits, len);
143        }
144    }
145
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    }
155
156    public void reset() {
157        internalReset();
158    }
159
160    protected void internalReset() {
161        bits = null;
162        currentState = BitsState.UNKNOWN;
163    }
164
165    public boolean isReset() {
166        return currentState == BitsState.UNKNOWN;
167    }
168
169    public Bits assign(Bits someBits) {
170        bits = someBits.dup().bits;
171        currentState = BitsState.NORMAL;
172        return this;
173    }
174
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    }
184
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    }
195
196    /** Include x in this set.
197     */
198    public void incl(int x) {
199        Assert.check(currentState != BitsState.UNKNOWN);
200        Assert.check(x >= 0);
201        sizeTo((x >>> wordshift) + 1);
202        bits[x >>> wordshift] = bits[x >>> wordshift] |
203            (1 << (x & wordmask));
204        currentState = BitsState.NORMAL;
205    }
206
207
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    }
219
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    }
230
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    }
241
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    }
250
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    }
259
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    }
267
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    }
279
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    }
292
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    }
304
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    }
320
321    /** Return the index of the least bit position &ge; 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    }
346
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    }
361
362}
363