}
  }

  // TODO(fry): Separate logic for consistency between emul and nonemul implementation.
  // TODO(fry): Look into Maps.KeySet and Maps.Values, which can ideally be reused here but are
  // currently only package visible.
  abstract class AbstractCacheSet<T> extends AbstractSet<T> {
    final ConcurrentMap<?, ?> map;

    AbstractCacheSet(ConcurrentMap<?, ?> map) {
      this.map = map;

      Iterable<? extends IteratorFeature> features,
      Iterable<E> expectedElements,
      KnownOrder knownOrder,
      int startIndex) {
    // periodically we should manually try (steps * 3 / 2) here; all tests but
    // one should still pass (testVerifyGetsCalled()).
    stimuli = (Stimulus<E, ? super I>[]) new Stimulus<?, ?>[steps];
    if (!elementsToInsertIterable.iterator().hasNext()) {

      return key;
    } else if (oldEntryForKey != null && !force) {
      throw new IllegalArgumentException("key already present: " + key);
    }

    /*
     * The ordering here is important: if we deleted the key entry and then the value entry,
     * the key entry's prev or next pointer might point to the dead value entry, and when we

    }

    AvlNode<E> add(
        Comparator<? super E> comparator, @ParametricNullness E e, int count, int[] result) {
      /*
       * It speeds things up considerably to unconditionally add count to totalCount here,
       * but that destroys failure atomicity in the case of count overflow. =(
       */
      int cmp = comparator.compare(e, getElement());
      if (cmp < 0) {
        AvlNode<E> initLeft = left;

    assertNull(map.get(unmappedKey));
  }

  public void testGetNull() {
    Map<K, V> map = makeEitherMap();
    if (allowsNullKeys) {
      if (allowsNullValues) {
        // TODO: decide what to test here.
      } else {
        assertEquals(map.containsKey(null), map.get(null) != null);
      }
    } else {
      try {
        map.get(null);
      } catch (NullPointerException optional) {
      }
    }

  private static <E extends @Nullable Object> boolean addAllImpl(
      Multiset<E> self, Multiset<? extends E> elements) {
    // It'd be nice if we could specialize for ImmutableMultiset here without also retaining
    // its code when it's not in scope...
    if (elements instanceof AbstractMapBasedMultiset) {
      return addAllImpl(self, (AbstractMapBasedMultiset<? extends E>) elements);

   * needed.
   *
   * A single spinlock ("busy") is used for initializing and
   * resizing the table, as well as populating slots with new Cells.
   * There is no need for a blocking lock; when the lock is not
   * available, threads try other slots (or the base).  During these
   * retries, there is increased contention and reduced locality,
   * which is still better than alternatives.
   *
   * Per-thread hash codes are initialized to random values.

    try {
      CallerClass2.get(future);
      fail();
    } catch (CancellationException expected) {
      // There should be two CancellationException chained together.  The outer one should have the
      // stack trace of where the get() call was made, and the inner should have the stack trace of
      // where the immediateCancelledFuture() call was made.
      List<StackTraceElement> stackTrace = ImmutableList.copyOf(expected.getStackTrace());

      }
    },
    /**
     * Return {@code ~insertionIndex}, where {@code insertionIndex} is defined as the point at which
     * the key would be inserted into the list: the index of the next higher element in the list, or
     * {@code list.size()} if there is no such element.
     *
     * <p>Note that the return value will be {@code >= 0} if and only if there is an element of the
     * list that compares as equal to the key.
     *

      }
      // re-read value, if we get here then we must have observed a TOMBSTONE while trying to add a
      // waiter.
      // requireNonNull is safe because value is always set before TOMBSTONE.
      return getDoneValue(requireNonNull(value));
    }
    // If we get here then we have remainingNanos < SPIN_THRESHOLD_NANOS and there is no node on the
    // waiters list
    while (remainingNanos > 0) {