Package org.antlr.v4.runtime.dfa

Class HashEdgeMap<T>

java.lang.Object
org.antlr.v4.runtime.dfa.AbstractEdgeMap<T>
org.antlr.v4.runtime.dfa.HashEdgeMap<T>
All Implemented Interfaces:
EdgeMap<T>
public final class HashEdgeMap<T> extends AbstractEdgeMap<T>
Sparse open-addressed edge map used while a DFA state has only a few outgoing edges. Grows by doubling and promotes to ArrayEdgeMap when density approaches half of the allowed symbol range.

PERF: isEmpty() / size() are O(1) via a retained occupancy counter (updated only under the same monitor as structural mutations). toMap() remains a cold diagnostic path (sorted TreeMap for stable DFASerializer output); hot emptiness checks must use isEmpty() directly rather than toMap().isEmpty().

Lexer maps whose keys all lie in [0, tableLength) may be stored identity-indexed (isDirectIndex()). get(int) does not branch on that layout — parser maps stay on the hashed probe. DFAState publishes directArray() for the lexer hot path.

  • Field Details

    • DEFAULT_MAX_SIZE

      private static final int DEFAULT_MAX_SIZE
      Initial open-addressed table length (power of two). Raised from 2 to 8 so the common "handful of outgoing edges" case (parser token edges, short lexer loops) avoids collision-driven resize churn on the first few put(int, T) calls. Tables still promote to ArrayEdgeMap once density approaches half of the allowed symbol range.
      See Also:

    • keys

      private final AtomicIntegerArray keys

    • values

      private final T[] values

    • size

      private final AtomicInteger size
      Number of non-null slots. Updated only inside synchronized (this) mutation paths; read without the monitor for O(1) size() / isEmpty() (same visibility model as ArrayEdgeMap).

    • directIndex

      private final boolean directIndex
      When true, slot i holds key i and getDirect(int) is a plain array load. Final: an out-of-range put(int, T) publishes a new hashed map rather than flipping this flag. Public constructors stay hashed so the first inserts mutate in place. Parser maps (minIndex < 0, EOF is a key) never set this.

  • Constructor Details

    • HashEdgeMap

      public HashEdgeMap(int minIndex, int maxIndex)

    • HashEdgeMap

      public HashEdgeMap(int minIndex, int maxIndex, int maxSparseSize)

    • HashEdgeMap

      private HashEdgeMap(@NotNull HashEdgeMap<T> map, int maxSparseSize)

    • HashEdgeMap

      private HashEdgeMap(@NotNull HashEdgeMap<T> map, int maxSparseSize, boolean allowDirect)

  • Method Details

    • isDirectIndex

      boolean isDirectIndex()
      Identity-indexed lexer layout. Package-private; not part of the public API.

    • tableLength

      int tableLength()
      Table length. Package-private; used by tests and getDirect(int).

    • directArray

      Object[] directArray()
      Values array for an identity-indexed map, or null when this map is hashed. Slot i holds key i. Package-private.

    • getDirect

      final T getDirect(int key)
      Identity lookup. Valid only when isDirectIndex() is true. Keys outside [0, tableLength) miss. Does not read the key word, so a hashed map must not be queried through this method.

    • keysFit

      private static boolean keysFit(HashEdgeMap<?> src, int length)

    • bucket

      private static int bucket(int length, int key)

    • bucket

      private int bucket(int key)

    • getKeys

      @NotNull AtomicIntegerArray getKeys()

    • getValues

      @NotNull T[] getValues()

    • size

      public int size()

    • isEmpty

      public boolean isEmpty()

    • containsKey

      public boolean containsKey(int key)

    • get

      public T get(int key)

    • put

      public AbstractEdgeMap<T> put(int key, T value)
      Specified by:
      put in interface EdgeMap<T>
      Specified by:
      put in class AbstractEdgeMap<T>

    • remove

      public HashEdgeMap<T> remove(int key)
      Specified by:
      remove in interface EdgeMap<T>
      Specified by:
      remove in class AbstractEdgeMap<T>

    • clear

      public AbstractEdgeMap<T> clear()
      Specified by:
      clear in interface EdgeMap<T>
      Specified by:
      clear in class AbstractEdgeMap<T>

    • toMap

      public Map<Integer,T> toMap()

    • entrySet

      public Set<Map.Entry<Integer,T>> entrySet()