Top Description Inners Fields Constructors Methods
org.eclipse.jetty.util

pack-priv Class ArrayTernaryTrie<V>

extends AbstractTrie<V>
Class Inheritance
Annotations
@Deprecated
Type Parameters
<V>
the Entry type
Imports
java.nio.ByteBuffer, java.util.AbstractMap, .Arrays, .HashSet, .Map, .Objects, .Set

Deprecated

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 and Inner Type Summary

Modifier and TypeClass and Description
public static class
ArrayTernaryTrie.Growing<V>

Deprecated

Field Summary

Modifier and TypeField and Description
private final String[]
_key

The key (if any) for a Trie row.

private char
_rows

The number of rows allocated

private final char[]
_tree

The Trie rows in a single array which allows a lookup of row,character to the next row in the Trie.

private final V[]
_value

The value (if any) for a Trie row.

private static final int
EQ

private static final int
HI

private static final int
LO

private static final int
MAX_CAPACITY

The maximum capacity of the implementation.

private static final int
ROW_SIZE

The Size of a Trie row is the char, and the low, equal and high child pointers

Inherited from org.eclipse.jetty.util.AbstractTrie:
_caseSensitive

Constructor Summary

AccessConstructor and Description
pack-priv
ArrayTernaryTrie(boolean
true if the Trie is insensitive to the case of the key.
caseSensitive, int
The capacity of the Trie, which is in the worst case is the total number of characters of all keys stored in the Trie.
capacity)

Create a Trie

Method Summary

Modifier and TypeMethod and Description
public void
clear()

Implements org.eclipse.jetty.util.Index.Mutable.clear.

Remove all entries from the index.
public void
dump()

public Set<Map.Entry<String, V>>
entrySet()

public V
get(String
The key
s, int
The offset within the string of the key
offset, int
the length of the key
len)

Implements org.eclipse.jetty.util.Index.get.

Get an exact match from a String key
public V
get(ByteBuffer
The buffer
b, int
The offset within the buffer of the key
offset, int
the length of the key
len)

Implements org.eclipse.jetty.util.Index.get.

Get an exact match from a segment of a ByteBuffer as key
public V
getBest(String
The string
s)

Overrides org.eclipse.jetty.util.AbstractTrie.getBest.

Implements org.eclipse.jetty.util.Index.getBest.

Get the best match from key in a String, which may be a prefix match or an exact match.
public V
getBest(String
The string
s, int
The offset within the string of the key
offset, int
the length of the key
length)

Implements org.eclipse.jetty.util.Index.getBest.

Get the best match from key in a String.
private V
getBest(int t, String s, int offset, int len)

public V
getBest(ByteBuffer
The buffer
b, int
The offset within the buffer of the key
offset, int
the length of the key
len)

Implements org.eclipse.jetty.util.Index.getBest.

Get the best match from key in a byte buffer.
public V
getBest(byte[]
The buffer
b, int
The offset within the array of the key
offset, int
the length of the key
len)

Overrides org.eclipse.jetty.util.AbstractTrie.getBest.

Implements org.eclipse.jetty.util.Index.getBest.

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, ByteBuffer b, int offset, int len)

public static int
hilo(int diff)

public boolean
isEmpty()

Implements org.eclipse.jetty.util.Index.isEmpty.

Check if the index contains any entry.
public Set<String>
keySet()

Implements org.eclipse.jetty.util.Index.keySet.

Get a Set of the keys contained in this index.
public boolean
put(String
The key for the entry. Must be non null, but can be empty.
s, V
The value of the entry. Must be non null.
v)

Implements org.eclipse.jetty.util.Index.Mutable.put.

Put an entry into the index.
public int
size()

Implements org.eclipse.jetty.util.Index.size.

Get the number of entries in the index.
public String
toString()

Overrides java.lang.Object.toString.

Returns a string representation of the object.
Inherited from org.eclipse.jetty.util.AbstractTrie:
getgetisCaseInsensitiveisCaseSensitiveputputAllremoverequiredCapacity

Field Detail

_keyback to summary
private final String[] _key

The key (if any) for a Trie row. A row may be a leaf, a node or both in the Trie tree.

_rowsback to summary
private char _rows

The number of rows allocated

_treeback to summary
private final char[] _tree

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.

