ducky/devices

Paddy 2015-12-19 Parent:c24a6c5fcd8c

17:ad63b888f899 Go to Latest

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

Fix JSON pointers in errors when creating devices. Our JSON pointers used to point at the root of the document, but the properties were actually in objects in an array keyed off of "devices", so we had to update the field property of our errors to match. While we were in there, we fixed the "insufficient" error for a Device's name to be "missing" when the name is an empty string. So far, the only way for a Device's name for it to be insufficient is _for it to be the empty string_, but if in the future we raise the minimum length of the Device name, there will be a distinction and I'd like the code to recognise it.

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 }