jetty-9 added Ternary Trie impl for connection field cache

8 files changed, 474 insertions, 66 deletions

diff --git a/jetty-http/src/main/java/org/eclipse/jetty/http/HttpField.java b/jetty-http/src/main/java/org/eclipse/jetty/http/HttpField.java
index 9bdf39bfb0..c1a9ef2243 100644
--- a/jetty-http/src/main/java/org/eclipse/jetty/http/HttpField.java
+++ b/jetty-http/src/main/java/org/eclipse/jetty/http/HttpField.java
@@ -33,7 +33,7 @@ import org.eclipse.jetty.util.Trie;
  */
 public class HttpField
 {
-    public final static Trie<HttpField> CACHE = new ArrayTrie<>(768);
+    public final static Trie<HttpField> CACHE = new ArrayTrie<>(1024);
     public final static Trie<HttpField> CONTENT_TYPE = new ArrayTrie<>(512);
     
     static
@@ -41,8 +41,14 @@ public class HttpField
         CACHE.put(new CachedHttpField(HttpHeader.CONNECTION,HttpHeaderValue.CLOSE));
         CACHE.put(new CachedHttpField(HttpHeader.CONNECTION,HttpHeaderValue.KEEP_ALIVE));
         CACHE.put(new CachedHttpField(HttpHeader.CONNECTION,HttpHeaderValue.UPGRADE));
+        CACHE.put(new CachedHttpField(HttpHeader.ACCEPT_ENCODING,"gzip"));
         CACHE.put(new CachedHttpField(HttpHeader.ACCEPT_ENCODING,"gzip, deflate"));
+        CACHE.put(new CachedHttpField(HttpHeader.ACCEPT_ENCODING,"gzip,deflate,sdch"));
         CACHE.put(new CachedHttpField(HttpHeader.ACCEPT_LANGUAGE,"en-US,en;q=0.5"));
+        CACHE.put(new CachedHttpField(HttpHeader.ACCEPT_LANGUAGE,"en-GB,en-US;q=0.8,en;q=0.6"));
+        CACHE.put(new CachedHttpField(HttpHeader.ACCEPT_CHARSET,"ISO-8859-1,utf-8;q=0.7,*;q=0.3"));
+        CACHE.put(new CachedHttpField(HttpHeader.ACCEPT,"*/*"));
+        CACHE.put(new CachedHttpField(HttpHeader.ACCEPT,"image/png,image/*;q=0.8,*/*;q=0.5"));
         CACHE.put(new CachedHttpField(HttpHeader.ACCEPT,"text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8"));
         CACHE.put(new CachedHttpField(HttpHeader.PRAGMA,"no-cache"));
         CACHE.put(new CachedHttpField(HttpHeader.CACHE_CONTROL,"private, no-cache, no-cache=Set-Cookie, proxy-revalidate"));
@@ -52,9 +58,6 @@ public class HttpField
         CACHE.put(new CachedHttpField(HttpHeader.CONTENT_ENCODING,"deflate"));
         CACHE.put(new CachedHttpField(HttpHeader.EXPIRES,"Fri, 01 Jan 1990 00:00:00 GMT"));
         
-        // TODO more user agents
-        CACHE.put(new CachedHttpField(HttpHeader.USER_AGENT,"Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:17.0) Gecko/17.0 Firefox/17.0"));
-        
         // Content types
         for (String type : new String[]{"text/plain","text/html","text/xml","text/json","application/x-www-form-urlencoded"})
         {
@@ -80,6 +83,12 @@ public class HttpField
         for (HttpHeader h:headers)
             if (!CACHE.put(new HttpField(h,(String)null)))
                 throw new IllegalStateException("CACHE FULL");
+        // Add some more common headers
+        CACHE.put(new HttpField(HttpHeader.REFERER,(String)null));
+        CACHE.put(new HttpField(HttpHeader.IF_MODIFIED_SINCE,(String)null));
+        CACHE.put(new HttpField(HttpHeader.IF_NONE_MATCH,(String)null));
+        CACHE.put(new HttpField(HttpHeader.AUTHORIZATION,(String)null));
+        CACHE.put(new HttpField(HttpHeader.COOKIE,(String)null));
     }
 
     private final static byte[] __colon_space = new byte[] {':',' '};
diff --git a/jetty-http/src/main/java/org/eclipse/jetty/http/HttpParser.java b/jetty-http/src/main/java/org/eclipse/jetty/http/HttpParser.java
index 30996c4cf5..bb55923e2f 100644
--- a/jetty-http/src/main/java/org/eclipse/jetty/http/HttpParser.java
+++ b/jetty-http/src/main/java/org/eclipse/jetty/http/HttpParser.java
@@ -22,6 +22,8 @@ import java.io.IOException;
 import java.nio.ByteBuffer;
 
 import org.eclipse.jetty.http.HttpTokens.EndOfContent;
+import org.eclipse.jetty.util.ArrayTernaryTrie;
+import org.eclipse.jetty.util.ArrayTrie;
 import org.eclipse.jetty.util.BufferUtil;
 import org.eclipse.jetty.util.StringUtil;
 import org.eclipse.jetty.util.TreeTrie;
@@ -78,7 +80,7 @@ public class HttpParser
     private HttpMethod _method;
     private String _methodString;
     private HttpVersion _version;
-    private ByteBuffer _uri=ByteBuffer.allocate(128); // Tune?
+    private ByteBuffer _uri=ByteBuffer.allocate(256); // Tune?
     private byte _eol;
     private EndOfContent _endOfContent;
     private long _contentLength;
@@ -87,7 +89,7 @@ public class HttpParser
     private int _chunkPosition;
     private boolean _headResponse;
     private ByteBuffer _contentChunk;
-    private final Trie<HttpField> _connectionFields=new TreeTrie<>();
+    private final Trie<HttpField> _connectionFields=new ArrayTernaryTrie<>(256);
 
     private int _length;
     private final StringBuilder _string=new StringBuilder();
@@ -627,14 +629,19 @@ public class HttpParser
                     _requestHandler.parsedHostHeader(host,port);
                 
               break;
-              
-            case USER_AGENT:
+
+            case AUTHORIZATION:
             case ACCEPT:
+            case ACCEPT_CHARSET:
+            case ACCEPT_ENCODING:
             case ACCEPT_LANGUAGE:
+            case COOKIE:
+            case CACHE_CONTROL:
+            case USER_AGENT:
                 add_to_connection_trie=_field==null;
         }
     