_valueback to summary
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.

EQback to summary
private static final int EQ
HIback to summary
private static final int HI
LOback to summary
private static final int LO
MAX_CAPACITYback to summary
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.

ROW_SIZEback to summary
private static final int ROW_SIZE

The Size of a Trie row is the char, and the low, equal and high child pointers

Constructor Detail

ArrayTernaryTrieback to summary
pack-priv ArrayTernaryTrie(boolean caseSensitive, int capacity)

Create a Trie

Parameters
caseSensitive:boolean

true if the Trie is insensitive to the case of the key.

capacity:int

The capacity of the Trie, which is in the worst case is the total number of characters of all keys stored in the Trie.

Annotations
@SuppressWarnings:unchecked
See Also
AbstractTrie#requiredCapacity(Set, boolean)

Method Detail

clearback to summary
public void clear()

Implements org.eclipse.jetty.util.Index.Mutable.clear.

Doc from org.eclipse.jetty.util.Index.Mutable.clear.

Remove all entries from the index.

Annotations
@Override
dumpback to summary
public void dump()
entrySetback to summary
public Set<Map.Entry<String, V>> entrySet()
getback to summary
public V get(String s, int offset, int len)

Implements org.eclipse.jetty.util.Index.get.

Doc from org.eclipse.jetty.util.Index.get.

Get an exact match from a String key

Parameters
s:String

The key

offset:int

The offset within the string of the key

len:int

the length of the key

Returns:V

the value for the string / offset / length

Annotations
@Override
getback to summary
public V get(ByteBuffer b, int offset, int len)

Implements org.eclipse.jetty.util.Index.get.

Doc from org.eclipse.jetty.util.Index.get.

Get an exact match from a segment of a ByteBuffer as key

Parameters
b:ByteBuffer

The buffer

offset:int

The offset within the buffer of the key

len:int

the length of the key

Returns:V

The value or null if not found

Annotations
@Override
getBestback to summary
public V getBest(String s)

Overrides org.eclipse.jetty.util.AbstractTrie.getBest.

Implements org.eclipse.jetty.util.Index.getBest.

Doc from org.eclipse.jetty.util.Index.getBest.

Get the best match from key in a String, which may be a prefix match or an exact match.

Parameters
s:String

The string

Returns:V

The value or null if not found

Annotations
@Override
getBestback to summary
public V getBest(String s, int offset, int length)

Implements org.eclipse.jetty.util.Index.getBest.

Doc from org.eclipse.jetty.util.Index.getBest.

Get the best match from key in a String.

Parameters
s:String

The string

offset:int

The offset within the string of the key

length:int

the length of the key

Returns:V

The value or null if not found

Annotations
@Override
getBestback to summary
private V getBest(int t, String s, int offset, int len)
getBestback to summary
public V getBest(ByteBuffer b, int offset, int len)

Implements org.eclipse.jetty.util.Index.getBest.

Doc from org.eclipse.jetty.util.Index.getBest.

Get the best match from key in a byte buffer. The key is assumed to by ISO_8859_1 characters.

Parameters
b:ByteBuffer

The buffer

offset:int

The offset within the buffer of the key

len:int

the length of the key

Returns:V

The value or null if not found

Annotations
@Override
getBestback to summary
public V getBest(byte[] b, int offset, int len)

Overrides org.eclipse.jetty.util.AbstractTrie.getBest.

Implements org.eclipse.jetty.util.Index.getBest.

Doc from org.eclipse.jetty.util.Index.getBest.

Get the best match from key in a byte array. The key is assumed to by ISO_8859_1 characters.

Parameters
b:byte[]

The buffer

offset:int

The offset within the array of the key

len:int

the length of the key

Returns:V

The value or null if not found

Annotations
@Override
getBestback to summary
private V getBest(int t, byte[] b, int offset, int len)
getBestback to summary
private V getBest(int t, ByteBuffer b, int offset, int len)
hiloback to summary
public static int hilo(int diff)
isEmptyback to summary
public boolean isEmpty()

Implements org.eclipse.jetty.util.Index.isEmpty.

Doc from org.eclipse.jetty.util.Index.isEmpty.

Check if the index contains any entry.

Returns:boolean

true if the index does not contain any entry.

