-
Notifications
You must be signed in to change notification settings - Fork 4.6k
/
domain_matcher.go
88 lines (74 loc) · 1.55 KB
/
domain_matcher.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
package strmatcher
import "strings"
func breakDomain(domain string) []string {
return strings.Split(domain, ".")
}
type node struct {
value uint32
sub map[string]*node
}
// DomainMatcherGroup is a IndexMatcher for a large set of Domain matchers.
// Visible for testing only.
type DomainMatcherGroup struct {
root *node
}
func (g *DomainMatcherGroup) Add(domain string, value uint32) {
if g.root == nil {
g.root = new(node)
}
current := g.root
parts := breakDomain(domain)
for i := len(parts) - 1; i >= 0; i-- {
if current.value > 0 {
// if current node is already a match, it is not necessary to match further.
return
}
part := parts[i]
if current.sub == nil {
current.sub = make(map[string]*node)
}
next := current.sub[part]
if next == nil {
next = new(node)
current.sub[part] = next
}
current = next
}
current.value = value
current.sub = nil // shortcut sub nodes as current node is a match.
}
func (g *DomainMatcherGroup) addMatcher(m domainMatcher, value uint32) {
g.Add(string(m), value)
}
func (g *DomainMatcherGroup) Match(domain string) uint32 {
if len(domain) == 0 {
return 0
}
current := g.root
if current == nil {
return 0
}
nextPart := func(idx int) int {
for i := idx - 1; i >= 0; i-- {
if domain[i] == '.' {
return i
}
}
return -1
}
idx := len(domain)
for {
if idx == -1 || current.sub == nil {
break
}
nidx := nextPart(idx)
part := domain[nidx+1 : idx]
next := current.sub[part]
if next == nil {
break
}
current = next
idx = nidx
}
return current.value
}