You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by si...@apache.org on 2013/01/18 16:25:59 UTC
svn commit: r1435191 - in /lucene/dev/trunk/lucene/core/src:
java/org/apache/lucene/util/FixedBitSet.java
test/org/apache/lucene/util/TestFixedBitSet.java
Author: simonw
Date: Fri Jan 18 15:25:58 2013
New Revision: 1435191
URL: http://svn.apache.org/viewvc?rev=1435191&view=rev
Log:
LUCENE-4693: FixedBitset might return wrong results if words.length > actual words in the bitset
Modified:
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java
lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestFixedBitSet.java
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=1435191&r1=1435190&r2=1435191&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 Fri Jan 18 15:25:58 2013
@@ -39,6 +39,7 @@ import org.apache.lucene.search.DocIdSet
public final class FixedBitSet extends DocIdSet implements Bits {
private final long[] bits;
private final int numBits;
+ private final int wordLength;
/** returns the number of 64 bit words it would take to hold numBits */
public static int bits2words(int numBits) {
@@ -52,23 +53,29 @@ public final class FixedBitSet extends D
public FixedBitSet(int numBits) {
this.numBits = numBits;
bits = new long[bits2words(numBits)];
+ wordLength = bits.length;
}
- public FixedBitSet(long[]storedBits,int numBits) {
+ public FixedBitSet(long[] storedBits, int numBits) {
+ this.wordLength = bits2words(numBits);
+ if (wordLength > storedBits.length) {
+ throw new IllegalArgumentException("The given long array is too small to hold " + numBits + " bits");
+ }
this.numBits = numBits;
this.bits = storedBits;
}
/** Makes full copy. */
public FixedBitSet(FixedBitSet other) {
- bits = new long[other.bits.length];
- System.arraycopy(other.bits, 0, bits, 0, bits.length);
+ bits = new long[other.wordLength];
+ System.arraycopy(other.bits, 0, bits, 0, other.wordLength);
numBits = other.numBits;
+ wordLength = other.wordLength;
}
@Override
public DocIdSetIterator iterator() {
- return new OpenBitSetIterator(bits, bits.length);
+ return new OpenBitSetIterator(bits, wordLength);
}
@Override
@@ -159,7 +166,7 @@ public final class FixedBitSet extends D
return (i<<6) + subIndex + Long.numberOfTrailingZeros(word);
}
- while(++i < bits.length) {
+ while(++i < wordLength) {
word = bits[i];
if (word != 0) {
return (i<<6) + Long.numberOfTrailingZeros(word);
@@ -211,12 +218,12 @@ public final class FixedBitSet extends D
/** this = this OR other */
public void or(FixedBitSet other) {
- or(other.bits, other.bits.length);
+ or(other.bits, other.wordLength);
}
private void or(final long[] otherArr, final int otherLen) {
final long[] thisArr = this.bits;
- int pos = Math.min(thisArr.length, otherLen);
+ int pos = Math.min(wordLength, otherLen);
while (--pos >= 0) {
thisArr[pos] |= otherArr[pos];
}
@@ -247,17 +254,17 @@ public final class FixedBitSet extends D
/** this = this AND other */
public void and(FixedBitSet other) {
- and(other.bits, other.bits.length);
+ and(other.bits, other.wordLength);
}
private void and(final long[] otherArr, final int otherLen) {
final long[] thisArr = this.bits;
- int pos = Math.min(thisArr.length, otherLen);
+ int pos = Math.min(this.wordLength, otherLen);
while(--pos >= 0) {
thisArr[pos] &= otherArr[pos];
}
- if (thisArr.length > otherLen) {
- Arrays.fill(thisArr, otherLen, thisArr.length, 0L);
+ if (this.wordLength > otherLen) {
+ Arrays.fill(thisArr, otherLen, this.wordLength, 0L);
}
}
@@ -285,7 +292,7 @@ public final class FixedBitSet extends D
private void andNot(final long[] otherArr, final int otherLen) {
final long[] thisArr = this.bits;
- int pos = Math.min(thisArr.length, otherLen);
+ int pos = Math.min(this.wordLength, otherLen);
while(--pos >= 0) {
thisArr[pos] &= ~otherArr[pos];
}
@@ -418,7 +425,7 @@ public final class FixedBitSet extends D
@Override
public int hashCode() {
long h = 0;
- for (int i = bits.length; --i>=0;) {
+ for (int i = wordLength; --i>=0;) {
h ^= bits[i];
h = (h << 1) | (h >>> 63); // rotate left
}
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=1435191&r1=1435190&r2=1435191&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 Fri Jan 18 15:25:58 2013
@@ -265,7 +265,18 @@ public class TestFixedBitSet extends Luc
}
private FixedBitSet makeFixedBitSet(int[] a, int numBits) {
- FixedBitSet bs = new FixedBitSet(numBits);
+ FixedBitSet bs;
+ 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);
+ }
for (int e: a) {
bs.set(e);
}
@@ -291,6 +302,23 @@ public class TestFixedBitSet extends Luc
checkPrevSetBitArray(new int[] {0}, 1);
checkPrevSetBitArray(new int[] {0,2}, 3);
}
+
+
+ private void checkNextSetBitArray(int [] a, int numBits) {
+ FixedBitSet obs = makeFixedBitSet(a, numBits);
+ BitSet bs = makeBitSet(a);
+ doNextSetBit(bs, obs);
+ }
+
+ public void testNextBitSet() {
+ int[] setBits = new int[0+random().nextInt(1000)];
+ for (int i = 0; i < setBits.length; i++) {
+ setBits[i] = random().nextInt(setBits.length);
+ }
+ checkNextSetBitArray(setBits, setBits.length + random().nextInt(10));
+
+ checkNextSetBitArray(new int[0], setBits.length + random().nextInt(10));
+ }
}