-
Notifications
You must be signed in to change notification settings - Fork 16
/
matcher_suffix.go
130 lines (106 loc) · 3.42 KB
/
matcher_suffix.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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
package domainset
import "github.com/database64128/shadowsocks-go/maphelper"
// MaxLinearSuffixes is the maximum number of suffix rules under which a linear matcher can outperform a trie matcher.
const MaxLinearSuffixes = 4
// SuffixLinearMatcher matches suffix rules by iterating over the suffixes.
// It is faster than [SuffixTrieMatcher] when the number of rules is
// no greater than [MaxLinearSuffixes].
type SuffixLinearMatcher []string
// NewSuffixLinearMatcher creates a [SuffixLinearMatcher] with the specified initial capacity.
func NewSuffixLinearMatcher(capacity int) MatcherBuilder {
slm := make(SuffixLinearMatcher, 0, capacity)
return &slm
}
// Match implements the Matcher Match method.
func (slm SuffixLinearMatcher) Match(domain string) bool {
for _, suffix := range slm {
if matchDomainSuffix(domain, suffix) {
return true
}
}
return false
}
// Insert implements the MatcherBuilder Insert method.
func (slmp *SuffixLinearMatcher) Insert(rule string) {
*slmp = append(*slmp, rule)
}
// Rules implements the MatcherBuilder Rules method.
func (slm SuffixLinearMatcher) Rules() []string {
return slm
}
// MatcherCount implements the MatcherBuilder MatcherCount method.
func (slm SuffixLinearMatcher) MatcherCount() int {
if len(slm) == 0 {
return 0
}
return 1
}
// AppendTo implements the MatcherBuilder AppendTo method.
func (slmp *SuffixLinearMatcher) AppendTo(matchers []Matcher) ([]Matcher, error) {
slm := *slmp
if len(slm) == 0 {
return matchers, nil
}
if len(slm) > MaxLinearSuffixes {
return append(matchers, DomainSuffixTrieFromSlice(slm)), nil
}
return append(matchers, slmp), nil
}
func matchDomainSuffix(domain, suffix string) bool {
return domain == suffix || len(domain) > len(suffix) && domain[len(domain)-len(suffix)-1] == '.' && domain[len(domain)-len(suffix):] == suffix
}
// SuffixMapMatcher matches suffix rules using a single map.
type SuffixMapMatcher map[string]struct{}
// NewSuffixMapMatcher creates a [SuffixMapMatcher] with the specified initial capacity.
func NewSuffixMapMatcher(capacity int) MatcherBuilder {
smm := make(SuffixMapMatcher, capacity)
return &smm
}
// SuffixMapMatcherFromSlice creates a [SuffixMapMatcher] from a slice of suffix rules.
func SuffixMapMatcherFromSlice(suffixes []string) SuffixMapMatcher {
smm := make(SuffixMapMatcher, len(suffixes))
for _, suffix := range suffixes {
smm.Insert(suffix)
}
return smm
}
// Match implements the Matcher Match method.
func (smm SuffixMapMatcher) Match(domain string) bool {
for i := len(domain) - 1; i >= 0; i-- {
if domain[i] != '.' {
continue
}
if _, ok := smm[domain[i+1:]]; ok {
return true
}
}
_, ok := smm[domain]
return ok
}
// Insert implements the MatcherBuilder Insert method.
func (smm SuffixMapMatcher) Insert(rule string) {
smm[rule] = struct{}{}
}
// Rules implements the MatcherBuilder Rules method.
func (smm SuffixMapMatcher) Rules() []string {
return maphelper.Keys(smm)
}
// MatcherCount implements the MatcherBuilder MatcherCount method.
func (smm SuffixMapMatcher) MatcherCount() int {
if len(smm) == 0 {
return 0
}
return 1
}
// AppendTo implements the MatcherBuilder AppendTo method.
func (smmp *SuffixMapMatcher) AppendTo(matchers []Matcher) ([]Matcher, error) {
smm := *smmp
if len(smm) == 0 {
return matchers, nil
}
if len(smm) <= MaxLinearSuffixes {
slm := SuffixLinearMatcher(maphelper.Keys(smm))
return slm.AppendTo(matchers)
}
return append(matchers, smmp), nil
}