trout

Paddy 2015-03-16 Child:bf38b050b6c4

0:6c6ea726570a Go to Latest

trout/trie.go

First pass at a router library. First pass at a router library and, incidentally, implementing a trie. I could probably optimise the search for the right branch somehow, but I honestly just can't be bothered right now. I also haven't tested this at all or even tried to run it, so who knows if my code even works. But it compiles, go vet and golint have found nothing to complain about, it has documentation, and it's properly formatted. So it's already better than most software out there. </ba dump tiss>

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