Tue, 12 Feb 2013 19:25:09 +0000
8007464: Add graph inference support
Summary: Add support for more aggressive type-inference scheme
Reviewed-by: jjg
1 /*
2 * Copyright (c) 1999, 2012, 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 /** 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 {
40 private final static int wordlen = 32;
41 private final static int wordshift = 5;
42 private final static int wordmask = wordlen - 1;
44 private int[] bits;
46 /** Construct an initially empty set.
47 */
48 public Bits() {
49 this(new int[1]);
50 }
52 /** Construct a set consisting initially of given bit vector.
53 */
54 public Bits(int[] bits) {
55 this.bits = bits;
56 }
58 /** Construct a set consisting initially of given range.
59 */
60 public Bits(int start, int limit) {
61 this();
62 inclRange(start, limit);
63 }
65 private void sizeTo(int len) {
66 if (bits.length < len) {
67 bits = Arrays.copyOf(bits, len);
68 }
69 }
71 /** This set = {}.
72 */
73 public void clear() {
74 for (int i = 0; i < bits.length; i++) bits[i] = 0;
75 }
77 /** Return a copy of this set.
78 */
79 public Bits dup() {
80 int[] newbits = new int[bits.length];
81 System.arraycopy(bits, 0, newbits, 0, bits.length);
82 return new Bits(newbits);
83 }
85 /** Include x in this set.
86 */
87 public void incl(int x) {
88 Assert.check(x >= 0);
89 sizeTo((x >>> wordshift) + 1);
90 bits[x >>> wordshift] = bits[x >>> wordshift] |
91 (1 << (x & wordmask));
92 }
95 /** Include [start..limit) in this set.
96 */
97 public void inclRange(int start, int limit) {
98 sizeTo((limit >>> wordshift) + 1);
99 for (int x = start; x < limit; x++)
100 bits[x >>> wordshift] = bits[x >>> wordshift] |
101 (1 << (x & wordmask));
102 }
104 /** Exclude [start...end] from this set.
105 */
106 public void excludeFrom(int start) {
107 Bits temp = new Bits();
108 temp.sizeTo(bits.length);
109 temp.inclRange(0, start);
110 andSet(temp);
111 }
113 /** Exclude x from this set.
114 */
115 public void excl(int x) {
116 Assert.check(x >= 0);
117 sizeTo((x >>> wordshift) + 1);
118 bits[x >>> wordshift] = bits[x >>> wordshift] &
119 ~(1 << (x & wordmask));
120 }
122 /** Is x an element of this set?
123 */
124 public boolean isMember(int x) {
125 return
126 0 <= x && x < (bits.length << wordshift) &&
127 (bits[x >>> wordshift] & (1 << (x & wordmask))) != 0;
128 }
130 /** {@literal this set = this set & xs}.
131 */
132 public Bits andSet(Bits xs) {
133 sizeTo(xs.bits.length);
134 for (int i = 0; i < xs.bits.length; i++)
135 bits[i] = bits[i] & xs.bits[i];
136 return this;
137 }
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 }
148 /** this set = this set \ xs.
149 */
150 public Bits diffSet(Bits xs) {
151 for (int i = 0; i < bits.length; i++) {
152 if (i < xs.bits.length) {
153 bits[i] = bits[i] & ~xs.bits[i];
154 }
155 }
156 return this;
157 }
159 /** this set = this set ^ xs.
160 */
161 public Bits xorSet(Bits xs) {
162 sizeTo(xs.bits.length);
163 for (int i = 0; i < xs.bits.length; i++)
164 bits[i] = bits[i] ^ xs.bits[i];
165 return this;
166 }
168 /** Count trailing zero bits in an int. Algorithm from "Hacker's
169 * Delight" by Henry S. Warren Jr. (figure 5-13)
170 */
171 private static int trailingZeroBits(int x) {
172 Assert.check(wordlen == 32);
173 if (x == 0) return 32;
174 int n = 1;
175 if ((x & 0xffff) == 0) { n += 16; x >>>= 16; }
176 if ((x & 0x00ff) == 0) { n += 8; x >>>= 8; }
177 if ((x & 0x000f) == 0) { n += 4; x >>>= 4; }
178 if ((x & 0x0003) == 0) { n += 2; x >>>= 2; }
179 return n - (x&1);
180 }
182 /** Return the index of the least bit position ≥ x that is set.
183 * If none are set, returns -1. This provides a nice way to iterate
184 * over the members of a bit set:
185 * <pre>{@code
186 * for (int i = bits.nextBit(0); i>=0; i = bits.nextBit(i+1)) ...
187 * }</pre>
188 */
189 public int nextBit(int x) {
190 int windex = x >>> wordshift;
191 if (windex >= bits.length) return -1;
192 int word = bits[windex] & ~((1 << (x & wordmask))-1);
193 while (true) {
194 if (word != 0)
195 return (windex << wordshift) + trailingZeroBits(word);
196 windex++;
197 if (windex >= bits.length) return -1;
198 word = bits[windex];
199 }
200 }
202 /** a string representation of this set.
203 */
204 public String toString() {
205 char[] digits = new char[bits.length * wordlen];
206 for (int i = 0; i < bits.length * wordlen; i++)
207 digits[i] = isMember(i) ? '1' : '0';
208 return new String(digits);
209 }
211 /** Test Bits.nextBit(int). */
212 public static void main(String[] args) {
213 java.util.Random r = new java.util.Random();
214 Bits bits = new Bits();
215 int dupCount = 0;
216 for (int i=0; i<125; i++) {
217 int k;
218 do {
219 k = r.nextInt(250);
220 } while (bits.isMember(k));
221 System.out.println("adding " + k);
222 bits.incl(k);
223 }
224 int count = 0;
225 for (int i = bits.nextBit(0); i >= 0; i = bits.nextBit(i+1)) {
226 System.out.println("found " + i);
227 count ++;
228 }
229 if (count != 125) throw new Error();
230 }
231 }