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 26package jdk.nashorn.internal.runtime; 27 28import java.util.Arrays; 29 30/** 31 * Faster implementation of BitSet 32 */ 33public 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} 279