Package com.google.thirdparty.publicsuffix

Class PublicSuffixTrie

  • @GwtCompatible
public final class PublicSuffixTrie
extends java.lang.Object
    A memory-efficient binary trie structure for public suffix lookups. The trie is stored as a series of 16-bit characters in a String.

    The trie data is stored in a CharSequence where each node takes 3 characters:

    1. The offset of the label in the stringPool.
    2. The index of the first child node in the trieData.
    3. A bitfield containing:
      • Bits 0-10: Number of children.
      • Bit 11: Whether this node represents an exclusion (!rule).
      • Bits 12-13: The type of wildcard match (*.rule) at this node (0=none, 1=REGISTRY, 2=PRIVATE).
      • Bits 14-15: The type of exact match (rule) at this node (0=none, 1=REGISTRY, 2=PRIVATE).

    The stringPool stores the labels of the nodes as length-prefixed strings.

    Capacity Limits and Scalability:

    • Total nodes: 65535 (16-bit index in the trie)
    • String pool size: 65535 characters (16-bit offset in the String Pool)
    • Max children per node: 2047 (11-bit count in the bitfield)

    As of Jan 2026, the capacity usage is approximately:

    • Total nodes: ~16% (10k / 65k)
    • String pool size: ~79% (52k / 65k)
    • Max children per node: ~71% (1.5k / 2k)

    If any of these limits are exceeded, the definitive solution is to increase the node size from 3 to 4 characters. This would allow:

    • A full 32-bit offset for the String Pool (using 2 characters).
    • A full 16-bit child count (using the freed bits from the 4th character).

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      int findSuffixIndex​(java.util.List<java.lang.String> labels)
      Performs a lookup for the public suffix of the given labels, considering all public suffix types.
      int findSuffixIndex​(java.util.List<java.lang.String> labels, @Nullable PublicSuffixType desiredType)
      Performs a lookup for the public suffix of the given labels and returns the index of the leftmost label in the public suffix.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Method Detail

      • findSuffixIndex

        public int findSuffixIndex​(java.util.List<java.lang.String> labels)
        Performs a lookup for the public suffix of the given labels, considering all public suffix types. Returns the index of the leftmost label in the public suffix, or -1 if no match found.
        Parameters:
        labels - the domain labels, from left to right.
        Returns:
        the index of the leftmost label in the public suffix, or -1 if not found.

      • findSuffixIndex

        public int findSuffixIndex​(java.util.List<java.lang.String> labels,
                           @Nullable PublicSuffixType desiredType)
        Performs a lookup for the public suffix of the given labels and returns the index of the leftmost label in the public suffix. Returns -1 if no match found.
        Parameters:
        labels - the domain labels, from left to right.
        desiredType - the desired type of public suffix (e.g. REGISTRY or PRIVATE). If null, any PublicSuffixType will be considered a match.
        Returns:
        the index of the leftmost label in the public suffix, or -1 if not found.