* {@link #unmodifiableKeySet()}. By design, the cache is cleared when this structure is mutated. If
 * this structure is never mutated, it provides a thread-safe view of the backing map.
 *
 * <p>The {@link MapIteratorCache} assumes ownership of the backing map, and cannot guarantee
 * correctness in the face of external mutations to the backing map. As such, it is <b>strongly</b>

/** Tests for {@link MapIteratorCache} and {@link MapRetrievalCache}. */
@AndroidIncompatible
// TODO(cpovirk): Figure out Android JUnit 4 support. Does it work with Gingerbread? @RunWith?
@RunWith(Parameterized.class)
public final class MapCacheTest {
  private final MapIteratorCache<String, String> mapCache;

  public MapCacheTest(MapIteratorCache<String, String> mapCache) {
    this.mapCache = mapCache;
  }

  private final ElementOrder<E> edgeOrder;

  final MapIteratorCache<N, NetworkConnections<N, E>> nodeConnections;

  // We could make this a Map<E, EndpointPair<N>>. It would make incidentNodes(edge) slightly
  // faster, but also make Networks consume 5 to 20+% (increasing with average degree) more memory.
  final MapIteratorCache<E, N> edgeToReferenceNode; // referenceNode == source if directed

/** Tests for {@link MapIteratorCache} and {@link MapRetrievalCache}. */
@AndroidIncompatible
// TODO(cpovirk): Figure out Android JUnit 4 support. Does it work with Gingerbread? @RunWith?
@RunWith(Parameterized.class)
public final class MapCacheTest {
  private final MapIteratorCache<String, String> mapCache;

  public MapCacheTest(MapIteratorCache<String, String> mapCache) {
    this.mapCache = mapCache;
  }

import javax.annotation.CheckForNull;

/**
 * A {@link MapIteratorCache} that adds additional caching. In addition to the caching provided by
 * {@link MapIteratorCache}, this structure caches values for the two most recently retrieved keys.
 *
 * @author James Sexton
 */
@ElementTypesAreNonnullByDefault
final class MapRetrievalCache<K, V> extends MapIteratorCache<K, V> {
  // See the note about volatile in the superclass.

@ElementTypesAreNonnullByDefault
class StandardValueGraph<N, V> extends AbstractValueGraph<N, V> {
  private final boolean isDirected;
  private final boolean allowsSelfLoops;
  private final ElementOrder<N> nodeOrder;

  final MapIteratorCache<N, GraphConnections<N, V>> nodeConnections;

  long edgeCount; // must be updated when edges are added or removed

  /** Constructs a graph with the properties specified in {@code builder}. */

     * The real purpose of this test is to produce a TSAN failure if MapIteratorCache is unsafe for
     * reads from multiple threads -- unsafe, in fact, even in the absence of a concurrent write.
     * The specific problem we had was unsafe reads of lastEntryReturnedBySomeIterator. (To fix the
     * problem, we've since marked that field as volatile.)
     *
     * When MapIteratorCache is used from Immutable* classes, the TSAN failure doesn't indicate a

     * The real purpose of this test is to produce a TSAN failure if MapIteratorCache is unsafe for
     * reads from multiple threads -- unsafe, in fact, even in the absence of a concurrent write.
     * The specific problem we had was unsafe reads of lastEntryReturnedBySomeIterator. (To fix the
     * problem, we've since marked that field as volatile.)
     *
     * When MapIteratorCache is used from Immutable* classes, the TSAN failure doesn't indicate a