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
105
106
|
package bloom
type key struct {
hashes []uint32
}
func keyvec(path []byte, settings *Settings) ([]key, error) {
if len(path) == 0 {
return nil, nil
}
count := 1
for _, b := range path {
if b == '/' {
count++
}
}
keys := make([]key, 0, count)
full, err := keyFill(path, settings)
if err != nil {
return nil, err
}
keys = append(keys, full)
for i := len(path) - 1; i >= 0; i-- {
if path[i] == '/' {
k, err := keyFill(path[:i], settings)
if err != nil {
return nil, err
}
keys = append(keys, k)
}
}
return keys, nil
}
func keyFill(path []byte, settings *Settings) (key, error) {
const (
seed0 = 0x293ae76f
seed1 = 0x7e646e2c
)
var (
h0 uint32
h1 uint32
err error
)
if settings.HashVersion == 2 { //nolint:nestif
h0, err = murmur3SeededV2(seed0, path)
if err != nil {
return key{}, err
}
h1, err = murmur3SeededV2(seed1, path)
if err != nil {
return key{}, err
}
} else {
h0, err = murmur3SeededV1(seed0, path)
if err != nil {
return key{}, err
}
h1, err = murmur3SeededV1(seed1, path)
if err != nil {
return key{}, err
}
}
hashes := make([]uint32, settings.NumHashes)
for i := range settings.NumHashes {
hashes[i] = h0 + i*h1
}
return key{hashes: hashes}, nil
}
func filterContainsKey(filter *Filter, key *key, settings *Settings) bool {
if filter == nil || key == nil || settings == nil {
return false
}
if len(filter.Data) == 0 {
return false
}
mod := uint64(len(filter.Data)) * 8
for _, h := range key.hashes {
idx := uint64(h) % mod
bytePos := idx / 8
bit := byte(1 << (idx & 7))
if filter.Data[bytePos]&bit == 0 {
return false
}
}
return true
}
|
