1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
package cuckoo
import (
"crypto/rand"
"io"
"math/bits"
"testing"
"github.com/stretchr/testify/assert"
)
func TestIndexAndFP(t *testing.T) {
data := []byte("seif")
bucketPow := uint(bits.TrailingZeros(1024))
i1, fp := getIndexAndFingerprint(data, bucketPow)
i2 := getAltIndex(fp, i1, bucketPow)
i11 := getAltIndex(fp, i2, bucketPow)
i22 := getAltIndex(fp, i11, bucketPow)
assert.EqualValues(t, i11, i1)
assert.EqualValues(t, i22, i2)
}
func TestCap(t *testing.T) {
const capacity = 10000
res := getNextPow2(uint64(capacity)) / bucketSize
assert.EqualValues(t, res, 4096)
}
func TestInsert(t *testing.T) {
const cap = 10000
filter := NewFilter(cap)
var hash [32]byte
io.ReadFull(rand.Reader, hash[:])
for i := 0; i < 100; i++ {
filter.Insert(hash[:])
}
assert.EqualValues(t, filter.Count(), 8)
}
func TestFilter_Lookup(t *testing.T) {
const cap = 10000
var (
m = make(map[[32]byte]struct{})
filter = NewFilter(cap)
hash [32]byte
)
for i := 0; i < cap; i++ {
io.ReadFull(rand.Reader, hash[:])
m[hash] = struct{}{}
filter.Insert(hash[:])
}
assert.EqualValues(t, len(m), 10000)
var lookFail int
for k := range m {
if !filter.Lookup(k[:]) {
lookFail++
}
}
assert.EqualValues(t, lookFail, 0)
}
func TestReset(t *testing.T) {
const cap = 10000
var (
filter = NewFilter(cap)
hash [32]byte
insertSuccess int
insertFails int
)
for i := 0; i < 10*cap; i++ {
io.ReadFull(rand.Reader, hash[:])
if filter.Insert(hash[:]) {
insertSuccess++
} else {
insertFails++
filter.Reset()
}
}
assert.EqualValues(t, insertSuccess, 99994)
assert.EqualValues(t, insertFails, 6)
}
func TestBucket_Reset(t *testing.T) {
var bkt bucket
for i := byte(0); i < bucketSize; i++ {
bkt[i] = fingerprint(i)
}
bkt.reset()
for _, val := range bkt {
assert.EqualValues(t, 0, val)
}
}
|