keySetback to summary
public Set<String> keySet()

Implements org.eclipse.jetty.util.Index.keySet.

Doc from org.eclipse.jetty.util.Index.keySet.

Get a Set of the keys contained in this index.

Returns:Set<String>

a Set of the keys contained in this index.

Annotations
@Override
putback to summary
public boolean put(String s, V v)

Implements org.eclipse.jetty.util.Index.Mutable.put.

Doc from org.eclipse.jetty.util.Index.Mutable.put.

Put an entry into the index.

Parameters
s:String

The key for the entry. Must be non null, but can be empty.

v:V

The value of the entry. Must be non null.

Returns:boolean

True if the index had capacity to add the field.

Annotations
@Override
sizeback to summary
public int size()

Implements org.eclipse.jetty.util.Index.size.

Doc from org.eclipse.jetty.util.Index.size.

Get the number of entries in the index.

Returns:int

the index' entries count.

toStringback to summary
public String toString()

Overrides java.lang.Object.toString.

Doc from java.lang.Object.toString.

Returns a string representation of the object.

Returns:String

a string representation of the object.

Annotations
@Override
org.eclipse.jetty.util back to summary

public Class ArrayTernaryTrie.Growing<V>

extends AbstractTrie<V>
Class Inheritance
Annotations
@Deprecated

Deprecated

Field Summary

Modifier and TypeField and Description
private final int
_growby

private ArrayTernaryTrie<V>
_trie

Deprecated as a consequence of ArrayTernaryTrie being deprecated.
Inherited from org.eclipse.jetty.util.AbstractTrie:
_caseSensitive

Constructor Summary

AccessConstructor and Description
public
Growing(boolean insensitive, int capacity, int growby)

Method Summary

Modifier and TypeMethod and Description
public void
clear()

Implements org.eclipse.jetty.util.Index.Mutable.clear.

Remove all entries from the index.
public void
dump()

public boolean
equals(Object
the reference object with which to compare.
o)

Overrides java.lang.Object.equals.

Indicates whether some other object is "equal to" this one.
public V
get(String
The key
s)

Overrides org.eclipse.jetty.util.AbstractTrie.get.

Implements org.eclipse.jetty.util.Index.get.

Get an exact match from a String key
public V
get(ByteBuffer
The buffer
b)

Overrides org.eclipse.jetty.util.AbstractTrie.get.

Implements org.eclipse.jetty.util.Index.get.

Get an exact match from a segment of a ByteBuffer as key
public V
get(String
The key
s, int
The offset within the string of the key
offset, int
the length of the key
len)

Implements org.eclipse.jetty.util.Index.get.

Get an exact match from a String key
public V
get(ByteBuffer
The buffer
b, int
The offset within the buffer of the key
offset, int
the length of the key
len)

Implements org.eclipse.jetty.util.Index.get.

Get an exact match from a segment of a ByteBuffer as key
public V
getBest(byte[]
The buffer
b, int
The offset within the array of the key
offset, int
the length of the key
len)

Overrides org.eclipse.jetty.util.AbstractTrie.getBest.

Implements org.eclipse.jetty.util.Index.getBest.

Get the best match from key in a byte array.
public V
getBest(String
The string
s)

Overrides org.eclipse.jetty.util.AbstractTrie.getBest.

Implements org.eclipse.jetty.util.Index.getBest.

Get the best match from key in a String, which may be a prefix match or an exact match.
public V
getBest(String
The string
s, int
The offset within the string of the key
offset, int
the length of the key
length)

Implements org.eclipse.jetty.util.Index.getBest.

Get the best match from key in a String.
public V
getBest(ByteBuffer
The buffer
b, int
The offset within the buffer of the key
offset, int
the length of the key
len)

Implements org.eclipse.jetty.util.Index.getBest.

Get the best match from key in a byte buffer.
public int
hashCode()

Overrides java.lang.Object.hashCode.

Returns a hash code value for the object.
public boolean
isEmpty()

Implements org.eclipse.jetty.util.Index.isEmpty.

Check if the index contains any entry.
public Set<String>
keySet()

Implements org.eclipse.jetty.util.Index.keySet.

Get a Set of the keys contained in this index.
public boolean
put(V
The value and key
v)

Overrides org.eclipse.jetty.util.AbstractTrie.put.

