Class ArrayTernaryTrie<V>
- Type Parameters:
V
- the Entry type
- All Implemented Interfaces:
Trie<V>
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:
- char[] _tree
- This is semantically 2 dimensional array flattened into a 1 dimensional char array. The second dimension is that every 4 sequential elements represents a row of: character; hi index; eq index; low index, used to build a ternary trie of key strings.
- String[] _key
- An array of key values where each element matches a row in the _tree array. A non zero key element 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.
-
Nested Class Summary
Nested Classes -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final String[]
The key (if any) for a Trie row.private char
The number of rows allocatedprivate final char[]
The Trie rows in a single array which allows a lookup of row,character to the next row in the Trie.private final V[]
The value (if any) for a Trie row.private static int
private static int
private static int
private static final int
The Size of a Trie row is the char, and the low, equal and high child pointersFields inherited from class org.eclipse.jetty.util.AbstractTrie
_caseInsensitive
-
Constructor Summary
ConstructorsConstructorDescriptionCreate a case insensitive Trie of default capacity.ArrayTernaryTrie
(boolean insensitive) Create a Trie of default capacityArrayTernaryTrie
(boolean insensitive, int capacity) Create a TrieArrayTernaryTrie
(int capacity) Create a case insensitive TrieArrayTernaryTrie
(ArrayTernaryTrie<V> trie, double factor) Copy Trie and change capacity by a factor -
Method Summary
Modifier and TypeMethodDescriptionvoid
clear()
void
dump()
entrySet()
Get an exact match from a String keyget
(ByteBuffer b, int offset, int len) Get an exact match from a segment of a ByteBuufer as keygetBest
(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
private V
getBest
(int t, ByteBuffer b, int offset, int len) Get the best match from key in a String.Get the best match from key in a String.getBest
(ByteBuffer b, int offset, int len) Get the best match from key in a byte buffer.static int
hilo
(int diff) boolean
isEmpty()
boolean
isFull()
keySet()
boolean
Put an entry into the Trieint
size()
toString()
Methods inherited from class org.eclipse.jetty.util.AbstractTrie
get, get, isCaseInsensitive, put, remove
-
Field Details
-
LO
private static int LO -
EQ
private static int EQ -
HI
private static int HI -
ROW_SIZE
private static final int ROW_SIZEThe Size of a Trie row is the char, and the low, equal and high child pointers- See Also:
-
_tree
private final char[] _treeThe 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. -
_key
The key (if any) for a Trie row. A row may be a leaf, a node or both in the Trie tree. -
_value
The value (if any) for a Trie row. A row may be a leaf, a node or both in the Trie tree. -
_rows
private char _rowsThe number of rows allocated
-
-
Constructor Details
-
ArrayTernaryTrie
public ArrayTernaryTrie()Create a case insensitive Trie of default capacity. -
ArrayTernaryTrie
public ArrayTernaryTrie(boolean insensitive) Create a Trie of default capacity- Parameters:
insensitive
- true if the Trie is insensitive to the case of the key.
-
ArrayTernaryTrie
public ArrayTernaryTrie(int capacity) Create a case insensitive Trie- Parameters:
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".
-
ArrayTernaryTrie
public ArrayTernaryTrie(boolean insensitive, int capacity) Create a Trie- Parameters:
insensitive
- true if the Trie is insensitive to the case of the key.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".
-
ArrayTernaryTrie
Copy Trie and change capacity by a factor- Parameters:
trie
- the trie to copy fromfactor
- the factor to grow the capacity by
-
-
Method Details
-
clear
public void clear() -
put
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
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
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
Description copied from interface:Trie
Get the best match from key in a String. -
getBest
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 keylength
- the length of the key- Returns:
- The value or null if not found
-
getBest
-
getBest
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
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
-
getBest
-
toString
-
keySet
-
size
public int size() -
isEmpty
public boolean isEmpty() -
entrySet
-
isFull
public boolean isFull() -
hilo
public static int hilo(int diff) -
dump
public void dump()
-