-        if (add_to_connection_trie)
+        if (add_to_connection_trie && !_connectionFields.isFull())
         {
             _field=new HttpField.CachedHttpField(_header,_valueString);
             _connectionFields.put(_field);
@@ -782,8 +789,7 @@ public class HttpParser
                                     _field=_connectionFields.getBest(buffer,-1,buffer.remaining());
                                     if (_field==null)
                                         _field=HttpField.CACHE.getBest(buffer,-1,buffer.remaining());
-                                    
-                                    //_field=HttpField.CACHE.getBest(buffer.array(),buffer.arrayOffset()+buffer.position()-1,buffer.remaining()+1);
+                                        
                                     if (_field!=null)
                                     {
                                         _header=_field.getHeader();
@@ -848,7 +854,7 @@ public class HttpParser
                             if (_headerString==null)
                             {
                                 _headerString=takeLengthString();
-                                _header=HttpHeader.CACHE.get(_headerString);
+                                _header=HttpHeader.CACHE.get(_headerString); 
                             }
                             setState(State.HEADER_VALUE);
                             break;
@@ -1260,6 +1266,7 @@ public class HttpParser
             }
 
             LOG.warn("badMessage: "+e.toString()+" for "+_handler);
+            e.printStackTrace();
             LOG.debug(e);
             badMessage(buffer,HttpStatus.BAD_REQUEST_400,null);
             return true;
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
new file mode 100644
index 0000000000..cfaf64eee1
--- /dev/null
+++ b/jetty-util/src/main/java/org/eclipse/jetty/util/ArrayTernaryTrie.java
@@ -0,0 +1,356 @@
+//
+//  ========================================================================
+//  Copyright (c) 1995-2012 Mort Bay Consulting Pty. Ltd.
+//  ------------------------------------------------------------------------
+//  All rights reserved. This program and the accompanying materials
+//  are made available under the terms of the Eclipse Public License v1.0
+//  and Apache License v2.0 which accompanies this distribution.
+//
+//      The Eclipse Public License is available at
+//      http://www.eclipse.org/legal/epl-v10.html
+//
+//      The Apache License v2.0 is available at
+//      http://www.opensource.org/licenses/apache2.0.php
+//
+//  You may elect to redistribute this code under either of these licenses.
+//  ========================================================================
+//
+
+package org.eclipse.jetty.util;
+
+import java.io.IOException;
+import java.nio.ByteBuffer;
+import java.util.HashSet;
+import java.util.Set;
+
+
+/* ------------------------------------------------------------ */
+/** A Ternary Trie String lookup data structure.
+ * This Trie is of a fixed size and cannot grow (which can be a good thing with regards to DOS when used as a cache).
+ * @param <V>
+ */
+public class ArrayTernaryTrie<V> implements Trie<V>
+{
+    private static int LO=1;
+    private static int EQ=2;
+    private static int HI=3;
+    
+    /**
+     * The Size of a Trie row is the char, and the low, equal and high
+     * child pointers
+     */
+    private static final int ROW_SIZE = 4;
+    
+    /**
+     * The Trie rows in a single array which allows a lookup of row,character
+     * to the next row in the Trie.  This is actually a 2 dimensional
+     * array that has been flattened to achieve locality of reference.
+     */
+    private final char[] _tree;
+    
+    /**
+     * The key (if any) for a Trie row. 
+     * A row may be a leaf, a node or both in the Trie tree.
+     */
+    private final String[] _key;
+    
+    /**
+     * The value (if any) for a Trie row. 
+     * A row may be a leaf, a node or both in the Trie tree.
+     */
+    private final Object[] _value;
+    
+    
+    /**
+     * The number of rows allocated
+     */
+    private char _rows;
+
+    public ArrayTernaryTrie()
+    {
+        this(128);
+    }
+    
+    public ArrayTernaryTrie(int capacityInNodes)
+    {
+        _value=new Object[capacityInNodes];
+        _tree=new char[capacityInNodes*ROW_SIZE];
+        _key=new String[capacityInNodes];
+    }
+    
+    
+    /* ------------------------------------------------------------ */
+    @Override
+    public boolean put(String s, V v)
+    {
+        int last=EQ;
+        int t=_tree[last];
+        int k;
+        int limit = s.length();
+        int node=0;
+        for(k=0; k < limit; k++)
+        {
+            char c=s.charAt(k);
+            if (c<128)
+              c=StringUtil.lowercases[c&0x7f];
+            
+            while (true)
+            {
+                if (t==0)
+                {
+                    node=t=++_rows;
+                    if (_rows==_key.length)
+                        return false;
+                    int row=ROW_SIZE*t;
+                    _tree[row]=c;
+                    _tree[last]=(char)t;
+                    last=row+EQ;
+                    t=0;
+                    break;
+                }
+
+                int row=ROW_SIZE*t;
+                char n=_tree[row];
+                int diff=n-c;
+                if (diff==0)
+                {
+                    node=t;
+                    t=_tree[last=(row+EQ)];
+                    break;
+                }
+                if (diff<0)
+                    t=_tree[last=(row+LO)];
+                else
+                    t=_tree[last=(row+HI)];
+            }
+        }
+        _key[node]=v==null?null:s;
+        _value[node] = v;
+        
+        return true;
+    }
+
+
+    /* ------------------------------------------------------------ */
+    @Override
+    public boolean put(V v)
+    {
+        return put(v.toString(),v);
+    }
+
+    /* ------------------------------------------------------------ */
+    @Override
+    public V remove(String s)
+    {
+        V o=get(s);
+        put(s,null);
+        return o;
+    }
+
+    /* ------------------------------------------------------------ */
+    @Override
+    public V get(String s)
+    {
+        int t = _tree[EQ];
+        int len = s.length();
+        int node=0;
+        for(int i=0; t!=0 && i < len ; i++)
+        {
+            char c=StringUtil.lowercases[s.charAt(i)&0x7f];
+            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];
+                    break;
+                }
+
+                if (diff<0)
+                    t=_tree[row+LO];
+                else
+                    t=_tree[row+HI];
+            }
+        }
+        
+        return (V)_value[node];
+    }
+
+    /* ------------------------------------------------------------ */
+    @Override
+    public V get(ByteBuffer b,int offset,int len)
+    {
+        int t = _tree[EQ];
+        int node=0;
+        for(int i=0; t!=0 && i<len; i++)
+        {
+            char c=StringUtil.lowercases[b.get(offset+i)&0x7f];
+            
+            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];
+                    break;
+                }
+
+                if (diff<0)
+                    t=_tree[row+LO];
+                else
+                    t=_tree[row+HI];
+            }
+        }
+        
+        return (V)_value[node];
+    }
+
+    /* ------------------------------------------------------------ */
+    @Override
+    public V getBest(byte[] b,int offset,int len)
+    {
+        return getBest(_tree[EQ],b,offset,len);
+    }
+
+    /* ------------------------------------------------------------ */
+    @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++)
+        {
+            char c=StringUtil.lowercases[b[offset+i]&0x7f];
+
+            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;
+                }
+
+                if (diff<0)
+                    t=_tree[row+LO];
+                else
+                    t=_tree[row+HI];
+            }
+        }
+        return null;
+    }
+
+    private V getBest(int t,ByteBuffer b,int offset,int len)
+    {
+        int pos=b.position()+offset;
+        int node=0;
+        for(int i=0; t!=0 && i<len; i++)
+        {
+            char c=StringUtil.lowercases[b.get(pos++)&0x7f];
+
+            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;
+                }
+
+                if (diff<0)
+                    t=_tree[row+LO];
+                else
+                    t=_tree[row+HI];
+            }
+        }
+        return null;
+    }
+    
+    
+    
+
+    @Override
+    public String toString()
+    {
+        StringBuilder buf = new StringBuilder();
+        for (int r=1;r<=_rows;r++)
+        {
+            if (_key[r]!=null && _value[r]!=null)
+            {
+                buf.append(',');
+                buf.append(_key[r]);
+                buf.append('=');
+                buf.append(_value[r].toString());
+            }
+        }
+        if (buf.length()==0)
+            return "{}";
+        
+        buf.setCharAt(0,'{');
+        buf.append('}');
+        return buf.toString();
+    }
+
+
+
+    @Override
+    public Set<String> keySet()
+    {
+        Set<String> keys = new HashSet<>();
+
+        for (int r=1;r<=_rows;r++)
+        {
+            if (_key[r]!=null && _value[r]!=null)
+                keys.add(_key[r]);
+        }
+        return keys;
+    }
+
+    @Override
+    public boolean isFull()
+    {
+        return _rows+1==_key.length;
+    }
+}
diff --git a/jetty-util/src/main/java/org/eclipse/jetty/util/ArrayTrie.java b/jetty-util/src/main/java/org/eclipse/jetty/util/ArrayTrie.java
index bf746dc1c2..9db4d04a6d 100644
--- a/jetty-util/src/main/java/org/eclipse/jetty/util/ArrayTrie.java
+++ b/jetty-util/src/main/java/org/eclipse/jetty/util/ArrayTrie.java
@@ -123,9 +123,9 @@ public class ArrayTrie<V> implements Trie<V>
                 t=_rowIndex[idx];
                 if (t==0)
                 {
-                    if (_rows==_value.length)
+                    if (++_rows>=_value.length)
                         return false;
-                    t=_rowIndex[idx]=++_rows;
+                    t=_rowIndex[idx]=_rows;
                 }
             }
             else if (c>127)
