jdk8-mips64-public/langtools: src/share/classes/com/sun/tools/javac/util/Bits.java@ca5783d9a597 (annotated)

src/share/classes/com/sun/tools/javac/util/Bits.java@ca5783d9a597 (annotated)

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

Mon, 16 Oct 2017 16:07:48 +0800

author: aoqi
date: Mon, 16 Oct 2017 16:07:48 +0800
changeset 2893: ca5783d9a597
parent 2820: 7f6d6b80a58b
parent 2702: 9ca8d8713094
permissions: -rw-r--r--

merge

 /*
  * Copyright (c) 1999, 2015, Oracle and/or its affiliates. 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.  Oracle designates this
  * particular file as subject to the "Classpath" exception as provided
  * by Oracle 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  * or visit www.oracle.com if you need additional information or have any
  * questions.
  */
 package com.sun.tools.javac.util;
 import java.util.Arrays;
 /** A class for extensible, mutable bit sets.
  *
  *  <p><b>This is NOT part of any supported API.
  *  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 {
     //       ____________      reset    _________
     //      /  UNKNOWN   \   <-------- / UNINIT  \
     //      \____________/       |     \_________/
     //            |              |          |
     //            |assign        |          | any
     //            |        ___________      |
     //            ------> /  NORMAL   \ <----
     //                    \___________/     |
     //                            |         |
     //                            |         |
     //                            -----------
     //                               any
     protected enum BitsState {
         /*  A Bits instance is in UNKNOWN state if it has been explicitly reset.
          *  It is possible to get to this state from any other by calling the
          *  reset method. An instance in the UNKNOWN state can pass to the
          *  NORMAL state after being assigned another Bits instance.
          *
          *  Bits instances are final fields in Flow so the UNKNOWN state models
          *  the null assignment.
          */
         UNKNOWN,
         /*  A Bits instance is in UNINIT when it is created with the default
          *  constructor but it isn't explicitly reset. The main objective of this
          *  internal state is to save some memory.
          */
         UNINIT,
         /*  The normal state is reached after creating a Bits instance from an
          *  existing one or after applying any operation to an instance on UNINIT
          *  or NORMAL state. From this state a bits instance can pass to the
          *  UNKNOWN state by calling the reset method.
          */
         NORMAL;
         static BitsState getState(int[] someBits, boolean reset) {
             if (reset) {
                 return UNKNOWN;
             } else {
                 if (someBits != unassignedBits) {
                     return NORMAL;
                 } else {
                     return UNINIT;
                 }
             }
         }
     }
     private final static int wordlen = 32;
     private final static int wordshift = 5;
     private final static int wordmask = wordlen - 1;
     public int[] bits = null;
     // This field will store last version of bits after every change.
     private static final int[] unassignedBits = new int[0];
     protected BitsState currentState;
     /** Construct an initially empty set.
      */
     public Bits() {
         this(false);
     }
     public Bits(Bits someBits) {
         this(someBits.dup().bits, BitsState.getState(someBits.bits, false));
     }
     public Bits(boolean reset) {
         this(unassignedBits, BitsState.getState(unassignedBits, reset));
     }
     /** Construct a set consisting initially of given bit vector.
      */
     protected Bits(int[] bits, BitsState initState) {
         this.bits = bits;
         this.currentState = initState;
         switch (initState) {
             case UNKNOWN:
                 this.bits = null;
                 break;
             case NORMAL:
                 Assert.check(bits != unassignedBits);
                 break;
         }
     }
     protected void sizeTo(int len) {
         if (bits.length < len) {
             bits = Arrays.copyOf(bits, len);
         }
     }
     /** This set = {}.
      */
     public void clear() {
         Assert.check(currentState != BitsState.UNKNOWN);
         for (int i = 0; i < bits.length; i++) {
             bits[i] = 0;
         }
         currentState = BitsState.NORMAL;
     }
     public void reset() {
         internalReset();
     }
     protected void internalReset() {
         bits = null;
         currentState = BitsState.UNKNOWN;
     }
     public boolean isReset() {
         return currentState == BitsState.UNKNOWN;
     }
     public Bits assign(Bits someBits) {
         bits = someBits.dup().bits;
         currentState = BitsState.NORMAL;
         return this;
     }
     /** Return a copy of this set.
      */
     public Bits dup() {
         Assert.check(currentState != BitsState.UNKNOWN);
         Bits tmp = new Bits();
         tmp.bits = dupBits();
         currentState = BitsState.NORMAL;
         return tmp;
     }
     protected int[] dupBits() {
         int [] result;
         if (currentState != BitsState.NORMAL) {
             result = bits;
         } else {
             result = new int[bits.length];
             System.arraycopy(bits, 0, result, 0, bits.length);
         }
         return result;
     }
     /** Include x in this set.
      */
     public void incl(int x) {
         Assert.check(currentState != BitsState.UNKNOWN);
         Assert.check(x >= 0, "Value of x " + x);
         sizeTo((x >>> wordshift) + 1);
         bits[x >>> wordshift] = bits[x >>> wordshift] |
             (1 << (x & wordmask));
         currentState = BitsState.NORMAL;
     }
     /** Include [start..limit) in this set.
      */
     public void inclRange(int start, int limit) {
         Assert.check(currentState != BitsState.UNKNOWN);
         sizeTo((limit >>> wordshift) + 1);
         for (int x = start; x < limit; x++) {
             bits[x >>> wordshift] = bits[x >>> wordshift] |
                 (1 << (x & wordmask));
         }
         currentState = BitsState.NORMAL;
     }
     /** Exclude [start...end] from this set.
      */
     public void excludeFrom(int start) {
         Assert.check(currentState != BitsState.UNKNOWN);
         Bits temp = new Bits();
         temp.sizeTo(bits.length);
         temp.inclRange(0, start);
         internalAndSet(temp);
         currentState = BitsState.NORMAL;
     }
     /** Exclude x from this set.
      */
     public void excl(int x) {
         Assert.check(currentState != BitsState.UNKNOWN);
         Assert.check(x >= 0);
         sizeTo((x >>> wordshift) + 1);
         bits[x >>> wordshift] = bits[x >>> wordshift] &
             ~(1 << (x & wordmask));
         currentState = BitsState.NORMAL;
     }
     /** Is x an element of this set?
      */
     public boolean isMember(int x) {
         Assert.check(currentState != BitsState.UNKNOWN);
         return
 <= x && x < (bits.length << wordshift) &&
             (bits[x >>> wordshift] & (1 << (x & wordmask))) != 0;
     }
     /** {@literal this set = this set & xs}.
      */
     public Bits andSet(Bits xs) {
         Assert.check(currentState != BitsState.UNKNOWN);
         internalAndSet(xs);
         currentState = BitsState.NORMAL;
         return this;
     }
     protected void internalAndSet(Bits xs) {
         Assert.check(currentState != BitsState.UNKNOWN);
         sizeTo(xs.bits.length);
         for (int i = 0; i < xs.bits.length; i++) {
             bits[i] = bits[i] & xs.bits[i];
         }
     }
     /** this set = this set | xs.
      */
     public Bits orSet(Bits xs) {
         Assert.check(currentState != BitsState.UNKNOWN);
         sizeTo(xs.bits.length);
         for (int i = 0; i < xs.bits.length; i++) {
             bits[i] = bits[i] | xs.bits[i];
         }
         currentState = BitsState.NORMAL;
         return this;
     }
     /** this set = this set \ xs.
      */
     public Bits diffSet(Bits xs) {
         Assert.check(currentState != BitsState.UNKNOWN);
         for (int i = 0; i < bits.length; i++) {
             if (i < xs.bits.length) {
                 bits[i] = bits[i] & ~xs.bits[i];
             }
         }
         currentState = BitsState.NORMAL;
         return this;
     }
     /** this set = this set ^ xs.
      */
     public Bits xorSet(Bits xs) {
         Assert.check(currentState != BitsState.UNKNOWN);
         sizeTo(xs.bits.length);
         for (int i = 0; i < xs.bits.length; i++) {
             bits[i] = bits[i] ^ xs.bits[i];
         }
         currentState = BitsState.NORMAL;
         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.check(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 &ge; 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>{@code
      *  for (int i = bits.nextBit(0); i>=0; i = bits.nextBit(i+1)) ...
      *  }</pre>
      */
     public int nextBit(int x) {
         Assert.check(currentState != BitsState.UNKNOWN);
         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.
      */
     @Override
     public String toString() {
         if (bits != null && bits.length > 0) {
             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);
         } else {
             return "[]";
         }
     }
     /** Test Bits.nextBit(int). */
     public static void main(String[] args) {
         java.util.Random r = new java.util.Random();
         Bits bits = new Bits();
         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 / annotate

src/share/classes/com/sun/tools/javac/util/Bits.java@ca5783d9a597 (annotated)

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