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