cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jbel...@apache.org
Subject 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...
Date Thu, 27 Oct 2011 21:44:29 GMT
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 &lt= bits.length, and
-   * any existing words in the array at position &gt= 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



Mime
View raw message