1
2
3
4
5
6
7 package filter
8
9 import (
10 "encoding/binary"
11 "github.com/syndtr/goleveldb/leveldb/util"
12 "testing"
13 )
14
15 type harness struct {
16 t *testing.T
17
18 bloom Filter
19 generator FilterGenerator
20 filter []byte
21 }
22
23 func newHarness(t *testing.T) *harness {
24 bloom := NewBloomFilter(10)
25 return &harness{
26 t: t,
27 bloom: bloom,
28 generator: bloom.NewGenerator(),
29 }
30 }
31
32 func (h *harness) add(key []byte) {
33 h.generator.Add(key)
34 }
35
36 func (h *harness) addNum(key uint32) {
37 var b [4]byte
38 binary.LittleEndian.PutUint32(b[:], key)
39 h.add(b[:])
40 }
41
42 func (h *harness) build() {
43 b := &util.Buffer{}
44 h.generator.Generate(b)
45 h.filter = b.Bytes()
46 }
47
48 func (h *harness) reset() {
49 h.filter = nil
50 }
51
52 func (h *harness) filterLen() int {
53 return len(h.filter)
54 }
55
56 func (h *harness) assert(key []byte, want, silent bool) bool {
57 got := h.bloom.Contains(h.filter, key)
58 if !silent && got != want {
59 h.t.Errorf("assert on '%v' failed got '%v', want '%v'", key, got, want)
60 }
61 return got
62 }
63
64 func (h *harness) assertNum(key uint32, want, silent bool) bool {
65 var b [4]byte
66 binary.LittleEndian.PutUint32(b[:], key)
67 return h.assert(b[:], want, silent)
68 }
69
70 func TestBloomFilter_Empty(t *testing.T) {
71 h := newHarness(t)
72 h.build()
73 h.assert([]byte("hello"), false, false)
74 h.assert([]byte("world"), false, false)
75 }
76
77 func TestBloomFilter_Small(t *testing.T) {
78 h := newHarness(t)
79 h.add([]byte("hello"))
80 h.add([]byte("world"))
81 h.build()
82 h.assert([]byte("hello"), true, false)
83 h.assert([]byte("world"), true, false)
84 h.assert([]byte("x"), false, false)
85 h.assert([]byte("foo"), false, false)
86 }
87
88 func nextN(n int) int {
89 switch {
90 case n < 10:
91 n += 1
92 case n < 100:
93 n += 10
94 case n < 1000:
95 n += 100
96 default:
97 n += 1000
98 }
99 return n
100 }
101
102 func TestBloomFilter_VaryingLengths(t *testing.T) {
103 h := newHarness(t)
104 var mediocre, good int
105 for n := 1; n < 10000; n = nextN(n) {
106 h.reset()
107 for i := 0; i < n; i++ {
108 h.addNum(uint32(i))
109 }
110 h.build()
111
112 got := h.filterLen()
113 want := (n * 10 / 8) + 40
114 if got > want {
115 t.Errorf("filter len test failed, '%d' > '%d'", got, want)
116 }
117
118 for i := 0; i < n; i++ {
119 h.assertNum(uint32(i), true, false)
120 }
121
122 var rate float32
123 for i := 0; i < 10000; i++ {
124 if h.assertNum(uint32(i+1000000000), true, true) {
125 rate++
126 }
127 }
128 rate /= 10000
129 if rate > 0.02 {
130 t.Errorf("false positive rate is more than 2%%, got %v, at len %d", rate, n)
131 }
132 if rate > 0.0125 {
133 mediocre++
134 } else {
135 good++
136 }
137 }
138 t.Logf("false positive rate: %d good, %d mediocre", good, mediocre)
139 if mediocre > good/5 {
140 t.Error("mediocre false positive rate is more than expected")
141 }
142 }
143
View as plain text