Package org.eclipse.jetty.util

Class ArrayTernaryTrie<V>

  • Type Parameters:
    V - the Entry type
    All Implemented Interfaces:
    Trie<V>
    @Deprecated(since="2021-05-27")
public class ArrayTernaryTrie<V>
extends AbstractTrie<V>
    Deprecated.
    The Eclipse Jetty and Apache Felix Http Jetty packages are no longer supported.

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

    • Constructor Summary

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

    • Method Summary

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

      • Methods inherited from class java.lang.Object

        equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

    • Constructor Detail

      • ArrayTernaryTrie

        public ArrayTernaryTrie()
        Deprecated.
        Create a case insensitive Trie of default capacity.

      • ArrayTernaryTrie

        public ArrayTernaryTrie​(boolean insensitive)
        Deprecated.
        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)
        Deprecated.
        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)
        Deprecated.
        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)
        Deprecated.
        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()
        Deprecated.

      • put

        public boolean put​(java.lang.String s,
                   V v)
        Deprecated.
        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)
        Deprecated.
        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)
        Deprecated.
        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)
        Deprecated.
        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)
        Deprecated.
        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)
        Deprecated.
        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)
        Deprecated.
        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()
        Deprecated.
        Overrides:
        toString in class java.lang.Object

      • keySet

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

      • size

        public int size()
        Deprecated.

      • isEmpty

        public boolean isEmpty()
        Deprecated.

      • entrySet

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

      • isFull

        public boolean isFull()
        Deprecated.

      • hilo

        public static int hilo​(int diff)
        Deprecated.

      • dump

        public void dump()
        Deprecated.