1 /*
   2  * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package jdk.nashorn.internal.runtime;
  27 
  28 import java.util.Arrays;
  29 
  30 /**
  31  * Faster implementation of BitSet
  32  */
  33 public final class BitVector implements Cloneable {
  34     /** Number of bits per slot. */
  35     private static final int BITSPERSLOT = 64;
  36 
  37     /** Growth quanta when resizing. */
  38     private static final int SLOTSQUANTA = 4;
  39 
  40     /** Shift for indexing. */
  41     private static final int BITSHIFT = 6;
  42 
  43     /** Mask for indexing. */
  44     private static final int BITMASK = BITSPERSLOT - 1;
  45 
  46     /** Bit area. */
  47     private long[] bits;
  48 
  49     /**
  50      * Constructor.
  51      */
  52     public BitVector() {
  53         this.bits = new long[SLOTSQUANTA];
  54     }
  55 
  56     /**
  57      * Constructor
  58      * @param length initial length in bits
  59      */
  60     public BitVector(final long length) {
  61         final int need = (int)growthNeeded(length);
  62         this.bits = new long[need];
  63     }
  64 
  65     /**
  66      * Copy constructor
  67      * @param bits a bits array from another bit vector
  68      */
  69     public BitVector(final long[] bits) {
  70         this.bits = bits.clone();
  71     }
  72 
  73     /**
  74      * Copy another BitVector into this one
  75      * @param other the source
  76      */
  77     public void copy(final BitVector other) {
  78         bits = other.bits.clone();
  79     }
  80 
  81     /**
  82      * Calculate the number of slots need for the specified length of bits.
  83      * @param length Number of bits required.
  84      * @return Number of slots needed.
  85      */
  86     private static long slotsNeeded(final long length) {
  87         return (length + BITMASK) >> BITSHIFT;
  88     }
  89 
  90     /**
  91      * Calculate the number of slots need for the specified length of bits
  92      * rounded to allocation quanta.
  93      * @param length Number of bits required.
  94      * @return Number of slots needed rounded to allocation quanta.
  95      */
  96     private static long growthNeeded(final long length) {
  97         return (slotsNeeded(length) + SLOTSQUANTA - 1) / SLOTSQUANTA * SLOTSQUANTA;
  98     }
  99 
 100     /**
 101      * Return a slot from bits, zero if slot is beyond length.
 102      * @param index Slot index.
 103      * @return Slot value.
 104      */
 105     private long slot(final int index) {
 106         return 0 <= index && index < bits.length ? bits[index] : 0L;
 107     }
 108 
 109     /**
 110      * Resize the bit vector to accommodate the new length.
 111      * @param length Number of bits required.
 112      */
 113     public void resize(final long length) {
 114         final int need = (int)growthNeeded(length);
 115 
 116         if (bits.length != need) {
 117             bits = Arrays.copyOf(bits, need);
 118         }
 119 
 120         final int shift = (int)(length & BITMASK);
 121         int slot = (int)(length >> BITSHIFT);
 122 
 123         if (shift != 0) {
 124             bits[slot] &= (1L << shift) - 1;
 125             slot++;
 126         }
 127 
 128         for ( ; slot < bits.length; slot++) {
 129             bits[slot] = 0;
 130         }
 131     }
 132 
 133     /**
 134      * Set a bit in the bit vector.
 135      * @param bit Bit number.
 136      */
 137     public void set(final long bit) {
 138         bits[(int)(bit >> BITSHIFT)] |= (1L << (int)(bit & BITMASK));
 139     }
 140 
 141     /**
 142      * Clear a bit in the bit vector.
 143      * @param bit Bit number.
 144      */
 145     public void clear(final long bit) {
 146         bits[(int)(bit >> BITSHIFT)] &= ~(1L << (int)(bit & BITMASK));
 147     }
 148 
 149     /**
 150      * Toggle a bit in the bit vector.
 151      * @param bit Bit number.
 152      */
 153     public void toggle(final long bit) {
 154         bits[(int)(bit >> BITSHIFT)] ^= (1L << (int)(bit & BITMASK));
 155     }
 156 
 157     /**
 158      * Sets all bits in the vector up to the length.
 159      *
 160      * @param length max bit where to stop setting bits
 161      */
 162     public void setTo(final long length) {
 163         if (0 < length) {
 164             final int lastWord = (int)(length >> BITSHIFT);
 165             final long lastBits = (1L << (int)(length & BITMASK)) - 1L;
 166             Arrays.fill(bits, 0, lastWord, ~0L);
 167 
 168             if (lastBits != 0L) {
 169                 bits[lastWord] |= lastBits;
 170             }
 171         }
 172     }
 173 
 174     /**
 175      * Clears all bits in the vector.
 176      */
 177     public void clearAll() {
 178         Arrays.fill(bits, 0L);
 179     }
 180 
 181     /**
 182      * Test if bit is set in the bit vector.
 183      * @param bit Bit number.
 184      * @return true if bit in question is set
 185      */
 186     public boolean isSet(final long bit) {
 187         return (bits[(int)(bit >> BITSHIFT)] & (1L << (int)(bit & BITMASK))) != 0;
 188     }
 189 
 190     /**
 191      * Test if a bit is clear in the bit vector.
 192      * @param bit Bit number.
 193      * @return true if bit in question is clear
 194      */
 195     public boolean isClear(final long bit) {
 196         return (bits[(int)(bit >> BITSHIFT)] & (1L << (int)(bit & BITMASK))) == 0;
 197     }
 198 
 199     /**
 200      * Shift bits to the left by shift.
 201      * @param shift  Amount of shift.
 202      * @param length Length of vector after shift.
 203      */
 204     public void shiftLeft(final long shift, final long length) {
 205         if (shift != 0) {
 206             final int leftShift  = (int)(shift & BITMASK);
 207             final int rightShift = BITSPERSLOT - leftShift;
 208             final int slotShift  = (int)(shift >> BITSHIFT);
 209             final int slotCount  = bits.length - slotShift;
 210             int slot, from;
 211 
 212             if (leftShift == 0) {
 213                 for (slot = 0, from = slotShift; slot < slotCount; slot++, from++) {
 214                     bits[slot] = slot(from);
 215                 }
 216             } else {
 217                 for (slot = 0, from = slotShift; slot < slotCount; slot++) {
 218                     bits[slot] = (slot(from) >>>  leftShift) | (slot(++from) <<  rightShift);
 219                 }
 220             }
 221         }
 222 
 223         resize(length);
 224     }
 225 
 226     /**
 227      * Shift bits to the right by shift.
 228      * @param shift  Amount of shift.
 229      * @param length Length of vector after shift.
 230      */
 231     public void shiftRight(final long shift, final long length) {
 232         // Make room.
 233         resize(length);
 234 
 235         if (shift != 0) {
 236             final int rightShift  = (int)(shift & BITMASK);
 237             final int leftShift = BITSPERSLOT - rightShift;
 238             final int slotShift  = (int)(shift >> BITSHIFT);
 239             int slot, from;
 240 
 241             if (leftShift == 0) {
 242                 for (slot = bits.length, from = slot - slotShift; slot >= slotShift;) {
 243                     slot--; from--;
 244                     bits[slot] = slot(from);
 245                 }
 246             } else {
 247                 for (slot = bits.length, from = slot - slotShift; slot > 0;) {
 248                     slot--; from--;
 249                     bits[slot] = (slot(from - 1) >>>  leftShift) | (slot(from) <<  rightShift);
 250                 }
 251             }
 252         }
 253 
 254         // Mask out surplus.
 255         resize(length);
 256     }
 257 
 258     /**
 259      * Set a bit range.
 260      * @param fromIndex  from index (inclusive)
 261      * @param toIndex    to index (exclusive)
 262      */
 263     public void setRange(final long fromIndex, final long toIndex) {
 264         if (fromIndex < toIndex) {
 265             final int firstWord = (int)(fromIndex >> BITSHIFT);
 266             final int lastWord = (int)(toIndex - 1 >> BITSHIFT);
 267             final long firstBits = (~0L << fromIndex);
 268             final long lastBits = (~0L >>> -toIndex);
 269             if (firstWord == lastWord) {
 270                 bits[firstWord] |= firstBits & lastBits;
 271             } else {
 272                 bits[firstWord] |= firstBits;
 273                 Arrays.fill(bits, firstWord + 1, lastWord, ~0L);
 274                 bits[lastWord] |= lastBits;
 275             }
 276         }
 277     }
 278 }