Modified: cassandra/trunk/src/java/org/apache/cassandra/utils/obs/OpenBitSet.java URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/utils/obs/OpenBitSet.java?rev=1190047&r1=1190046&r2=1190047&view=diff ============================================================================== --- cassandra/trunk/src/java/org/apache/cassandra/utils/obs/OpenBitSet.java (original) +++ cassandra/trunk/src/java/org/apache/cassandra/utils/obs/OpenBitSet.java Thu Oct 27 21:44:27 2011 @@ -73,42 +73,60 @@ Test system: AMD Opteron, 64 bit linux, </table> */ -public class OpenBitSet implements Cloneable, Serializable { - protected long[] bits; +public class OpenBitSet implements Serializable { + protected long[][] bits; protected int wlen; // number of words (elements) used in the array + /** + * length of bits[][] page in long[] elements. + * Choosing unform size for all sizes of bitsets fight fragmentation for very large + * bloom filters. + */ + protected static final int PAGE_SIZE= 4096; /** Constructs an OpenBitSet large enough to hold numBits. * * @param numBits */ - public OpenBitSet(long numBits) { - bits = new long[bits2words(numBits)]; - wlen = bits.length; + public OpenBitSet(long numBits) + { + this(numBits,true); + } + + public OpenBitSet(long numBits, boolean allocatePages) + { + wlen= bits2words(numBits); + + bits = new long[getPageCount()][]; + + if (allocatePages) + { + for (int allocated=0,i=0;allocated<wlen;allocated+=PAGE_SIZE,i++) + bits[i]=new long[PAGE_SIZE]; + } } public OpenBitSet() { this(64); } - /** Constructs an OpenBitSet from an existing long[]. - * <br/> - * The first 64 bits are in long[0], - * with bit index 0 at the least significant bit, and bit index 63 at the most significant. - * Given a bit index, - * the word containing it is long[index/64], and it is at bit number index%64 within that word. - * <p> - * numWords are the number of elements in the array that contain - * set bits (non-zero longs). - * numWords should be <= bits.length, and - * any existing words in the array at position >= numWords should be zero. - * + /** + * @return the pageSize */ - public OpenBitSet(long[] bits, int numWords) { - this.bits = bits; - this.wlen = numWords; + public int getPageSize() + { + return PAGE_SIZE; + } + + public int getPageCount() + { + return wlen / PAGE_SIZE + 1; } - + public long[] getPage(int pageIdx) + { + return bits[pageIdx]; + } + /** Contructs an OpenBitset from a BitSet */ public OpenBitSet(BitSet bits) { @@ -116,7 +134,7 @@ public class OpenBitSet implements Clone } /** Returns the current capacity in bits (1 greater than the index of the last bit) */ - public long capacity() { return bits.length << 6; } + public long capacity() { return ((long)wlen) << 6; } /** * Returns the current capacity of this set. Included for @@ -127,37 +145,29 @@ public class OpenBitSet implements Clone } // @Override -- not until Java 1.6 - public int length() { - return bits.length << 6; + public long length() { + return capacity(); } /** Returns true if there are no set bits */ public boolean isEmpty() { return cardinality()==0; } - /** Expert: returns the long[] storing the bits */ - public long[] getBits() { return bits; } - - /** Expert: sets a new long[] to use as the bit storage */ - public void setBits(long[] bits) { this.bits = bits; } /** Expert: gets the number of longs in the array that are in use */ public int getNumWords() { return wlen; } - /** Expert: sets the number of longs in the array that are in use */ - public void setNumWords(int nWords) { this.wlen=nWords; } - - /** Returns true or false for the specified bit index. */ public boolean get(int index) { int i = index >> 6; // div 64 // signed shift will keep a negative index and force an // array-index-out-of-bounds-exception, removing the need for an explicit check. - if (i>=bits.length) return false; + if (i>=wlen) return false; int bit = index & 0x3f; // mod 64 long bitmask = 1L << bit; - return (bits[i] & bitmask) != 0; + // TODO perfectionist one can implement this using bit operations + return (bits[i / PAGE_SIZE ][i % PAGE_SIZE] & bitmask) != 0; } @@ -170,7 +180,8 @@ public class OpenBitSet implements Clone // array-index-out-of-bounds-exception, removing the need for an explicit check. int bit = index & 0x3f; // mod 64 long bitmask = 1L << bit; - return (bits[i] & bitmask) != 0; + // TODO perfectionist one can implement this using bit operations + return (bits[i / PAGE_SIZE][i % PAGE_SIZE ] & bitmask) != 0; } @@ -179,10 +190,11 @@ public class OpenBitSet implements Clone */ public boolean get(long index) { int i = (int)(index >> 6); // div 64 - if (i>=bits.length) return false; + if (i>=wlen) return false; int bit = (int)index & 0x3f; // mod 64 long bitmask = 1L << bit; - return (bits[i] & bitmask) != 0; + // TODO perfectionist one can implement this using bit operations + return (bits[i / PAGE_SIZE][i % PAGE_SIZE ] & bitmask) != 0; } /** Returns true or false for the specified bit index. @@ -192,21 +204,9 @@ public class OpenBitSet implements Clone int i = (int)(index >> 6); // div 64 int bit = (int)index & 0x3f; // mod 64 long bitmask = 1L << bit; - return (bits[i] & bitmask) != 0; - } - - /* - // alternate implementation of get() - public boolean get1(int index) { - int i = index >> 6; // div 64 - int bit = index & 0x3f; // mod 64 - return ((bits[i]>>>bit) & 0x01) != 0; - // this does a long shift and a bittest (on x86) vs - // a long shift, and a long AND, (the test for zero is prob a no-op) - // testing on a P4 indicates this is slower than (bits[i] & bitmask) != 0; + // TODO perfectionist one can implement this using bit operations + return (bits[i / PAGE_SIZE][i % PAGE_SIZE ] & bitmask) != 0; } - */ - /** returns 1 if the bit is set, 0 if not. * The index should be less than the OpenBitSet size @@ -214,25 +214,16 @@ public class OpenBitSet implements Clone public int getBit(int index) { int i = index >> 6; // div 64 int bit = index & 0x3f; // mod 64 - return ((int)(bits[i]>>>bit)) & 0x01; + return ((int)(bits[i / PAGE_SIZE][i % PAGE_SIZE ]>>>bit)) & 0x01; } - /* - public boolean get2(int index) { - int word = index >> 6; // div 64 - int bit = index & 0x0000003f; // mod 64 - return (bits[word] << bit) < 0; // hmmm, this would work if bit order were reversed - // we could right shift and check for parity bit, if it was available to us. - } - */ - /** sets a bit, expanding the set size if necessary */ public void set(long index) { int wordNum = expandingWordNum(index); int bit = (int)index & 0x3f; long bitmask = 1L << bit; - bits[wordNum] |= bitmask; + bits[ wordNum / PAGE_SIZE ][ wordNum % PAGE_SIZE ] |= bitmask; } @@ -243,7 +234,7 @@ public class OpenBitSet implements Clone int wordNum = index >> 6; // div 64 int bit = index & 0x3f; // mod 64 long bitmask = 1L << bit; - bits[wordNum] |= bitmask; + bits[ wordNum / PAGE_SIZE ][ wordNum % PAGE_SIZE ] |= bitmask; } /** Sets the bit at the specified index. @@ -253,7 +244,7 @@ public class OpenBitSet implements Clone int wordNum = (int)(index >> 6); int bit = (int)index & 0x3f; long bitmask = 1L << bit; - bits[wordNum] |= bitmask; + bits[ wordNum / PAGE_SIZE ][ wordNum % PAGE_SIZE ] |= bitmask; } /** Sets a range of bits, expanding the set size if necessary @@ -274,13 +265,15 @@ public class OpenBitSet implements Clone long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex due to wrap if (startWord == endWord) { - bits[startWord] |= (startmask & endmask); + bits[startWord / PAGE_SIZE][startWord % PAGE_SIZE] |= (startmask & endmask); return; } - bits[startWord] |= startmask; - Arrays.fill(bits, startWord+1, endWord, -1L); - bits[endWord] |= endmask; + assert startWord / PAGE_SIZE == endWord / PAGE_SIZE : "cross page sets not suppotred at all - they are not used"; + + bits[startWord / PAGE_SIZE][startWord % PAGE_SIZE] |= startmask; + Arrays.fill(bits[ startWord / PAGE_SIZE], (startWord+1) % PAGE_SIZE , endWord % PAGE_SIZE , -1L); + bits[endWord / PAGE_SIZE][endWord % PAGE_SIZE] |= endmask; } @@ -302,7 +295,7 @@ public class OpenBitSet implements Clone int wordNum = index >> 6; int bit = index & 0x03f; long bitmask = 1L << bit; - bits[wordNum] &= ~bitmask; + bits[wordNum / PAGE_SIZE][wordNum % PAGE_SIZE] &= ~bitmask; // hmmm, it takes one more instruction to clear than it does to set... any // way to work around this? If there were only 63 bits per word, we could // use a right shift of 10111111...111 in binary to position the 0 in the @@ -319,7 +312,7 @@ public class OpenBitSet implements Clone int wordNum = (int)(index >> 6); // div 64 int bit = (int)index & 0x3f; // mod 64 long bitmask = 1L << bit; - bits[wordNum] &= ~bitmask; + bits[wordNum / PAGE_SIZE][wordNum % PAGE_SIZE] &= ~bitmask; } /** clears a bit, allowing access beyond the current set size without changing the size.*/ @@ -328,7 +321,7 @@ public class OpenBitSet implements Clone if (wordNum>=wlen) return; int bit = (int)index & 0x3f; // mod 64 long bitmask = 1L << bit; - bits[wordNum] &= ~bitmask; + bits[wordNum / PAGE_SIZE][wordNum % PAGE_SIZE] &= ~bitmask; } /** Clears a range of bits. Clearing past the end does not change the size of the set. @@ -354,16 +347,24 @@ public class OpenBitSet implements Clone endmask = ~endmask; if (startWord == endWord) { - bits[startWord] &= (startmask | endmask); + bits[startWord / PAGE_SIZE][startWord % PAGE_SIZE] &= (startmask | endmask); return; } + - bits[startWord] &= startmask; + bits[startWord / PAGE_SIZE][startWord % PAGE_SIZE] &= startmask; int middle = Math.min(wlen, endWord); - Arrays.fill(bits, startWord+1, middle, 0L); + if (startWord / PAGE_SIZE == middle / PAGE_SIZE) + { + Arrays.fill(bits[startWord/PAGE_SIZE], (startWord+1) % PAGE_SIZE, middle % PAGE_SIZE, 0L); + } else + { + while (++startWord<middle) + bits[startWord / PAGE_SIZE][startWord % PAGE_SIZE] = 0L; + } if (endWord < wlen) { - bits[endWord] &= endmask; + bits[endWord / PAGE_SIZE][endWord % PAGE_SIZE] &= endmask; } } @@ -391,16 +392,23 @@ public class OpenBitSet implements Clone endmask = ~endmask; if (startWord == endWord) { - bits[startWord] &= (startmask | endmask); - return; + bits[startWord / PAGE_SIZE][startWord % PAGE_SIZE] &= (startmask | endmask); + return; } - bits[startWord] &= startmask; + bits[startWord / PAGE_SIZE][startWord % PAGE_SIZE] &= startmask; int middle = Math.min(wlen, endWord); - Arrays.fill(bits, startWord+1, middle, 0L); + if (startWord / PAGE_SIZE == middle / PAGE_SIZE) + { + Arrays.fill(bits[startWord/PAGE_SIZE], (startWord+1) % PAGE_SIZE, middle % PAGE_SIZE, 0L); + } else + { + while (++startWord<middle) + bits[startWord / PAGE_SIZE][startWord % PAGE_SIZE] = 0L; + } if (endWord < wlen) { - bits[endWord] &= endmask; + bits[endWord / PAGE_SIZE][endWord % PAGE_SIZE] &= endmask; } } @@ -413,8 +421,8 @@ public class OpenBitSet implements Clone int wordNum = index >> 6; // div 64 int bit = index & 0x3f; // mod 64 long bitmask = 1L << bit; - boolean val = (bits[wordNum] & bitmask) != 0; - bits[wordNum] |= bitmask; + boolean val = (bits[wordNum / PAGE_SIZE][wordNum % PAGE_SIZE] & bitmask) != 0; + bits[wordNum / PAGE_SIZE][wordNum % PAGE_SIZE] |= bitmask; return val; } @@ -425,8 +433,8 @@ public class OpenBitSet implements Clone int wordNum = (int)(index >> 6); // div 64 int bit = (int)index & 0x3f; // mod 64 long bitmask = 1L << bit; - boolean val = (bits[wordNum] & bitmask) != 0; - bits[wordNum] |= bitmask; + boolean val = (bits[wordNum / PAGE_SIZE][wordNum % PAGE_SIZE] & bitmask) != 0; + bits[wordNum / PAGE_SIZE][wordNum % PAGE_SIZE] |= bitmask; return val; } @@ -437,7 +445,7 @@ public class OpenBitSet implements Clone int wordNum = index >> 6; // div 64 int bit = index & 0x3f; // mod 64 long bitmask = 1L << bit; - bits[wordNum] ^= bitmask; + bits[wordNum / PAGE_SIZE][wordNum % PAGE_SIZE] ^= bitmask; } /** flips a bit. @@ -447,7 +455,7 @@ public class OpenBitSet implements Clone int wordNum = (int)(index >> 6); // div 64 int bit = (int)index & 0x3f; // mod 64 long bitmask = 1L << bit; - bits[wordNum] ^= bitmask; + bits[wordNum / PAGE_SIZE][wordNum % PAGE_SIZE] ^= bitmask; } /** flips a bit, expanding the set size if necessary */ @@ -455,7 +463,7 @@ public class OpenBitSet implements Clone int wordNum = expandingWordNum(index); int bit = (int)index & 0x3f; // mod 64 long bitmask = 1L << bit; - bits[wordNum] ^= bitmask; + bits[wordNum / PAGE_SIZE][wordNum % PAGE_SIZE] ^= bitmask; } /** flips a bit and returns the resulting bit value. @@ -465,8 +473,8 @@ public class OpenBitSet implements Clone int wordNum = index >> 6; // div 64 int bit = index & 0x3f; // mod 64 long bitmask = 1L << bit; - bits[wordNum] ^= bitmask; - return (bits[wordNum] & bitmask) != 0; + bits[wordNum / PAGE_SIZE][wordNum % PAGE_SIZE] ^= bitmask; + return (bits[wordNum / PAGE_SIZE][wordNum % PAGE_SIZE] & bitmask) != 0; } /** flips a bit and returns the resulting bit value. @@ -476,8 +484,8 @@ public class OpenBitSet implements Clone int wordNum = (int)(index >> 6); // div 64 int bit = (int)index & 0x3f; // mod 64 long bitmask = 1L << bit; - bits[wordNum] ^= bitmask; - return (bits[wordNum] & bitmask) != 0; + bits[wordNum / PAGE_SIZE][wordNum % PAGE_SIZE] ^= bitmask; + return (bits[wordNum / PAGE_SIZE][wordNum % PAGE_SIZE] & bitmask) != 0; } /** Flips a range of bits, expanding the set size if necessary @@ -504,94 +512,30 @@ public class OpenBitSet implements Clone long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex due to wrap if (startWord == endWord) { - bits[startWord] ^= (startmask & endmask); + bits[startWord / PAGE_SIZE][startWord % PAGE_SIZE] ^= (startmask & endmask); return; } - bits[startWord] ^= startmask; + bits[startWord / PAGE_SIZE][startWord % PAGE_SIZE] ^= startmask; for (int i=startWord+1; i<endWord; i++) { - bits[i] = ~bits[i]; + bits[i / PAGE_SIZE][ i % PAGE_SIZE] = ~bits[i / PAGE_SIZE][ i % PAGE_SIZE]; } - bits[endWord] ^= endmask; - } - - - /* - public static int pop(long v0, long v1, long v2, long v3) { - // derived from pop_array by setting last four elems to 0. - // exchanges one pop() call for 10 elementary operations - // saving about 7 instructions... is there a better way? - long twosA=v0 & v1; - long ones=v0^v1; - - long u2=ones^v2; - long twosB =(ones&v2)|(u2&v3); - ones=u2^v3; - - long fours=(twosA&twosB); - long twos=twosA^twosB; - - return (pop(fours)<<2) - + (pop(twos)<<1) - + pop(ones); - + bits[endWord / PAGE_SIZE][endWord % PAGE_SIZE] ^= endmask; } - */ /** @return the number of set bits */ - public long cardinality() { - return BitUtil.pop_array(bits,0,wlen); - } - - /** Returns the popcount or cardinality of the intersection of the two sets. - * Neither set is modified. - */ - public static long intersectionCount(OpenBitSet a, OpenBitSet b) { - return BitUtil.pop_intersect(a.bits, b.bits, 0, Math.min(a.wlen, b.wlen)); - } - - /** Returns the popcount or cardinality of the union of the two sets. - * Neither set is modified. - */ - public static long unionCount(OpenBitSet a, OpenBitSet b) { - long tot = BitUtil.pop_union(a.bits, b.bits, 0, Math.min(a.wlen, b.wlen)); - if (a.wlen < b.wlen) { - tot += BitUtil.pop_array(b.bits, a.wlen, b.wlen-a.wlen); - } else if (a.wlen > b.wlen) { - tot += BitUtil.pop_array(a.bits, b.wlen, a.wlen-b.wlen); - } - return tot; - } - - /** Returns the popcount or cardinality of "a and not b" - * or "intersection(a, not(b))". - * Neither set is modified. - */ - public static long andNotCount(OpenBitSet a, OpenBitSet b) { - long tot = BitUtil.pop_andnot(a.bits, b.bits, 0, Math.min(a.wlen, b.wlen)); - if (a.wlen > b.wlen) { - tot += BitUtil.pop_array(a.bits, b.wlen, a.wlen-b.wlen); - } - return tot; + public long cardinality() + { + long bitCount = 0L; + for (int i=getPageCount();i-->0;) + bitCount+=BitUtil.pop_array(bits[i],0,wlen); + + return bitCount; } - /** Returns the popcount or cardinality of the exclusive-or of the two sets. - * Neither set is modified. - */ - public static long xorCount(OpenBitSet a, OpenBitSet b) { - long tot = BitUtil.pop_xor(a.bits, b.bits, 0, Math.min(a.wlen, b.wlen)); - if (a.wlen < b.wlen) { - tot += BitUtil.pop_array(b.bits, a.wlen, b.wlen-a.wlen); - } else if (a.wlen > b.wlen) { - tot += BitUtil.pop_array(a.bits, b.wlen, a.wlen-b.wlen); - } - return tot; - } - - /** Returns the index of the first set bit starting at the index specified. * -1 is returned if there are no more set bits. */ @@ -599,14 +543,14 @@ public class OpenBitSet implements Clone int i = index>>6; if (i>=wlen) return -1; int subIndex = index & 0x3f; // index within the word - long word = bits[i] >> subIndex; // skip all the bits to the right of index + long word = bits[i / PAGE_SIZE][ i % PAGE_SIZE] >> subIndex; // skip all the bits to the right of index if (word!=0) { return (i<<6) + subIndex + BitUtil.ntz(word); } while(++i < wlen) { - word = bits[i]; + word = bits[i / PAGE_SIZE][i % PAGE_SIZE]; if (word!=0) return (i<<6) + BitUtil.ntz(word); } @@ -620,97 +564,41 @@ public class OpenBitSet implements Clone int i = (int)(index>>>6); if (i>=wlen) return -1; int subIndex = (int)index & 0x3f; // index within the word - long word = bits[i] >>> subIndex; // skip all the bits to the right of index + long word = bits[i / PAGE_SIZE][i % PAGE_SIZE] >>> subIndex; // skip all the bits to the right of index if (word!=0) { return (((long)i)<<6) + (subIndex + BitUtil.ntz(word)); } while(++i < wlen) { - word = bits[i]; + word = bits[i / PAGE_SIZE][i % PAGE_SIZE]; if (word!=0) return (((long)i)<<6) + BitUtil.ntz(word); } return -1; } - - - - @Override - public Object clone() { - try { - OpenBitSet obs = (OpenBitSet)super.clone(); - obs.bits = obs.bits.clone(); // hopefully an array clone is as fast(er) than arraycopy - return obs; - } catch (CloneNotSupportedException e) { - throw new RuntimeException(e); - } - } - /** this = this AND other */ public void intersect(OpenBitSet other) { int newLen= Math.min(this.wlen,other.wlen); - long[] thisArr = this.bits; - long[] otherArr = other.bits; + long[][] thisArr = this.bits; + long[][] otherArr = other.bits; + int thisPageSize = this.PAGE_SIZE; + int otherPageSize = other.PAGE_SIZE; // testing against zero can be more efficient int pos=newLen; while(--pos>=0) { - thisArr[pos] &= otherArr[pos]; + thisArr[pos / thisPageSize][ pos % thisPageSize] &= otherArr[pos / otherPageSize][pos % otherPageSize]; } + if (this.wlen > newLen) { // fill zeros from the new shorter length to the old length - Arrays.fill(bits,newLen,this.wlen,0); - } - this.wlen = newLen; - } - - /** this = this OR other */ - public void union(OpenBitSet other) { - int newLen = Math.max(wlen,other.wlen); - ensureCapacityWords(newLen); - - long[] thisArr = this.bits; - long[] otherArr = other.bits; - int pos=Math.min(wlen,other.wlen); - while(--pos>=0) { - thisArr[pos] |= otherArr[pos]; - } - if (this.wlen < newLen) { - System.arraycopy(otherArr, this.wlen, thisArr, this.wlen, newLen-this.wlen); + for (pos=wlen;pos-->newLen;) + thisArr[pos / thisPageSize][ pos % thisPageSize] =0; } this.wlen = newLen; } - - /** Remove all elements set in other. this = this AND_NOT other */ - public void remove(OpenBitSet other) { - int idx = Math.min(wlen,other.wlen); - long[] thisArr = this.bits; - long[] otherArr = other.bits; - while(--idx>=0) { - thisArr[idx] &= ~otherArr[idx]; - } - } - - /** this = this XOR other */ - public void xor(OpenBitSet other) { - int newLen = Math.max(wlen,other.wlen); - ensureCapacityWords(newLen); - - long[] thisArr = this.bits; - long[] otherArr = other.bits; - int pos=Math.min(wlen,other.wlen); - while(--pos>=0) { - thisArr[pos] ^= otherArr[pos]; - } - if (this.wlen < newLen) { - System.arraycopy(otherArr, this.wlen, thisArr, this.wlen, newLen-this.wlen); - } - this.wlen = newLen; - } - - // some BitSet compatability methods //** see {@link intersect} */ @@ -718,36 +606,13 @@ public class OpenBitSet implements Clone intersect(other); } - //** see {@link union} */ - public void or(OpenBitSet other) { - union(other); - } - - //** see {@link andNot} */ - public void andNot(OpenBitSet other) { - remove(other); - } - - /** returns true if the sets have any elements in common */ - public boolean intersects(OpenBitSet other) { - int pos = Math.min(this.wlen, other.wlen); - long[] thisArr = this.bits; - long[] otherArr = other.bits; - while (--pos>=0) { - if ((thisArr[pos] & otherArr[pos])!=0) return true; - } - return false; - } - - /** Expand the long[] with the size given as a number of words (64 bit longs). * getNumWords() is unchanged by this call. */ - public void ensureCapacityWords(int numWords) { - if (bits.length < numWords) { - bits = ArrayUtil.grow(bits, numWords); - } + public void ensureCapacityWords(int numWords) + { + assert numWords<=wlen : "Growing of paged bitset is not supported"; } /** Ensure that the long[] is big enough to hold numBits, expanding it if necessary. @@ -762,7 +627,7 @@ public class OpenBitSet implements Clone */ public void trimTrailingZeros() { int idx = wlen-1; - while (idx>=0 && bits[idx]==0) idx--; + while (idx>=0 && bits[idx / PAGE_SIZE][idx % PAGE_SIZE]==0) idx--; wlen = idx+1; } @@ -771,7 +636,6 @@ public class OpenBitSet implements Clone return (int)(((numBits-1)>>>6)+1); } - /** returns true if both sets have the same bits set */ @Override public boolean equals(Object o) { @@ -785,14 +649,17 @@ public class OpenBitSet implements Clone } else { a=this; } + + int aPageSize = this.PAGE_SIZE; + int bPageSize = b.PAGE_SIZE; // check for any set bits out of the range of b for (int i=a.wlen-1; i>=b.wlen; i--) { - if (a.bits[i]!=0) return false; + if (a.bits[i/aPageSize][i % aPageSize]!=0) return false; } for (int i=b.wlen-1; i>=0; i--) { - if (a.bits[i] != b.bits[i]) return false; + if (a.bits[i/aPageSize][i % aPageSize] != b.bits[i/bPageSize][i % bPageSize]) return false; } return true; @@ -804,8 +671,8 @@ public class OpenBitSet implements Clone // Start with a zero hash and use a mix that results in zero if the input is zero. // This effectively truncates trailing zeros without an explicit check. long h = 0; - for (int i = bits.length; --i>=0;) { - h ^= bits[i]; + for (int i = wlen; --i>=0;) { + h ^= bits[i / PAGE_SIZE][i % PAGE_SIZE]; h = (h << 1) | (h >>> 63); // rotate left } // fold leftmost bits into right and add a constant to prevent
