Merge "Update notes about password security"

[gigi.git] / lib / jetty / org / eclipse / jetty / util / ArrayTrie.java

diff --git a/lib/jetty/org/eclipse/jetty/util/ArrayTrie.java b/lib/jetty/org/eclipse/jetty/util/ArrayTrie.java
index 73ccc424fd01e16327c5bc1a01c957998d6b7707..9dbf994a551ea4145fb8c621e8d79ea4158afe21 100644 (file)
--- a/lib/jetty/org/eclipse/jetty/util/ArrayTrie.java
+++ b/lib/jetty/org/eclipse/jetty/util/ArrayTrie.java
@@ -1,6 +1,6 @@
 //
 //  ========================================================================
-//  Copyright (c) 1995-2014 Mort Bay Consulting Pty. Ltd.
+//  Copyright (c) 1995-2016 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
@@ -24,9 +24,25 @@ import java.util.HashSet;
 import java.util.Set;
 
 /* ------------------------------------------------------------ */
-/** A Trie String lookup data structure using a fixed size array.
+/** 
+ * <p>A Trie String lookup data structure using a fixed size array.</p>
  * <p>This implementation is always case insensitive and is optimal for
- * a small number of fixed strings with few special characters.
+ * a small number of fixed strings with few special characters.  The
+ * Trie is stored in an array of lookup tables, each indexed by the 
+ * next character of the key.   Frequently used characters are directly
+ * indexed in each lookup table, whilst infrequently used characters
+ * must use a big character table.
+ * </p>
+ * <p>This Trie is very space efficient if the key characters are 
+ * from ' ', '+', '-', ':', ';', '.', 'A' to 'Z' or 'a' to 'z'. 
+ * Other ISO-8859-1 characters can be used by the key, but less space
+ * efficiently.
+ * </p>
+ * <p>This Trie is not Threadsafe and contains no mutual exclusion 
+ * or deliberate memory barriers.  It is intended for an ArrayTrie to be
+ * built by a single thread and then used concurrently by multiple threads
+ * and not mutated during that access.  If concurrent mutations of the
+ * Trie is required external locks need to be applied.
  * </p>
  * @param <V>
  */
@@ -47,8 +63,8 @@ public class ArrayTrie<V> extends AbstractTrie<V>
     private static final int[] __lookup = 
     { // 0   1   2   3   4   5   6   7   8   9   A   B   C   D   E   F
    /*0*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 
-   /*1*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 30, 
-   /*2*/31, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 26, -1, 27, -1, -1,
+   /*1*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 
+   /*2*/31, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 26, -1, 27, 30, -1,
    /*3*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 28, 29, -1, -1, -1, -1,
    /*4*/-1,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14,
    /*5*/15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
@@ -79,7 +95,7 @@ public class ArrayTrie<V> extends AbstractTrie<V>
      * 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;
+    private final V[] _value;
     
     /**
      * A big index for each row.
@@ -99,12 +115,22 @@ public class ArrayTrie<V> extends AbstractTrie<V>
         this(128);
     }
     
-    public ArrayTrie(int capacityInNodes)
+    /* ------------------------------------------------------------ */
+    /**
+     * @param capacity  The capacity of the trie, which at the worst case
+     * is the total number of characters of all keys stored in the Trie.
+     * The capacity needed is dependent of the shared prefixes of the keys.
+     * For example, a capacity of 6 nodes is required to store keys "foo" 
+     * and "bar", but a capacity of only 4 is required to
+     * store "bar" and "bat".
+     */
+    @SuppressWarnings("unchecked")
+    public ArrayTrie(int capacity)
     {
         super(true);
-        _value=new Object[capacityInNodes];
-        _rowIndex=new char[capacityInNodes*32];
-        _key=new String[capacityInNodes];
+        _value=(V[])new Object[capacity];
+        _rowIndex=new char[capacity*32];
+        _key=new String[capacity];
     }
     
     
@@ -151,8 +177,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;
     }
@@ -183,7 +215,7 @@ public class ArrayTrie<V> extends AbstractTrie<V>
                     return null;
             }
         }
-        return (V)_value[t];
+        return _value[t];
     }
 
     /* ------------------------------------------------------------ */
@@ -374,7 +406,7 @@ public class ArrayTrie<V> extends AbstractTrie<V>
     }
 
 
-    private <V> void toString(Appendable out, int t)
+    private void toString(Appendable out, int t)
     {
         if (_value[t]!=null)
         {
@@ -440,6 +472,6 @@ public class ArrayTrie<V> extends AbstractTrie<V>
     @Override
     public boolean isFull()
     {
-        return _rows+1==_key.length;
+        return _rows+1>=_key.length;
     }
 }