1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/classes/com/sun/tools/javac/util/Bits.java Wed Apr 27 01:34:52 2016 +0800
1.3 @@ -0,0 +1,369 @@
1.4 +/*
1.5 + * Copyright (c) 1999, 2013, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation. Oracle designates this
1.11 + * particular file as subject to the "Classpath" exception as provided
1.12 + * by Oracle in the LICENSE file that accompanied this code.
1.13 + *
1.14 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.15 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.16 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.17 + * version 2 for more details (a copy is included in the LICENSE file that
1.18 + * accompanied this code).
1.19 + *
1.20 + * You should have received a copy of the GNU General Public License version
1.21 + * 2 along with this work; if not, write to the Free Software Foundation,
1.22 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.23 + *
1.24 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.25 + * or visit www.oracle.com if you need additional information or have any
1.26 + * questions.
1.27 + */
1.28 +
1.29 +package com.sun.tools.javac.util;
1.30 +
1.31 +import java.util.Arrays;
1.32 +
1.33 +/** A class for extensible, mutable bit sets.
1.34 + *
1.35 + * <p><b>This is NOT part of any supported API.
1.36 + * If you write code that depends on this, you do so at your own risk.
1.37 + * This code and its internal interfaces are subject to change or
1.38 + * deletion without notice.</b>
1.39 + */
1.40 +public class Bits {
1.41 +
1.42 + // ____________ reset _________
1.43 + // / UNKNOWN \ <-------- / UNINIT \
1.44 + // \____________/ | \_________/
1.45 + // | | |
1.46 + // |assign | | any
1.47 + // | ___________ |
1.48 + // ------> / NORMAL \ <----
1.49 + // \___________/ |
1.50 + // | |
1.51 + // | |
1.52 + // -----------
1.53 + // any
1.54 + protected enum BitsState {
1.55 + /* A Bits instance is in UNKNOWN state if it has been explicitly reset.
1.56 + * It is possible to get to this state from any other by calling the
1.57 + * reset method. An instance in the UNKNOWN state can pass to the
1.58 + * NORMAL state after being assigned another Bits instance.
1.59 + *
1.60 + * Bits instances are final fields in Flow so the UNKNOWN state models
1.61 + * the null assignment.
1.62 + */
1.63 + UNKNOWN,
1.64 + /* A Bits instance is in UNINIT when it is created with the default
1.65 + * constructor but it isn't explicitly reset. The main objective of this
1.66 + * internal state is to save some memory.
1.67 + */
1.68 + UNINIT,
1.69 + /* The normal state is reached after creating a Bits instance from an
1.70 + * existing one or after applying any operation to an instance on UNINIT
1.71 + * or NORMAL state. From this state a bits instance can pass to the
1.72 + * UNKNOWN state by calling the reset method.
1.73 + */
1.74 + NORMAL;
1.75 +
1.76 + static BitsState getState(int[] someBits, boolean reset) {
1.77 + if (reset) {
1.78 + return UNKNOWN;
1.79 + } else {
1.80 + if (someBits != unassignedBits) {
1.81 + return NORMAL;
1.82 + } else {
1.83 + return UNINIT;
1.84 + }
1.85 + }
1.86 + }
1.87 +
1.88 + }
1.89 +
1.90 + private final static int wordlen = 32;
1.91 + private final static int wordshift = 5;
1.92 + private final static int wordmask = wordlen - 1;
1.93 +
1.94 + public int[] bits = null;
1.95 + // This field will store last version of bits after every change.
1.96 + private static final int[] unassignedBits = new int[0];
1.97 +
1.98 + protected BitsState currentState;
1.99 +
1.100 + /** Construct an initially empty set.
1.101 + */
1.102 + public Bits() {
1.103 + this(false);
1.104 + }
1.105 +
1.106 + public Bits(Bits someBits) {
1.107 + this(someBits.dup().bits, BitsState.getState(someBits.bits, false));
1.108 + }
1.109 +
1.110 + public Bits(boolean reset) {
1.111 + this(unassignedBits, BitsState.getState(unassignedBits, reset));
1.112 + }
1.113 +
1.114 + /** Construct a set consisting initially of given bit vector.
1.115 + */
1.116 + protected Bits(int[] bits, BitsState initState) {
1.117 + this.bits = bits;
1.118 + this.currentState = initState;
1.119 + switch (initState) {
1.120 + case UNKNOWN:
1.121 + this.bits = null;
1.122 + break;
1.123 + case NORMAL:
1.124 + Assert.check(bits != unassignedBits);
1.125 + break;
1.126 + }
1.127 + }
1.128 +
1.129 + protected void sizeTo(int len) {
1.130 + if (bits.length < len) {
1.131 + bits = Arrays.copyOf(bits, len);
1.132 + }
1.133 + }
1.134 +
1.135 + /** This set = {}.
1.136 + */
1.137 + public void clear() {
1.138 + Assert.check(currentState != BitsState.UNKNOWN);
1.139 + for (int i = 0; i < bits.length; i++) {
1.140 + bits[i] = 0;
1.141 + }
1.142 + currentState = BitsState.NORMAL;
1.143 + }
1.144 +
1.145 + public void reset() {
1.146 + internalReset();
1.147 + }
1.148 +
1.149 + protected void internalReset() {
1.150 + bits = null;
1.151 + currentState = BitsState.UNKNOWN;
1.152 + }
1.153 +
1.154 + public boolean isReset() {
1.155 + return currentState == BitsState.UNKNOWN;
1.156 + }
1.157 +
1.158 + public Bits assign(Bits someBits) {
1.159 + bits = someBits.dup().bits;
1.160 + currentState = BitsState.NORMAL;
1.161 + return this;
1.162 + }
1.163 +
1.164 + /** Return a copy of this set.
1.165 + */
1.166 + public Bits dup() {
1.167 + Assert.check(currentState != BitsState.UNKNOWN);
1.168 + Bits tmp = new Bits();
1.169 + tmp.bits = dupBits();
1.170 + currentState = BitsState.NORMAL;
1.171 + return tmp;
1.172 + }
1.173 +
1.174 + protected int[] dupBits() {
1.175 + int [] result;
1.176 + if (currentState != BitsState.NORMAL) {
1.177 + result = bits;
1.178 + } else {
1.179 + result = new int[bits.length];
1.180 + System.arraycopy(bits, 0, result, 0, bits.length);
1.181 + }
1.182 + return result;
1.183 + }
1.184 +
1.185 + /** Include x in this set.
1.186 + */
1.187 + public void incl(int x) {
1.188 + Assert.check(currentState != BitsState.UNKNOWN);
1.189 + Assert.check(x >= 0, "Value of x " + x);
1.190 + sizeTo((x >>> wordshift) + 1);
1.191 + bits[x >>> wordshift] = bits[x >>> wordshift] |
1.192 + (1 << (x & wordmask));
1.193 + currentState = BitsState.NORMAL;
1.194 + }
1.195 +
1.196 +
1.197 + /** Include [start..limit) in this set.
1.198 + */
1.199 + public void inclRange(int start, int limit) {
1.200 + Assert.check(currentState != BitsState.UNKNOWN);
1.201 + sizeTo((limit >>> wordshift) + 1);
1.202 + for (int x = start; x < limit; x++) {
1.203 + bits[x >>> wordshift] = bits[x >>> wordshift] |
1.204 + (1 << (x & wordmask));
1.205 + }
1.206 + currentState = BitsState.NORMAL;
1.207 + }
1.208 +
1.209 + /** Exclude [start...end] from this set.
1.210 + */
1.211 + public void excludeFrom(int start) {
1.212 + Assert.check(currentState != BitsState.UNKNOWN);
1.213 + Bits temp = new Bits();
1.214 + temp.sizeTo(bits.length);
1.215 + temp.inclRange(0, start);
1.216 + internalAndSet(temp);
1.217 + currentState = BitsState.NORMAL;
1.218 + }
1.219 +
1.220 + /** Exclude x from this set.
1.221 + */
1.222 + public void excl(int x) {
1.223 + Assert.check(currentState != BitsState.UNKNOWN);
1.224 + Assert.check(x >= 0);
1.225 + sizeTo((x >>> wordshift) + 1);
1.226 + bits[x >>> wordshift] = bits[x >>> wordshift] &
1.227 + ~(1 << (x & wordmask));
1.228 + currentState = BitsState.NORMAL;
1.229 + }
1.230 +
1.231 + /** Is x an element of this set?
1.232 + */
1.233 + public boolean isMember(int x) {
1.234 + Assert.check(currentState != BitsState.UNKNOWN);
1.235 + return
1.236 + 0 <= x && x < (bits.length << wordshift) &&
1.237 + (bits[x >>> wordshift] & (1 << (x & wordmask))) != 0;
1.238 + }
1.239 +
1.240 + /** {@literal this set = this set & xs}.
1.241 + */
1.242 + public Bits andSet(Bits xs) {
1.243 + Assert.check(currentState != BitsState.UNKNOWN);
1.244 + internalAndSet(xs);
1.245 + currentState = BitsState.NORMAL;
1.246 + return this;
1.247 + }
1.248 +
1.249 + protected void internalAndSet(Bits xs) {
1.250 + Assert.check(currentState != BitsState.UNKNOWN);
1.251 + sizeTo(xs.bits.length);
1.252 + for (int i = 0; i < xs.bits.length; i++) {
1.253 + bits[i] = bits[i] & xs.bits[i];
1.254 + }
1.255 + }
1.256 +
1.257 + /** this set = this set | xs.
1.258 + */
1.259 + public Bits orSet(Bits xs) {
1.260 + Assert.check(currentState != BitsState.UNKNOWN);
1.261 + sizeTo(xs.bits.length);
1.262 + for (int i = 0; i < xs.bits.length; i++) {
1.263 + bits[i] = bits[i] | xs.bits[i];
1.264 + }
1.265 + currentState = BitsState.NORMAL;
1.266 + return this;
1.267 + }
1.268 +
1.269 + /** this set = this set \ xs.
1.270 + */
1.271 + public Bits diffSet(Bits xs) {
1.272 + Assert.check(currentState != BitsState.UNKNOWN);
1.273 + for (int i = 0; i < bits.length; i++) {
1.274 + if (i < xs.bits.length) {
1.275 + bits[i] = bits[i] & ~xs.bits[i];
1.276 + }
1.277 + }
1.278 + currentState = BitsState.NORMAL;
1.279 + return this;
1.280 + }
1.281 +
1.282 + /** this set = this set ^ xs.
1.283 + */
1.284 + public Bits xorSet(Bits xs) {
1.285 + Assert.check(currentState != BitsState.UNKNOWN);
1.286 + sizeTo(xs.bits.length);
1.287 + for (int i = 0; i < xs.bits.length; i++) {
1.288 + bits[i] = bits[i] ^ xs.bits[i];
1.289 + }
1.290 + currentState = BitsState.NORMAL;
1.291 + return this;
1.292 + }
1.293 +
1.294 + /** Count trailing zero bits in an int. Algorithm from "Hacker's
1.295 + * Delight" by Henry S. Warren Jr. (figure 5-13)
1.296 + */
1.297 + private static int trailingZeroBits(int x) {
1.298 + Assert.check(wordlen == 32);
1.299 + if (x == 0) {
1.300 + return 32;
1.301 + }
1.302 + int n = 1;
1.303 + if ((x & 0xffff) == 0) { n += 16; x >>>= 16; }
1.304 + if ((x & 0x00ff) == 0) { n += 8; x >>>= 8; }
1.305 + if ((x & 0x000f) == 0) { n += 4; x >>>= 4; }
1.306 + if ((x & 0x0003) == 0) { n += 2; x >>>= 2; }
1.307 + return n - (x&1);
1.308 + }
1.309 +
1.310 + /** Return the index of the least bit position ≥ x that is set.
1.311 + * If none are set, returns -1. This provides a nice way to iterate
1.312 + * over the members of a bit set:
1.313 + * <pre>{@code
1.314 + * for (int i = bits.nextBit(0); i>=0; i = bits.nextBit(i+1)) ...
1.315 + * }</pre>
1.316 + */
1.317 + public int nextBit(int x) {
1.318 + Assert.check(currentState != BitsState.UNKNOWN);
1.319 + int windex = x >>> wordshift;
1.320 + if (windex >= bits.length) {
1.321 + return -1;
1.322 + }
1.323 + int word = bits[windex] & ~((1 << (x & wordmask))-1);
1.324 + while (true) {
1.325 + if (word != 0) {
1.326 + return (windex << wordshift) + trailingZeroBits(word);
1.327 + }
1.328 + windex++;
1.329 + if (windex >= bits.length) {
1.330 + return -1;
1.331 + }
1.332 + word = bits[windex];
1.333 + }
1.334 + }
1.335 +
1.336 + /** a string representation of this set.
1.337 + */
1.338 + @Override
1.339 + public String toString() {
1.340 + if (bits != null && bits.length > 0) {
1.341 + char[] digits = new char[bits.length * wordlen];
1.342 + for (int i = 0; i < bits.length * wordlen; i++) {
1.343 + digits[i] = isMember(i) ? '1' : '0';
1.344 + }
1.345 + return new String(digits);
1.346 + } else {
1.347 + return "[]";
1.348 + }
1.349 + }
1.350 +
1.351 + /** Test Bits.nextBit(int). */
1.352 + public static void main(String[] args) {
1.353 + java.util.Random r = new java.util.Random();
1.354 + Bits bits = new Bits();
1.355 + for (int i=0; i<125; i++) {
1.356 + int k;
1.357 + do {
1.358 + k = r.nextInt(250);
1.359 + } while (bits.isMember(k));
1.360 + System.out.println("adding " + k);
1.361 + bits.incl(k);
1.362 + }
1.363 + int count = 0;
1.364 + for (int i = bits.nextBit(0); i >= 0; i = bits.nextBit(i+1)) {
1.365 + System.out.println("found " + i);
1.366 + count ++;
1.367 + }
1.368 + if (count != 125) {
1.369 + throw new Error();
1.370 + }
1.371 + }
1.372 +}
