bloom_test.go 2.8 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394
  1. // bloom_test.go - Bloom filter tests.
  2. // Written in 2017 by Yawning Angel
  3. //
  4. // To the extent possible under law, the author(s) have dedicated all copyright
  5. // and related and neighboring rights to this software to the public domain
  6. // worldwide. This software is distributed without any warranty.
  7. //
  8. // You should have received a copy of the CC0 Public Domain Dedication along
  9. // with this software. If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.
  10. package bloom
  11. import (
  12. "crypto/rand"
  13. "testing"
  14. "github.com/stretchr/testify/assert"
  15. "github.com/stretchr/testify/require"
  16. )
  17. func TestFilter(t *testing.T) {
  18. const (
  19. entryLength = 32
  20. falsePositiveRate = 0.01
  21. filterSize = 15 // 2^15 bits = 4 KiB
  22. expectedEntries = 3418
  23. expectedHashes = 7
  24. )
  25. assert := assert.New(t)
  26. require := require.New(t)
  27. // 4 KiB filter, 0.01 false positive rate.
  28. f, err := New(rand.Reader, filterSize, falsePositiveRate)
  29. require.NoError(err, "New()")
  30. assert.Equal(0, f.Entries(), "Entries(), empty filter")
  31. assert.Equal(4096, len(f.b), "Backing store size")
  32. // Assert that the bloom filter math is correct.
  33. assert.Equal(expectedEntries, f.MaxEntries(), "Max entries")
  34. assert.Equal(expectedHashes, f.nrHashes, "Hashes")
  35. assert.Equal(filterSize, DeriveSize(f.MaxEntries(), falsePositiveRate), "DeriveSize()")
  36. // Generate enough entries to fully saturate the filter.
  37. max := f.MaxEntries()
  38. entries := make(map[[entryLength]byte]bool)
  39. for count := 0; count < max; {
  40. var ent [entryLength]byte
  41. rand.Read(ent[:])
  42. // This needs to ignore false positives.
  43. if !f.TestAndSet(ent[:]) {
  44. entries[ent] = true
  45. count++
  46. }
  47. }
  48. assert.Equal(max, f.Entries(), "After populating")
  49. // Ensure that all the entries are present in the filter.
  50. idx := 0
  51. for ent := range entries {
  52. assert.True(f.Test(ent[:]), "Test(ent #: %v)", idx)
  53. assert.True(f.TestAndSet(ent[:]), "TestAndSet(ent #: %v)", idx)
  54. idx++
  55. }
  56. // Test the false positive rate, by generating another set of entries
  57. // NOT in the filter, and counting the false positives.
  58. //
  59. // This may have suprious failures once in a blue moon because the
  60. // algorithm is probabalistic, but that's *exceedingly* unlikely with
  61. // the chosen delta.
  62. randomEntries := make(map[[entryLength]byte]bool)
  63. for count := 0; count < max; {
  64. var ent [entryLength]byte
  65. rand.Read(ent[:])
  66. if !entries[ent] && !randomEntries[ent] {
  67. randomEntries[ent] = true
  68. count++
  69. }
  70. }
  71. falsePositives := 0
  72. for ent := range randomEntries {
  73. if f.Test(ent[:]) {
  74. falsePositives++
  75. }
  76. }
  77. observedP := float64(falsePositives) / float64(max)
  78. t.Logf("Observed False Positive Rate: %v", observedP)
  79. assert.InDelta(falsePositiveRate, observedP, 0.02, "False positive rate")
  80. assert.Equal(max, f.Entries(), "After tests") // Should still be = max.
  81. }