Implements org.eclipse.jetty.util.Index.Mutable.put.

Put a value as both a key and a value.
public boolean
put(String
The key for the entry. Must be non null, but can be empty.
s, V
The value of the entry. Must be non null.
v)

Implements org.eclipse.jetty.util.Index.Mutable.put.

Put an entry into the index.
public V
remove(String
The key for the entry
s)

Overrides org.eclipse.jetty.util.AbstractTrie.remove.

Implements org.eclipse.jetty.util.Index.Mutable.remove.

Remove an entry from the index.
public int
size()

Implements org.eclipse.jetty.util.Index.size.

Get the number of entries in the index.
public String
toString()

Overrides java.lang.Object.toString.

Returns a string representation of the object.
Inherited from org.eclipse.jetty.util.AbstractTrie:
isCaseInsensitiveisCaseSensitiveputAllrequiredCapacity

Field Detail

_growbyback to summary
private final int _growby
_trieback to summary
private ArrayTernaryTrie<V> _trie

Deprecated

as a consequence of ArrayTernaryTrie being deprecated. See corresponding docs for further information.

Constructor Detail

Growingback to summary
public Growing(boolean insensitive, int capacity, int growby)

Method Detail

clearback to summary
public void clear()

Implements org.eclipse.jetty.util.Index.Mutable.clear.

Doc from org.eclipse.jetty.util.Index.Mutable.clear.

Remove all entries from the index.

Annotations
@Override
dumpback to summary
public void dump()
equalsback to summary
public boolean equals(Object o)

Overrides java.lang.Object.equals.

Doc from java.lang.Object.equals.

Indicates whether some other object is "equal to" this one.

The equals method implements an equivalence relation on non-null object references:

  • It is reflexive: for any non-null reference value x, x.equals(x) should return true.
  • It is symmetric: for any non-null reference values x and y, x.equals(y) should return true if and only if y.equals(x) returns true.
  • It is transitive: for any non-null reference values x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) should return true.
  • It is consistent: for any non-null reference values x and y, multiple invocations of x.equals(y) consistently return true or consistently return false, provided no information used in equals comparisons on the objects is modified.
  • For any non-null reference value x, x.equals(null) should return false.

An equivalence relation partitions the elements it operates on into equivalence classes; all the members of an equivalence class are equal to each other. Members of an equivalence class are substitutable for each other, at least for some purposes.

Parameters
o:Object

the reference object with which to compare.

Returns:boolean

true if this object is the same as the obj argument; false otherwise.

Annotations
@Override
getback to summary
public V get(String s)

Overrides org.eclipse.jetty.util.AbstractTrie.get.

Implements org.eclipse.jetty.util.Index.get.

Doc from org.eclipse.jetty.util.Index.get.

Get an exact match from a String key

Parameters
s:String

The key

Returns:V

the value for the string key

Annotations
@Override
getback to summary
public V get(ByteBuffer b)

Overrides org.eclipse.jetty.util.AbstractTrie.get.

Implements org.eclipse.jetty.util.Index.get.

Doc from org.eclipse.jetty.util.Index.get.

Get an exact match from a segment of a ByteBuffer as key

Parameters
b:ByteBuffer

The buffer

Returns:V

The value or null if not found

Annotations
@Override
getback to summary
public V get(String s, int offset, int len)

Implements org.eclipse.jetty.util.Index.get.

Doc from org.eclipse.jetty.util.Index.get.

Get an exact match from a String key

Parameters
s:String

The key

offset:int

The offset within the string of the key

len:int

the length of the key

Returns:V

the value for the string / offset / length

Annotations
@Override
getback to summary
public V get(ByteBuffer b, int offset, int len)

Implements org.eclipse.jetty.util.Index.get.

Doc from org.eclipse.jetty.util.Index.get.

Get an exact match from a segment of a ByteBuffer as key

Parameters
b:ByteBuffer

The buffer

offset:int

The offset within the buffer of the key

len:int

the length of the key

Returns:V

The value or null if not found

Annotations
@Override
getBestback to summary
public V getBest(byte[] b, int offset, int len)

Overrides org.eclipse.jetty.util.AbstractTrie.getBest.

Implements org.eclipse.jetty.util.Index.getBest.

