* the capacity, it is doubled in size unless some other thread
   * holds the lock. If a hashed slot is empty, and lock is
   * available, a new Cell is created. Otherwise, if the slot
   * exists, a CAS is tried.  Retries proceed by "double hashing",
   * using a secondary hash (Marsaglia XorShift) to try to find a
   * free slot.
   *
   * The table size is capped because, when there are more threads

   * the capacity, it is doubled in size unless some other thread
   * holds the lock. If a hashed slot is empty, and lock is
   * available, a new Cell is created. Otherwise, if the slot
   * exists, a CAS is tried.  Retries proceed by "double hashing",
   * using a secondary hash (Marsaglia XorShift) to try to find a
   * free slot.
   *
   * The table size is capped because, when there are more threads

   * the capacity, it is doubled in size unless some other thread
   * holds the lock. If a hashed slot is empty, and lock is
   * available, a new Cell is created. Otherwise, if the slot
   * exists, a CAS is tried.  Retries proceed by "double hashing",
   * using a secondary hash (Marsaglia XorShift) to try to find a
   * free slot.
   *
   * The table size is capped because, when there are more threads

      int hash = element.hashCode();
      for (int j = Hashing.smear(hash); ; j++) {
        int index = j & mask;
        Object value = table[index];
        if (value == null) {
          // Came to an empty slot. Put the element here.
          elements[uniques++] = element;
          table[index] = element;
          hashCode += hash;
          break;
        } else if (value.equals(element)) {
          break;

  static final class Whitespace extends NamedFastMatcher {

    // TABLE is a precomputed hashset of whitespace characters. MULTIPLIER serves as a hash function
    // whose key property is that it maps 25 characters into the 32-slot table without collision.
    // Basically this is an opportunistic fast implementation as opposed to "good code". For most
    // other use-cases, the reduction in readability isn't worth it.
    static final String TABLE =

        // We only ever register ArrayReferences with the queue so this is always safe.
        ArrayReference<? extends L> arrayRef = (ArrayReference<? extends L>) ref;
        // Try to clear out the array slot, n.b. if we fail that is fine, in either case the
        // arrayRef will be out of the array after this step.
        locks.compareAndSet(arrayRef.index, arrayRef, null);
      }
    }

    @Override

    //     fgha[c]|[b]de -> fgha[b]|[c]de. Because these two blocks are the same size, we are done.
    // The Dolphin algorithm is attractive because it does the fewest array reads and writes: each
    // array slot is read and written exactly once. However, it can have very poor memory locality:
    // benchmarking shows it can take 7 times longer than the other two in some cases. The other two

      if (state instanceof Blocker) {
        blocker = (Blocker) state;
      }
      spinCount++;
      if (spinCount > MAX_BUSY_WAIT_SPINS) {
        /*
         * If we have spun a lot, just park ourselves. This will save CPU while we wait for a slow
         * interrupting thread. In theory, interruptTask() should be very fast, but due to
         * InterruptibleChannel and JavaLangAccess.blockedOn(Thread, Interruptible), it isn't

    testExhaustively(Ordering.<String>natural(), "a", "b", "d");
  }

  @GwtIncompatible // too slow
  public void testCombinationsExhaustively_startingFromExplicit() {
    testExhaustively(Ordering.explicit("a", "b", "c", "d"), "a", "b", "d");
  }

  @GwtIncompatible // too slow
  public void testCombinationsExhaustively_startingFromUsingToString() {
    testExhaustively(Ordering.usingToString(), 1, 12, 2);

    testExhaustively(Ordering.<String>natural(), "a", "b", "d");
  }

  @GwtIncompatible // too slow
  public void testCombinationsExhaustively_startingFromExplicit() {
    testExhaustively(Ordering.explicit("a", "b", "c", "d"), "a", "b", "d");
  }

  @GwtIncompatible // too slow
  public void testCombinationsExhaustively_startingFromUsingToString() {
    testExhaustively(Ordering.usingToString(), 1, 12, 2);