-
Notifications
You must be signed in to change notification settings - Fork 10
/
bloom.go
92 lines (71 loc) · 1.6 KB
/
bloom.go
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
package bloom
import (
"context"
"fmt"
"github.com/spaolacci/murmur3"
)
const defaultMaps = 14
type Option func(opt *FilterOption)
type FilterOption struct {
Context context.Context
}
func WithContext(ctx context.Context) Option {
return func(opt *FilterOption) {
opt.Context = ctx
}
}
func NewFilterOptions(opts ...Option) *FilterOption {
fo := &FilterOption{Context: context.Background()}
for _, opt := range opts {
opt(fo)
}
return fo
}
type BloomFilterConfig struct {
BitSet BitSet
Key string
Bits int
Maps int
}
func New(config BloomFilterConfig) (*BloomFilter, error) {
if config.Bits <= 0 {
return nil, fmt.Errorf("bits must great than zero")
}
if config.Maps <= 0 {
config.Maps = defaultMaps
}
if config.BitSet == nil {
config.BitSet = newBitSet(config.Bits)
}
return &BloomFilter{
BloomFilterConfig: config,
}, nil
}
type BloomFilter struct {
BloomFilterConfig
}
func (f *BloomFilter) Reset(opts ...Option) error {
return f.BitSet.Reset(opts...)
}
func (f *BloomFilter) Add(data []byte, opts ...Option) error {
if len(data) == 0 {
return nil
}
locations := f.getLocations(data)
return f.BitSet.Add(locations, opts...)
}
func (f *BloomFilter) Exists(data []byte, opts ...Option) (bool, error) {
if len(data) == 0 {
return false, nil
}
locations := f.getLocations(data)
return f.BitSet.Exists(locations, opts...)
}
func (f *BloomFilter) getLocations(data []byte) []int {
locations := make([]int, f.Maps)
for i := 0; i < int(f.Maps); i++ {
val := murmur3.Sum64(append(data, byte(i)))
locations[i] = int(val % uint64(f.Bits))
}
return locations
}