--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/langtools/src/share/classes/com/sun/tools/javac/util/Bits.java Sat Dec 01 00:00:00 2007 +0000
@@ -0,0 +1,222 @@
+/*
+ * Copyright 1999-2005 Sun Microsystems, Inc. All Rights Reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation. Sun designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Sun in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ */
+
+package com.sun.tools.javac.util;
+
+/** A class for extensible, mutable bit sets.
+ *
+ * <p><b>This is NOT part of any API supported by Sun Microsystems. If
+ * you write code that depends on this, you do so at your own risk.
+ * This code and its internal interfaces are subject to change or
+ * deletion without notice.</b>
+ */
+public class Bits {
+
+
+ private final static int wordlen = 32;
+ private final static int wordshift = 5;
+ private final static int wordmask = wordlen - 1;
+
+ private int[] bits;
+
+ /** Construct an initially empty set.
+ */
+ public Bits() {
+ this(new int[1]);
+ }
+
+ /** Construct a set consisting initially of given bit vector.
+ */
+ public Bits(int[] bits) {
+ this.bits = bits;
+ }
+
+ /** Construct a set consisting initially of given range.
+ */
+ public Bits(int start, int limit) {
+ this();
+ inclRange(start, limit);
+ }
+
+ private void sizeTo(int len) {
+ if (bits.length < len) {
+ int[] newbits = new int[len];
+ System.arraycopy(bits, 0, newbits, 0, bits.length);
+ bits = newbits;
+ }
+ }
+
+ /** This set = {}.
+ */
+ public void clear() {
+ for (int i = 0; i < bits.length; i++) bits[i] = 0;
+ }
+
+ /** Return a copy of this set.
+ */
+ public Bits dup() {
+ int[] newbits = new int[bits.length];
+ System.arraycopy(bits, 0, newbits, 0, bits.length);
+ return new Bits(newbits);
+ }
+
+ /** Include x in this set.
+ */
+ public void incl(int x) {
+ assert x >= 0;
+ sizeTo((x >>> wordshift) + 1);
+ bits[x >>> wordshift] = bits[x >>> wordshift] |
+ (1 << (x & wordmask));
+ }
+
+
+ /** Include [start..limit) in this set.
+ */
+ public void inclRange(int start, int limit) {
+ sizeTo((limit >>> wordshift) + 1);
+ for (int x = start; x < limit; x++)
+ bits[x >>> wordshift] = bits[x >>> wordshift] |
+ (1 << (x & wordmask));
+ }
+
+ /** Exclude x from this set.
+ */
+ public void excl(int x) {
+ assert x >= 0;
+ sizeTo((x >>> wordshift) + 1);
+ bits[x >>> wordshift] = bits[x >>> wordshift] &
+ ~(1 << (x & wordmask));
+ }
+
+ /** Is x an element of this set?
+ */
+ public boolean isMember(int x) {
+ return
+ 0 <= x && x < (bits.length << wordshift) &&
+ (bits[x >>> wordshift] & (1 << (x & wordmask))) != 0;
+ }
+
+ /** this set = this set & xs.
+ */
+ public Bits andSet(Bits xs) {
+ sizeTo(xs.bits.length);
+ for (int i = 0; i < xs.bits.length; i++)
+ bits[i] = bits[i] & xs.bits[i];
+ return this;
+ }
+
+ /** this set = this set | xs.
+ */
+ public Bits orSet(Bits xs) {
+ sizeTo(xs.bits.length);
+ for (int i = 0; i < xs.bits.length; i++)
+ bits[i] = bits[i] | xs.bits[i];
+ return this;
+ }
+
+ /** this set = this set \ xs.
+ */
+ public Bits diffSet(Bits xs) {
+ for (int i = 0; i < bits.length; i++) {
+ if (i < xs.bits.length) {
+ bits[i] = bits[i] & ~xs.bits[i];
+ }
+ }
+ return this;
+ }
+
+ /** this set = this set ^ xs.
+ */
+ public Bits xorSet(Bits xs) {
+ sizeTo(xs.bits.length);
+ for (int i = 0; i < xs.bits.length; i++)
+ bits[i] = bits[i] ^ xs.bits[i];
+ return this;
+ }
+
+ /** Count trailing zero bits in an int. Algorithm from "Hacker's
+ * Delight" by Henry S. Warren Jr. (figure 5-13)
+ */
+ private static int trailingZeroBits(int x) {
+ assert wordlen == 32;
+ if (x == 0) return 32;
+ int n = 1;
+ if ((x & 0xffff) == 0) { n += 16; x >>>= 16; }
+ if ((x & 0x00ff) == 0) { n += 8; x >>>= 8; }
+ if ((x & 0x000f) == 0) { n += 4; x >>>= 4; }
+ if ((x & 0x0003) == 0) { n += 2; x >>>= 2; }
+ return n - (x&1);
+ }
+
+ /** Return the index of the least bit position >= x that is set.
+ * If none are set, returns -1. This provides a nice way to iterate
+ * over the members of a bit set:
+ * <pre>
+ * for (int i = bits.nextBit(0); i>=0; i = bits.nextBit(i+1)) ...
+ * </pre>
+ */
+ public int nextBit(int x) {
+ int windex = x >>> wordshift;
+ if (windex >= bits.length) return -1;
+ int word = bits[windex] & ~((1 << (x & wordmask))-1);
+ while (true) {
+ if (word != 0)
+ return (windex << wordshift) + trailingZeroBits(word);
+ windex++;
+ if (windex >= bits.length) return -1;
+ word = bits[windex];
+ }
+ }
+
+ /** a string representation of this set.
+ */
+ public String toString() {
+ char[] digits = new char[bits.length * wordlen];
+ for (int i = 0; i < bits.length * wordlen; i++)
+ digits[i] = isMember(i) ? '1' : '0';
+ return new String(digits);
+ }
+
+ /** Test Bits.nextBit(int). */
+ public static void main(String[] args) {
+ java.util.Random r = new java.util.Random();
+ Bits bits = new Bits();
+ int dupCount = 0;
+ for (int i=0; i<125; i++) {
+ int k;
+ do {
+ k = r.nextInt(250);
+ } while (bits.isMember(k));
+ System.out.println("adding " + k);
+ bits.incl(k);
+ }
+ int count = 0;
+ for (int i = bits.nextBit(0); i >= 0; i = bits.nextBit(i+1)) {
+ System.out.println("found " + i);
+ count ++;
+ }
+ if (count != 125) throw new Error();
+ }
+}