Save indices and path prefix in one string
diff --git a/tree.go b/tree.go
index d768e04..f248a57 100644
--- a/tree.go
+++ b/tree.go
@@ -4,10 +4,7 @@
package httprouter
-import (
- "strings"
- "unicode"
-)
+import "strings"
func min(a, b int) int {
if a <= b {
@@ -30,6 +27,13 @@
return uint8(n)
}
+func toLower(b byte) byte {
+ if 'A' <= b && b <= 'Z' {
+ b += 'a' - 'A'
+ }
+ return b
+}
+
type nodeType uint8
const (
@@ -39,14 +43,13 @@
)
type node struct {
- prefix string
+ pfx string // first len(children) bytes are indices, rest is path prefix
wildChild bool
nType nodeType
maxParams uint8
- indices string
+ priority uint32
children []*node
handle Handle
- priority uint32
}
// increments priority of the given child and reorders if necessary
@@ -67,9 +70,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
@@ -83,7 +86,8 @@
numParams := countParams(path)
// non-empty tree
- if len(n.prefix) > 0 || len(n.children) > 0 {
+ if len(n.pfx) > 0 {
+ prefix := n.pfx[len(n.children):]
walk:
for {
// Update maxParams of the current node
@@ -95,17 +99,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.prefix))
- for i < max && path[i] == n.prefix[i] {
+ max := min(len(path), len(prefix))
+ for i < max && path[i] == prefix[i] {
i++
}
// Split edge
- if i < len(n.prefix) {
+ if i < len(prefix) {
child := node{
- prefix: n.prefix[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,
@@ -120,8 +123,7 @@
n.children = []*node{&child}
// []byte for proper unicode char conversion, see #65
- n.indices = string([]byte{n.prefix[i]})
- n.prefix = path[:i]
+ n.pfx = string([]byte{prefix[i]}) + path[:i]
n.handle = nil
n.wildChild = false
}
@@ -133,6 +135,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 {
@@ -141,15 +144,15 @@
numParams--
// Check if the wildcard matches
- if len(path) >= len(n.prefix) && n.prefix == path[:len(n.prefix)] {
+ if len(path) >= len(prefix) && prefix == path[:len(prefix)] {
// check for longer wildcard, e.g. :name and :names
- if len(n.prefix) >= len(path) || path[len(n.prefix)] == '/' {
+ if len(prefix) >= len(path) || path[len(prefix)] == '/' {
continue walk
}
}
panic("path segment '" + path +
- "' conflicts with existing wildcard '" + n.prefix +
+ "' conflicts with existing wildcard '" + prefix +
"' in path '" + fullPath + "'")
}
@@ -159,14 +162,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
}
}
@@ -174,12 +179,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)
@@ -236,8 +241,10 @@
if c == ':' { // param
// split path at the beginning of the wildcard
if i > 0 {
- n.prefix = path[offset:i]
+ n.pfx = ":" + path[offset:i]
offset = i
+ } else {
+ n.pfx = ":" + n.pfx
}
child := &node{
@@ -253,7 +260,7 @@
// if the path doesn't end with the wildcard, then there
// will be another non-wildcard subpath starting with '/'
if end < max {
- n.prefix = path[offset:end]
+ n.pfx = "/" + path[offset:end]
offset = end
child := &node{
@@ -269,7 +276,7 @@
panic("catch-all routes are only allowed at the end of the path in path '" + fullPath + "'")
}
- if len(n.prefix) > 0 && n.prefix[len(n.prefix)-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 + "'")
}
@@ -279,22 +286,22 @@
panic("no / before catch-all in path '" + fullPath + "'")
}
- n.prefix = 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{
- prefix: path[i:],
+ pfx: path[i:],
nType: catchAll,
maxParams: 1,
handle: handle,
@@ -307,7 +314,7 @@
}
// insert remaining path part and handle to the leaf
- n.prefix = path[offset:]
+ n.pfx = n.pfx[:len(n.children)] + path[offset:]
n.handle = handle
}
@@ -319,16 +326,19 @@
func (n *node) getValue(path string, psp *Params) (handle Handle, tsr bool) {
walk: // Outer loop for walking the tree
for {
- if len(path) > len(n.prefix) {
- if path[:len(n.prefix)] == n.prefix {
- path = path[len(n.prefix):]
+ 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
// 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++ {
+ if c == n.pfx[i] {
n = n.children[i]
continue walk
}
@@ -356,7 +366,7 @@
if psp != nil {
i := len(*psp)
*psp = (*psp)[:i+1] // expand slice within preallocated capacity
- (*psp)[i].Key = n.prefix[1:]
+ (*psp)[i].Key = n.pfx[len(n.children)+1:]
(*psp)[i].Value = path[:end]
}
@@ -379,7 +389,7 @@
// No handle found. Check if a handle for this path + a
// trailing slash exists for TSR recommendation
n = n.children[0]
- tsr = (n.prefix == "/" && n.handle != nil)
+ tsr = (n.handle != nil && n.pfx[len(n.children):] == "/")
}
return
@@ -389,7 +399,7 @@
if psp != nil {
i := len(*psp)
*psp = (*psp)[:i+1] // expand slice within preallocated capacity
- (*psp)[i].Key = n.prefix[2:]
+ (*psp)[i].Key = n.pfx[2:]
(*psp)[i].Value = path
}
@@ -400,7 +410,7 @@
panic("invalid node type")
}
}
- } else if path == n.prefix {
+ } 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 {
@@ -409,10 +419,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.prefix) == 1 && n.handle != nil) ||
+ tsr = (len(n.pfx)-len(n.children) == 1 && n.handle != nil) ||
(n.nType == catchAll && n.children[0].handle != nil)
return
}
@@ -424,8 +434,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.prefix) == len(path)+1 && n.prefix[len(path)] == '/' &&
- path == n.prefix[:len(n.prefix)-1] && n.handle != nil)
+ (len(prefix) == len(path)+1 && prefix[len(path)] == '/' &&
+ path == prefix[:len(prefix)-1] && n.handle != nil)
return
}
}
@@ -436,22 +446,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.prefix) && strings.ToLower(path[:len(n.prefix)]) == strings.ToLower(n.prefix) {
- path = path[len(n.prefix):]
- ciPath = append(ciPath, n.prefix...)
+ 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
@@ -482,6 +493,7 @@
if len(n.children) > 0 {
path = path[k:]
n = n.children[0]
+ prefix = n.pfx[len(n.children):]
continue
}
@@ -498,7 +510,7 @@
// No handle found. Check if a handle for this path + a
// trailing slash exists
n = n.children[0]
- if n.prefix == "/" && n.handle != nil {
+ if n.pfx[len(n.children):] == "/" && n.handle != nil {
return append(ciPath, '/'), true
}
}
@@ -520,10 +532,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.prefix) == 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
}
@@ -541,10 +553,10 @@
if path == "/" {
return ciPath, true
}
- if len(path)+1 == len(n.prefix) && n.prefix[len(path)] == '/' &&
- strings.ToLower(path) == strings.ToLower(n.prefix[: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.prefix...), true
+ return append(ciPath, prefix...), true
}
}
return
diff --git a/tree_test.go b/tree_test.go
index c0be57c..eb83499 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.prefix, len(n.children), n.handle, n.wildChild, n.nType)
- for l := len(n.prefix); 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 {
@@ -80,7 +82,7 @@
if n.priority != prio {
t.Errorf(
"priority mismatch for node '%s': is %d, should be %d",
- n.prefix, n.priority, prio,
+ n.pfx[:len(n.children)], n.priority, prio,
)
}
@@ -102,7 +104,7 @@
if n.maxParams != maxParams {
t.Errorf(
"maxParams mismatch for node '%s': is %d, should be %d",
- n.prefix, n.maxParams, maxParams,
+ n.pfx[:len(n.children)], n.maxParams, maxParams,
)
}
