content: /*
   * 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 openjdk.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;
                  }
              }
          }
  
      }
  
  
      public enum BitsOpKind {
          INIT,
          CLEAR,
          INCL_BIT,
          EXCL_BIT,
          ASSIGN,
          AND_SET,
          OR_SET,
          DIFF_SET,
          XOR_SET,
          INCL_RANGE,
          EXCL_RANGE,
      }
  
      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);
          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
              0 <= 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 "[]";
          }
      }
  
  }
  