Class Machine

java/com/google/re2j/Machine.java:18–445

//
// Called by RE2.doExecute.
class Machine {

  // A logical thread in the NFA.
  private static class Thread {
    Thread(int n) {
      this.cap = new int[n];
    }

    int[] cap;
    Inst inst;
  }

  // A queue is a 'sparse array' holding pending threads of execution.  See:
  // research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html
  private static class Queue {

    final Thread[] denseThreads; // may contain stale Thread in slots >= size
    final int[] densePcs; // may contain stale pc in slots >= size
    final int[] sparse; // may contain stale but in-bounds values.
    int size; // of prefix of |dense| that is logically populated

    Queue(int n) {
      this.sparse = new int[n];
      this.densePcs = new int[n];
      this.denseThreads = new Thread[n];
    }

    boolean contains(int pc) {
      int j = sparse[pc];
      return j < size && densePcs[j] == pc;
    }

    boolean isEmpty() {
      return size == 0;
    }

    int add(int pc) {
      int j = size++;
      sparse[pc] = j;
      denseThreads[j] = null;
      densePcs[j] = pc;
      return j;
    }

    void clear() {
      size = 0;
    }

    @Override
    public String toString() {
      StringBuilder out = new StringBuilder();
      out.append('{');
      for (int i = 0; i < size; ++i) {
        if (i != 0) {
          out.append(", ");
        }
        out.append(densePcs[i]);
      }