You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by jb...@apache.org on 2011/10/27 23:44:29 UTC
svn commit: r1190047 [2/2] - in /cassandra/trunk: ./ bin/daemon/ conf/
contrib/ interface/ interface/thrift/gen-java/org/apache/cassandra/thrift/
src/java/org/apache/cassandra/config/ src/java/org/apache/cassandra/db/
src/java/org/apache/cassandra/db/m...
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