449594 Handle ArrayTrie overflow with false return

2 files changed, 27 insertions, 2 deletions

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 9d8013cacd..c65cb57e08 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
@@ -99,6 +99,7 @@ public class ArrayTrie<V> extends AbstractTrie<V>
         this(128);
     }
     
+    @SuppressWarnings("unchecked")
     public ArrayTrie(int capacityInNodes)
     {
         super(true);
@@ -151,8 +152,14 @@ public class ArrayTrie<V> extends AbstractTrie<V>
                 }
             }
         }
+        
+        if (t>=_key.length)
+        {
+            _rows=(char)_key.length;
+            return false;
+        }
+        
         _key[t]=v==null?null:s;
-        V old=(V)_value[t];
         _value[t] = v;
         return true;
     }
@@ -440,6 +447,6 @@ public class ArrayTrie<V> extends AbstractTrie<V>
     @Override
     public boolean isFull()
     {
-        return _rows+1==_key.length;
+        return _rows+1>=_key.length;
     }
 }
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 a4a444cb67..25dc4c351e 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
@@ -66,6 +66,24 @@ public class TrieTest
     }
 
     @Test
+    public void testOverflow() throws Exception
+    {
+        int i=0;
+        while (true) 
+        {
+            if (++i>10000)
+                break; // must not be fixed size
+            if (!trie.put("prefix" + i, i))
+            {
+                Assert.assertTrue(trie.isFull());
+                break;
+            }
+        }
+        
+        Assert.assertTrue(!trie.isFull() || !trie.put("overflow", 0));
+    }
+    
+    @Test
     public void testKeySet() throws Exception
     {
         Assert.assertTrue(trie.keySet().contains("hello"));