ducky/devices

Paddy 2016-01-02 Parent:c24a6c5fcd8c

19:51ad0db105c8 Go to Latest

ducky/devices/vendor/code.secondbit.org/trout.hg/trie.go

Update trout to fix routing bug. Update to tip on trout to fix the routing bug that was causing us such issues. See the commit message of trout at 3df515f0cec5 for more details.

Download raw file
View source Diff to previous Annotate
History
paddy@15 1 package trout
paddy@15 2
paddy@15 3 import (
paddy@15 4 "net/http"
paddy@15 5 "sort"
paddy@15 6 "sync"
paddy@15 7 )
paddy@15 8
paddy@15 9 type trie struct {
paddy@15 10 branch *branch
paddy@15 11 sync.RWMutex
paddy@15 12 }
paddy@15 13
paddy@15 14 func (t *trie) match(input []string) ([]int, bool) {
paddy@15 15 if t.branch == nil {
paddy@15 16 t.branch = &branch{}
paddy@15 17 }
paddy@15 18 b := t.branch
paddy@15 19 path := []int{}
paddy@15 20 offset := 0
paddy@15 21 num := len(input)
paddy@15 22 for i := 0; i < num; i++ {
paddy@15 23 // if we're on a nil branch, we're at the end of our line
paddy@15 24 if b == nil {
paddy@15 25 return path, false
paddy@15 26 }
paddy@15 27 offset = pickNextBranch(b, offset, input[i])
paddy@15 28 if offset == -1 {
paddy@15 29 if len(path) == 0 {
paddy@15 30 // can't find it, bail
paddy@15 31 return path, false
paddy@15 32 }
paddy@15 33 // no match, backup
paddy@15 34 path, offset = backup(path)
paddy@15 35 offset = offset + 1 // we want the next index from the previously matched one
paddy@15 36 b = b.parent // we need to be picking a branch from our parent, again
paddy@15 37 i = i - 2 // back up to the choice before the one that got us here
paddy@15 38 } else {
paddy@15 39 path = append(path, offset)
paddy@15 40 b = b.children[offset]
paddy@15 41 offset = 0
paddy@15 42 }
paddy@15 43 }
paddy@15 44 return path, true
paddy@15 45 }
paddy@15 46
paddy@15 47 type branch struct {
paddy@15 48 parent *branch
paddy@15 49 children []*branch
paddy@15 50 key string
paddy@15 51 isParam bool
paddy@15 52 methods map[string]http.Handler
paddy@15 53 }
paddy@15 54
paddy@15 55 func (b *branch) Less(i, j int) bool {
paddy@15 56 if b.children[i].key == b.children[j].key {
paddy@15 57 return b.children[j].isParam && !b.children[i].isParam
paddy@15 58 }
paddy@15 59 return b.children[i].key < b.children[j].key
paddy@15 60 }
paddy@15 61
paddy@15 62 func (b *branch) Len() int {
paddy@15 63 return len(b.children)
paddy@15 64 }
paddy@15 65
paddy@15 66 func (b *branch) Swap(i, j int) {
paddy@15 67 b.children[i], b.children[j] = b.children[j], b.children[i]
paddy@15 68 }
paddy@15 69
paddy@15 70 func (b *branch) addChild(key string, param bool) *branch {
paddy@15 71 child := &branch{key: key, parent: b, isParam: param}
paddy@15 72 if b.children == nil {
paddy@15 73 b.children = []*branch{child}
paddy@15 74 return child
paddy@15 75 }
paddy@15 76 b.children = append(b.children, child)
paddy@15 77 sort.Sort(b)
paddy@15 78 return child
paddy@15 79 }
paddy@15 80
paddy@15 81 func (b *branch) check(input string) bool {
paddy@15 82 if b.isParam && b.key != "" {
paddy@15 83 return true
paddy@15 84 }
paddy@15 85 if b.key == input {
paddy@15 86 return true
paddy@15 87 }
paddy@15 88 return false
paddy@15 89 }
paddy@15 90
paddy@15 91 func (b *branch) setHandler(method string, handler http.Handler) {
paddy@15 92 if b.methods == nil {
paddy@15 93 b.methods = map[string]http.Handler{}
paddy@15 94 }
paddy@15 95 b.methods[method] = handler
paddy@15 96 }
paddy@15 97
paddy@15 98 func pickNextBranch(b *branch, offset int, input string) int {
paddy@15 99 count := len(b.children)
paddy@15 100 for i := offset; i < count; i++ {
paddy@15 101 if b.children[i].check(input) {
paddy@15 102 return i
paddy@15 103 }
paddy@15 104 }
paddy@15 105 return -1
paddy@15 106 }
paddy@15 107
paddy@15 108 func backup(path []int) ([]int, int) {
paddy@15 109 last := len(path) - 1
paddy@15 110 pos := path[last]
paddy@15 111 path = path[:last]
paddy@15 112 return path, pos
paddy@15 113 }