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

pack-priv Class ArrayTrie<V>

extends AbstractTrie<V>
Class Inheritance
Type Parameters
<V>
the entry type
Imports
java.nio.ByteBuffer, java.util.Arrays, .Map, .Objects, .Set, java.util.stream.Collectors

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 space efficient if the key characters are from ' ', '+', '-', ':', ';', '.', '0' - '9', 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.

Nested and Inner Type Summary

Modifier and TypeClass and Description
private static class
ArrayTrie.Node<
The value type of the node.
V>

A Node in the tree.

Field Summary

Modifier and TypeField and Description
private final int
_bigRowSize

private final int[]
_lookup

private final ArrayTrie.Node<V>[]
_node

private char
_rows

private final char[]
_table

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

private static final int
BIG_ROW_INSENSITIVE

private static final int
BIG_ROW_SENSITIVE

private static final int[]
LOOKUP_INSENSITIVE

The index lookup table, this maps a character as a byte (ISO-8859-1 or UTF8) to a Trie index within a Trie row.

private static final int[]
LOOKUP_SENSITIVE

The index lookup table, this maps a character as a byte (ISO-8859-1 or UTF8) to a Trie index within a Trie row.

public static int
MAX_CAPACITY

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.

private static final int
X

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

Constructor Summary

AccessConstructor and Description
pack-priv
ArrayTrie(int
The capacity of the trie, which at the worst case is the total number of characters of all keys stored in the Trie, plus 1 for the empty key.
capacity)

pack-priv
ArrayTrie(boolean caseSensitive, int capacity)

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
dumpStdErr()

public static <
The value type of the Trie
V> ArrayTrie<V>

Returns:

a Trie containing the contents or null if not possible.
from(int
The maximum capacity of the Trie or -1 for unlimited capacity
capacity, boolean
True if the Trie keys are case sensitive
caseSensitive, Map<String, V>
The known contents of the Trie
contents)

Create a trie from capacity and content

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(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(String
The string
s, int
The offset within the string 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 String.

private V
getBest(int row, String s, int offset, int len)

private V
getBest(int row, byte[] b, int offset, int len)

private V
getBest(int row, ByteBuffer b, int offset, int len)

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.

private int
lookup(int row, char c)

public boolean
put(String
The key for the entry. Must be non null, but can be empty.
key, V
The value of the entry. Must be non null.
value)

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:
getgetgetBestisCaseInsensitiveisCaseSensitiveputputAllremoverequiredCapacity

Field Detail

_bigRowSizeback to summary
private final int _bigRowSize
_lookupback to summary
private final int[] _lookup
_nodeback to summary
private final ArrayTrie.Node<V>[] _node
_rowsback to summary
private char _rows
_tableback to summary
private final char[] _table

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][column], we use _rows[row*ROW_SIZE+column] to look up the next row for a given character. The array is of characters rather than integers to save space.

BIG_ROW_INSENSITIVEback to summary
private static final int BIG_ROW_INSENSITIVE
BIG_ROW_SENSITIVEback to summary
private static final int BIG_ROW_SENSITIVE
LOOKUP_INSENSITIVEback to summary
private static final int[] LOOKUP_INSENSITIVE

The index lookup table, this maps a character as a byte (ISO-8859-1 or UTF8) to a Trie index within a Trie row. Positive values are column indexes within the main _table. Negative values are indexes within a Node#_bigRow. Values of X are not indexed and must be searched for in the extended Node#_bigRow

LOOKUP_SENSITIVEback to summary
private static final int[] LOOKUP_SENSITIVE

The index lookup table, this maps a character as a byte (ISO-8859-1 or UTF8) to a Trie index within a Trie row. Positive values are column indexes within the main _table. Negative values are indexes within a Node#_bigRow. Values of X are not indexed and must be searched for in the extended Node#_bigRow

MAX_CAPACITYback to summary
public static int MAX_CAPACITY
ROW_SIZEback to summary
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.

Xback to summary
private static final int X

Constructor Detail

ArrayTrieback to summary
pack-priv ArrayTrie(int capacity)
Parameters
capacity:int

The capacity of the trie, which at the worst case is the total number of characters of all keys stored in the Trie, plus 1 for the empty key.

See Also
AbstractTrie#requiredCapacity(Set, boolean)
ArrayTrieback to summary
pack-priv ArrayTrie(boolean caseSensitive, int capacity)
Annotations
@SuppressWarnings:unchecked

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
dumpStdErrback to summary
public void dumpStdErr()
fromback to summary
public static <V> ArrayTrie<V> from(int capacity, boolean caseSensitive, Map<String, V> contents)

Create a trie from capacity and content

Parameters
<V>
The value type of the Trie
capacity:int

The maximum capacity of the Trie or -1 for unlimited capacity

caseSensitive:boolean

True if the Trie keys are case sensitive

contents:Map<String, V>

The known contents of the Trie

Returns:ArrayTrie<V>

a Trie containing the contents or null if not possible.

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(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(String s, 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 String.

Parameters
s:String

The string

offset:int

The offset within the string 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 row, String s, int offset, int len)
getBestback to summary
private V getBest(int row, byte[] b, int offset, int len)
getBestback to summary
private V getBest(int row, ByteBuffer b, int offset, int len)
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.

Annotations
@Override
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
lookupback to summary
private int lookup(int row, char c)
putback to summary
public boolean put(String key, V value)

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

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

Put an entry into the index.

Parameters
key:String

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

value: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.

Annotations
@Override
toStringback to summary
public String toString()

Overrides java.lang.Object.toString.

Doc from java.lang.Object.toString.

Returns a string representation of the object. Satisfying this method's contract implies a non-null result must be returned.

Returns:String

a string representation of the object

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

private Class ArrayTrie.Node<V>

extends Object
Class Inheritance
Type Parameters
<V>
The value type of the node.
A Node in the tree. A Node instance is only needed for rows in the _table array that either have a key/value pair or a _bigRow extended row.

Field Summary

Modifier and TypeField and Description
pack-priv char[]
_bigRow

A big row of indexes in which extended characters can be found.

pack-priv String
_key

pack-priv V
_value

Constructor Summary

AccessConstructor and Description
private
Node()

Method Summary

Modifier and TypeMethod and Description
public String
toString()

Overrides java.lang.Object.toString.

Returns a string representation of the object.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAllwaitwaitwait

Field Detail

_bigRowback to summary
pack-priv char[] _bigRow

A big row of indexes in which extended characters can be found. The first ArrayTrie#_bigRowSize entries are accessed by negative indexes from the ArrayTrie#_lookup table. The following entries are character/row pairs that must be searched looking for a match. A big row is dynamically allocated to minimum size required for it's entries.

_keyback to summary
pack-priv String _key
_valueback to summary
pack-priv V _value

Constructor Detail

Nodeback to summary
private Node()

Method Detail

toStringback to summary
public String toString()

Overrides java.lang.Object.toString.

Doc from java.lang.Object.toString.

Returns a string representation of the object. Satisfying this method's contract implies a non-null result must be returned.

Returns:String

a string representation of the object

Annotations
@Override