@@ -134,6 +134,8 @@ public class ArrayTrie<V> implements Trie<V>
             {
                 if (_bigIndex==null)
                     _bigIndex=new char[_value.length][];
+                if (t>=_bigIndex.length)
+                    return false;
                 char[] big=_bigIndex[t];
                 if (big==null)
                     big=_bigIndex[t]=new char[128];
@@ -234,6 +236,15 @@ public class ArrayTrie<V> implements Trie<V>
     {
         return getBest(0,b,offset,len);
     }
+
+    /* ------------------------------------------------------------ */
+    @Override
+    public V getBest(ByteBuffer b,int offset,int len)
+    {
+        if (b.hasArray())
+            return getBest(0,b.array(),b.arrayOffset()+b.position()+offset,len);
+        return getBest(0,b,offset,len);
+    }
     
     private V getBest(int t,byte[] b,int offset,int len)
     {
@@ -270,16 +281,7 @@ public class ArrayTrie<V> implements Trie<V>
         }
         return (V)_value[t];
     }
-
-    /* ------------------------------------------------------------ */
-    @Override
-    public V getBest(ByteBuffer b,int offset,int len)
-    {
-        if (b.hasArray())
-            return getBest(0,b.array(),b.arrayOffset()+b.position()+offset,len);
-        return getBest(0,b,offset,len);
-    }
-
+    
     private V getBest(int t,ByteBuffer b,int offset,int len)
     {
         int pos=b.position()+offset;
@@ -379,17 +381,17 @@ public class ArrayTrie<V> implements Trie<V>
     
     private void keySet(Set<String> set, int t)
     {
-        if (_value[t]!=null)
+        if (t<_value.length&&_value[t]!=null)
             set.add(_key[t]);
 
         for(int i=0; i < ROW_SIZE; i++)
         {
             int idx=t*ROW_SIZE+i;
-            if (_rowIndex[idx] != 0)
+            if (idx<_rowIndex.length && _rowIndex[idx] != 0)
                 keySet(set,_rowIndex[idx]);
         }
         
-        char[] big = _bigIndex==null?null:_bigIndex[t];
+        char[] big = _bigIndex==null||t>=_bigIndex.length?null:_bigIndex[t];
         if (big!=null)
         {
             for (int i:big)
@@ -397,4 +399,10 @@ public class ArrayTrie<V> implements Trie<V>
                     keySet(set,i);
         }
     }
+    
+    @Override
+    public boolean isFull()
+    {
+        return _rows+1==_key.length;
+    }
 }
