X-Git-Url: https://code.wpia.club/?p=gigi.git;a=blobdiff_plain;f=lib%2Fjetty%2Forg%2Feclipse%2Fjetty%2Futil%2FArrayTernaryTrie.java;h=79f0871805e481a3da8e2e56f109bd534ce1802b;hp=fdca4ce1350088b77a16ae30bb561b3ccb16fa0a;hb=ba4f228fa9f72d50991a2218cfd83987ef5d385e;hpb=875b5e9651498a0cd8e0001c0742ba843e47cad0
diff --git a/lib/jetty/org/eclipse/jetty/util/ArrayTernaryTrie.java b/lib/jetty/org/eclipse/jetty/util/ArrayTernaryTrie.java
index fdca4ce1..79f08718 100644
--- a/lib/jetty/org/eclipse/jetty/util/ArrayTernaryTrie.java
+++ b/lib/jetty/org/eclipse/jetty/util/ArrayTernaryTrie.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
@@ -25,7 +25,8 @@ import java.util.Set;
/* ------------------------------------------------------------ */
-/** A Ternary Trie String lookup data structure.
+/**
+ *
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).
*
* The Trie is stored in 3 arrays:
@@ -36,10 +37,21 @@ import java.util.Set;
* indicates that the _tree row is a complete key rather than an intermediate character of a longer key.
* - V[] _value
- An array of values corresponding to the _key array
*
+ *
* The lookup of a value will iterate through the _tree array matching characters. If the equal tree branch is followed,
* then the _key array is looked up to see if this is a complete match. If a match is found then the _value array is looked up
* to return the matching value.
*
+ *
+ * This Trie may be instantiated either as case sensitive or insensitive.
+ *
+ * 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
*/
public class ArrayTernaryTrie extends AbstractTrie
@@ -71,34 +83,60 @@ public class ArrayTernaryTrie 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;
/**
* The number of rows allocated
*/
private char _rows;
+ /* ------------------------------------------------------------ */
+ /** Create a case insensitive Trie of default capacity.
+ */
public ArrayTernaryTrie()
{
this(128);
}
+ /* ------------------------------------------------------------ */
+ /** Create a Trie of default capacity
+ * @param insensitive true if the Trie is insensitive to the case of the key.
+ */
public ArrayTernaryTrie(boolean insensitive)
{
this(insensitive,128);
}
- public ArrayTernaryTrie(int capacityInNodes)
+ /* ------------------------------------------------------------ */
+ /** Create a case insensitive Trie
+ * @param capacity The capacity of the Trie, which is in 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".
+ */
+ public ArrayTernaryTrie(int capacity)
{
- this(true,capacityInNodes);
+ this(true,capacity);
}
- public ArrayTernaryTrie(boolean insensitive, int capacityInNodes)
+ /* ------------------------------------------------------------ */
+ /** Create a Trie
+ * @param insensitive true if the Trie is insensitive to the case of the key.
+ * @param capacity The capacity of the Trie, which is in 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".
+ */
+ public ArrayTernaryTrie(boolean insensitive, int capacity)
{
super(insensitive);
- _value=new Object[capacityInNodes];
- _tree=new char[capacityInNodes*ROW_SIZE];
- _key=new String[capacityInNodes];
+ _value=(V[])new Object[capacity];
+ _tree=new char[capacity*ROW_SIZE];
+ _key=new String[capacity];
}
/* ------------------------------------------------------------ */
@@ -216,7 +254,7 @@ public class ArrayTernaryTrie extends AbstractTrie
}
}
- return (V)_value[t];
+ return _value[t];
}