404511 fixed poor methods in ArrayTernaryTrie

2 files changed, 129 insertions, 19 deletions

diff --git a/jetty-util/src/main/java/org/eclipse/jetty/util/AbstractTrie.java b/jetty-util/src/main/java/org/eclipse/jetty/util/AbstractTrie.java
index dd2f53c933..a9cb82791c 100644
--- a/jetty-util/src/main/java/org/eclipse/jetty/util/AbstractTrie.java
+++ b/jetty-util/src/main/java/org/eclipse/jetty/util/AbstractTrie.java
@@ -57,16 +57,6 @@ public abstract class AbstractTrie<V> implements Trie<V>
         return get(s,0,s.length());
     }
 
-
-    @Override
-    public V get(ByteBuffer b, int offset, int len)
-    {
-        b=b.duplicate();
-        b.position(b.position()+offset);
-        b.limit(b.position()+len);
-        return get(BufferUtil.toString(b,StringUtil.__ISO_8859_1_CHARSET));
-    }
-
     @Override
     public V get(ByteBuffer b)
     {
@@ -86,15 +76,6 @@ public abstract class AbstractTrie<V> implements Trie<V>
     }
 
     @Override
-    public V getBest(ByteBuffer b, int offset, int len)
-    {
-        b=b.duplicate();
-        b.position(b.position()+offset);
-        b.limit(b.position()+len);
-        return getBest(BufferUtil.toString(b,StringUtil.__ISO_8859_1_CHARSET));
-    }
-
-    @Override
     public boolean isCaseInsensitive()
     {
         return _caseInsensitive;
diff --git a/jetty-util/src/main/java/org/eclipse/jetty/util/ArrayTernaryTrie.java b/jetty-util/src/main/java/org/eclipse/jetty/util/ArrayTernaryTrie.java
index 7c92ac5477..312bd966fe 100644
--- a/jetty-util/src/main/java/org/eclipse/jetty/util/ArrayTernaryTrie.java
+++ b/jetty-util/src/main/java/org/eclipse/jetty/util/ArrayTernaryTrie.java
@@ -18,6 +18,7 @@
 
 package org.eclipse.jetty.util;
 
+import java.nio.ByteBuffer;
 import java.util.HashSet;
 import java.util.Set;
 
@@ -194,6 +195,45 @@ public class ArrayTernaryTrie<V> extends AbstractTrie<V>
     }
 
     
+    @Override
+    public V get(ByteBuffer b, int offset, int length)
+    {
+        int t = _tree[EQ];
+        int len = length;
+        int i=0;
+        offset+=b.position();
+        
+        while(i<len)
+        {
+            byte c=(byte)(b.get(offset+i++)&0x7f);
+            if(isCaseInsensitive())
+                c=(byte)StringUtil.lowercases[c];
+            
+            while (true)
+            {
+                int row = ROW_SIZE*t;
+                char n=_tree[row];
+                int diff=n-c;
+                
+                if (diff==0)
+                {
+                    if (i==len)
+                        return (V)_value[t];
+                    t=_tree[row+EQ];
+                    if (t==0)
+                        return null;
+                    break;
+                }
+
+                t=_tree[row+((diff<0)?LO:HI)];
+                if (t==0)
+                    return null;
+            }
+        }
+        
+        return null;
+    }
+
     /* ------------------------------------------------------------ */
     @Override
     public V getBest(String s)
@@ -248,6 +288,95 @@ public class ArrayTernaryTrie<V> extends AbstractTrie<V>
     }
 
 
+    /* ------------------------------------------------------------ */
+    @Override
+    public V getBest(ByteBuffer b, int offset, int len)
+    {
+        if (b.hasArray())
+            return getBest(_tree[EQ],b.array(),b.arrayOffset()+b.position()+offset,len);
+        return getBest(_tree[EQ],b,offset,len);
+    }
+
+    /* ------------------------------------------------------------ */
+    private V getBest(int t,byte[] b, int offset, int len)
+    {
+        int node=0;
+        for(int i=0; t!=0 && i<len; i++)
+        {
+            byte c=(byte)(b[offset+i]&0x7f);
+            if(isCaseInsensitive())
+                c=(byte)StringUtil.lowercases[c];
+
+            while (t!=0)
+            {
+                int row = ROW_SIZE*t;
+                char n=_tree[row];
+                int diff=n-c;
+                
+                if (diff==0)
+                {
+                    node=t;
+                    t=_tree[row+EQ];
+                    
+                    // if this node is a match, recurse to remember 
+                    if (_key[node]!=null)
+                    {
+                        V best=getBest(t,b,offset+i+1,len-i-1);
+                        if (best!=null)
+                            return best;
+                        return (V)_value[node];
+                    }
+                    
+                    break;
+                }
+
+                t=_tree[row+((diff<0)?LO:HI)];
+            }
+        }
+        return null;
+    }
+
+    /* ------------------------------------------------------------ */
+    private V getBest(int t,ByteBuffer b, int offset, int len)
+    {
+        int node=0;
+        int o= offset+b.position();
+        
+        for(int i=0; t!=0 && i<len; i++)
+        {
+            byte c=(byte)(b.get(o+i)&0x7f);
+            if(isCaseInsensitive())
+                c=(byte)StringUtil.lowercases[c];
+
+            while (t!=0)
+            {
+                int row = ROW_SIZE*t;
+                char n=_tree[row];
+                int diff=n-c;
+                
+                if (diff==0)
+                {
+                    node=t;
+                    t=_tree[row+EQ];
+                    
+                    // if this node is a match, recurse to remember 
+                    if (_key[node]!=null)
+                    {
+                        V best=getBest(t,b,offset+i+1,len-i-1);
+                        if (best!=null)
+                            return best;
+                        return (V)_value[node];
+                    }
+                    
+                    break;
+                }
+
+                t=_tree[row+((diff<0)?LO:HI)];
+            }
+        }
+        return null;
+    }
+
     @Override
     public String toString()
     {