-
Notifications
You must be signed in to change notification settings - Fork 51
/
urisearch.go
120 lines (98 loc) · 2.18 KB
/
urisearch.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
package urisearch
import (
"github.com/aporeto-inc/trireme-lib/policy"
)
type node struct {
children map[string]*node
verbs map[string]struct{}
leaf bool
data interface{}
}
// APICache represents an API cache.
type APICache struct {
root *node
}
// NewAPICache creates a new API cache
func NewAPICache(rules []*policy.HTTPRule) *APICache {
a := &APICache{
root: &node{},
}
empty := struct{}{}
for _, rule := range rules {
verbs := map[string]struct{}{}
for _, verb := range rule.Verbs {
verbs[verb] = empty
}
for _, uri := range rule.URIs {
insert(a.root, uri, verbs, rule.Scopes)
}
}
return a
}
// Find finds a URI in the cache and returns true and the data if found.
// If not found it returns false.
func (c *APICache) Find(verb, uri string) (bool, interface{}) {
return search(c.root, verb, uri)
}
// parse parses a URI and splits into prefix, suffix
func parse(s string) (string, string) {
if s == "/" {
return s, ""
}
for i := 1; i < len(s); i++ {
if s[i] == '/' {
return s[0:i], s[i:len(s)]
}
}
return s, ""
}
// insert adds an api to the api cache
func insert(n *node, api string, verbs map[string]struct{}, data interface{}) {
if len(api) == 0 {
n.data = data
n.leaf = true
n.verbs = verbs
return
}
prefix, suffix := parse(api)
// root node or terminal node
if prefix == "/" {
n.data = data
n.leaf = true
n.verbs = verbs
return
}
if n.children == nil {
n.children = map[string]*node{}
}
// If there is no child, add the new child.
next, ok := n.children[prefix]
if !ok {
next = &node{}
n.children[prefix] = next
}
insert(next, suffix, verbs, data)
}
func search(n *node, verb string, api string) (found bool, data interface{}) {
prefix, suffix := parse(api)
if prefix == "/" {
if n.leaf {
_, matched := n.verbs[verb]
return matched, n.data
}
}
next, foundPrefix := n.children[prefix]
if !foundPrefix {
// If not found, try the star
next, foundPrefix = n.children["/*"]
}
// We found either an exact match or a * match
if foundPrefix {
return search(next, verb, suffix)
}
if n.leaf && len(prefix) == 0 {
_, matched := n.verbs[verb]
return matched, n.data
}
return false, nil
}