/
pit_matcher.go
112 lines (107 loc) · 2.31 KB
/
pit_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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
package ndn
import "github.com/NDNLink/lpm"
type pitMatcher struct{ pitNode }
type pitNode struct {
val *map[chan<- *Data]pitEntry
table map[string]*pitNode
}
func (n *pitNode) Empty() bool {
return n.val == nil && len(n.table) == 0
}
func pitDeref(val *map[chan<- *Data]pitEntry) (map[chan<- *Data]pitEntry, bool) {
if val == nil {
var t map[chan<- *Data]pitEntry
return t, false
}
return *val, true
}
func (n *pitNode) Match(key []lpm.Component) (val map[chan<- *Data]pitEntry, found bool) {
if len(key) == 0 {
return pitDeref(n.val)
}
if n.table == nil {
return pitDeref(n.val)
}
child, ok := n.table[string(key[0])]
if !ok {
return pitDeref(n.val)
}
return child.Match(key[1:])
}
func (n *pitNode) Get(key []lpm.Component) (val map[chan<- *Data]pitEntry, found bool) {
if len(key) == 0 {
return pitDeref(n.val)
}
if n.table == nil {
return pitDeref(nil)
}
child, ok := n.table[string(key[0])]
if !ok {
return pitDeref(nil)
}
return child.Get(key[1:])
}
func (n *pitNode) Update(key []lpm.Component, val map[chan<- *Data]pitEntry) {
if len(key) == 0 {
n.val = &val
return
}
if n.table == nil {
n.table = make(map[string]*pitNode)
}
if _, ok := n.table[string(key[0])]; !ok {
n.table[string(key[0])] = &pitNode{}
}
n.table[string(key[0])].Update(key[1:], val)
}
func (n *pitNode) Delete(key []lpm.Component) {
if len(key) == 0 {
n.val = nil
return
}
if n.table == nil {
return
}
child, ok := n.table[string(key[0])]
if !ok {
return
}
child.Delete(key[1:])
if child.Empty() {
delete(n.table, string(key[0]))
}
}
type pitUpdateFunc func([]lpm.Component, map[chan<- *Data]pitEntry) (val map[chan<- *Data]pitEntry, del bool)
func (n *pitNode) UpdateAll(key []lpm.Component, f pitUpdateFunc) {
for i := len(key); i > 0; i-- {
k := key[:i]
val, _ := n.Get(k)
val2, del := f(k, val)
if !del {
n.Update(k, val2)
} else {
n.Delete(k)
}
}
}
func (n *pitNode) visit(key []lpm.Component, f func([]lpm.Component)) {
for k, v := range n.table {
v.visit(append(key, lpm.Component(k)), f)
}
if n.val != nil {
f(key)
}
}
func (n *pitNode) Visit(f pitUpdateFunc) {
n.visit(make([]lpm.Component, 0, 16), func(k []lpm.Component) {
val, found := n.Get(k)
if found {
val2, del := f(k, val)
if !del {
n.Update(k, val2)
} else {
n.Delete(k)
}
}
})
}