Doc from org.eclipse.jetty.util.Index.getBest.

Get the best match from key in a byte array. The key is assumed to by ISO_8859_1 characters.

Parameters
b:byte[]

The buffer

offset:int

The offset within the array of the key

len:int

the length of the key

Returns:V

The value or null if not found

Annotations
@Override
getBestback to summary
public V getBest(String s)

Overrides org.eclipse.jetty.util.AbstractTrie.getBest.

Implements org.eclipse.jetty.util.Index.getBest.

Doc from org.eclipse.jetty.util.Index.getBest.

Get the best match from key in a String, which may be a prefix match or an exact match.

Parameters
s:String

The string

Returns:V

The value or null if not found

Annotations
@Override
getBestback to summary
public V getBest(String s, int offset, int length)

Implements org.eclipse.jetty.util.Index.getBest.

Doc from org.eclipse.jetty.util.Index.getBest.

Get the best match from key in a String.

Parameters
s:String

The string

offset:int

The offset within the string of the key

length:int

the length of the key

Returns:V

The value or null if not found

Annotations
@Override
getBestback to summary
public V getBest(ByteBuffer b, int offset, int len)

Implements org.eclipse.jetty.util.Index.getBest.

Doc from org.eclipse.jetty.util.Index.getBest.

Get the best match from key in a byte buffer. The key is assumed to by ISO_8859_1 characters.

Parameters
b:ByteBuffer

The buffer

offset:int

The offset within the buffer of the key

len:int

the length of the key

Returns:V

The value or null if not found

Annotations
@Override
hashCodeback to summary
public int hashCode()

Overrides java.lang.Object.hashCode.

Doc from java.lang.Object.hashCode.

Returns a hash code value for the object. This method is supported for the benefit of hash tables such as those provided by java.util.HashMap.

The general contract of hashCode is:

  • Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
  • If two objects are equal according to the equals method, then calling the hashCode method on each of the two objects must produce the same integer result.
  • It is not required that if two objects are unequal according to the equals method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.
Returns:int

a hash code value for this object.

Annotations
@Override
isEmptyback to summary
public boolean isEmpty()

Implements org.eclipse.jetty.util.Index.isEmpty.

Doc from org.eclipse.jetty.util.Index.isEmpty.

Check if the index contains any entry.

Returns:boolean

true if the index does not contain any entry.

keySetback to summary
public Set<String> keySet()

Implements org.eclipse.jetty.util.Index.keySet.

Doc from org.eclipse.jetty.util.Index.keySet.

Get a Set of the keys contained in this index.

Returns:Set<String>

a Set of the keys contained in this index.

Annotations
@Override
putback to summary
public boolean put(V v)

Overrides org.eclipse.jetty.util.AbstractTrie.put.

Implements org.eclipse.jetty.util.Index.Mutable.put.

Doc from org.eclipse.jetty.util.Index.Mutable.put.

Put a value as both a key and a value.

Parameters
v:V

The value and key

Returns:boolean

True if the Trie had capacity to add the field.

Annotations
@Override
putback to summary
public boolean put(String s, V v)

Implements org.eclipse.jetty.util.Index.Mutable.put.

Doc from org.eclipse.jetty.util.Index.Mutable.put.

Put an entry into the index.

Parameters
s:String

The key for the entry. Must be non null, but can be empty.

v:V

The value of the entry. Must be non null.

Returns:boolean

True if the index had capacity to add the field.

Annotations
@Override
removeback to summary
public V remove(String s)

Overrides org.eclipse.jetty.util.AbstractTrie.remove.

Implements org.eclipse.jetty.util.Index.Mutable.remove.

Doc from org.eclipse.jetty.util.Index.Mutable.remove.

Remove an entry from the index.

Parameters
s:String

The key for the entry

Returns:V

The removed value of the entry

Annotations
@Override
sizeback to summary
public int size()

Implements org.eclipse.jetty.util.Index.size.

Doc from org.eclipse.jetty.util.Index.size.

Get the number of entries in the index.

Returns:int

the index' entries count.

toStringback to summary
public String toString()

Overrides java.lang.Object.toString.

Doc from java.lang.Object.toString.

Returns a string representation of the object.

Returns:String

a string representation of the object.

Annotations
@Override