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, ) }