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 Details

    • LOOKUP

      private static final int[] LOOKUP
    • INDEX

      private static final int INDEX
      See Also:
    • _nextIndex

      private final TreeTrie<V>[] _nextIndex
    • _nextOther

      private final List<TreeTrie<V>> _nextOther
    • _c

      private final char _c
    • _key

      private String _key
    • _value

      private V _value
  • Constructor Details

    • TreeTrie

      public TreeTrie()
    • TreeTrie

      private TreeTrie(char c)
  • 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(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(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(ByteBuffer b, int offset, int len)
    • toString

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

      private static <V> void toString(Appendable out, TreeTrie<V> t)
    • keySet

      public Set<String> keySet()
    • keySet

      private static <V> void keySet(Set<String> set, TreeTrie<V> t)
    • isFull

      public boolean isFull()