Package org.eclipse.jetty.util

Class 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 Description
      ArrayTrie()  
      ArrayTrie​(int capacity)  

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void clear()  
      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, int offset, int len)
      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.
      boolean isFull()  
      java.util.Set<java.lang.String> keySet()  
      boolean put​(java.lang.String s, V v)
      Put an entry into the Trie
      java.lang.String toString()  

      • 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​(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​(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​(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​(java.lang.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 java.lang.String toString()
        Overrides:
        toString in class java.lang.Object

      • keySet

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

      • isFull

        public boolean isFull()