diff --git a/jetty-util/src/main/java/org/eclipse/jetty/util/StringUtil.java b/jetty-util/src/main/java/org/eclipse/jetty/util/StringUtil.java
index c0e2ddeefa..59426d48ea 100644
--- a/jetty-util/src/main/java/org/eclipse/jetty/util/StringUtil.java
+++ b/jetty-util/src/main/java/org/eclipse/jetty/util/StringUtil.java
@@ -109,7 +109,7 @@ public class StringUtil
     
     
     
-    private static char[] lowercases = {
+    public static char[] lowercases = {
           '\000','\001','\002','\003','\004','\005','\006','\007',
           '\010','\011','\012','\013','\014','\015','\016','\017',
           '\020','\021','\022','\023','\024','\025','\026','\027',
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 13de6d4f96..417bbce30b 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
@@ -57,11 +57,13 @@ public class TreeTrie<V> implements Trie<V>
         this._c=c;
     }
 
+    @Override
     public boolean put(V v)
     {
         return put(v.toString(),v);
     }
-    
+
+    @Override
     public boolean put(String s, V v)
     {
         TreeTrie<V> t = this;
@@ -102,6 +104,7 @@ public class TreeTrie<V> implements Trie<V>
         return true;
     }
 
+    @Override
     public V remove(String s)
     {
         V o=get(s);
@@ -109,6 +112,7 @@ public class TreeTrie<V> implements Trie<V>
         return o;
     }
 
+    @Override
     public V get(String s)
     {
         TreeTrie<V> t = this;
@@ -141,6 +145,7 @@ public class TreeTrie<V> implements Trie<V>
         return t._value;
     }
 
+    @Override
     public V get(ByteBuffer b,int offset,int len)
     {
         TreeTrie<V> t = this;
@@ -172,6 +177,7 @@ public class TreeTrie<V> implements Trie<V>
         return t._value;
     }
 
+    @Override
     public V getBest(byte[] b,int offset,int len)
     {
         TreeTrie<V> t = this;
@@ -213,6 +219,7 @@ public class TreeTrie<V> implements Trie<V>
         return t._value;
     }
 
+    @Override
     public V getBest(ByteBuffer b,int offset,int len)
     {
         if (b.hasArray())
@@ -262,8 +269,6 @@ public class TreeTrie<V> implements Trie<V>
         return t._value;
     }
     
-    
-    
 
     @Override
     public String toString()
@@ -279,7 +284,6 @@ public class TreeTrie<V> implements Trie<V>
         return buf.toString();
     }
 
