Package org.eclipse.jetty.util

Class ArrayTernaryTrie<V>

java.lang.Object

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

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

Type Parameters:

V - the Entry type

All Implemented Interfaces:

Trie<V>

public class ArrayTernaryTrie<V>
extends AbstractTrie<V>

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 Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	ArrayTernaryTrie.Growing<V>

Field Summary

Fields

Modifier and Type	Field	Description
static int	MAX_CAPACITY	The maximum capacity of the implementation.

Constructor Summary

Constructors

Constructor	Description
ArrayTernaryTrie()	Create a case insensitive Trie of default capacity.
ArrayTernaryTrie(boolean insensitive)	Create a Trie of default capacity
ArrayTernaryTrie(boolean insensitive, int capacity)	Create a Trie
ArrayTernaryTrie(int capacity)	Create a case insensitive Trie
ArrayTernaryTrie(ArrayTernaryTrie<V> trie, double factor)	Copy Trie and change capacity by a factor

Method Summary

Modifier and Type	Method	Description
void	clear()
void	dump()
java.util.Set<java.util.Map.Entry<java.lang.String,V>>	entrySet()
V	get(java.lang.String s, int offset, int len)	Get an exact match from a String key
V	get(java.nio.ByteBuffer b, int offset, int len)	Get an exact match from a segment of a ByteBuufer as key
V	getBest(byte[] b, int offset, int len)	Get the best match from key in a byte array.
V	getBest(java.lang.String s)	Get the best match from key in a String.
V	getBest(java.lang.String s, int offset, int length)	Get the best match from key in a String.
V	getBest(java.nio.ByteBuffer b, int offset, int len)	Get the best match from key in a byte buffer.
static int	hilo(int diff)
boolean	isEmpty()
boolean	isFull()
java.util.Set<java.lang.String>	keySet()
boolean	put(java.lang.String s, V v)	Put an entry into the Trie
int	size()
java.lang.String	toString()

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

get, get, isCaseInsensitive, put, remove

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.eclipse.jetty.util.Trie

getBest, getBest

Field Detail

MAX_CAPACITY

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

See Also:

Constant Field Values

Constructor Detail

ArrayTernaryTrie

public ArrayTernaryTrie()

Create a case insensitive Trie of default capacity.

ArrayTernaryTrie

public ArrayTernaryTrie(boolean insensitive)

Create a Trie of default capacity

Parameters:

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

ArrayTernaryTrie

public ArrayTernaryTrie(int capacity)

Create a case insensitive Trie

Parameters:

capacity - The capacity of the Trie, which is in 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".

ArrayTernaryTrie

public ArrayTernaryTrie(boolean insensitive,
                        int capacity)

Create a Trie

Parameters:

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

capacity - The capacity of the Trie, which is in 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".

ArrayTernaryTrie

public ArrayTernaryTrie(ArrayTernaryTrie<V> trie,
                        double factor)

Copy Trie and change capacity by a factor

Parameters:

trie - the trie to copy from

factor - the factor to grow the capacity by

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(java.lang.String s)

Description copied from interface: Trie

Get the best match from key in a String.

Specified by:

getBest in interface Trie<V>

Overrides:

getBest in class AbstractTrie<V>

Parameters:

s - The string

Returns:

The value or null if not found

getBest

public V getBest(java.lang.String s,
                 int offset,
                 int length)

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

length - 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

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

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

keySet

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

size

public int size()

isEmpty

public boolean isEmpty()

entrySet

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

isFull

public boolean isFull()

hilo

public static int hilo(int diff)

dump

public void dump()