Class ArrayTrie<V>
- java.lang.Object
-
- org.eclipse.jetty.util.AbstractTrie<V>
-
- org.eclipse.jetty.util.ArrayTrie<V>
-
- Type Parameters:
V
- the entry type
- All Implemented Interfaces:
Trie<V>
public class ArrayTrie<V> extends AbstractTrie<V>
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. 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.
-
-
Field Summary
Fields Modifier and Type Field Description private static int[]
__lookup
The index lookup table, this maps a character as a byte (ISO-8859-1 or UTF8) to an index within a Trie rowprivate char[][]
_bigIndex
A big index for each row.private java.lang.String[]
_key
The key (if any) for a Trie row.private char[]
_rowIndex
The Trie rows in a single array which allows a lookup of row,character to the next row in the Trie.private char
_rows
The number of rows allocatedprivate V[]
_value
The value (if any) for a Trie row.private static int
MAX_CAPACITY
The maximum capacity of the implementation.private static int
ROW_SIZE
The Size of a Trie row is how many characters can be looked up directly without going to a big index.-
Fields inherited from class org.eclipse.jetty.util.AbstractTrie
_caseInsensitive
-
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
clear()
V
get(java.lang.String s, int offset, int len)
Get an exact match from a String keyV
get(java.nio.ByteBuffer b, int offset, int len)
Get an exact match from a segment of a ByteBuufer as keyV
getBest(byte[] b, int offset, int len)
Get the best match from key in a byte array.private V
getBest(int t, byte[] b, int offset, int len)
private V
getBest(int t, java.lang.String s, int offset, int len)
private V
getBest(int t, java.nio.ByteBuffer b, int offset, int len)
V
getBest(java.lang.String s, int offset, int len)
Get the best match from key in a String.V
getBest(java.nio.ByteBuffer b, int offset, int len)
Get the best match from key in a byte buffer.boolean
isFull()
java.util.Set<java.lang.String>
keySet()
boolean
put(java.lang.String s, V v)
Put an entry into the Triejava.lang.String
toString()
-
Methods inherited from class org.eclipse.jetty.util.AbstractTrie
get, get, getBest, isCaseInsensitive, put, remove
-
-
-
-
Field Detail
-
ROW_SIZE
private static final int ROW_SIZE
The Size of a Trie row is how many characters can be looked up directly without going to a big index. This is set at 32 to cover case insensitive alphabet and a few other common characters.- See Also:
- Constant Field Values
-
MAX_CAPACITY
private static final int MAX_CAPACITY
The maximum capacity of the implementation. Over that, the 16 bit indexes can overflow and the trie cannot find existing entries anymore.- See Also:
- Constant Field Values
-
__lookup
private static final int[] __lookup
The index lookup table, this maps a character as a byte (ISO-8859-1 or UTF8) to an index within a Trie row
-
_rowIndex
private final char[] _rowIndex
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. The first ROW_SIZE entries are for row 0, then next ROW_SIZE entries are for row 1 etc. So in general instead of using _rows[row][index], we use _rows[row*ROW_SIZE+index] to look up the next row for a given character. The array is of characters rather than integers to save space.
-
_key
private final java.lang.String[] _key
The key (if any) for a Trie row. A row may be a leaf, a node or both in the Trie tree.
-
_value
private final V[] _value
The value (if any) for a Trie row. A row may be a leaf, a node or both in the Trie tree.
-
_bigIndex
private char[][] _bigIndex
A big index for each row. If a character outside of the lookup map is needed, then a big index will be created for the row, with 256 entries, one for each possible byte.
-
_rows
private char _rows
The number of rows allocated
-
-
Constructor Detail
-
ArrayTrie
public ArrayTrie()
-
ArrayTrie
public ArrayTrie(int capacity)
- Parameters:
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".
-
-
Method Detail
-
clear
public void clear()
-
put
public boolean put(java.lang.String s, V v)
Description copied from interface:Trie
Put an entry into the Trie- Parameters:
s
- The key for the entryv
- The value of the entry- Returns:
- True if the Trie had capacity to add the field.
-
get
public V get(java.lang.String s, int offset, int len)
Description copied from interface:Trie
Get an exact match from a String key- Parameters:
s
- The keyoffset
- The offset within the string of the keylen
- the length of the key- Returns:
- the value for the string / offset / length
-
get
public V get(java.nio.ByteBuffer b, int offset, int len)
Description copied from interface:Trie
Get an exact match from a segment of a ByteBuufer as key- Parameters:
b
- The bufferoffset
- The offset within the buffer of the keylen
- the length of the key- Returns:
- The value or null if not found
-
getBest
public V getBest(byte[] b, int offset, int len)
Description copied from interface:Trie
Get the best match from key in a byte array. The key is assumed to by ISO_8859_1 characters.
-
getBest
public V getBest(java.nio.ByteBuffer b, int offset, int len)
Description copied from interface:Trie
Get the best match from key in a byte buffer. The key is assumed to by ISO_8859_1 characters.- Parameters:
b
- The bufferoffset
- The offset within the buffer of the keylen
- the length of the key- Returns:
- The value or null if not found
-
getBest
public V getBest(java.lang.String s, int offset, int len)
Description copied from interface:Trie
Get the best match from key in a String.- Parameters:
s
- The stringoffset
- The offset within the string of the keylen
- the length of the key- Returns:
- The value or null if not found
-
getBest
private V getBest(int t, java.lang.String s, int offset, int len)
-
getBest
private V getBest(int t, byte[] b, int offset, int len)
-
getBest
private V getBest(int t, java.nio.ByteBuffer b, int offset, int len)
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
keySet
public java.util.Set<java.lang.String> keySet()
-
isFull
public boolean isFull()
-
-