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.

  • Field Details

    • LO

      private static int LO
    • EQ

      private static int EQ
    • HI

      private static int HI
    • ROW_SIZE

      private static final int ROW_SIZE
      The Size of a Trie row is the char, and the low, equal and high child pointers
      See Also:
    • _tree

      private final char[] _tree
      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.
    • _key

      private final String[] _key
      The key (if any) for a Trie row. A row may be a leaf, a node or both in the Trie tree.
    • _value

      private final V[] _value
      The value (if any) for a Trie row. A row may be a leaf, a node or both in the Trie tree.
    • _rows

      private char _rows
      The number of rows allocated
  • Constructor Details

    • 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 Details

    • 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(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(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

      private V getBest(int t, String s, int offset, int len)
    • 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(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

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

      private V getBest(int t, ByteBuffer b, int offset, int len)
    • toString

      public String toString()
      Overrides:
      toString in class Object
    • keySet

      public Set<String> keySet()
    • size

      public int size()
    • isEmpty

      public boolean isEmpty()
    • entrySet

      public Set<Map.Entry<String,V>> entrySet()
    • isFull

      public boolean isFull()
    • hilo

      public static int hilo(int diff)
    • dump

      public void dump()