X-Git-Url: https://code.wpia.club/?p=gigi.git;a=blobdiff_plain;f=lib%2Fjetty%2Forg%2Feclipse%2Fjetty%2Futil%2FArrayTrie.java;fp=lib%2Fjetty%2Forg%2Feclipse%2Fjetty%2Futil%2FArrayTrie.java;h=9dbf994a551ea4145fb8c621e8d79ea4158afe21;hp=73ccc424fd01e16327c5bc1a01c957998d6b7707;hb=aa5723dbb64ec8efa63909d39ff72364f0a5ee96;hpb=e443f19911df6a30ab07ef70d23970bda671b194
diff --git a/lib/jetty/org/eclipse/jetty/util/ArrayTrie.java b/lib/jetty/org/eclipse/jetty/util/ArrayTrie.java
index 73ccc424..9dbf994a 100644
--- 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.
+/**
+ *
A Trie String lookup data structure using a fixed size array.
* 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.
+ *
+ * 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.
+ *
+ * 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.
*
* @param
*/
@@ -47,8 +63,8 @@ public class ArrayTrie extends AbstractTrie
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 extends AbstractTrie
* 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 extends AbstractTrie
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 extends AbstractTrie
}
}
}
+
+ 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 extends AbstractTrie
return null;
}
}
- return (V)_value[t];
+ return _value[t];
}
/* ------------------------------------------------------------ */
@@ -374,7 +406,7 @@ public class ArrayTrie extends AbstractTrie
}
- private void toString(Appendable out, int t)
+ private void toString(Appendable out, int t)
{
if (_value[t]!=null)
{
@@ -440,6 +472,6 @@ public class ArrayTrie extends AbstractTrie
@Override
public boolean isFull()
{
- return _rows+1==_key.length;
+ return _rows+1>=_key.length;
}
}