diff options
author | Greg Wilkins | 2015-03-25 23:41:41 +0000 |
---|---|---|
committer | Greg Wilkins | 2015-03-26 01:18:06 +0000 |
commit | eca04f401af2a2c21bfea285175ab267e5614e9c (patch) | |
tree | ccf6cd9e3442f2b491db445f9e1e67da9ce26386 | |
parent | 5d14d0ca7a90639a2f0ee305b65fc15d13793b3c (diff) | |
download | org.eclipse.jetty.project-eca04f401af2a2c21bfea285175ab267e5614e9c.tar.gz org.eclipse.jetty.project-eca04f401af2a2c21bfea285175ab267e5614e9c.tar.xz org.eclipse.jetty.project-eca04f401af2a2c21bfea285175ab267e5614e9c.zip |
TreeTrie getBest String implementation
-rw-r--r-- | jetty-util/src/main/java/org/eclipse/jetty/util/TreeTrie.java | 40 |
1 files changed, 37 insertions, 3 deletions
diff --git a/jetty-util/src/main/java/org/eclipse/jetty/util/TreeTrie.java b/jetty-util/src/main/java/org/eclipse/jetty/util/TreeTrie.java index 9114f33ebc..d6228940a1 100644 --- a/jetty-util/src/main/java/org/eclipse/jetty/util/TreeTrie.java +++ b/jetty-util/src/main/java/org/eclipse/jetty/util/TreeTrie.java @@ -224,9 +224,43 @@ public class TreeTrie<V> extends AbstractTrie<V> @Override public V getBest(String s, int offset, int len) { - // TODO inefficient - byte[] b=s.substring(offset,offset+len).getBytes(StandardCharsets.ISO_8859_1); - return getBest(b,0,b.length); + TreeTrie<V> t = this; + for(int i=0; i < len; i++) + { + byte c=(byte)(0xff&s.charAt(offset+i)); + int index=c>=0&&c<0x7f?__lookup[c]:-1; + if (index>=0) + { + if (t._nextIndex[index] == null) + break; + t = t._nextIndex[index]; + } + else + { + TreeTrie<V> n=null; + for (int j=t._nextOther.size();j-->0;) + { + n=t._nextOther.get(j); + if (n._c==c) + break; + n=null; + } + if (n==null) + break; + t=n; + } + + // Is the next Trie is a match + if (t._key!=null) + { + // Recurse so we can remember this possibility + V best=t.getBest(s,offset+i+1,len-i-1); + if (best!=null) + return best; + break; + } + } + return t._value; } @Override |