You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by jp...@apache.org on 2015/04/28 22:37:15 UTC
svn commit: r1676617 - in /lucene/dev/trunk: lucene/
lucene/core/src/java/org/apache/lucene/util/
lucene/core/src/test/org/apache/lucene/util/
solr/core/src/test/org/apache/solr/search/
Author: jpountz
Date: Tue Apr 28 20:37:15 2015
New Revision: 1676617
URL: http://svn.apache.org/r1676617
Log:
LUCENE-6427: Added assertion about the presence of ghost bits in (Fixed|Long)BitSet.
Modified:
lucene/dev/trunk/lucene/CHANGES.txt
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/LongBitSet.java
lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestFixedBitSet.java
lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestLongBitSet.java
lucene/dev/trunk/solr/core/src/test/org/apache/solr/search/TestFiltering.java
Modified: lucene/dev/trunk/lucene/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/CHANGES.txt?rev=1676617&r1=1676616&r2=1676617&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/CHANGES.txt (original)
+++ lucene/dev/trunk/lucene/CHANGES.txt Tue Apr 28 20:37:15 2015
@@ -140,6 +140,9 @@ Bug Fixes
missing the field being highlighted, in PostingsHighlighter (Roman
Khmelichek via Mike McCandless)
+* LUCENE-6427: Added assertion about the presence of ghost bits in
+ (Fixed|Long)BitSet. (Luc Vanlerberghe via Adrien Grand)
+
API Changes
* LUCENE-6377: SearcherFactory#newSearcher now accepts the previous reader
Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java?rev=1676617&r1=1676616&r2=1676617&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java Tue Apr 28 20:37:15 2015
@@ -1,3 +1,5 @@
+package org.apache.lucene.util;
+
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
@@ -15,8 +17,6 @@
* limitations under the License.
*/
-package org.apache.lucene.util;
-
import java.io.IOException;
import java.util.Arrays;
@@ -35,20 +35,25 @@ public final class FixedBitSet extends B
private static final long BASE_RAM_BYTES_USED = RamUsageEstimator.shallowSizeOfInstance(FixedBitSet.class);
+ private final long[] bits; // Array of longs holding the bits
+ private final int numBits; // The number of bits in use
+ private final int numWords; // The exact number of longs needed to hold numBits (<= bits.length)
+
/**
- * If the given {@link FixedBitSet} is large enough to hold {@code numBits},
+ * If the given {@link FixedBitSet} is large enough to hold {@code numBits+1},
* returns the given bits, otherwise returns a new {@link FixedBitSet} which
* can hold the requested number of bits.
- *
* <p>
* <b>NOTE:</b> the returned bitset reuses the underlying {@code long[]} of
* the given {@code bits} if possible. Also, calling {@link #length()} on the
* returned bits may return a value greater than {@code numBits}.
*/
public static FixedBitSet ensureCapacity(FixedBitSet bits, int numBits) {
- if (numBits < bits.length()) {
+ if (numBits < bits.numBits) {
return bits;
} else {
+ // Depends on the ghost bits being clear!
+ // (Otherwise, they may become visible in the new instance)
int numWords = bits2words(numBits);
long[] arr = bits.getBits();
if (numWords >= arr.length) {
@@ -68,6 +73,7 @@ public final class FixedBitSet extends B
* Neither set is modified.
*/
public static long intersectionCount(FixedBitSet a, FixedBitSet b) {
+ // Depends on the ghost bits being clear!
return BitUtil.pop_intersect(a.bits, b.bits, 0, Math.min(a.numWords, b.numWords));
}
@@ -76,6 +82,7 @@ public final class FixedBitSet extends B
* set is modified.
*/
public static long unionCount(FixedBitSet a, FixedBitSet b) {
+ // Depends on the ghost bits being clear!
long tot = BitUtil.pop_union(a.bits, b.bits, 0, Math.min(a.numWords, b.numWords));
if (a.numWords < b.numWords) {
tot += BitUtil.pop_array(b.bits, a.numWords, b.numWords - a.numWords);
@@ -90,6 +97,7 @@ public final class FixedBitSet extends B
* "intersection(a, not(b))". Neither set is modified.
*/
public static long andNotCount(FixedBitSet a, FixedBitSet b) {
+ // Depends on the ghost bits being clear!
long tot = BitUtil.pop_andnot(a.bits, b.bits, 0, Math.min(a.numWords, b.numWords));
if (a.numWords > b.numWords) {
tot += BitUtil.pop_array(a.bits, b.numWords, a.numWords - b.numWords);
@@ -97,16 +105,24 @@ public final class FixedBitSet extends B
return tot;
}
- final long[] bits;
- final int numBits;
- final int numWords;
-
+ /**
+ * Creates a new LongBitSet.
+ * The internally allocated long array will be exactly the size needed to accommodate the numBits specified.
+ * @param numBits the number of bits needed
+ */
public FixedBitSet(int numBits) {
this.numBits = numBits;
bits = new long[bits2words(numBits)];
numWords = bits.length;
}
+ /**
+ * Creates a new LongBitSet using the provided long[] array as backing store.
+ * The storedBits array must be large enough to accommodate the numBits specified, but may be larger.
+ * In that case the 'extra' or 'ghost' bits must be clear (or they may provoke spurious side-effects)
+ * @param storedBits the array to use as backing store
+ * @param numBits the number of bits actually needed
+ */
public FixedBitSet(long[] storedBits, int numBits) {
this.numWords = bits2words(numBits);
if (numWords > storedBits.length) {
@@ -114,8 +130,27 @@ public final class FixedBitSet extends B
}
this.numBits = numBits;
this.bits = storedBits;
+
+ assert verifyGhostBitsClear();
}
+ /**
+ * Checks if the bits past numBits are clear.
+ * Some methods rely on this implicit assumption: search for "Depends on the ghost bits being clear!"
+ * @return true if the bits past numBits are clear.
+ */
+ private boolean verifyGhostBitsClear() {
+ for (int i = numWords; i < bits.length; i++) {
+ if (bits[i] != 0) return false;
+ }
+
+ if ((numBits & 0x3f) == 0) return true;
+
+ long mask = -1L << numBits;
+
+ return (bits[numWords - 1] & mask) == 0;
+ }
+
@Override
public int length() {
return numBits;
@@ -131,9 +166,14 @@ public final class FixedBitSet extends B
return bits;
}
+ /** Returns number of set bits. NOTE: this visits every
+ * long in the backing bits array, and the result is not
+ * internally cached!
+ */
@Override
public int cardinality() {
- return (int) BitUtil.pop_array(bits, 0, bits.length);
+ // Depends on the ghost bits being clear!
+ return (int) BitUtil.pop_array(bits, 0, numWords);
}
@Override
@@ -154,7 +194,7 @@ public final class FixedBitSet extends B
}
public boolean getAndSet(int index) {
- assert index >= 0 && index < numBits;
+ assert index >= 0 && index < numBits: "index=" + index + ", numBits=" + numBits;
int wordNum = index >> 6; // div 64
long bitmask = 1L << index;
boolean val = (bits[wordNum] & bitmask) != 0;
@@ -164,14 +204,14 @@ public final class FixedBitSet extends B
@Override
public void clear(int index) {
- assert index >= 0 && index < numBits;
+ assert index >= 0 && index < numBits: "index=" + index + ", numBits=" + numBits;
int wordNum = index >> 6;
long bitmask = 1L << index;
bits[wordNum] &= ~bitmask;
}
public boolean getAndClear(int index) {
- assert index >= 0 && index < numBits;
+ assert index >= 0 && index < numBits: "index=" + index + ", numBits=" + numBits;
int wordNum = index >> 6; // div 64
long bitmask = 1L << index;
boolean val = (bits[wordNum] & bitmask) != 0;
@@ -181,6 +221,7 @@ public final class FixedBitSet extends B
@Override
public int nextSetBit(int index) {
+ // Depends on the ghost bits being clear!
assert index >= 0 && index < numBits : "index=" + index + ", numBits=" + numBits;
int i = index >> 6;
long word = bits[i] >> index; // skip all the bits to the right of index
@@ -275,6 +316,7 @@ public final class FixedBitSet extends B
/** returns true if the sets have any elements in common */
public boolean intersects(FixedBitSet other) {
+ // Depends on the ghost bits being clear!
int pos = Math.min(numWords, other.numWords);
while (--pos>=0) {
if ((bits[pos] & other.bits[pos]) != 0) return true;
@@ -300,7 +342,7 @@ public final class FixedBitSet extends B
/** this = this AND NOT other */
public void andNot(FixedBitSet other) {
- andNot(other.bits, other.bits.length);
+ andNot(other.bits, other.numWords);
}
private void andNot(final long[] otherArr, final int otherNumWords) {
@@ -311,9 +353,24 @@ public final class FixedBitSet extends B
}
}
- // NOTE: no .isEmpty() here because that's trappy (ie,
- // typically isEmpty is low cost, but this one wouldn't
- // be)
+ /**
+ * Scans the backing store to check if all bits are clear.
+ * The method is deliberately not called "isEmpty" to emphasize it is not low cost (as isEmpty usually is).
+ * @return true if all bits are clear.
+ */
+ public boolean scanIsEmpty() {
+ // This 'slow' implementation is still faster than any external one could be
+ // (e.g.: (bitSet.length() == 0 || bitSet.nextSetBit(0) == -1))
+ // especially for small BitSets
+ // Depends on the ghost bits being clear!
+ final int count = numWords;
+
+ for (int i = 0; i < count; i++) {
+ if (bits[i] != 0) return false;
+ }
+
+ return true;
+ }
/** Flips a range of bits
*
@@ -358,8 +415,7 @@ public final class FixedBitSet extends B
public void flip(int index) {
assert index >= 0 && index < numBits: "index=" + index + " numBits=" + numBits;
int wordNum = index >> 6; // div 64
- int bit = index & 0x3f; // mod 64
- long bitmask = 1L << bit;
+ long bitmask = 1L << index; // mod 64 is implicit
bits[wordNum] ^= bitmask;
}
@@ -369,8 +425,8 @@ public final class FixedBitSet extends B
* @param endIndex one-past the last bit to set
*/
public void set(int startIndex, int endIndex) {
- assert startIndex >= 0 && startIndex < numBits;
- assert endIndex >= 0 && endIndex <= numBits;
+ assert startIndex >= 0 && startIndex < numBits : "startIndex=" + startIndex + ", numBits=" + numBits;
+ assert endIndex >= 0 && endIndex <= numBits : "endIndex=" + endIndex + ", numBits=" + numBits;
if (endIndex <= startIndex) {
return;
}
@@ -422,11 +478,10 @@ public final class FixedBitSet extends B
@Override
public FixedBitSet clone() {
long[] bits = new long[this.bits.length];
- System.arraycopy(this.bits, 0, bits, 0, bits.length);
+ System.arraycopy(this.bits, 0, bits, 0, numWords);
return new FixedBitSet(bits, numBits);
}
- /** returns true if both sets have the same bits set */
@Override
public boolean equals(Object o) {
if (this == o) {
@@ -436,14 +491,16 @@ public final class FixedBitSet extends B
return false;
}
FixedBitSet other = (FixedBitSet) o;
- if (numBits != other.length()) {
+ if (numBits != other.numBits) {
return false;
}
+ // Depends on the ghost bits being clear!
return Arrays.equals(bits, other.bits);
}
@Override
public int hashCode() {
+ // Depends on the ghost bits being clear!
long h = 0;
for (int i = numWords; --i>=0;) {
h ^= bits[i];
Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/LongBitSet.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/LongBitSet.java?rev=1676617&r1=1676616&r2=1676617&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/LongBitSet.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/LongBitSet.java Tue Apr 28 20:37:15 2015
@@ -1,7 +1,5 @@
package org.apache.lucene.util;
-import java.util.Arrays;
-
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
@@ -19,6 +17,8 @@ import java.util.Arrays;
* limitations under the License.
*/
+import java.util.Arrays;
+
/**
* BitSet of fixed length (numBits), backed by accessible ({@link #getBits})
* long[], accessed with a long index. Use it only if you intend to store more
@@ -28,24 +28,25 @@ import java.util.Arrays;
*/
public final class LongBitSet {
- private final long[] bits;
- private final long numBits;
- private final int numWords;
+ private final long[] bits; // Array of longs holding the bits
+ private final long numBits; // The number of bits in use
+ private final int numWords; // The exact number of longs needed to hold numBits (<= bits.length)
/**
* If the given {@link LongBitSet} is large enough to hold
- * {@code numBits}, returns the given bits, otherwise returns a new
+ * {@code numBits+1}, returns the given bits, otherwise returns a new
* {@link LongBitSet} which can hold the requested number of bits.
- *
* <p>
* <b>NOTE:</b> the returned bitset reuses the underlying {@code long[]} of
* the given {@code bits} if possible. Also, calling {@link #length()} on the
* returned bits may return a value greater than {@code numBits}.
*/
public static LongBitSet ensureCapacity(LongBitSet bits, long numBits) {
- if (numBits < bits.length()) {
+ if (numBits < bits.numBits) {
return bits;
} else {
+ // Depends on the ghost bits being clear!
+ // (Otherwise, they may become visible in the new instance)
int numWords = bits2words(numBits);
long[] arr = bits.getBits();
if (numWords >= arr.length) {
@@ -60,12 +61,24 @@ public final class LongBitSet {
return (int)((numBits - 1) >> 6) + 1; // I.e.: get the word-offset of the last bit and add one (make sure to use >> so 0 returns 0!)
}
+ /**
+ * Creates a new LongBitSet.
+ * The internally allocated long array will be exactly the size needed to accommodate the numBits specified.
+ * @param numBits the number of bits needed
+ */
public LongBitSet(long numBits) {
this.numBits = numBits;
bits = new long[bits2words(numBits)];
numWords = bits.length;
}
+ /**
+ * Creates a new LongBitSet using the provided long[] array as backing store.
+ * The storedBits array must be large enough to accommodate the numBits specified, but may be larger.
+ * In that case the 'extra' or 'ghost' bits must be clear (or they may provoke spurious side-effects)
+ * @param storedBits the array to use as backing store
+ * @param numBits the number of bits actually needed
+ */
public LongBitSet(long[] storedBits, long numBits) {
this.numWords = bits2words(numBits);
if (numWords > storedBits.length) {
@@ -73,6 +86,25 @@ public final class LongBitSet {
}
this.numBits = numBits;
this.bits = storedBits;
+
+ assert verifyGhostBitsClear();
+ }
+
+ /**
+ * Checks if the bits past numBits are clear.
+ * Some methods rely on this implicit assumption: search for "Depends on the ghost bits being clear!"
+ * @return true if the bits past numBits are clear.
+ */
+ private boolean verifyGhostBitsClear() {
+ for (int i = numWords; i < bits.length; i++) {
+ if (bits[i] != 0) return false;
+ }
+
+ if ((numBits & 0x3f) == 0) return true;
+
+ long mask = -1L << numBits;
+
+ return (bits[numWords - 1] & mask) == 0;
}
/** Returns the number of bits stored in this bitset. */
@@ -87,13 +119,15 @@ public final class LongBitSet {
/** Returns number of set bits. NOTE: this visits every
* long in the backing bits array, and the result is not
- * internally cached! */
+ * internally cached!
+ */
public long cardinality() {
- return BitUtil.pop_array(bits, 0, bits.length);
+ // Depends on the ghost bits being clear!
+ return BitUtil.pop_array(bits, 0, numWords);
}
public boolean get(long index) {
- assert index >= 0 && index < numBits: "index=" + index;
+ assert index >= 0 && index < numBits: "index=" + index + ", numBits=" + numBits;
int i = (int) (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.
@@ -109,7 +143,7 @@ public final class LongBitSet {
}
public boolean getAndSet(long index) {
- assert index >= 0 && index < numBits;
+ assert index >= 0 && index < numBits: "index=" + index + ", numBits=" + numBits;
int wordNum = (int) (index >> 6); // div 64
long bitmask = 1L << index;
boolean val = (bits[wordNum] & bitmask) != 0;
@@ -118,14 +152,14 @@ public final class LongBitSet {
}
public void clear(long index) {
- assert index >= 0 && index < numBits;
+ assert index >= 0 && index < numBits: "index=" + index + ", numBits=" + numBits;
int wordNum = (int) (index >> 6);
long bitmask = 1L << index;
bits[wordNum] &= ~bitmask;
}
public boolean getAndClear(long index) {
- assert index >= 0 && index < numBits;
+ assert index >= 0 && index < numBits: "index=" + index + ", numBits=" + numBits;
int wordNum = (int) (index >> 6); // div 64
long bitmask = 1L << index;
boolean val = (bits[wordNum] & bitmask) != 0;
@@ -137,7 +171,8 @@ public final class LongBitSet {
* -1 is returned if there are no more set bits.
*/
public long nextSetBit(long index) {
- assert index >= 0 && index < numBits;
+ // Depends on the ghost bits being clear!
+ assert index >= 0 && index < numBits: "index=" + index + ", numBits=" + numBits;
int i = (int) (index >> 6);
long word = bits[i] >> index; // skip all the bits to the right of index
@@ -198,6 +233,7 @@ public final class LongBitSet {
/** returns true if the sets have any elements in common */
public boolean intersects(LongBitSet other) {
+ // Depends on the ghost bits being clear!
int pos = Math.min(numWords, other.numWords);
while (--pos>=0) {
if ((bits[pos] & other.bits[pos]) != 0) return true;
@@ -218,15 +254,30 @@ public final class LongBitSet {
/** this = this AND NOT other */
public void andNot(LongBitSet other) {
- int pos = Math.min(numWords, other.bits.length);
+ int pos = Math.min(numWords, other.numWords);
while (--pos >= 0) {
bits[pos] &= ~other.bits[pos];
}
}
- // NOTE: no .isEmpty() here because that's trappy (ie,
- // typically isEmpty is low cost, but this one wouldn't
- // be)
+ /**
+ * Scans the backing store to check if all bits are clear.
+ * The method is deliberately not called "isEmpty" to emphasize it is not low cost (as isEmpty usually is).
+ * @return true if all bits are clear.
+ */
+ public boolean scanIsEmpty() {
+ // This 'slow' implementation is still faster than any external one could be
+ // (e.g.: (bitSet.length() == 0 || bitSet.nextSetBit(0) == -1))
+ // especially for small BitSets
+ // Depends on the ghost bits being clear!
+ final int count = numWords;
+
+ for (int i = 0; i < count; i++) {
+ if (bits[i] != 0) return false;
+ }
+
+ return true;
+ }
/** Flips a range of bits
*
@@ -267,14 +318,22 @@ public final class LongBitSet {
bits[endWord] ^= endmask;
}
+ /** Flip the bit at the provided index. */
+ public void flip(long index) {
+ assert index >= 0 && index < numBits: "index=" + index + " numBits=" + numBits;
+ int wordNum = (int) (index >> 6); // div 64
+ long bitmask = 1L << index; // mod 64 is implicit
+ bits[wordNum] ^= bitmask;
+ }
+
/** Sets a range of bits
*
* @param startIndex lower index
* @param endIndex one-past the last bit to set
*/
public void set(long startIndex, long endIndex) {
- assert startIndex >= 0 && startIndex < numBits;
- assert endIndex >= 0 && endIndex <= numBits;
+ assert startIndex >= 0 && startIndex < numBits : "startIndex=" + startIndex + ", numBits=" + numBits;
+ assert endIndex >= 0 && endIndex <= numBits : "endIndex=" + endIndex + ", numBits=" + numBits;
if (endIndex <= startIndex) {
return;
}
@@ -301,8 +360,8 @@ public final class LongBitSet {
* @param endIndex one-past the last bit to clear
*/
public void clear(long startIndex, long endIndex) {
- assert startIndex >= 0 && startIndex < numBits;
- assert endIndex >= 0 && endIndex <= numBits;
+ assert startIndex >= 0 && startIndex < numBits : "startIndex=" + startIndex + ", numBits=" + numBits;
+ assert endIndex >= 0 && endIndex <= numBits : "endIndex=" + endIndex + ", numBits=" + numBits;
if (endIndex <= startIndex) {
return;
}
@@ -330,7 +389,7 @@ public final class LongBitSet {
@Override
public LongBitSet clone() {
long[] bits = new long[this.bits.length];
- System.arraycopy(this.bits, 0, bits, 0, bits.length);
+ System.arraycopy(this.bits, 0, bits, 0, numWords);
return new LongBitSet(bits, numBits);
}
@@ -344,14 +403,16 @@ public final class LongBitSet {
return false;
}
LongBitSet other = (LongBitSet) o;
- if (numBits != other.length()) {
+ if (numBits != other.numBits) {
return false;
}
+ // Depends on the ghost bits being clear!
return Arrays.equals(bits, other.bits);
}
@Override
public int hashCode() {
+ // Depends on the ghost bits being clear!
long h = 0;
for (int i = numWords; --i>=0;) {
h ^= bits[i];
Modified: lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestFixedBitSet.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestFixedBitSet.java?rev=1676617&r1=1676616&r2=1676617&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestFixedBitSet.java (original)
+++ lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestFixedBitSet.java Tue Apr 28 20:37:15 2015
@@ -18,6 +18,7 @@ package org.apache.lucene.util;
*/
import java.io.IOException;
+import java.util.Random;
import org.apache.lucene.search.DocIdSetIterator;
@@ -32,8 +33,8 @@ public class TestFixedBitSet extends Bas
return set;
}
-
void doGet(java.util.BitSet a, FixedBitSet b) {
+ assertEquals(a.cardinality(), b.cardinality());
int max = b.length();
for (int i=0; i<max; i++) {
if (a.get(i) != b.get(i)) {
@@ -43,7 +44,9 @@ public class TestFixedBitSet extends Bas
}
void doNextSetBit(java.util.BitSet a, FixedBitSet b) {
- int aa=-1,bb=-1;
+ assertEquals(a.cardinality(), b.cardinality());
+ int aa=-1;
+ int bb=-1;
do {
aa = a.nextSetBit(aa+1);
if (aa == -1) {
@@ -55,6 +58,7 @@ public class TestFixedBitSet extends Bas
}
void doPrevSetBit(java.util.BitSet a, FixedBitSet b) {
+ assertEquals(a.cardinality(), b.cardinality());
int aa = a.size() + random().nextInt(100);
int bb = aa;
do {
@@ -83,6 +87,7 @@ public class TestFixedBitSet extends Bas
}
void doIterate1(java.util.BitSet a, FixedBitSet b) throws IOException {
+ assertEquals(a.cardinality(), b.cardinality());
int aa=-1,bb=-1;
DocIdSetIterator iterator = new BitSetIterator(b, 0);
do {
@@ -93,6 +98,7 @@ public class TestFixedBitSet extends Bas
}
void doIterate2(java.util.BitSet a, FixedBitSet b) throws IOException {
+ assertEquals(a.cardinality(), b.cardinality());
int aa=-1,bb=-1;
DocIdSetIterator iterator = new BitSetIterator(b, 0);
do {
@@ -286,11 +292,7 @@ public class TestFixedBitSet extends Bas
if (random().nextBoolean()) {
int bits2words = FixedBitSet.bits2words(numBits);
long[] words = new long[bits2words + random().nextInt(100)];
- for (int i = bits2words; i < words.length; i++) {
- words[i] = random().nextLong();
- }
bs = new FixedBitSet(words, numBits);
-
} else {
bs = new FixedBitSet(numBits);
}
@@ -363,4 +365,132 @@ public class TestFixedBitSet extends Bas
assertTrue(bits.get(1));
assertFalse(newBits.get(1));
}
+
+ public void testBits2Words() {
+ assertEquals(0, FixedBitSet.bits2words(0));
+ assertEquals(1, FixedBitSet.bits2words(1));
+ // ...
+ assertEquals(1, FixedBitSet.bits2words(64));
+ assertEquals(2, FixedBitSet.bits2words(65));
+ // ...
+ assertEquals(2, FixedBitSet.bits2words(128));
+ assertEquals(3, FixedBitSet.bits2words(129));
+ // ...
+ assertEquals(1024, FixedBitSet.bits2words(65536));
+ assertEquals(1025, FixedBitSet.bits2words(65537));
+ // ...
+ assertEquals(1 << (31-6), FixedBitSet.bits2words(Integer.MAX_VALUE));
+ }
+
+ private int[] makeIntArray(Random random, int count, int min, int max) {
+ int[] rv = new int[count];
+
+ for (int i = 0; i < count; ++i) {
+ rv[i] = TestUtil.nextInt(random, min, max);
+ }
+
+ return rv;
+ }
+
+ // Demonstrates that the presence of ghost bits in the last used word can cause spurious failures
+ public void testIntersectionCount() {
+ Random random = random();
+
+ int numBits1 = TestUtil.nextInt(random, 1000, 2000);
+ int numBits2 = TestUtil.nextInt(random, 1000, 2000);
+
+ int count1 = TestUtil.nextInt(random, 0, numBits1 - 1);
+ int count2 = TestUtil.nextInt(random, 0, numBits2 - 1);
+
+ int[] bits1 = makeIntArray(random, count1, 0, numBits1 - 1);
+ int[] bits2 = makeIntArray(random, count2, 0, numBits2 - 1);
+
+ FixedBitSet fixedBitSet1 = makeFixedBitSet(bits1, numBits1);
+ FixedBitSet fixedBitSet2 = makeFixedBitSet(bits2, numBits2);
+
+ // If ghost bits are present, these may fail too, but that's not what we want to demonstrate here
+ //assertTrue(fixedBitSet1.cardinality() <= bits1.length);
+ //assertTrue(fixedBitSet2.cardinality() <= bits2.length);
+
+ long intersectionCount = FixedBitSet.intersectionCount(fixedBitSet1, fixedBitSet2);
+
+ java.util.BitSet bitSet1 = makeBitSet(bits1);
+ java.util.BitSet bitSet2 = makeBitSet(bits2);
+
+ // If ghost bits are present, these may fail too, but that's not what we want to demonstrate here
+ //assertEquals(bitSet1.cardinality(), fixedBitSet1.cardinality());
+ //assertEquals(bitSet2.cardinality(), fixedBitSet2.cardinality());
+
+ bitSet1.and(bitSet2);
+
+ assertEquals(bitSet1.cardinality(), intersectionCount);
+ }
+
+ // Demonstrates that the presence of ghost bits in the last used word can cause spurious failures
+ public void testUnionCount() {
+ Random random = random();
+
+ int numBits1 = TestUtil.nextInt(random, 1000, 2000);
+ int numBits2 = TestUtil.nextInt(random, 1000, 2000);
+
+ int count1 = TestUtil.nextInt(random, 0, numBits1 - 1);
+ int count2 = TestUtil.nextInt(random, 0, numBits2 - 1);
+
+ int[] bits1 = makeIntArray(random, count1, 0, numBits1 - 1);
+ int[] bits2 = makeIntArray(random, count2, 0, numBits2 - 1);
+
+ FixedBitSet fixedBitSet1 = makeFixedBitSet(bits1, numBits1);
+ FixedBitSet fixedBitSet2 = makeFixedBitSet(bits2, numBits2);
+
+ // If ghost bits are present, these may fail too, but that's not what we want to demonstrate here
+ //assertTrue(fixedBitSet1.cardinality() <= bits1.length);
+ //assertTrue(fixedBitSet2.cardinality() <= bits2.length);
+
+ long unionCount = FixedBitSet.unionCount(fixedBitSet1, fixedBitSet2);
+
+ java.util.BitSet bitSet1 = makeBitSet(bits1);
+ java.util.BitSet bitSet2 = makeBitSet(bits2);
+
+ // If ghost bits are present, these may fail too, but that's not what we want to demonstrate here
+ //assertEquals(bitSet1.cardinality(), fixedBitSet1.cardinality());
+ //assertEquals(bitSet2.cardinality(), fixedBitSet2.cardinality());
+
+ bitSet1.or(bitSet2);
+
+ assertEquals(bitSet1.cardinality(), unionCount);
+ }
+
+ // Demonstrates that the presence of ghost bits in the last used word can cause spurious failures
+ public void testAndNotCount() {
+ Random random = random();
+
+ int numBits1 = TestUtil.nextInt(random, 1000, 2000);
+ int numBits2 = TestUtil.nextInt(random, 1000, 2000);
+
+ int count1 = TestUtil.nextInt(random, 0, numBits1 - 1);
+ int count2 = TestUtil.nextInt(random, 0, numBits2 - 1);
+
+ int[] bits1 = makeIntArray(random, count1, 0, numBits1 - 1);
+ int[] bits2 = makeIntArray(random, count2, 0, numBits2 - 1);
+
+ FixedBitSet fixedBitSet1 = makeFixedBitSet(bits1, numBits1);
+ FixedBitSet fixedBitSet2 = makeFixedBitSet(bits2, numBits2);
+
+ // If ghost bits are present, these may fail too, but that's not what we want to demonstrate here
+ //assertTrue(fixedBitSet1.cardinality() <= bits1.length);
+ //assertTrue(fixedBitSet2.cardinality() <= bits2.length);
+
+ long andNotCount = FixedBitSet.andNotCount(fixedBitSet1, fixedBitSet2);
+
+ java.util.BitSet bitSet1 = makeBitSet(bits1);
+ java.util.BitSet bitSet2 = makeBitSet(bits2);
+
+ // If ghost bits are present, these may fail too, but that's not what we want to demonstrate here
+ //assertEquals(bitSet1.cardinality(), fixedBitSet1.cardinality());
+ //assertEquals(bitSet2.cardinality(), fixedBitSet2.cardinality());
+
+ bitSet1.andNot(bitSet2);
+
+ assertEquals(bitSet1.cardinality(), andNotCount);
+ }
}
Modified: lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestLongBitSet.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestLongBitSet.java?rev=1676617&r1=1676616&r2=1676617&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestLongBitSet.java (original)
+++ lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestLongBitSet.java Tue Apr 28 20:37:15 2015
@@ -1,3 +1,5 @@
+package org.apache.lucene.util;
+
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
@@ -15,14 +17,12 @@
* limitations under the License.
*/
-package org.apache.lucene.util;
-
import java.io.IOException;
-import java.util.BitSet;
public class TestLongBitSet extends LuceneTestCase {
- void doGet(BitSet a, LongBitSet b) {
+ void doGet(java.util.BitSet a, LongBitSet b) {
+ assertEquals(a.cardinality(), b.cardinality());
long max = b.length();
for (int i=0; i<max; i++) {
if (a.get(i) != b.get(i)) {
@@ -31,7 +31,8 @@ public class TestLongBitSet extends Luce
}
}
- void doNextSetBit(BitSet a, LongBitSet b) {
+ void doNextSetBit(java.util.BitSet a, LongBitSet b) {
+ assertEquals(a.cardinality(), b.cardinality());
int aa=-1;
long bb=-1;
do {
@@ -41,7 +42,8 @@ public class TestLongBitSet extends Luce
} while (aa>=0);
}
- void doPrevSetBit(BitSet a, LongBitSet b) {
+ void doPrevSetBit(java.util.BitSet a, LongBitSet b) {
+ assertEquals(a.cardinality(), b.cardinality());
int aa = a.size() + random().nextInt(100);
long bb = aa;
do {
@@ -64,12 +66,12 @@ public class TestLongBitSet extends Luce
}
void doRandomSets(int maxSize, int iter, int mode) throws IOException {
- BitSet a0=null;
+ java.util.BitSet a0=null;
LongBitSet b0=null;
for (int i=0; i<iter; i++) {
int sz = TestUtil.nextInt(random(), 2, maxSize);
- BitSet a = new BitSet(sz);
+ java.util.BitSet a = new java.util.BitSet(sz);
LongBitSet b = new LongBitSet(sz);
// test the various ways of setting bits
@@ -87,12 +89,12 @@ public class TestLongBitSet extends Luce
b.clear(idx);
idx = random().nextInt(sz);
- a.flip(idx);
+ a.flip(idx, idx+1);
b.flip(idx, idx+1);
idx = random().nextInt(sz);
a.flip(idx);
- b.flip(idx, idx+1);
+ b.flip(idx);
boolean val2 = b.get(idx);
boolean val = b.getAndSet(idx);
@@ -111,12 +113,12 @@ public class TestLongBitSet extends Luce
int fromIndex, toIndex;
fromIndex = random().nextInt(sz/2);
toIndex = fromIndex + random().nextInt(sz - fromIndex);
- BitSet aa = (BitSet)a.clone(); aa.flip(fromIndex,toIndex);
+ java.util.BitSet aa = (java.util.BitSet)a.clone(); aa.flip(fromIndex,toIndex);
LongBitSet bb = b.clone(); bb.flip(fromIndex,toIndex);
fromIndex = random().nextInt(sz/2);
toIndex = fromIndex + random().nextInt(sz - fromIndex);
- aa = (BitSet)a.clone(); aa.clear(fromIndex,toIndex);
+ aa = (java.util.BitSet)a.clone(); aa.clear(fromIndex,toIndex);
bb = b.clone(); bb.clear(fromIndex,toIndex);
doNextSetBit(aa,bb); // a problem here is from clear() or nextSetBit
@@ -125,7 +127,7 @@ public class TestLongBitSet extends Luce
fromIndex = random().nextInt(sz/2);
toIndex = fromIndex + random().nextInt(sz - fromIndex);
- aa = (BitSet)a.clone(); aa.set(fromIndex,toIndex);
+ aa = (java.util.BitSet)a.clone(); aa.set(fromIndex,toIndex);
bb = b.clone(); bb.set(fromIndex,toIndex);
doNextSetBit(aa,bb); // a problem here is from set() or nextSetBit
@@ -135,10 +137,10 @@ public class TestLongBitSet extends Luce
if (b0 != null && b0.length() <= b.length()) {
assertEquals(a.cardinality(), b.cardinality());
- BitSet a_and = (BitSet)a.clone(); a_and.and(a0);
- BitSet a_or = (BitSet)a.clone(); a_or.or(a0);
- BitSet a_xor = (BitSet)a.clone(); a_xor.xor(a0);
- BitSet a_andn = (BitSet)a.clone(); a_andn.andNot(a0);
+ java.util.BitSet a_and = (java.util.BitSet)a.clone(); a_and.and(a0);
+ java.util.BitSet a_or = (java.util.BitSet)a.clone(); a_or.or(a0);
+ java.util.BitSet a_xor = (java.util.BitSet)a.clone(); a_xor.xor(a0);
+ java.util.BitSet a_andn = (java.util.BitSet)a.clone(); a_andn.andNot(a0);
LongBitSet b_and = b.clone(); assertEquals(b,b_and); b_and.and(b0);
LongBitSet b_or = b.clone(); b_or.or(b0);
@@ -162,8 +164,9 @@ public class TestLongBitSet extends Luce
// large enough to flush obvious bugs, small enough to run in <.5 sec as part of a
// larger testsuite.
public void testSmall() throws IOException {
- doRandomSets(atLeast(1200), atLeast(1000), 1);
- doRandomSets(atLeast(1200), atLeast(1000), 2);
+ final int iters = TEST_NIGHTLY ? atLeast(1000) : 100;
+ doRandomSets(atLeast(1200), iters, 1);
+ doRandomSets(atLeast(1200), iters, 2);
}
// uncomment to run a bigger test (~2 minutes).
@@ -234,16 +237,12 @@ public class TestLongBitSet extends Luce
}
}
- private LongBitSet makeLongFixedBitSet(int[] a, int numBits) {
+ private LongBitSet makeLongBitSet(int[] a, int numBits) {
LongBitSet bs;
if (random().nextBoolean()) {
int bits2words = LongBitSet.bits2words(numBits);
long[] words = new long[bits2words + random().nextInt(100)];
- for (int i = bits2words; i < words.length; i++) {
- words[i] = random().nextLong();
- }
bs = new LongBitSet(words, numBits);
-
} else {
bs = new LongBitSet(numBits);
}
@@ -253,8 +252,8 @@ public class TestLongBitSet extends Luce
return bs;
}
- private BitSet makeBitSet(int[] a) {
- BitSet bs = new BitSet();
+ private java.util.BitSet makeBitSet(int[] a) {
+ java.util.BitSet bs = new java.util.BitSet();
for (int e: a) {
bs.set(e);
}
@@ -262,8 +261,8 @@ public class TestLongBitSet extends Luce
}
private void checkPrevSetBitArray(int [] a, int numBits) {
- LongBitSet obs = makeLongFixedBitSet(a, numBits);
- BitSet bs = makeBitSet(a);
+ LongBitSet obs = makeLongBitSet(a, numBits);
+ java.util.BitSet bs = makeBitSet(a);
doPrevSetBit(bs, obs);
}
@@ -275,8 +274,8 @@ public class TestLongBitSet extends Luce
private void checkNextSetBitArray(int [] a, int numBits) {
- LongBitSet obs = makeLongFixedBitSet(a, numBits);
- BitSet bs = makeBitSet(a);
+ LongBitSet obs = makeLongBitSet(a, numBits);
+ java.util.BitSet bs = makeBitSet(a);
doNextSetBit(bs, obs);
}
@@ -340,8 +339,8 @@ public class TestLongBitSet extends Luce
assertEquals(2, LongBitSet.bits2words(128));
assertEquals(3, LongBitSet.bits2words(129));
// ...
- assertEquals(1 << (31-6), LongBitSet.bits2words(1L << 31));
- assertEquals((1 << (31-6)) + 1, LongBitSet.bits2words((1L << 31)) + 1);
+ assertEquals(1 << (31-6), LongBitSet.bits2words((long)Integer.MAX_VALUE + 1)); // == 1L << 31
+ assertEquals((1 << (31-6)) + 1, LongBitSet.bits2words((long)Integer.MAX_VALUE + 2)); // == (1L << 31) + 1
// ...
assertEquals(1 << (32-6), LongBitSet.bits2words(1L << 32));
assertEquals((1 << (32-6)) + 1, LongBitSet.bits2words((1L << 32)) + 1);
Modified: lucene/dev/trunk/solr/core/src/test/org/apache/solr/search/TestFiltering.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/solr/core/src/test/org/apache/solr/search/TestFiltering.java?rev=1676617&r1=1676616&r2=1676617&view=diff
==============================================================================
--- lucene/dev/trunk/solr/core/src/test/org/apache/solr/search/TestFiltering.java (original)
+++ lucene/dev/trunk/solr/core/src/test/org/apache/solr/search/TestFiltering.java Tue Apr 28 20:37:15 2015
@@ -204,10 +204,18 @@ public class TestFiltering extends SolrT
return frangeStr(!positive, l, u, cache, cost, exclude);
} else {
// term or boolean query
- FixedBitSet pset = new FixedBitSet(model.indexSize);
- for (int i=0; i<pset.getBits().length; i++) {
- pset.getBits()[i] = random().nextLong(); // set 50% of the bits on average
+ int numWords = FixedBitSet.bits2words(model.indexSize);
+ long[] psetBits = new long[numWords];
+ for (int i=0; i<psetBits.length; i++) {
+ psetBits[i] = random().nextLong(); // set 50% of the bits on average
}
+ // Make sure no 'ghost' bits are set beyond model.indexSize (see FixedBitSet.verifyGhostBitsClear)
+ if ((model.indexSize & 0x3f) != 0) {
+ long mask = -1L << model.indexSize; // & 0x3f is implicit
+
+ psetBits[numWords - 1] &= ~mask;
+ }
+ FixedBitSet pset = new FixedBitSet(psetBits, model.indexSize);
if (positive) {
for (FixedBitSet set : sets) {
set.and(pset);