Join path and prefix
diff --git a/tree.go b/tree.go index af95bd4..64269e0 100644 --- a/tree.go +++ b/tree.go
@@ -6,7 +6,6 @@ import ( "strings" - "unicode" ) func min(a, b int) int { @@ -30,6 +29,13 @@ return uint8(n) } +func toLower(b byte) byte { + if 'A' <= b && b <= 'Z' { + b += 'a' - 'A' + } + return b +} + type nodeType uint8 const ( @@ -40,11 +46,10 @@ ) type node struct { - path string + pfx string // first len(children) byte are indices, other are prefix wildChild bool nType nodeType maxParams uint8 - indices string children []*node handle Handle priority uint32 @@ -68,9 +73,9 @@ // build new index char string if newPos != pos { - n.indices = n.indices[:newPos] + // unchanged prefix, might be empty - n.indices[pos:pos+1] + // the index char we move - n.indices[newPos:pos] + n.indices[pos+1:] // rest without char at 'pos' + n.pfx = n.pfx[:newPos] + // unchanged prefix, might be empty + n.pfx[pos:pos+1] + // the index char we move + n.pfx[newPos:pos] + n.pfx[pos+1:] // rest without char at 'pos' } return newPos @@ -84,7 +89,8 @@ numParams := countParams(path) // non-empty tree - if len(n.path) > 0 || len(n.children) > 0 { + if len(n.pfx) > 0 { + prefix := n.pfx[len(n.children):] walk: for { // Update maxParams of the current node @@ -96,17 +102,16 @@ // This also implies that the common prefix contains no ':' or '*' // since the existing key can't contain those chars. i := 0 - max := min(len(path), len(n.path)) - for i < max && path[i] == n.path[i] { + max := min(len(path), len(prefix)) + for i < max && path[i] == prefix[i] { i++ } // Split edge - if i < len(n.path) { + if i < len(prefix) { child := node{ - path: n.path[i:], + pfx: n.pfx[:len(n.children)] + prefix[i:], wildChild: n.wildChild, - indices: n.indices, children: n.children, handle: n.handle, priority: n.priority - 1, @@ -121,8 +126,7 @@ n.children = []*node{&child} // []byte for proper unicode char conversion, see #65 - n.indices = string([]byte{n.path[i]}) - n.path = path[:i] + n.pfx = string([]byte{prefix[i]}) + path[:i] n.handle = nil n.wildChild = false } @@ -134,6 +138,7 @@ if n.wildChild { n = n.children[0] n.priority++ + prefix = n.pfx[len(n.children):] // Update maxParams of the child node if numParams > n.maxParams { @@ -142,15 +147,15 @@ numParams-- // Check if the wildcard matches - if len(path) >= len(n.path) && n.path == path[:len(n.path)] { + if len(path) >= len(prefix) && prefix == path[:len(prefix)] { // check for longer wildcard, e.g. :name and :names - if len(n.path) >= len(path) || path[len(n.path)] == '/' { + if len(prefix) >= len(path) || path[len(prefix)] == '/' { continue walk } } panic("path segment '" + path + - "' conflicts with existing wildcard '" + n.path + + "' conflicts with existing wildcard '" + prefix + "' in path '" + fullPath + "'") } @@ -160,14 +165,16 @@ if n.nType == param && c == '/' && len(n.children) == 1 { n = n.children[0] n.priority++ + prefix = n.pfx[len(n.children):] continue walk } // Check if a child with the next path byte exists - for i := 0; i < len(n.indices); i++ { - if c == n.indices[i] { + for i := 0; i < len(n.children); i++ { + if c == n.pfx[i] { i = n.incrementChildPrio(i) n = n.children[i] + prefix = n.pfx[len(n.children):] continue walk } } @@ -175,12 +182,12 @@ // Otherwise insert it if c != ':' && c != '*' { // []byte for proper unicode char conversion, see #65 - n.indices += string([]byte{c}) + n.pfx = n.pfx[:len(n.children)] + string([]byte{c}) + n.pfx[len(n.children):] child := &node{ maxParams: numParams, } n.children = append(n.children, child) - n.incrementChildPrio(len(n.indices) - 1) + n.incrementChildPrio(len(n.children) - 1) n = child } n.insertChild(numParams, path, fullPath, handle) @@ -238,8 +245,10 @@ if c == ':' { // param // split path at the beginning of the wildcard if i > 0 { - n.path = path[offset:i] + n.pfx = ":" + path[offset:i] offset = i + } else { + n.pfx = ":" + n.pfx } child := &node{ @@ -255,7 +264,7 @@ // if the path doesn't end with the wildcard, then there // will be another non-wildcard subpath starting with '/' if end < max { - n.path = path[offset:end] + n.pfx = "/" + path[offset:end] offset = end child := &node{ @@ -271,7 +280,7 @@ panic("catch-all routes are only allowed at the end of the path in path '" + fullPath + "'") } - if len(n.path) > 0 && n.path[len(n.path)-1] == '/' { + if len(n.pfx)-len(n.children) > 0 && n.pfx[len(n.pfx)-1] == '/' { panic("catch-all conflicts with existing handle for the path segment root in path '" + fullPath + "'") } @@ -281,22 +290,22 @@ panic("no / before catch-all in path '" + fullPath + "'") } - n.path = path[offset:i] + n.pfx = string(path[i]) + path[offset:i] // first node: catchAll node with empty path child := &node{ + pfx: "/", wildChild: true, nType: catchAll, maxParams: 1, } n.children = []*node{child} - n.indices = string(path[i]) n = child n.priority++ // second node: node holding the variable child = &node{ - path: path[i:], + pfx: path[i:], nType: catchAll, maxParams: 1, handle: handle, @@ -309,7 +318,7 @@ } // insert remaining path part and handle to the leaf - n.path = path[offset:] + n.pfx = n.pfx[:len(n.children)] + path[offset:] n.handle = handle } @@ -321,16 +330,18 @@ func (n *node) getValue(path string) (handle Handle, p Params, tsr bool) { walk: // Outer loop for walking the tree for { - if len(path) > len(n.path) { - if path[:len(n.path)] == n.path { - path = path[len(n.path):] + prefix := n.pfx[len(n.children):] + + if len(path) > len(prefix) { + if path[:len(prefix)] == prefix { + path = path[len(prefix):] // If this node does not have a wildcard (param or catchAll) - // child, we can just look up the next child node and continue + // child, we can just look up the next child node and continue // to walk down the tree if !n.wildChild { c := path[0] - for i := 0; i < len(n.indices); i++ { - if c == n.indices[i] { + for i := 0; i < len(n.children); i++ { // TODO: cache max? + if c == n.pfx[i] { // TODO: cache indices? n = n.children[i] continue walk } @@ -361,7 +372,7 @@ } i := len(p) p = p[:i+1] // expand slice within preallocated capacity - p[i].Key = n.path[1:] + p[i].Key = n.pfx[len(n.children)+1:] p[i].Value = path[:end] // we need to go deeper! @@ -383,7 +394,7 @@ // No handle found. Check if a handle for this path + a // trailing slash exists for TSR recommendation n = n.children[0] - tsr = (n.path == "/" && n.handle != nil) + tsr = (n.handle != nil && n.pfx[len(n.children):] == "/") } return @@ -396,7 +407,7 @@ } i := len(p) p = p[:i+1] // expand slice within preallocated capacity - p[i].Key = n.path[2:] + p[i].Key = n.pfx[2:] p[i].Value = path handle = n.handle @@ -406,7 +417,7 @@ panic("invalid node type") } } - } else if path == n.path { + } else if path == prefix { // We should have reached the node containing the handle. // Check if this node has a handle registered. if handle = n.handle; handle != nil { @@ -420,10 +431,10 @@ // No handle found. Check if a handle for this path + a // trailing slash exists for trailing slash recommendation - for i := 0; i < len(n.indices); i++ { - if n.indices[i] == '/' { + for i := 0; i < len(n.children); i++ { + if n.pfx[i] == '/' { n = n.children[i] - tsr = (len(n.path) == 1 && n.handle != nil) || + tsr = (len(n.pfx)-len(n.children) == 1 && n.handle != nil) || (n.nType == catchAll && n.children[0].handle != nil) return } @@ -435,8 +446,8 @@ // Nothing found. We can recommend to redirect to the same URL with an // extra trailing slash if a leaf exists for that path tsr = (path == "/") || - (len(n.path) == len(path)+1 && n.path[len(path)] == '/' && - path == n.path[:len(n.path)-1] && n.handle != nil) + (len(prefix) == len(path)+1 && prefix[len(path)] == '/' && + path == prefix[:len(prefix)-1] && n.handle != nil) return } } @@ -447,22 +458,23 @@ // was successful. func (n *node) findCaseInsensitivePath(path string, fixTrailingSlash bool) (ciPath []byte, found bool) { ciPath = make([]byte, 0, len(path)+1) // preallocate enough memory + prefix := n.pfx[len(n.children):] // Outer loop for walking the tree - for len(path) >= len(n.path) && strings.ToLower(path[:len(n.path)]) == strings.ToLower(n.path) { - path = path[len(n.path):] - ciPath = append(ciPath, n.path...) + for len(path) >= len(prefix) && strings.ToLower(path[:len(prefix)]) == strings.ToLower(prefix) { + path = path[len(prefix):] + ciPath = append(ciPath, prefix...) if len(path) > 0 { // If this node does not have a wildcard (param or catchAll) child, // we can just look up the next child node and continue to walk down // the tree if !n.wildChild { - r := unicode.ToLower(rune(path[0])) - for i, index := range n.indices { - // must use recursive approach since both index and - // ToLower(index) could exist. We must check both. - if r == unicode.ToLower(index) { + c := toLower(path[0]) + for i := 0; i < len(n.children); i++ { + if c == toLower(n.pfx[i]) { + // must use recursive approach since both index and + // ToLower(index) could exist. We must check both. out, found := n.children[i].findCaseInsensitivePath(path, fixTrailingSlash) if found { return append(ciPath, out...), true @@ -493,6 +505,7 @@ if len(n.children) > 0 { path = path[k:] n = n.children[0] + prefix = n.pfx[len(n.children):] continue } @@ -509,7 +522,7 @@ // No handle found. Check if a handle for this path + a // trailing slash exists n = n.children[0] - if n.path == "/" && n.handle != nil { + if n.pfx[len(n.children):] == "/" && n.handle != nil { return append(ciPath, '/'), true } } @@ -531,10 +544,10 @@ // No handle found. // Try to fix the path by adding a trailing slash if fixTrailingSlash { - for i := 0; i < len(n.indices); i++ { - if n.indices[i] == '/' { + for i := 0; i < len(n.children); i++ { + if n.pfx[i] == '/' { n = n.children[i] - if (len(n.path) == 1 && n.handle != nil) || + if (len(n.pfx)-len(n.children) == 1 && n.handle != nil) || (n.nType == catchAll && n.children[0].handle != nil) { return append(ciPath, '/'), true } @@ -552,10 +565,10 @@ if path == "/" { return ciPath, true } - if len(path)+1 == len(n.path) && n.path[len(path)] == '/' && - strings.ToLower(path) == strings.ToLower(n.path[:len(path)]) && + if len(path)+1 == len(prefix) && prefix[len(path)] == '/' && + strings.ToLower(path) == strings.ToLower(prefix[:len(path)]) && n.handle != nil { - return append(ciPath, n.path...), true + return append(ciPath, prefix...), true } } return
diff --git a/tree_test.go b/tree_test.go index 46d3299..84ecda6 100644 --- a/tree_test.go +++ b/tree_test.go
@@ -13,8 +13,10 @@ ) func printChildren(n *node, prefix string) { - fmt.Printf(" %02d:%02d %s%s[%d] %v %t %d \r\n", n.priority, n.maxParams, prefix, n.path, len(n.children), n.handle, n.wildChild, n.nType) - for l := len(n.path); l > 0; l-- { + indices := n.pfx[:len(n.children)] + path := n.pfx[len(n.children):] + fmt.Printf(" %02d:%02d %s%s [%d:%s] %v %t %d \r\n", n.priority, n.maxParams, prefix, path, len(n.children), indices, n.handle, n.wildChild, n.nType) + for l := len(path); l > 0; l-- { prefix += " " } for _, child := range n.children { @@ -74,7 +76,7 @@ if n.priority != prio { t.Errorf( "priority mismatch for node '%s': is %d, should be %d", - n.path, n.priority, prio, + n.pfx[:len(n.children)], n.priority, prio, ) } @@ -96,7 +98,7 @@ if n.maxParams != maxParams { t.Errorf( "maxParams mismatch for node '%s': is %d, should be %d", - n.path, n.maxParams, maxParams, + n.pfx[:len(n.children)], n.maxParams, maxParams, ) }