org.eclipse.jetty.util

Class ArrayTrie<V>

java.lang.Object

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

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

Type Parameters:

V - the entry type

All Implemented Interfaces:

Trie<V>

public class ArrayTrie<V>
extends AbstractTrie<V>

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

Constructor Summary

Constructors

Constructor and Description
ArrayTrie()
ArrayTrie(int capacity)

Method Summary

Modifier and Type	Method and Description
void	clear()
V	get(ByteBuffer b, int offset, int len) Get an exact match from a segment of a ByteBuufer as key
V	get(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(ByteBuffer b, int offset, int len) Get the best match from key in a byte buffer.
V	getBest(String s, int offset, int len) Get the best match from key in a String.
boolean	isFull()
Set<String>	keySet()
boolean	put(String s, V v) Put an entry into the Trie
String	toString()

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

Constructor Detail

ArrayTrie

public ArrayTrie()

ArrayTrie

public ArrayTrie(int capacity)

Parameters:

capacity - The capacity of the trie, which at 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".

Method Detail

clear

public void clear()

put

public boolean put(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(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(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(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

getBest

public V getBest(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

toString

public String toString()

Overrides:

toString in class Object

keySet

public Set<String> keySet()

isFull

public boolean isFull()