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.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private static final int[]
    The index lookup table, this maps a character as a byte (ISO-8859-1 or UTF8) to an index within a Trie row
    private char[][]
    A big index for each row.
    private final String[]
    The key (if any) for a Trie row.
    private final char[]
    The Trie rows in a single array which allows a lookup of row,character to the next row in the Trie.
    private char
    The number of rows allocated
    private final V[]
    The value (if any) for a Trie row.
    private static final int
    The Size of a Trie row is how many characters can be looked up directly without going to a big index.

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

    _caseInsensitive
  • Constructor Summary

    Constructors
    Constructor
    Description
     
    ArrayTrie(int capacity)
     
  • Method Summary

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

    • ROW_SIZE

      private static final int ROW_SIZE
      The Size of a Trie row is how many characters can be looked up directly without going to a big index. This is set at 32 to cover case insensitive alphabet and a few other common characters.
      See Also:
    • __lookup

      private static final int[] __lookup
      The index lookup table, this maps a character as a byte (ISO-8859-1 or UTF8) to an index within a Trie row
    • _rowIndex

      private final char[] _rowIndex
      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. The first ROW_SIZE entries are for row 0, then next ROW_SIZE entries are for row 1 etc. So in general instead of using _rows[row][index], we use _rows[row*ROW_SIZE+index] to look up the next row for a given character. The array is of characters rather than integers to save space.
    • _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.
    • _bigIndex

      private char[][] _bigIndex
      A big index for each row. If a character outside of the lookup map is needed, then a big index will be created for the row, with 256 entries, one for each possible byte.
    • _rows

      private char _rows
      The number of rows allocated
  • Constructor Details

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

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

      private void toString(Appendable out, int t)
    • keySet

      public Set<String> keySet()
    • keySet

      private void keySet(Set<String> set, int t)
    • isFull

      public boolean isFull()