commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From aherb...@apache.org
Subject [commons-collections] 01/20: Increase HasherBloomFilter test coverage.
Date Sat, 14 Mar 2020 14:21:44 GMT
This is an automated email from the ASF dual-hosted git repository.

aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-collections.git

commit c18cd7b86ef088d0591b395b71fc1d521148b5c2
Author: Alex Herbert <aherbert@apache.org>
AuthorDate: Mon Mar 9 22:07:09 2020 +0000

    Increase HasherBloomFilter test coverage.
    
    Coverage cannot reach 100% because assert statements have been included
    that test assumptions. These asserts are unreachable if the StaticHasher
    functions as expected and returns an iterator with at least 1 value when
    it reports a non-zero size.
---
 .../bloomfilter/HasherBloomFilter.java             | 26 ++++++++++----
 .../bloomfilter/HasherBloomFilterTest.java         | 42 ++++++++++++++++++++++
 2 files changed, 62 insertions(+), 6 deletions(-)

diff --git a/src/main/java/org/apache/commons/collections4/bloomfilter/HasherBloomFilter.java
b/src/main/java/org/apache/commons/collections4/bloomfilter/HasherBloomFilter.java
index e6436a8..3a5ab71 100644
--- a/src/main/java/org/apache/commons/collections4/bloomfilter/HasherBloomFilter.java
+++ b/src/main/java/org/apache/commons/collections4/bloomfilter/HasherBloomFilter.java
@@ -36,6 +36,8 @@ import org.apache.commons.collections4.iterators.IteratorChain;
  * @since 4.5
  */
 public class HasherBloomFilter extends AbstractBloomFilter {
+    /** The bit representation for an empty Bloom filter. */
+    private static final long[] EMPTY = new long[0];
 
     /**
      * The internal hasher representation.
@@ -95,9 +97,17 @@ public class HasherBloomFilter extends AbstractBloomFilter {
     @Override
     public long[] getBits() {
         if (hasher.size() == 0) {
-            return new long[0];
+            return EMPTY;
         }
-        final int n = (int) Math.ceil(hasher.getShape().getNumberOfBits() * 1.0 / Long.SIZE);
+
+        // Note: This can be simplified if the StaticHasher exposed a getMaxIndex()
+        // method. Since it maintains an ordered list of unique indices the maximum
+        // is the last value in the iterator. Knowing this value would allow
+        // exact allocation of the long[].
+        // For now we assume that the long[] will have a positive length and at least
+        // 1 bit set in the entire array.
+
+        final int n = (int) Math.ceil(hasher.getShape().getNumberOfBits() * (1.0 / Long.SIZE));
         final long[] result = new long[n];
         final OfInt iter = hasher.getBits(hasher.getShape());
         iter.forEachRemaining((IntConsumer) idx -> {
@@ -108,11 +118,15 @@ public class HasherBloomFilter extends AbstractBloomFilter {
         });
 
         int limit = result.length;
-        while (limit > 0 && result[limit - 1] == 0) {
+
+        // Assume the array has a non-zero length and at least 1 bit set.
+        // This is tested using assertions.
+        assert limit > 0 : "Number of bits in Shape is 0";
+        while (result[limit - 1] == 0) {
             limit--;
-        }
-        if (limit == 0) {
-            return new long[0];
+            // If the hasher was not empty it is not possible to return
+            // an array of length zero.
+            assert limit > 0 : "Hasher reported a non-zero size but has no indices";
         }
         if (limit < result.length) {
             return Arrays.copyOf(result, limit);
diff --git a/src/test/java/org/apache/commons/collections4/bloomfilter/HasherBloomFilterTest.java
b/src/test/java/org/apache/commons/collections4/bloomfilter/HasherBloomFilterTest.java
index a2ddd6f..b46fda3 100644
--- a/src/test/java/org/apache/commons/collections4/bloomfilter/HasherBloomFilterTest.java
+++ b/src/test/java/org/apache/commons/collections4/bloomfilter/HasherBloomFilterTest.java
@@ -19,11 +19,16 @@ package org.apache.commons.collections4.bloomfilter;
 import static org.junit.Assert.assertEquals;
 
 import org.apache.commons.collections4.bloomfilter.hasher.DynamicHasher;
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunctionIdentity;
 import org.apache.commons.collections4.bloomfilter.hasher.Hasher;
 import org.apache.commons.collections4.bloomfilter.hasher.Shape;
 import org.apache.commons.collections4.bloomfilter.hasher.function.MD5Cyclic;
+import org.junit.Assert;
 import org.junit.Test;
 
+import java.util.Arrays;
+import java.util.PrimitiveIterator.OfInt;
+
 /**
  * Tests the {@link HasherBloomFilter}.
  */
@@ -52,4 +57,41 @@ public class HasherBloomFilterTest extends AbstractBloomFilterTest {
     protected HasherBloomFilter createFilter(final Hasher hasher, final Shape shape) {
         return new HasherBloomFilter(hasher, shape);
     }
+
+    /**
+     * Test the edge case where the filter is empty and the getBits() function returns a
+     * zero length array.
+     */
+    @Test
+    public void getBitsTest_Empty() {
+        BloomFilter filter = createEmptyFilter(shape);
+        Assert.assertArrayEquals(new long[0], filter.getBits());
+    }
+
+    /**
+     * Test the edge case where the filter has only 1 bit in the lowest index and the getBits()
+     * function returns an array of length 1.
+     */
+    @Test
+    public void getBitsTest_LowestBitOnly() {
+        BloomFilter filter = createEmptyFilter(shape);
+        // Set the lowest bit index only.
+        filter.merge(new Hasher() {
+            @Override
+            public OfInt getBits(Shape shape) {
+                return Arrays.stream(new int[] {0}).iterator();
+            }
+
+            @Override
+            public HashFunctionIdentity getHashFunctionIdentity() {
+                return shape.getHashFunctionIdentity();
+            }
+
+            @Override
+            public boolean isEmpty() {
+                return false;
+            }
+        });
+        Assert.assertArrayEquals(new long[] {1L}, filter.getBits());
+    }
 }


Mime
View raw message