jdk8-mips64-public/langtools: comparison src/share/classes/com/sun/tools/javac/util/Bits.java

--1:000000000000
+:9a66ca7c79fa
+/*
+* 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();
+}
+}

Mercurial > jdk8-mips64-public > langtools / file comparison

comparison: src/share/classes/com/sun/tools/javac/util/Bits.java

src/share/classes/com/sun/tools/javac/util/Bits.java