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

pack-priv Class TreeTrie<V>

extends AbstractTrie<V>
Class Inheritance
Type Parameters
<V>
the entry type
Imports
java.io.IOException, java.nio.ByteBuffer, java.util.ArrayList, .Arrays, .HashSet, .List, .Map, .Set
A Trie String lookup data structure using a tree

This implementation is always case insensitive and is optimal for a variable number of fixed strings with few special characters.

This Trie is stored in a Tree and is unlimited in capacity

This Trie is not Threadsafe and contains no mutual exclusion or deliberate memory barriers. It is intended for an TreeTrie 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
TreeTrie.Node<V>

Field Summary

Modifier and TypeField and Description
private final int[]
_lookup

private final TreeTrie.Node<V>
_root

private static final int
INDEX

private static final int[]
LOOKUP_INSENSITIVE

private static final int[]
LOOKUP_SENSITIVE

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

Constructor Summary

AccessConstructor and Description
pack-priv
TreeTrie()

pack-priv
TreeTrie(boolean caseSensitive)

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 static <
The value type of the Trie
V> AbstractTrie<V>

Returns:

a Trie containing the contents or null if not possible.
from(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.

private V
getBest(TreeTrie.Node<V> node, byte[] b, int offset, int len)

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(TreeTrie.Node<V> node, 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.

private V
getBest(TreeTrie.Node<V> node, ByteBuffer b, int offset, int len)

public boolean
isEmpty()

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

Check if the index contains any entry.

private boolean
isEmpty(TreeTrie.Node<V> t)

public Set<String>
keySet()

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

Get a Set of the keys contained in this index.

private static <V> void
keySet(Set<String> set, TreeTrie.Node<V> t)

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.

private static <V> void
toString(Appendable out, TreeTrie.Node<V> t, String separator)

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

Field Detail

_lookupback to summary
private final int[] _lookup
_rootback to summary
private final TreeTrie.Node<V> _root
INDEXback to summary
private static final int INDEX
LOOKUP_INSENSITIVEback to summary
private static final int[] LOOKUP_INSENSITIVE
LOOKUP_SENSITIVEback to summary
private static final int[] LOOKUP_SENSITIVE

Constructor Detail

TreeTrieback to summary
pack-priv TreeTrie()
Annotations
@SuppressWarnings:unchecked
TreeTrieback to summary
pack-priv TreeTrie(boolean caseSensitive)

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
fromback to summary
public static <V> AbstractTrie<V> from(boolean caseSensitive, Map<String, V> contents)

Create a trie from capacity and content

Parameters
<V>
The value type of the Trie
caseSensitive:boolean

True if the Trie keys are case sensitive

contents:Map<String, V>

The known contents of the Trie

Returns:AbstractTrie<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
private V getBest(TreeTrie.Node<V> node, byte[] b, int offset, int len)
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(TreeTrie.Node<V> node, 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
private V getBest(TreeTrie.Node<V> node, 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
isEmptyback to summary
private boolean isEmpty(TreeTrie.Node<V> t)
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
keySetback to summary
private static <V> void keySet(Set<String> set, TreeTrie.Node<V> t)
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.

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
toStringback to summary
private static <V> void toString(Appendable out, TreeTrie.Node<V> t, String separator)
org.eclipse.jetty.util back to summary

private Class TreeTrie.Node<V>

extends Object
Class Inheritance

Field Summary

Modifier and TypeField and Description
private final char
_c

private String
_key

private final TreeTrie.Node<V>[]
_nextIndex

private final List<TreeTrie.Node<V>>
_nextOther

private V
_value

Constructor Summary

AccessConstructor and Description
private
Node(char c)

Method Summary

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

_cback to summary
private final char _c
_keyback to summary
private String _key
_nextIndexback to summary
private final TreeTrie.Node<V>[] _nextIndex
_nextOtherback to summary
private final List<TreeTrie.Node<V>> _nextOther
_valueback to summary
private V _value

Constructor Detail

Nodeback to summary
private Node(char c)
Annotations
@SuppressWarnings:unchecked