1.1 --- a/src/share/classes/com/sun/tools/javac/util/Bits.java Fri Apr 26 10:04:01 2013 +0100
1.2 +++ b/src/share/classes/com/sun/tools/javac/util/Bits.java Fri Apr 26 10:17:01 2013 +0100
1.3 @@ -1,5 +1,5 @@
1.4 /*
1.5 - * Copyright (c) 1999, 2012, Oracle and/or its affiliates. All rights reserved.
1.6 + * Copyright (c) 1999, 2013, Oracle and/or its affiliates. All rights reserved.
1.7 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.8 *
1.9 * This code is free software; you can redistribute it and/or modify it
1.10 @@ -27,6 +27,8 @@
1.11
1.12 import java.util.Arrays;
1.13
1.14 +import static com.sun.tools.javac.util.Bits.BitsOpKind.*;
1.15 +
1.16 /** A class for extensible, mutable bit sets.
1.17 *
1.18 * <p><b>This is NOT part of any supported API.
1.19 @@ -36,31 +38,114 @@
1.20 */
1.21 public class Bits {
1.22
1.23 + public enum BitsOpKind {
1.24 + INIT,
1.25 + CLEAR,
1.26 + INCL_BIT,
1.27 + EXCL_BIT,
1.28 + ASSIGN,
1.29 + AND_SET,
1.30 + OR_SET,
1.31 + DIFF_SET,
1.32 + XOR_SET,
1.33 + INCL_RANGE,
1.34 + EXCL_RANGE,
1.35 + }
1.36 +
1.37 + // ____________ reset _________
1.38 + // / UNKNOWN \ <-------- / UNINIT \
1.39 + // \____________/ | \_________/
1.40 + // | | |
1.41 + // |assign | | any
1.42 + // | ___________ |
1.43 + // ------> / NORMAL \ <----
1.44 + // \___________/ |
1.45 + // | |
1.46 + // | |
1.47 + // -----------
1.48 + // any
1.49 + private enum BitsState {
1.50 + /* A Bits instance is in UNKNOWN state if it has been explicitly reset.
1.51 + * It is possible to get to this state from any other by calling the
1.52 + * reset method. An instance in the UNKNOWN state can pass to the
1.53 + * NORMAL state after being assigned another Bits instance.
1.54 + */
1.55 + UNKNOWN,
1.56 + /* A Bits instance is in UNINIT when it is created with the default
1.57 + * constructor but it isn't explicitly reset. The main objective of this
1.58 + * internal state is to save some memory.
1.59 + */
1.60 + UNINIT,
1.61 + /* The normal state is reached after creating a Bits instance from an
1.62 + * existing one or after applying any operation to an instance on UNINIT
1.63 + * or NORMAL state. From this state a bits instance can pass to the
1.64 + * UNKNOWN state by calling the reset method.
1.65 + */
1.66 + NORMAL;
1.67 +
1.68 + static BitsState getState(int[] someBits, boolean reset) {
1.69 + if (reset) {
1.70 + return UNKNOWN;
1.71 + } else {
1.72 + if (someBits != unassignedBits) {
1.73 + return NORMAL;
1.74 + } else {
1.75 + return UNINIT;
1.76 + }
1.77 + }
1.78 + }
1.79 +
1.80 + }
1.81
1.82 private final static int wordlen = 32;
1.83 private final static int wordshift = 5;
1.84 private final static int wordmask = wordlen - 1;
1.85
1.86 - private int[] bits;
1.87 + public int[] bits = null;
1.88 + // This field will store last version of bits after every change.
1.89 + public int[] oldBits = null;
1.90 +
1.91 + public BitsOpKind lastOperation = null;
1.92 +
1.93 + private static final int[] unassignedBits = new int[0];
1.94 +
1.95 + private BitsState currentState;
1.96
1.97 /** Construct an initially empty set.
1.98 */
1.99 public Bits() {
1.100 - this(new int[1]);
1.101 + this(false);
1.102 + }
1.103 +
1.104 + public Bits(Bits someBits) {
1.105 + this(someBits.dup().bits, BitsState.getState(someBits.bits, false));
1.106 + }
1.107 +
1.108 + public Bits(boolean reset) {
1.109 + this(unassignedBits, BitsState.getState(unassignedBits, reset));
1.110 }
1.111
1.112 /** Construct a set consisting initially of given bit vector.
1.113 */
1.114 - public Bits(int[] bits) {
1.115 + private Bits(int[] bits, BitsState initState) {
1.116 this.bits = bits;
1.117 + this.currentState = initState;
1.118 + switch (initState) {
1.119 + case UNKNOWN:
1.120 + reset(); //this will also set current state;
1.121 + break;
1.122 + case NORMAL:
1.123 + Assert.check(bits != unassignedBits);
1.124 + lastOperation = INIT;
1.125 + break;
1.126 + }
1.127 }
1.128
1.129 - /** Construct a set consisting initially of given range.
1.130 + /** This method will be called after any operation that causes a change to
1.131 + * the bits. Subclasses can thus override it in order to extract information
1.132 + * from the changes produced to the bits by the given operation.
1.133 */
1.134 - public Bits(int start, int limit) {
1.135 - this();
1.136 - inclRange(start, limit);
1.137 - }
1.138 + public void changed() {}
1.139
1.140 private void sizeTo(int len) {
1.141 if (bits.length < len) {
1.142 @@ -71,57 +156,110 @@
1.143 /** This set = {}.
1.144 */
1.145 public void clear() {
1.146 + Assert.check(currentState != BitsState.UNKNOWN);
1.147 + oldBits = bits;
1.148 + lastOperation = CLEAR;
1.149 for (int i = 0; i < bits.length; i++) bits[i] = 0;
1.150 + changed();
1.151 + currentState = BitsState.NORMAL;
1.152 + }
1.153 +
1.154 + public void reset() {
1.155 + bits = null;
1.156 + oldBits = null;
1.157 + currentState = BitsState.UNKNOWN;
1.158 + }
1.159 +
1.160 + public boolean isReset() {
1.161 + return currentState == BitsState.UNKNOWN;
1.162 + }
1.163 +
1.164 + public Bits assign(Bits someBits) {
1.165 + lastOperation = ASSIGN;
1.166 + oldBits = bits;
1.167 + bits = someBits.dup().bits;
1.168 + changed();
1.169 + currentState = BitsState.NORMAL;
1.170 + return this;
1.171 }
1.172
1.173 /** Return a copy of this set.
1.174 */
1.175 - public Bits dup() {
1.176 - int[] newbits = new int[bits.length];
1.177 - System.arraycopy(bits, 0, newbits, 0, bits.length);
1.178 - return new Bits(newbits);
1.179 + private Bits dup() {
1.180 + Assert.check(currentState != BitsState.UNKNOWN);
1.181 + Bits tmp = new Bits();
1.182 + if (currentState != BitsState.NORMAL) {
1.183 + tmp.bits = bits;
1.184 + } else {
1.185 + tmp.bits = new int[bits.length];
1.186 + System.arraycopy(bits, 0, tmp.bits, 0, bits.length);
1.187 + }
1.188 + currentState = BitsState.NORMAL;
1.189 + return tmp;
1.190 }
1.191
1.192 /** Include x in this set.
1.193 */
1.194 public void incl(int x) {
1.195 + Assert.check(currentState != BitsState.UNKNOWN);
1.196 Assert.check(x >= 0);
1.197 + oldBits = bits;
1.198 + lastOperation = INCL_BIT;
1.199 sizeTo((x >>> wordshift) + 1);
1.200 bits[x >>> wordshift] = bits[x >>> wordshift] |
1.201 (1 << (x & wordmask));
1.202 + changed();
1.203 + currentState = BitsState.NORMAL;
1.204 }
1.205
1.206
1.207 /** Include [start..limit) in this set.
1.208 */
1.209 public void inclRange(int start, int limit) {
1.210 + Assert.check(currentState != BitsState.UNKNOWN);
1.211 + oldBits = bits;
1.212 + lastOperation = INCL_RANGE;
1.213 sizeTo((limit >>> wordshift) + 1);
1.214 - for (int x = start; x < limit; x++)
1.215 + for (int x = start; x < limit; x++) {
1.216 bits[x >>> wordshift] = bits[x >>> wordshift] |
1.217 (1 << (x & wordmask));
1.218 + }
1.219 + changed();
1.220 + currentState = BitsState.NORMAL;
1.221 }
1.222
1.223 /** Exclude [start...end] from this set.
1.224 */
1.225 public void excludeFrom(int start) {
1.226 + Assert.check(currentState != BitsState.UNKNOWN);
1.227 + oldBits = bits;
1.228 + lastOperation = EXCL_RANGE;
1.229 Bits temp = new Bits();
1.230 temp.sizeTo(bits.length);
1.231 temp.inclRange(0, start);
1.232 - andSet(temp);
1.233 + internalAndSet(temp);
1.234 + changed();
1.235 + currentState = BitsState.NORMAL;
1.236 }
1.237
1.238 /** Exclude x from this set.
1.239 */
1.240 public void excl(int x) {
1.241 + Assert.check(currentState != BitsState.UNKNOWN);
1.242 Assert.check(x >= 0);
1.243 + oldBits = bits;
1.244 + lastOperation = EXCL_BIT;
1.245 sizeTo((x >>> wordshift) + 1);
1.246 bits[x >>> wordshift] = bits[x >>> wordshift] &
1.247 ~(1 << (x & wordmask));
1.248 + changed();
1.249 + currentState = BitsState.NORMAL;
1.250 }
1.251
1.252 /** Is x an element of this set?
1.253 */
1.254 public boolean isMember(int x) {
1.255 + Assert.check(currentState != BitsState.UNKNOWN);
1.256 return
1.257 0 <= x && x < (bits.length << wordshift) &&
1.258 (bits[x >>> wordshift] & (1 << (x & wordmask))) != 0;
1.259 @@ -130,38 +268,66 @@
1.260 /** {@literal this set = this set & xs}.
1.261 */
1.262 public Bits andSet(Bits xs) {
1.263 + Assert.check(currentState != BitsState.UNKNOWN);
1.264 + oldBits = bits;
1.265 + lastOperation = AND_SET;
1.266 + internalAndSet(xs);
1.267 + changed();
1.268 + currentState = BitsState.NORMAL;
1.269 + return this;
1.270 + }
1.271 +
1.272 + private void internalAndSet(Bits xs) {
1.273 + Assert.check(currentState != BitsState.UNKNOWN);
1.274 sizeTo(xs.bits.length);
1.275 - for (int i = 0; i < xs.bits.length; i++)
1.276 + for (int i = 0; i < xs.bits.length; i++) {
1.277 bits[i] = bits[i] & xs.bits[i];
1.278 - return this;
1.279 + }
1.280 }
1.281
1.282 /** this set = this set | xs.
1.283 */
1.284 public Bits orSet(Bits xs) {
1.285 + Assert.check(currentState != BitsState.UNKNOWN);
1.286 + oldBits = bits;
1.287 + lastOperation = OR_SET;
1.288 sizeTo(xs.bits.length);
1.289 - for (int i = 0; i < xs.bits.length; i++)
1.290 + for (int i = 0; i < xs.bits.length; i++) {
1.291 bits[i] = bits[i] | xs.bits[i];
1.292 + }
1.293 + changed();
1.294 + currentState = BitsState.NORMAL;
1.295 return this;
1.296 }
1.297
1.298 /** this set = this set \ xs.
1.299 */
1.300 public Bits diffSet(Bits xs) {
1.301 + Assert.check(currentState != BitsState.UNKNOWN);
1.302 + oldBits = bits;
1.303 + lastOperation = DIFF_SET;
1.304 for (int i = 0; i < bits.length; i++) {
1.305 if (i < xs.bits.length) {
1.306 bits[i] = bits[i] & ~xs.bits[i];
1.307 }
1.308 }
1.309 + changed();
1.310 + currentState = BitsState.NORMAL;
1.311 return this;
1.312 }
1.313
1.314 /** this set = this set ^ xs.
1.315 */
1.316 public Bits xorSet(Bits xs) {
1.317 + Assert.check(currentState != BitsState.UNKNOWN);
1.318 + oldBits = bits;
1.319 + lastOperation = XOR_SET;
1.320 sizeTo(xs.bits.length);
1.321 - for (int i = 0; i < xs.bits.length; i++)
1.322 + for (int i = 0; i < xs.bits.length; i++) {
1.323 bits[i] = bits[i] ^ xs.bits[i];
1.324 + }
1.325 + changed();
1.326 + currentState = BitsState.NORMAL;
1.327 return this;
1.328 }
1.329
1.330 @@ -187,6 +353,7 @@
1.331 * }</pre>
1.332 */
1.333 public int nextBit(int x) {
1.334 + Assert.check(currentState != BitsState.UNKNOWN);
1.335 int windex = x >>> wordshift;
1.336 if (windex >= bits.length) return -1;
1.337 int word = bits[windex] & ~((1 << (x & wordmask))-1);
1.338 @@ -202,17 +369,20 @@
1.339 /** a string representation of this set.
1.340 */
1.341 public String toString() {
1.342 - char[] digits = new char[bits.length * wordlen];
1.343 - for (int i = 0; i < bits.length * wordlen; i++)
1.344 - digits[i] = isMember(i) ? '1' : '0';
1.345 - return new String(digits);
1.346 + if (bits.length > 0) {
1.347 + char[] digits = new char[bits.length * wordlen];
1.348 + for (int i = 0; i < bits.length * wordlen; i++)
1.349 + digits[i] = isMember(i) ? '1' : '0';
1.350 + return new String(digits);
1.351 + } else {
1.352 + return "[]";
1.353 + }
1.354 }
1.355
1.356 /** Test Bits.nextBit(int). */
1.357 public static void main(String[] args) {
1.358 java.util.Random r = new java.util.Random();
1.359 Bits bits = new Bits();
1.360 - int dupCount = 0;
1.361 for (int i=0; i<125; i++) {
1.362 int k;
1.363 do {
