You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by jm...@apache.org on 2024/03/30 07:30:50 UTC
(datasketches-java) branch bloom-direct updated: WIP: Increase test coverage, fixing issues along the way
This is an automated email from the ASF dual-hosted git repository.
jmalkin pushed a commit to branch bloom-direct
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
The following commit(s) were added to refs/heads/bloom-direct by this push:
new 33f73d5c WIP: Increase test coverage, fixing issues along the way
33f73d5c is described below
commit 33f73d5c0587c8ad0870b4046bd9f855a8493574
Author: jmalkin <78...@users.noreply.github.com>
AuthorDate: Sat Mar 30 00:30:42 2024 -0700
WIP: Increase test coverage, fixing issues along the way
---
.../datasketches/filters/bloomfilter/BitArray.java | 4 +-
.../filters/bloomfilter/BloomFilter.java | 16 +-
.../filters/bloomfilter/BloomFilterBuilder.java | 112 +++++++-----
.../filters/bloomfilter/HeapBitArray.java | 3 +
.../bloomfilter/BloomFilterBuilderTest.java | 5 +-
.../filters/bloomfilter/BloomFilterTest.java | 187 ++++++++++++++++++++-
.../filters/bloomfilter/DirectBitArrayRTest.java | 6 +-
.../filters/bloomfilter/DirectBitArrayTest.java | 14 ++
.../filters/bloomfilter/HeapBitArrayTest.java | 12 ++
9 files changed, 298 insertions(+), 61 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/filters/bloomfilter/BitArray.java b/src/main/java/org/apache/datasketches/filters/bloomfilter/BitArray.java
index 951d87fc..0dca87ed 100644
--- a/src/main/java/org/apache/datasketches/filters/bloomfilter/BitArray.java
+++ b/src/main/java/org/apache/datasketches/filters/bloomfilter/BitArray.java
@@ -56,9 +56,7 @@ abstract class BitArray {
abstract boolean isDirect();
- boolean isReadOnly() {
- return false;
- }
+ abstract boolean isReadOnly();
abstract boolean getBit(final long index);
diff --git a/src/main/java/org/apache/datasketches/filters/bloomfilter/BloomFilter.java b/src/main/java/org/apache/datasketches/filters/bloomfilter/BloomFilter.java
index ca4da16e..762e758f 100644
--- a/src/main/java/org/apache/datasketches/filters/bloomfilter/BloomFilter.java
+++ b/src/main/java/org/apache/datasketches/filters/bloomfilter/BloomFilter.java
@@ -63,6 +63,7 @@ public final class BloomFilter {
private static final int SER_VER = 1;
private static final int EMPTY_FLAG_MASK = 4;
private static final long BIT_ARRAY_OFFSET = 16;
+ private static final int FLAGS_BYTE = 3;
private long seed_; // hash seed
private short numHashes_; // number of hash values
@@ -98,7 +99,7 @@ public final class BloomFilter {
throw new SketchesArgumentException("Provided WritableMemory capacity insufficient to initialize BloomFilter");
}
- // we don't resize so initialize with non-empty preLongs value
+ // we don't resize so initialize wizth non-empty preLongs value
// and no empty flag
final WritableBuffer wbuf = wmem.asWritableBuffer();
wbuf.putByte((byte) Family.BLOOMFILTER.getMaxPreLongs());
@@ -165,9 +166,9 @@ public final class BloomFilter {
final BitArray bitArray;
if (isWrap) {
if (isWritable) {
- bitArray = DirectBitArray.writableWrap(wmem.writableRegion(BIT_ARRAY_OFFSET, wmem.getCapacity() - BIT_ARRAY_OFFSET), isEmpty);
+ bitArray = BitArray.writableWrap(wmem.writableRegion(BIT_ARRAY_OFFSET, wmem.getCapacity() - BIT_ARRAY_OFFSET), isEmpty);
} else {
- bitArray = DirectBitArrayR.wrap(wmem.region(BIT_ARRAY_OFFSET, wmem.getCapacity() - BIT_ARRAY_OFFSET), isEmpty);
+ bitArray = BitArray.wrap(wmem.region(BIT_ARRAY_OFFSET, wmem.getCapacity() - BIT_ARRAY_OFFSET), isEmpty);
}
return new BloomFilter(numHashes, seed, bitArray, wmem);
} else { // if heapify
@@ -225,7 +226,7 @@ public final class BloomFilter {
* @return true if read-only, otherwise false
*/
public boolean isReadOnly() {
- return wmem_ != null && wmem_.isReadOnly();
+ return wmem_ != null && bitArray_.isReadOnly();
}
/**
@@ -780,6 +781,9 @@ public final class BloomFilter {
((HeapBitArray) bitArray_).writeToBuffer(wbuf);
} else {
wmem_.getByteArray(0, bytes, 0, (int) sizeBytes);
+ if (isEmpty()) {
+ bytes[FLAGS_BYTE] |= EMPTY_FLAG_MASK;
+ }
}
return bytes;
}
@@ -809,6 +813,10 @@ public final class BloomFilter {
((HeapBitArray) bitArray_).writeToBuffer(wbuf);
} else {
wmem_.getLongArray(0, longs, 0, (int) (sizeBytes >>> 3));
+ if (isEmpty()) {
+ final long longMask = EMPTY_FLAG_MASK << (FLAGS_BYTE << 3);
+ longs[0] |= longMask;
+ }
}
return longs;
}
diff --git a/src/main/java/org/apache/datasketches/filters/bloomfilter/BloomFilterBuilder.java b/src/main/java/org/apache/datasketches/filters/bloomfilter/BloomFilterBuilder.java
index 3397ca2c..0352b035 100644
--- a/src/main/java/org/apache/datasketches/filters/bloomfilter/BloomFilterBuilder.java
+++ b/src/main/java/org/apache/datasketches/filters/bloomfilter/BloomFilterBuilder.java
@@ -25,7 +25,7 @@ import org.apache.datasketches.common.SketchesArgumentException;
import org.apache.datasketches.memory.WritableMemory;
/**
- * <p>This class provides methods to help estimate the correct paramters to use when
+ * <p>This class provides methods to help estimate the correct parameters when
* creating a Bloom filter, and methods to create the filter using those values.</p>
*
* <p>The underlying math is described in the
@@ -36,7 +36,7 @@ public final class BloomFilterBuilder {
/**
* Returns the optimal number of hash functions to given target numbers of distinct items
- * and the BloomFliter size in bits.
+ * and the BloomFilter size in bits.
* @param maxDistinctItems The maximum expected number of distinct items to add to the filter
* @param numFilterBits The intended size of the Bloom Filter in bits
* @return The suggested number of hash functions to use with the filter
@@ -80,9 +80,9 @@ public final class BloomFilterBuilder {
}
/**
- * Returns the minimum memory size, in bytes, needed for a serizlied BloomFilter with an optimal number of bits
+ * Returns the minimum memory size, in bytes, needed for a serialized BloomFilter with an optimal number of bits
* and hash functions for the given inputs. This is also the minimum size of a WritableMemory for
- * in-place filter intialization.
+ * in-place filter initialization.
* @param maxDistinctItems The maximum expected number of distinct items to add to the filter
* @param targetFalsePositiveProb A desired false positive probability per item
* @return The size, in bytes, required to hold the specified BloomFilter when serialized
@@ -92,8 +92,8 @@ public final class BloomFilterBuilder {
}
/**
- * Returns the minimum memory size, in bytes, needed for a serizlied BloomFilter with the given number of bits.
- * This is also the minimum size of a WritableMemory for in-place filter intialization.
+ * Returns the minimum memory size, in bytes, needed for a serialized BloomFilter with the given number of bits.
+ * This is also the minimum size of a WritableMemory for in-place filter initialization.
* @param numBits The number of bits in the target BloomFilter's bit array.
* @return The size, in bytes, required to hold the specified BloomFilter when serialized
*/
@@ -109,6 +109,8 @@ public final class BloomFilterBuilder {
* @return A new BloomFilter configured for the given input parameters
*/
public static BloomFilter createByAccuracy(final long maxDistinctItems, final double targetFalsePositiveProb) {
+
+
return createByAccuracy(maxDistinctItems, targetFalsePositiveProb, ThreadLocalRandom.current().nextLong());
}
@@ -121,12 +123,8 @@ public final class BloomFilterBuilder {
* @return A new BloomFilter configured for the given input parameters
*/
public static BloomFilter createByAccuracy(final long maxDistinctItems, final double targetFalsePositiveProb, final long seed) {
- if (maxDistinctItems <= 0) {
- throw new SketchesArgumentException("maxDistinctItems must be strictly positive");
- }
- if (targetFalsePositiveProb <= 0.0 || targetFalsePositiveProb > 1.0) {
- throw new SketchesArgumentException("targetFalsePositiveProb must be a valid probability and strictly greater than 0");
- }
+ validateAccuracyInputs(maxDistinctItems, targetFalsePositiveProb);
+
final long numBits = suggestNumFilterBits(maxDistinctItems, targetFalsePositiveProb);
final short numHashes = suggestNumHashes(maxDistinctItems, numBits);
return new BloomFilter(numBits, numHashes, seed);
@@ -144,7 +142,7 @@ public final class BloomFilterBuilder {
return createBySize(numBits, numHashes, ThreadLocalRandom.current().nextLong());
}
- /**
+ /**
* Creates a BloomFilter with given number of bits and number of hash functions,
* using the provided base seed for the hash function.
*
@@ -154,23 +152,46 @@ public final class BloomFilterBuilder {
* @return A new BloomFilter configured for the given input parameters
*/
public static BloomFilter createBySize(final long numBits, final int numHashes, final long seed) {
- if (numBits > BloomFilter.MAX_SIZE) {
- throw new SketchesArgumentException("Size of BloomFilter must be <= "
- + BloomFilter.MAX_SIZE + ". Requested: " + numBits);
- }
- if (numHashes < 1) {
- throw new SketchesArgumentException("Must specify a strictly positive number of hash functions. "
- + "Requested: " + numHashes);
- }
- if (numHashes > Short.MAX_VALUE) {
- throw new SketchesArgumentException("Number of hashes cannot exceed " + Short.MAX_VALUE
- + ". Requested: " + numHashes);
- }
+ validateSizeInputs(numBits, numHashes);
return new BloomFilter(numBits, numHashes, seed);
}
- /**
+ /**
+ * Creates a new BloomFilter with an optimal number of bits and hash functions for the given inputs,
+ * using a random base seed for the hash function and writing into the provided WritableMemory.
+ * @param maxDistinctItems The maximum expected number of distinct items to add to the filter
+ * @param targetFalsePositiveProb A desired false positive probability per item
+ * @param dstMem A WritableMemory to hold the initialized filter
+ * @return A new BloomFilter configured for the given input parameters
+ */
+ public static BloomFilter initializeByAccuracy(final long maxDistinctItems, final double targetFalsePositiveProb, final WritableMemory dstMem) {
+ return initializeByAccuracy(maxDistinctItems, targetFalsePositiveProb, ThreadLocalRandom.current().nextLong(), dstMem);
+ }
+
+ /**
+ * Creates a new BloomFilter with an optimal number of bits and hash functions for the given inputs,
+ * using the provided base seed for the hash function and writing into the provided WritableMemory.
+ * @param maxDistinctItems The maximum expected number of distinct items to add to the filter
+ * @param targetFalsePositiveProb A desired false positive probability per item
+ * @param seed A base hash seed
+ * @param dstMem A WritableMemory to hold the initialized filter
+ * @return A new BloomFilter configured for the given input parameters
+ */
+ public static BloomFilter initializeByAccuracy(final long maxDistinctItems, final double targetFalsePositiveProb, final long seed, final WritableMemory dstMem) {
+ validateAccuracyInputs(maxDistinctItems, targetFalsePositiveProb);
+
+ final long numBits = suggestNumFilterBits(maxDistinctItems, targetFalsePositiveProb);
+ final short numHashes = suggestNumHashes(maxDistinctItems, numBits);
+
+ if (dstMem.getCapacity() < BloomFilter.getSerializedSize(numBits)) {
+ throw new SketchesArgumentException("Provided WritableMemory is insufficint to hold requested filter");
+ }
+
+ return new BloomFilter(numBits, numHashes, seed, dstMem);
+ }
+
+ /**
* Initializes a BloomFilter with given number of bits and number of hash functions,
* using a random base seed for the hash function and writing into the provided WritableMemory.
*
@@ -179,11 +200,11 @@ public final class BloomFilterBuilder {
* @param dstMem A WritableMemory to hold the initialized filter
* @return A new BloomFilter configured for the given input parameters
*/
- public static BloomFilter initializeFilter(final long numBits, final int numHashes, final WritableMemory wmem) {
- return initializeFilter(numBits, numHashes, ThreadLocalRandom.current().nextLong(), wmem);
+ public static BloomFilter initializeBySize(final long numBits, final int numHashes, final WritableMemory dstMem) {
+ return initializeBySize(numBits, numHashes, ThreadLocalRandom.current().nextLong(), dstMem);
}
- /**
+ /**
* Initializes a BloomFilter with given number of bits and number of hash functions,
* using the provided base seed for the hash function and writing into the provided WritableMemory.
*
@@ -193,24 +214,37 @@ public final class BloomFilterBuilder {
* @param dstMem A WritableMemory to hold the initialized filter
* @return A new BloomFilter configured for the given input parameters
*/
- public static BloomFilter initializeFilter(final long numBits, final int numHashes, final long seed, final WritableMemory wmem) {
+ public static BloomFilter initializeBySize(final long numBits, final int numHashes, final long seed, final WritableMemory dstMem) {
+ validateSizeInputs(numBits, numHashes);
+
+ if (dstMem.getCapacity() < BloomFilter.getSerializedSize(numBits)) {
+ throw new SketchesArgumentException("Provided WritableMemory is insufficint to hold requested filter");
+ }
+
+ return new BloomFilter(numBits, numHashes, seed, dstMem);
+ }
+
+ private static void validateAccuracyInputs(long maxDistinctItems, double targetFalsePositiveProb) {
+ if (maxDistinctItems <= 0) {
+ throw new SketchesArgumentException("maxDistinctItems must be strictly positive");
+ }
+ if (targetFalsePositiveProb <= 0.0 || targetFalsePositiveProb > 1.0) {
+ throw new SketchesArgumentException("targetFalsePositiveProb must be a valid probability and strictly greater than 0");
+ }
+ }
+
+ private static void validateSizeInputs(final long numBits, final int numHashes) {
if (numBits > BloomFilter.MAX_SIZE) {
throw new SketchesArgumentException("Size of BloomFilter must be <= "
- + BloomFilter.MAX_SIZE + ". Requested: " + numBits);
+ + BloomFilter.MAX_SIZE + ". Requested: " + numBits);
}
if (numHashes < 1) {
throw new SketchesArgumentException("Must specify a strictly positive number of hash functions. "
- + "Requested: " + numHashes);
+ + "Requested: " + numHashes);
}
if (numHashes > Short.MAX_VALUE) {
throw new SketchesArgumentException("Number of hashes cannot exceed " + Short.MAX_VALUE
- + ". Requested: " + numHashes);
+ + ". Requested: " + numHashes);
}
- if (wmem.getCapacity() < BloomFilter.getSerializedSize(numBits)) {
- throw new SketchesArgumentException("Provided WritableMemory is insufficint to hold requested filter");
- }
-
- return new BloomFilter(numBits, numHashes, seed, wmem);
}
-
}
diff --git a/src/main/java/org/apache/datasketches/filters/bloomfilter/HeapBitArray.java b/src/main/java/org/apache/datasketches/filters/bloomfilter/HeapBitArray.java
index a003ce2a..4048b677 100644
--- a/src/main/java/org/apache/datasketches/filters/bloomfilter/HeapBitArray.java
+++ b/src/main/java/org/apache/datasketches/filters/bloomfilter/HeapBitArray.java
@@ -99,6 +99,9 @@ final class HeapBitArray extends BitArray {
return false;
}
+ @Override
+ boolean isReadOnly() { return false; }
+
// queries a single bit in the array
@Override
boolean getBit(final long index) {
diff --git a/src/test/java/org/apache/datasketches/filters/bloomfilter/BloomFilterBuilderTest.java b/src/test/java/org/apache/datasketches/filters/bloomfilter/BloomFilterBuilderTest.java
index fd86c651..10e4a801 100644
--- a/src/test/java/org/apache/datasketches/filters/bloomfilter/BloomFilterBuilderTest.java
+++ b/src/test/java/org/apache/datasketches/filters/bloomfilter/BloomFilterBuilderTest.java
@@ -19,12 +19,11 @@
package org.apache.datasketches.filters.bloomfilter;
-import static org.testng.Assert.assertEquals;
-import static org.testng.Assert.assertThrows;
-
import org.apache.datasketches.common.SketchesArgumentException;
import org.testng.annotations.Test;
+import static org.testng.Assert.*;
+
public class BloomFilterBuilderTest {
@Test
diff --git a/src/test/java/org/apache/datasketches/filters/bloomfilter/BloomFilterTest.java b/src/test/java/org/apache/datasketches/filters/bloomfilter/BloomFilterTest.java
index bb3e73b1..b54e7a1d 100644
--- a/src/test/java/org/apache/datasketches/filters/bloomfilter/BloomFilterTest.java
+++ b/src/test/java/org/apache/datasketches/filters/bloomfilter/BloomFilterTest.java
@@ -24,12 +24,113 @@ import static org.testng.Assert.assertFalse;
import static org.testng.Assert.assertThrows;
import static org.testng.Assert.assertTrue;
+import org.apache.datasketches.common.Family;
import org.apache.datasketches.common.SketchesArgumentException;
+import org.apache.datasketches.common.SketchesReadOnlyException;
import org.apache.datasketches.memory.Memory;
+import org.apache.datasketches.memory.WritableMemory;
import org.testng.annotations.Test;
public class BloomFilterTest {
+ @Test
+ public void createNewFilterTest() {
+ // construct the same filter multiple ways
+ final long numItems = 4000;
+ final double targetFpp = 0.01;
+
+ final long numBits = BloomFilterBuilder.suggestNumFilterBits(numItems, targetFpp);
+ final short numHashes = BloomFilterBuilder.suggestNumHashes(numItems, numBits);
+ final int sizeBytes = (int) BloomFilterBuilder.getSerializedFilterSize(numBits);
+ final long seed = 89023L;
+
+ final BloomFilter bf1 = new BloomFilter(numBits, numHashes, seed);
+ assertTrue(bf1.isEmpty());
+ assertFalse(bf1.hasMemory());
+ assertFalse(bf1.isDirect());
+ assertFalse(bf1.isReadOnly());
+
+ final WritableMemory wmem = WritableMemory.allocateDirect(sizeBytes).getWritable();
+ final BloomFilter bf2 = new BloomFilter(numBits, numHashes, seed, wmem);
+ assertTrue(bf2.isEmpty());
+ assertTrue(bf2.hasMemory());
+ assertTrue(bf2.isDirect());
+ assertFalse(bf2.isReadOnly());
+ }
+
+ @Test(expectedExceptions = SketchesArgumentException.class)
+ public void tooSmallMemoryTest() {
+ new BloomFilter(65536, 4, 1L, WritableMemory.allocate(32));
+ }
+
+ @Test
+ public void wrapEmptyFilterTest() {
+ final long numBits = 8192;
+ final int numHashes = 4;
+ final BloomFilter bf = BloomFilterBuilder.createBySize(numBits, numHashes);
+ assertTrue(bf.isEmpty());
+ assertEquals(bf.getBitsUsed(), 0);
+ assertEquals(bf.getCapacity(), numBits);
+ assertEquals(bf.getNumHashes(), numHashes);
+
+ final Memory mem = Memory.wrap(bf.toByteArray());
+ assertEquals(bf.getSerializedSizeBytes(), mem.getCapacity());
+
+ final WritableMemory wmem = WritableMemory.writableWrap(bf.toByteArray());
+ assertEquals(bf.getSerializedSizeBytes(), wmem.getCapacity());
+
+ // read-only
+ final BloomFilter bfReadOnly = BloomFilter.wrap(mem);
+ assertTrue(bfReadOnly.isEmpty());
+ assertEquals(bfReadOnly.getBitsUsed(), 0);
+ assertEquals(bfReadOnly.getCapacity(), numBits);
+ assertEquals(bfReadOnly.getNumHashes(), numHashes);
+ assertTrue(bfReadOnly.isReadOnly());
+
+ // writable should fail
+ assertThrows(SketchesArgumentException.class, () -> BloomFilter.writableWrap(wmem));
+ }
+
+ @Test
+ public void wrapNonEmptyFilterTest() {
+ final long numBits = 8192;
+ final int numHashes = 4;
+ final long seed = 52483905L;
+ final BloomFilter bf = BloomFilterBuilder.createBySize(numBits, numHashes, seed);
+
+ final long valStart = 1024;
+ final long valEnd = 2048;
+ for (long i = valStart; i < valEnd; ++i) {
+ bf.update(i);
+ }
+
+ final WritableMemory wmem = WritableMemory.writableWrap(bf.toByteArray());
+ assertEquals(bf.getSerializedSizeBytes(), wmem.getCapacity());
+
+ // writable
+ final BloomFilter bfWritable = BloomFilter.writableWrap(wmem);
+ assertFalse(bfWritable.isEmpty());
+ assertEquals(bfWritable.getBitsUsed(), bf.getBitsUsed());
+ assertEquals(bfWritable.getCapacity(), bf.getCapacity());
+ assertEquals(bfWritable.getNumHashes(), bf.getNumHashes());
+ assertFalse(bfWritable.isReadOnly());
+
+ // read-only, wrapping the same writable memory
+ final BloomFilter bfReadOnly = BloomFilter.wrap(wmem);
+ assertFalse(bfReadOnly.isEmpty());
+ assertEquals(bfReadOnly.getBitsUsed(), bf.getBitsUsed());
+ assertEquals(bfReadOnly.getCapacity(), bf.getCapacity());
+ assertEquals(bfReadOnly.getNumHashes(), bf.getNumHashes());
+ assertTrue(bfReadOnly.isReadOnly());
+
+ // update writable, should be reflected in read-only because
+ // they use the same underling Memory
+ assertFalse(bfWritable.queryAndUpdate(32768));
+ assertTrue(bfReadOnly.query(32768));
+
+ assertThrows(SketchesReadOnlyException.class, () -> bfReadOnly.update(99999));
+ }
+
@Test
public void basicFilterOperationsTest() {
final long numBits = 8192;
@@ -58,6 +159,14 @@ public class BloomFilterTest {
}
assertTrue(numFound >= n);
assertTrue(numFound < 1.1 * n);
+
+ assert(String.valueOf(bf).length() > 0);
+
+ bf.reset();
+ assertTrue(bf.isEmpty());
+ assertEquals(bf.getCapacity(), numBits); // n is multiple of 64 so should be exact
+ assertEquals(bf.getNumHashes(), numHashes);
+ assertEquals(bf.getBitsUsed(), 0);
}
@Test
@@ -89,7 +198,6 @@ public class BloomFilterTest {
count += bf.query(Integer.toString(i)) ? 1 : 0;
}
assertTrue(count > n);
-
}
@Test
@@ -179,18 +287,24 @@ public class BloomFilterTest {
final BloomFilter bf = BloomFilterBuilder.createBySize(numBits, numHashes);
final byte[] bytes = bf.toByteArray();
- Memory mem = Memory.wrap(bytes);
- final BloomFilter fromBytes = BloomFilter.heapify(mem);
+ final Memory memBytes = Memory.wrap(bytes);
+ final BloomFilter fromBytes = BloomFilter.heapify(memBytes);
assertTrue(fromBytes.isEmpty());
assertEquals(fromBytes.getCapacity(), numBits);
assertEquals(fromBytes.getNumHashes(), numHashes);
final long[] longs = bf.toLongArray();
- mem = Memory.wrap(longs);
- final BloomFilter fromLongs = BloomFilter.heapify(mem);
+ final Memory memLongs = Memory.wrap(longs);
+ final BloomFilter fromLongs = BloomFilter.heapify(memLongs);
assertTrue(fromLongs.isEmpty());
assertEquals(fromLongs.getCapacity(), numBits);
assertEquals(fromLongs.getNumHashes(), numHashes);
+
+ // compare memories
+ assertEquals(memBytes.getCapacity(), memLongs.getCapacity());
+ for (int i = 0; i < memBytes.getCapacity(); ++i) {
+ assertEquals(memBytes.getByte(i), memLongs.getByte(i));
+ }
}
@Test
@@ -212,8 +326,8 @@ public class BloomFilterTest {
}
final byte[] bytes = bf.toByteArray();
- Memory mem = Memory.wrap(bytes);
- final BloomFilter fromBytes = BloomFilter.heapify(mem);
+ final Memory memBytes = Memory.wrap(bytes);
+ final BloomFilter fromBytes = BloomFilter.heapify(memBytes);
assertFalse(fromBytes.isEmpty());
assertEquals(fromBytes.getCapacity(), numBits);
assertEquals(fromBytes.getBitsUsed(), numBitsSet);
@@ -227,8 +341,8 @@ public class BloomFilterTest {
assertEquals(fromBytesCount, n + count); // same numbers of items should match
final long[] longs = bf.toLongArray();
- mem = Memory.wrap(longs);
- final BloomFilter fromLongs = BloomFilter.heapify(mem);
+ final Memory memLongs = Memory.wrap(longs);
+ final BloomFilter fromLongs = BloomFilter.heapify(memLongs);
assertFalse(fromLongs.isEmpty());
assertEquals(fromLongs.getCapacity(), numBits);
assertEquals(fromLongs.getBitsUsed(), numBitsSet);
@@ -240,6 +354,61 @@ public class BloomFilterTest {
if (i < n) assertTrue(val);
}
assertEquals(fromLongsCount, n + count); // same numbers of items should match
+
+ assertEquals(memBytes.getCapacity(), memLongs.getCapacity());
+ for (long i = 0; i < memBytes.getCapacity(); ++i) {
+ assertEquals(memBytes.getByte(i), memLongs.getByte(i));
+ }
+ }
+
+ @Test
+ public void heapifyFromDirectTest() {
+ final long numDistinct = 10000;
+ final double targetFpp = 0.001;
+ final int numBytes = (int) BloomFilterBuilder.getSerializedFilterSizeByAccuracy(numDistinct, targetFpp);
+ final WritableMemory wmem = WritableMemory.allocate(numBytes);
+ final BloomFilter bf = BloomFilterBuilder.initializeByAccuracy(numDistinct, targetFpp, 89540235L, wmem);
+
+ byte[] bytes = bf.toByteArray();
+ assertEquals(bytes.length, Family.BLOOMFILTER.getMinPreLongs() * Long.BYTES);
+ BloomFilter bfBytes = BloomFilter.heapify(Memory.wrap(bytes));
+ assertTrue(bfBytes.isEmpty());
+ assertEquals(bfBytes.getNumHashes(), bf.getNumHashes());
+ assertEquals(bfBytes.getBitsUsed(), 0);
+ assertEquals(bfBytes.getCapacity(), bf.getCapacity()); // even though empty
+
+ long[] longs = bf.toLongArray();
+ assertEquals(longs.length, Family.BLOOMFILTER.getMinPreLongs());
+ BloomFilter bfLongs = BloomFilter.heapify(Memory.wrap(longs));
+ assertTrue(bfLongs.isEmpty());
+ assertEquals(bfLongs.getNumHashes(), bf.getNumHashes());
+ assertEquals(bfLongs.getBitsUsed(), 0);
+ assertEquals(bfLongs.getCapacity(), bf.getCapacity());
+
+ // add some items now
+ for (int i = 0; i < 10000; ++i) {
+ bf.queryAndUpdate(Integer.toString(i));
+ }
+
+ bytes = bf.toByteArray();
+ assertEquals(bytes.length, bf.getSerializedSizeBytes());
+ bfBytes = BloomFilter.heapify(Memory.wrap(bytes));
+ assertFalse(bfBytes.isEmpty());
+ assertEquals(bfBytes.getNumHashes(), bf.getNumHashes());
+ assertEquals(bfBytes.getBitsUsed(), bf.getBitsUsed());
+ assertEquals(bfBytes.getCapacity(), bf.getCapacity());
+ assertTrue(bfBytes.query(Integer.toString(5000)));
+ assertFalse(bfBytes.query(Integer.toString(50000)));
+
+ longs = bf.toLongArray();
+ assertEquals(longs.length, bf.getSerializedSizeBytes() / Long.BYTES);
+ bfLongs = BloomFilter.heapify(Memory.wrap(longs));
+ assertFalse(bfLongs.isEmpty());
+ assertEquals(bfLongs.getNumHashes(), bf.getNumHashes());
+ assertEquals(bfLongs.getBitsUsed(), bf.getBitsUsed());
+ assertEquals(bfLongs.getCapacity(), bf.getCapacity());
+ assertTrue(bfBytes.query(Integer.toString(7500)));
+ assertFalse(bfBytes.query(Integer.toString(75000)));
}
@Test
diff --git a/src/test/java/org/apache/datasketches/filters/bloomfilter/DirectBitArrayRTest.java b/src/test/java/org/apache/datasketches/filters/bloomfilter/DirectBitArrayRTest.java
index 26b9fe04..a36c028e 100644
--- a/src/test/java/org/apache/datasketches/filters/bloomfilter/DirectBitArrayRTest.java
+++ b/src/test/java/org/apache/datasketches/filters/bloomfilter/DirectBitArrayRTest.java
@@ -102,7 +102,7 @@ public class DirectBitArrayRTest {
@Test
public void countBitsWhenDirty() {
// like basicOperationTest but with setBit which does
- // not neecssarily track numBitsSet_
+ // not necessarily track numBitsSet_
final HeapBitArray hba = new HeapBitArray(128);
assertFalse(hba.getAndSetBit(1));
assertFalse(hba.getAndSetBit(2));
@@ -122,7 +122,7 @@ public class DirectBitArrayRTest {
}
@Test
- public void bitAddresOutOfBoundsEmptyTest() {
+ public void bitAddressOutOfBoundsEmptyTest() {
final int numBits = 256;
final HeapBitArray hba = new HeapBitArray(numBits);
final Memory mem = bitArrayToMemory(hba);
@@ -133,7 +133,7 @@ public class DirectBitArrayRTest {
}
@Test
- public void bitAddresOutOfBoundsNonEmptyTest() {
+ public void bitAddressOutOfBoundsNonEmptyTest() {
final int numBits = 1024;
final HeapBitArray hba = new HeapBitArray(numBits);
for (int i = 0; i < numBits; i += numBits / 8) {
diff --git a/src/test/java/org/apache/datasketches/filters/bloomfilter/DirectBitArrayTest.java b/src/test/java/org/apache/datasketches/filters/bloomfilter/DirectBitArrayTest.java
index 55ac733c..2aa039a8 100644
--- a/src/test/java/org/apache/datasketches/filters/bloomfilter/DirectBitArrayTest.java
+++ b/src/test/java/org/apache/datasketches/filters/bloomfilter/DirectBitArrayTest.java
@@ -69,6 +69,14 @@ public class DirectBitArrayTest {
// no text of max size because the BitArray allows up to Integer.MAX_VALUE
+ @Test
+ public void initializeTooSmallTest() {
+ final byte[] bytes = new byte[128];
+ final WritableMemory wmem = WritableMemory.writableWrap(bytes);
+ assertThrows(SketchesArgumentException.class, () -> DirectBitArray.initialize(128 * 65, wmem));
+ assertThrows(SketchesArgumentException.class, () -> DirectBitArray.initialize(-5, wmem));
+ }
+
@Test
public void basicInitializeOperationsTest() {
final byte[] bytes = new byte[56];
@@ -189,6 +197,12 @@ public class DirectBitArrayTest {
assertEquals(dba.getNumBitsSet(), numBits - numSet);
assertFalse(dba.getBit(0));
+
+ // update to make dirty and invert again
+ dba.setBit(0);
+ dba.invert();
+ assertEquals(dba.getNumBitsSet(), numSet - 1);
+ assertFalse(dba.getBit(0));
}
@Test
diff --git a/src/test/java/org/apache/datasketches/filters/bloomfilter/HeapBitArrayTest.java b/src/test/java/org/apache/datasketches/filters/bloomfilter/HeapBitArrayTest.java
index 41682442..0e91788e 100644
--- a/src/test/java/org/apache/datasketches/filters/bloomfilter/HeapBitArrayTest.java
+++ b/src/test/java/org/apache/datasketches/filters/bloomfilter/HeapBitArrayTest.java
@@ -38,6 +38,10 @@ public class HeapBitArrayTest {
assertEquals(ba.getArrayLength(), 2);
assertEquals(ba.getNumBitsSet(), 0);
assertTrue(ba.isEmpty());
+
+ assertFalse(ba.hasMemory());
+ assertFalse(ba.isDirect());
+ assertFalse(ba.isReadOnly());
}
@Test(expectedExceptions = SketchesArgumentException.class)
@@ -70,6 +74,8 @@ public class HeapBitArrayTest {
ba.reset();
assertTrue(ba.isEmpty());
assertEquals(ba.getNumBitsSet(), 0);
+
+ assertTrue(String.valueOf(ba).length() > 0);
}
@Test
@@ -97,6 +103,12 @@ public class HeapBitArrayTest {
assertEquals(ba.getNumBitsSet(), numBits - numSet);
assertFalse(ba.getBit(0));
+
+ // update to make dirty and invert again
+ ba.setBit(0);
+ ba.invert();
+ assertEquals(ba.getNumBitsSet(), numSet - 1);
+ assertFalse(ba.getBit(0));
}
@Test(expectedExceptions = SketchesArgumentException.class)
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org