-
     private static <V> void toString(Appendable out, TreeTrie<V> t)
     {
         if (t != null)
@@ -308,7 +312,8 @@ public class TreeTrie<V> implements Trie<V>
                 toString(out,t._nextOther.get(i));
         }           
     }
-    
+
+    @Override
     public Set<String> keySet()
     {
         Set<String> keys = new HashSet<>();
@@ -332,4 +337,11 @@ public class TreeTrie<V> implements Trie<V>
                 keySet(set,t._nextOther.get(i));
         }           
     }
+    
+    @Override
+    public boolean isFull()
+    {
+        return false;
+    }
+    
 }
diff --git a/jetty-util/src/main/java/org/eclipse/jetty/util/Trie.java b/jetty-util/src/main/java/org/eclipse/jetty/util/Trie.java
index d5cd46347b..3bf17ac20e 100644
--- a/jetty-util/src/main/java/org/eclipse/jetty/util/Trie.java
+++ b/jetty-util/src/main/java/org/eclipse/jetty/util/Trie.java
@@ -84,4 +84,7 @@ public interface Trie<V>
 
     /* ------------------------------------------------------------ */
     public Set<String> keySet();
+    
+    public boolean isFull();
+    
 }
diff --git a/jetty-util/src/test/java/org/eclipse/jetty/util/TrieTest.java b/jetty-util/src/test/java/org/eclipse/jetty/util/TrieTest.java
index c74d558d15..1febc2f26d 100644
--- a/jetty-util/src/test/java/org/eclipse/jetty/util/TrieTest.java
+++ b/jetty-util/src/test/java/org/eclipse/jetty/util/TrieTest.java
@@ -37,8 +37,9 @@ public class TrieTest
     public static Collection<Object[]> data()
     {
         Object[][] data = new Object[][]{
-            {new ArrayTrie<String>()},
-            {new TreeTrie<Integer>()}
+            {new ArrayTrie<Integer>(128)},
+            {new TreeTrie<Integer>()},
+            {new ArrayTernaryTrie<Integer>(128)}
         };
         return Arrays.asList(data);
     }
