org.archive.util
Class BloomFilterTestBase

java.lang.Object
  junit.framework.Assert
      junit.framework.TestCase
          org.archive.util.BloomFilterTestBase

All Implemented Interfaces:

junit.framework.Test

public abstract class BloomFilterTestBase
extends junit.framework.TestCase

BloomFilter tests.

Version:

$Date: 2009-11-19 14:39:53 -0800 (Thu, 19 Nov 2009) $, $Revision: 6674 $

Constructor Summary

BloomFilterTestBase()

Method Summary

protected int	checkAdds(BloomFilter bloom, long count) Check that the given filter behaves properly as a large number of constructed unique strings are added: responding positively to contains, and negatively to redundant adds.
protected int	checkContains(BloomFilter bloom, long count) Check if the given filter contains any of the given constructed strings.
void	checkDistribution(BloomFilter bloom) Check that the given bloom filter, assumed to have already had a significant number of items added, has bits set in the lower and upper 10% of its bit field.
(package private) abstract BloomFilter	createBloom(long n, int d, java.util.Random random)
void	testSmall()
protected void	trialWithParameters(long targetSize, int hashCount, long addCount, long containsCount)
void	xestDefaultAbbreviated()
void	xestDefaultFull() Test large (495MB), default-sized bloom at saturation for expected behavior and level of false-positives.
void	xestOversized() Test very-large (almost 800MB, spanning more than Integer.MAX_VALUE bit indexes) bloom at saturation for expected behavior and level of false-positives.

Methods inherited from class junit.framework.TestCase

countTestCases, createResult, getName, run, run, runBare, runTest, setName, setUp, tearDown, toString

Methods inherited from class junit.framework.Assert

assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertFalse, assertFalse, assertNotNull, assertNotNull, assertNotSame, assertNotSame, assertNull, assertNull, assertSame, assertSame, assertTrue, assertTrue, fail, fail, failNotEquals, failNotSame, failSame

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

BloomFilterTestBase

public BloomFilterTestBase()

Method Detail

createBloom

abstract BloomFilter createBloom(long n,
                                 int d,
                                 java.util.Random random)

trialWithParameters

protected void trialWithParameters(long targetSize,
                                   int hashCount,
                                   long addCount,
                                   long containsCount)

xestOversized

public void xestOversized()

Test very-large (almost 800MB, spanning more than Integer.MAX_VALUE bit indexes) bloom at saturation for expected behavior and level of false-positives. Renamed to non-'test' name so not automatically run, because can take 15+ minutes to complete.

xestDefaultFull

public void xestDefaultFull()

Test large (495MB), default-sized bloom at saturation for expected behavior and level of false-positives. Renamed to non-'test' name so not automatically run, because can take 15+ minutes to complete.

xestDefaultAbbreviated

public void xestDefaultAbbreviated()

testSmall

public void testSmall()

checkAdds

protected int checkAdds(BloomFilter bloom,
                        long count)

Check that the given filter behaves properly as a large number of constructed unique strings are added: responding positively to contains, and negatively to redundant adds. Assuming that the filter was empty before it was called, any add()s that report the string was already present are false-positives; report the total of same so the caller can evaluate if that level was suspiciously out of the expected error rate.

Parameters:

bloom - BloomFilter to check

count - int number of unique strings to check

Returns:

checkContains

protected int checkContains(BloomFilter bloom,
                            long count)

Check if the given filter contains any of the given constructed strings. Since the previously-added strings (of checkAdds) were different from these, *any* positive contains results are false-positives. Return the total count so that the calling method can determine if the false-positive rate is outside the expected range.

Parameters:

bloom - BloomFilter to check

count - int number of unique strings to check

Returns:

checkDistribution

public void checkDistribution(BloomFilter bloom)

Check that the given bloom filter, assumed to have already had a significant number of items added, has bits set in the lower and upper 10% of its bit field. (This would have caught previous int/long bugs in the filter hashing or conversion of bit indexes into array indexes and bit masks.)

Parameters:

bloom - BloomFilter to check