tree: avoid recursion in case-insensitive when possible
diff --git a/tree.go b/tree.go index 808f1e4..c5e0d85 100644 --- a/tree.go +++ b/tree.go
@@ -321,7 +321,7 @@ // made if a handle exists with an extra (without the) trailing slash for the // given path. func (n *node) getValue(path string) (handle Handle, p Params, tsr bool) { -walk: // Outer loop for walking the tree +walk: // outer loop for walking the tree for { if len(path) > len(n.path) { if path[:len(n.path)] == n.path { @@ -476,6 +476,7 @@ func (n *node) findCaseInsensitivePathRec(path, loPath string, ciPath []byte, rb [4]byte, fixTrailingSlash bool) ([]byte, bool) { loNPath := strings.ToLower(n.path) +walk: // outer loop for walking the tree for len(loPath) >= len(loNPath) && (len(loNPath) == 0 || loPath[1:len(loNPath)] == loNPath[1:]) { // add common path to result ciPath = append(ciPath, n.path...) @@ -495,11 +496,15 @@ // old rune not finished for i := 0; i < len(n.indices); i++ { if n.indices[i] == rb[0] { - if out, found := n.children[i].findCaseInsensitivePathRec( + // continue with child node + n = n.children[i] + loNPath = strings.ToLower(n.path) + continue walk + /*if out, found := n.children[i].findCaseInsensitivePathRec( path, loPath, ciPath, rb, fixTrailingSlash, ); found { return out, true - } + }*/ } } } else { @@ -523,16 +528,18 @@ // skipp already processed bytes rb = shiftNRuneBytes(rb, off) - // must use recursive approach since both the uppercase - // byte and the lowercase byte might exist as an index for i := 0; i < len(n.indices); i++ { // lowercase matches if n.indices[i] == rb[0] { + // must use a recursive approach since both the + // uppercase byte and the lowercase byte might exist + // as an index if out, found := n.children[i].findCaseInsensitivePathRec( path, loPath, ciPath, rb, fixTrailingSlash, ); found { return out, true } + break } } @@ -544,11 +551,10 @@ for i := 0; i < len(n.indices); i++ { // uppercase matches if n.indices[i] == rb[0] { - if out, found := n.children[i].findCaseInsensitivePathRec( - path, loPath, ciPath, rb, fixTrailingSlash, - ); found { - return out, true - } + // continue with child node + n = n.children[i] + loNPath = strings.ToLower(n.path) + continue walk } } }