@@ -61,7 +62,6 @@ public class TrieTest
         trie.put("foo-bar",6);
         trie.put("foo+bar",7);
         trie.put("HELL4",8);
-        
     }
     
     @Test
@@ -137,33 +137,33 @@ public class TrieTest
     @Test
     public void testGetBestArray() throws Exception
     {
-        Assert.assertEquals(1,trie.getBest(StringUtil.getUtf8Bytes("xhelloxxxx"),1,10).intValue());
-        Assert.assertEquals(2,trie.getBest(StringUtil.getUtf8Bytes("xhelxoxxxx"),1,10).intValue());
-        Assert.assertEquals(3,trie.getBest(StringUtil.getUtf8Bytes("xhellxxxxx"),1,10).intValue()); 
-        Assert.assertEquals(6,trie.getBest(StringUtil.getUtf8Bytes("xfoo-barxx"),1,10).intValue()); 
-        Assert.assertEquals(8,trie.getBest(StringUtil.getUtf8Bytes("xhell4xxxx"),1,10).intValue()); 
+        Assert.assertEquals(1,trie.getBest(StringUtil.getUtf8Bytes("xhelloxxxx"),1,8).intValue());
+        Assert.assertEquals(2,trie.getBest(StringUtil.getUtf8Bytes("xhelxoxxxx"),1,8).intValue());
+        Assert.assertEquals(3,trie.getBest(StringUtil.getUtf8Bytes("xhellxxxxx"),1,8).intValue()); 
+        Assert.assertEquals(6,trie.getBest(StringUtil.getUtf8Bytes("xfoo-barxx"),1,8).intValue()); 
+        Assert.assertEquals(8,trie.getBest(StringUtil.getUtf8Bytes("xhell4xxxx"),1,8).intValue()); 
         
-        Assert.assertEquals(1,trie.getBest(StringUtil.getUtf8Bytes("xHELLOxxxx"),1,10).intValue());
-        Assert.assertEquals(2,trie.getBest(StringUtil.getUtf8Bytes("xHELxoxxxx"),1,10).intValue());
-        Assert.assertEquals(3,trie.getBest(StringUtil.getUtf8Bytes("xHELLxxxxx"),1,10).intValue()); 
-        Assert.assertEquals(6,trie.getBest(StringUtil.getUtf8Bytes("xfoo-BARxx"),1,10).intValue()); 
-        Assert.assertEquals(8,trie.getBest(StringUtil.getUtf8Bytes("xHELL4xxxx"),1,10).intValue());  
+        Assert.assertEquals(1,trie.getBest(StringUtil.getUtf8Bytes("xHELLOxxxx"),1,8).intValue());
+        Assert.assertEquals(2,trie.getBest(StringUtil.getUtf8Bytes("xHELxoxxxx"),1,8).intValue());
+        Assert.assertEquals(3,trie.getBest(StringUtil.getUtf8Bytes("xHELLxxxxx"),1,8).intValue()); 
+        Assert.assertEquals(6,trie.getBest(StringUtil.getUtf8Bytes("xfoo-BARxx"),1,8).intValue()); 
+        Assert.assertEquals(8,trie.getBest(StringUtil.getUtf8Bytes("xHELL4xxxx"),1,8).intValue());  
     }
 
     @Test
     public void testGetBestBuffer() throws Exception
     {
-        Assert.assertEquals(1,trie.getBest(BufferUtil.toBuffer("xhelloxxxx"),1,10).intValue());
-        Assert.assertEquals(2,trie.getBest(BufferUtil.toBuffer("xhelxoxxxx"),1,10).intValue());
-        Assert.assertEquals(3,trie.getBest(BufferUtil.toBuffer("xhellxxxxx"),1,10).intValue()); 
-        Assert.assertEquals(6,trie.getBest(BufferUtil.toBuffer("xfoo-barxx"),1,10).intValue()); 
-        Assert.assertEquals(8,trie.getBest(BufferUtil.toBuffer("xhell4xxxx"),1,10).intValue()); 
+        Assert.assertEquals(1,trie.getBest(BufferUtil.toBuffer("xhelloxxxx"),1,8).intValue());
+        Assert.assertEquals(2,trie.getBest(BufferUtil.toBuffer("xhelxoxxxx"),1,8).intValue());
+        Assert.assertEquals(3,trie.getBest(BufferUtil.toBuffer("xhellxxxxx"),1,8).intValue()); 
+        Assert.assertEquals(6,trie.getBest(BufferUtil.toBuffer("xfoo-barxx"),1,8).intValue()); 
+        Assert.assertEquals(8,trie.getBest(BufferUtil.toBuffer("xhell4xxxx"),1,8).intValue()); 
         
-        Assert.assertEquals(1,trie.getBest(BufferUtil.toBuffer("xHELLOxxxx"),1,10).intValue());
-        Assert.assertEquals(2,trie.getBest(BufferUtil.toBuffer("xHELxoxxxx"),1,10).intValue());
-        Assert.assertEquals(3,trie.getBest(BufferUtil.toBuffer("xHELLxxxxx"),1,10).intValue()); 
-        Assert.assertEquals(6,trie.getBest(BufferUtil.toBuffer("xfoo-BARxx"),1,10).intValue()); 
-        Assert.assertEquals(8,trie.getBest(BufferUtil.toBuffer("xHELL4xxxx"),1,10).intValue());  
+        Assert.assertEquals(1,trie.getBest(BufferUtil.toBuffer("xHELLOxxxx"),1,8).intValue());
+        Assert.assertEquals(2,trie.getBest(BufferUtil.toBuffer("xHELxoxxxx"),1,8).intValue());
+        Assert.assertEquals(3,trie.getBest(BufferUtil.toBuffer("xHELLxxxxx"),1,8).intValue()); 
+        Assert.assertEquals(6,trie.getBest(BufferUtil.toBuffer("xfoo-BARxx"),1,8).intValue()); 
+        Assert.assertEquals(8,trie.getBest(BufferUtil.toBuffer("xHELL4xxxx"),1,8).intValue());  
         
         ByteBuffer buffer = (ByteBuffer)BufferUtil.toBuffer("xhelloxxxxxxx").position(2);
         Assert.assertEquals(1,trie.getBest(buffer,-1,10).intValue());
@@ -172,20 +172,33 @@ public class TrieTest
     @Test
     public void testGetBestDirectBuffer() throws Exception
     {
-        Assert.assertEquals(1,trie.getBest(BufferUtil.toDirectBuffer("xhelloxxxx"),1,10).intValue());
-        Assert.assertEquals(2,trie.getBest(BufferUtil.toDirectBuffer("xhelxoxxxx"),1,10).intValue());
-        Assert.assertEquals(3,trie.getBest(BufferUtil.toDirectBuffer("xhellxxxxx"),1,10).intValue()); 
-        Assert.assertEquals(6,trie.getBest(BufferUtil.toDirectBuffer("xfoo-barxx"),1,10).intValue()); 
-        Assert.assertEquals(8,trie.getBest(BufferUtil.toDirectBuffer("xhell4xxxx"),1,10).intValue()); 
+        Assert.assertEquals(1,trie.getBest(BufferUtil.toDirectBuffer("xhelloxxxx"),1,8).intValue());
+        Assert.assertEquals(2,trie.getBest(BufferUtil.toDirectBuffer("xhelxoxxxx"),1,8).intValue());
+        Assert.assertEquals(3,trie.getBest(BufferUtil.toDirectBuffer("xhellxxxxx"),1,8).intValue()); 
+        Assert.assertEquals(6,trie.getBest(BufferUtil.toDirectBuffer("xfoo-barxx"),1,8).intValue()); 
+        Assert.assertEquals(8,trie.getBest(BufferUtil.toDirectBuffer("xhell4xxxx"),1,8).intValue()); 
         
-        Assert.assertEquals(1,trie.getBest(BufferUtil.toDirectBuffer("xHELLOxxxx"),1,10).intValue());
-        Assert.assertEquals(2,trie.getBest(BufferUtil.toDirectBuffer("xHELxoxxxx"),1,10).intValue());
-        Assert.assertEquals(3,trie.getBest(BufferUtil.toDirectBuffer("xHELLxxxxx"),1,10).intValue()); 
-        Assert.assertEquals(6,trie.getBest(BufferUtil.toDirectBuffer("xfoo-BARxx"),1,10).intValue()); 
-        Assert.assertEquals(8,trie.getBest(BufferUtil.toDirectBuffer("xHELL4xxxx"),1,10).intValue());  
+        Assert.assertEquals(1,trie.getBest(BufferUtil.toDirectBuffer("xHELLOxxxx"),1,8).intValue());
+        Assert.assertEquals(2,trie.getBest(BufferUtil.toDirectBuffer("xHELxoxxxx"),1,8).intValue());
+        Assert.assertEquals(3,trie.getBest(BufferUtil.toDirectBuffer("xHELLxxxxx"),1,8).intValue()); 
+        Assert.assertEquals(6,trie.getBest(BufferUtil.toDirectBuffer("xfoo-BARxx"),1,8).intValue()); 
+        Assert.assertEquals(8,trie.getBest(BufferUtil.toDirectBuffer("xHELL4xxxx"),1,8).intValue());  
         
         ByteBuffer buffer = (ByteBuffer)BufferUtil.toDirectBuffer("xhelloxxxxxxx").position(2);
         Assert.assertEquals(1,trie.getBest(buffer,-1,10).intValue());
     }
     
+    @Test 
+    public void testFull() throws Exception
+    {
+       if (!(trie instanceof ArrayTrie<?> || trie instanceof ArrayTernaryTrie<?>))
+           return;
+       
+       Assert.assertFalse(trie.put("Large: This is a really large key and should blow the maximum size of the array trie as lots of nodes should already be used.",99));
+       testGetString();
+       testGetBestArray();
+       testGetBestBuffer();
+    }
+    
+    
 }