org.eclipse.jetty.util

Class TreeTrie<V>

java.lang.Object

org.eclipse.jetty.util.AbstractTrie<V>

org.eclipse.jetty.util.TreeTrie<V>

Type Parameters:

V - the entry type

All Implemented Interfaces:

Trie<V>

public class TreeTrie<V>
extends AbstractTrie<V>

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.

Field Summary

Fields

Modifier and Type	Field and Description
private static int[]	__lookup
private char	_c
private java.lang.String	_key
private TreeTrie<V>[]	_nextIndex
private java.util.List<TreeTrie<V>>	_nextOther
private V	_value
private static int	INDEX

Fields inherited from class org.eclipse.jetty.util.AbstractTrie

_caseInsensitive

Constructor Summary

Constructors

Modifier	Constructor and Description
	TreeTrie()
private	TreeTrie(char c)

Method Summary

Modifier and Type	Method and Description
void	clear()
V	get(java.nio.ByteBuffer b, int offset, int len) Get an exact match from a segment of a ByteBuufer as key
V	get(java.lang.String s, int offset, int len) Get an exact match from a String key
V	getBest(byte[] b, int offset, int len) Get the best match from key in a byte array.
V	getBest(java.nio.ByteBuffer b, int offset, int len) Get the best match from key in a byte buffer.
V	getBest(java.lang.String s, int offset, int len) Get the best match from key in a String.
private V	getBestByteBuffer(java.nio.ByteBuffer b, int offset, int len)
boolean	isFull()
java.util.Set<java.lang.String>	keySet()
private static <V> void	keySet(java.util.Set<java.lang.String> set, TreeTrie<V> t)
boolean	put(java.lang.String s, V v) Put an entry into the Trie
java.lang.String	toString()
private static <V> void	toString(java.lang.Appendable out, TreeTrie<V> t)

Methods inherited from class org.eclipse.jetty.util.AbstractTrie

get, get, getBest, isCaseInsensitive, put, remove

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

__lookup

private static final int[] __lookup

INDEX

private static final int INDEX

See Also:

Constant Field Values

_nextIndex

private final TreeTrie<V>[] _nextIndex

_nextOther

private final java.util.List<TreeTrie<V>> _nextOther

_c

private final char _c

_key

private java.lang.String _key

_value

private V _value

Constructor Detail

TreeTrie

public TreeTrie()

TreeTrie

private TreeTrie(char c)

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 entry

v - 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 key

offset - The offset within the string of the key

len - 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 buffer

offset - The offset within the buffer of the key

len - 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.

Specified by:

getBest in interface Trie<V>

Overrides:

getBest in class AbstractTrie<V>

Parameters:

b - The buffer

offset - The offset within the array of the key

len - 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 string

offset - The offset within the string of the key

len - the length of the key

Returns:

The value or null if not found

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 buffer

offset - The offset within the buffer of the key

len - the length of the key

Returns:

The value or null if not found

getBestByteBuffer

private V getBestByteBuffer(java.nio.ByteBuffer b,
                            int offset,
                            int len)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

toString

private static <V> void toString(java.lang.Appendable out,
                                 TreeTrie<V> t)

keySet

public java.util.Set<java.lang.String> keySet()

keySet

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

isFull

public boolean isFull()