guava-tests/test/com/google/common/cache/CacheTesting.java - platform/external/guava - Git at Google

 /*
  * Copyright (C) 2011 The Guava Authors
  *
  * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
  * in compliance with the License. You may obtain a copy of the License at
  *
  * http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software distributed under the License
  * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
  * or implied. See the License for the specific language governing permissions and limitations under
  * the License.
  */

 package com.google.common.cache;

 import static com.google.common.base.Preconditions.checkNotNull;
 import static com.google.common.truth.Truth.assertThat;
 import static junit.framework.Assert.assertEquals;
 import static junit.framework.Assert.assertFalse;
 import static junit.framework.Assert.assertNotNull;
 import static junit.framework.Assert.assertNotSame;
 import static junit.framework.Assert.assertNull;
 import static junit.framework.Assert.assertSame;
 import static junit.framework.Assert.assertTrue;

 import com.google.common.base.Preconditions;
 import com.google.common.cache.LocalCache.LocalLoadingCache;
 import com.google.common.cache.LocalCache.Segment;
 import com.google.common.cache.LocalCache.ValueReference;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Maps;
 import com.google.common.collect.Sets;
 import com.google.common.testing.EqualsTester;
 import com.google.common.testing.FakeTicker;
 import java.lang.ref.Reference;
 import java.util.Collection;
 import java.util.List;
 import java.util.Map;
 import java.util.Map.Entry;
 import java.util.Set;
 import java.util.concurrent.ConcurrentMap;
 import java.util.concurrent.TimeUnit;
 import java.util.concurrent.atomic.AtomicReferenceArray;
 import org.checkerframework.checker.nullness.qual.Nullable;

 /**
  * A collection of utilities for {@link Cache} testing.
  *
  * @author mike nonemacher
  */
 @SuppressWarnings("GuardedBy") // TODO(b/35466881): Fix or suppress.
 class CacheTesting {

   /**
    * Poke into the Cache internals to simulate garbage collection of the value associated with the
    * given key. This assumes that the associated entry is a WeakValueReference or a
    * SoftValueReference (and not a LoadingValueReference), and throws an IllegalStateException if
    * that assumption does not hold.
    */
   @SuppressWarnings("unchecked") // the instanceof check and the cast generate this warning
   static <K, V> void simulateValueReclamation(Cache<K, V> cache, K key) {
     ReferenceEntry<K, V> entry = getReferenceEntry(cache, key);
     if (entry != null) {
       ValueReference<K, V> valueRef = entry.getValueReference();
       // fail on strong/computing refs
       Preconditions.checkState(valueRef instanceof Reference);
       Reference<V> ref = (Reference<V>) valueRef;
       if (ref != null) {
         ref.clear();
       }
     }
   }

   /**
    * Poke into the Cache internals to simulate garbage collection of the given key. This assumes
    * that the given entry is a weak or soft reference, and throws an IllegalStateException if that
    * assumption does not hold.
    */
   @SuppressWarnings("unchecked") // the instanceof check and the cast generate this warning
   static <K, V> void simulateKeyReclamation(Cache<K, V> cache, K key) {
     ReferenceEntry<K, V> entry = getReferenceEntry(cache, key);

     Preconditions.checkState(entry instanceof Reference);
     Reference<?> ref = (Reference<?>) entry;
     if (ref != null) {
       ref.clear();
     }
   }

   static <K, V> ReferenceEntry<K, V> getReferenceEntry(Cache<K, V> cache, K key) {
     checkNotNull(cache);
     checkNotNull(key);
     LocalCache<K, V> map = toLocalCache(cache);
     return map.getEntry(key);
   }

   /**
    * Forces the segment containing the given {@code key} to expand (see {@link Segment#expand()}.
    */
   static <K, V> void forceExpandSegment(Cache<K, V> cache, K key) {
     checkNotNull(cache);
     checkNotNull(key);
     LocalCache<K, V> map = toLocalCache(cache);
     int hash = map.hash(key);
     Segment<K, V> segment = map.segmentFor(hash);
     segment.expand();
   }

   /**
    * Gets the {@link LocalCache} used by the given {@link Cache}, if any, or throws an
    * IllegalArgumentException if this is a Cache type that doesn't have a LocalCache.
    */
   static <K, V> LocalCache<K, V> toLocalCache(Cache<K, V> cache) {
     if (cache instanceof LocalLoadingCache) {
       return ((LocalLoadingCache<K, V>) cache).localCache;
     }
     throw new IllegalArgumentException(
         "Cache of type " + cache.getClass() + " doesn't have a LocalCache.");
   }

   /**
    * Determines whether the given cache can be converted to a LocalCache by {@link #toLocalCache}
    * without throwing an exception.
    */
   static boolean hasLocalCache(Cache<?, ?> cache) {
     return (checkNotNull(cache) instanceof LocalLoadingCache);
   }

   static void drainRecencyQueues(Cache<?, ?> cache) {
     if (hasLocalCache(cache)) {
       LocalCache<?, ?> map = toLocalCache(cache);
       for (Segment<?, ?> segment : map.segments) {
         drainRecencyQueue(segment);
       }
     }
   }

   static void drainRecencyQueue(Segment<?, ?> segment) {
     segment.lock();
     try {
       segment.cleanUp();
     } finally {
       segment.unlock();
     }
   }

   static void drainReferenceQueues(Cache<?, ?> cache) {
     if (hasLocalCache(cache)) {
       drainReferenceQueues(toLocalCache(cache));
     }
   }

   static void drainReferenceQueues(LocalCache<?, ?> cchm) {
     for (LocalCache.Segment<?, ?> segment : cchm.segments) {
       drainReferenceQueue(segment);
     }
   }

   static void drainReferenceQueue(LocalCache.Segment<?, ?> segment) {
     segment.lock();
     try {
       segment.drainReferenceQueues();
     } finally {
       segment.unlock();
     }
   }

   static int getTotalSegmentSize(Cache<?, ?> cache) {
     LocalCache<?, ?> map = toLocalCache(cache);
     int totalSize = 0;
     for (Segment<?, ?> segment : map.segments) {
       totalSize += segment.maxSegmentWeight;
     }
     return totalSize;
   }

   /**
    * Peeks into the cache's internals to check its internal consistency. Verifies that each
    * segment's count matches its #elements (after cleanup), each segment is unlocked, each entry
    * contains a non-null key and value, and the eviction and expiration queues are consistent (see
    * {@link #checkEviction}, {@link #checkExpiration}).
    */
   static void checkValidState(Cache<?, ?> cache) {
     if (hasLocalCache(cache)) {
       checkValidState(toLocalCache(cache));
     }
   }

   static void checkValidState(LocalCache<?, ?> cchm) {
     for (Segment<?, ?> segment : cchm.segments) {
       segment.cleanUp();
       assertFalse(segment.isLocked());
       Map<?, ?> table = segmentTable(segment);
       // cleanup and then check count after we have a strong reference to all entries
       segment.cleanUp();
       // under high memory pressure keys/values may be nulled out but not yet enqueued
       assertThat(table.size()).isAtMost(segment.count);
       for (Entry<?, ?> entry : table.entrySet()) {
         assertNotNull(entry.getKey());
         assertNotNull(entry.getValue());
         assertSame(entry.getValue(), cchm.get(entry.getKey()));
       }
     }
     checkEviction(cchm);
     checkExpiration(cchm);
   }

   /**
    * Peeks into the cache's internals to verify that its expiration queue is consistent. Verifies
    * that the next/prev links in the expiration queue are correct, and that the queue is ordered by
    * expiration time.
    */
   static void checkExpiration(Cache<?, ?> cache) {
     if (hasLocalCache(cache)) {
       checkExpiration(toLocalCache(cache));
     }
   }

   static void checkExpiration(LocalCache<?, ?> cchm) {
     for (Segment<?, ?> segment : cchm.segments) {
       if (cchm.usesWriteQueue()) {
         Set<ReferenceEntry<?, ?>> entries = Sets.newIdentityHashSet();

         ReferenceEntry<?, ?> prev = null;
         for (ReferenceEntry<?, ?> current : segment.writeQueue) {
           assertTrue(entries.add(current));
           if (prev != null) {
             assertSame(prev, current.getPreviousInWriteQueue());
             assertSame(prev.getNextInWriteQueue(), current);
             assertThat(prev.getWriteTime()).isAtMost(current.getWriteTime());
           }
           Object key = current.getKey();
           if (key != null) {
             assertSame(current, segment.getEntry(key, current.getHash()));
           }
           prev = current;
         }
         assertEquals(segment.count, entries.size());
       } else {
         assertTrue(segment.writeQueue.isEmpty());
       }

       if (cchm.usesAccessQueue()) {
         Set<ReferenceEntry<?, ?>> entries = Sets.newIdentityHashSet();

         ReferenceEntry<?, ?> prev = null;
         for (ReferenceEntry<?, ?> current : segment.accessQueue) {
           assertTrue(entries.add(current));
           if (prev != null) {
             assertSame(prev, current.getPreviousInAccessQueue());
             assertSame(prev.getNextInAccessQueue(), current);
             // read accesses may be slightly misordered
             assertTrue(
                 prev.getAccessTime() <= current.getAccessTime()
                     || prev.getAccessTime() - current.getAccessTime() < 1000);
           }
           Object key = current.getKey();
           if (key != null) {
             assertSame(current, segment.getEntry(key, current.getHash()));
           }
           prev = current;
         }
         assertEquals(segment.count, entries.size());
       } else {
         assertTrue(segment.accessQueue.isEmpty());
       }
     }
   }

   /**
    * Peeks into the cache's internals to verify that its eviction queue is consistent. Verifies that
    * the prev/next links are correct, and that all items in each segment are also in that segment's
    * eviction (recency) queue.
    */
   static void checkEviction(Cache<?, ?> cache) {
     if (hasLocalCache(cache)) {
       checkEviction(toLocalCache(cache));
     }
   }

   static void checkEviction(LocalCache<?, ?> map) {
     if (map.evictsBySize()) {
       for (Segment<?, ?> segment : map.segments) {
         drainRecencyQueue(segment);
         assertEquals(0, segment.recencyQueue.size());
         assertEquals(0, segment.readCount.get());

         ReferenceEntry<?, ?> prev = null;
         for (ReferenceEntry<?, ?> current : segment.accessQueue) {
           if (prev != null) {
             assertSame(prev, current.getPreviousInAccessQueue());
             assertSame(prev.getNextInAccessQueue(), current);
           }
           Object key = current.getKey();
           if (key != null) {
             assertSame(current, segment.getEntry(key, current.getHash()));
           }
           prev = current;
         }
       }
     } else {
       for (Segment<?, ?> segment : map.segments) {
         assertEquals(0, segment.recencyQueue.size());
       }
     }
   }

   static int segmentSize(Segment<?, ?> segment) {
     Map<?, ?> map = segmentTable(segment);
     return map.size();
   }

   static <K, V> Map<K, V> segmentTable(Segment<K, V> segment) {
     AtomicReferenceArray<? extends ReferenceEntry<K, V>> table = segment.table;
     Map<K, V> map = Maps.newLinkedHashMap();
     for (int i = 0; i < table.length(); i++) {
       for (ReferenceEntry<K, V> entry = table.get(i); entry != null; entry = entry.getNext()) {
         K key = entry.getKey();
         V value = entry.getValueReference().get();
         if (key != null && value != null) {
           assertNull(map.put(key, value));
         }
       }
     }
     return map;
   }

   static int writeQueueSize(Cache<?, ?> cache) {
     LocalCache<?, ?> cchm = toLocalCache(cache);

     int size = 0;
     for (Segment<?, ?> segment : cchm.segments) {
       size += writeQueueSize(segment);
     }
     return size;
   }

   static int writeQueueSize(Segment<?, ?> segment) {
     return segment.writeQueue.size();
   }

   static int accessQueueSize(Cache<?, ?> cache) {
     LocalCache<?, ?> cchm = toLocalCache(cache);
     int size = 0;
     for (Segment<?, ?> segment : cchm.segments) {
       size += accessQueueSize(segment);
     }
     return size;
   }

   static int accessQueueSize(Segment<?, ?> segment) {
     return segment.accessQueue.size();
   }

   static int expirationQueueSize(Cache<?, ?> cache) {
     return Math.max(accessQueueSize(cache), writeQueueSize(cache));
   }

   static void processPendingNotifications(Cache<?, ?> cache) {
     if (hasLocalCache(cache)) {
       LocalCache<?, ?> cchm = toLocalCache(cache);
       cchm.processPendingNotifications();
     }
   }

   interface Receiver<T> {
     void accept(@Nullable T object);
   }

   /**
    * Assuming the given cache has maximum size {@code maxSize}, this method populates the cache (by
    * getting a bunch of different keys), then makes sure all the items in the cache are also in the
    * eviction queue. It will invoke the given {@code operation} on the first element in the eviction
    * queue, and then reverify that all items in the cache are in the eviction queue, and verify that
    * the head of the eviction queue has changed as a result of the operation.
    */
   static void checkRecency(
       LoadingCache<Integer, Integer> cache,
       int maxSize,
       Receiver<ReferenceEntry<Integer, Integer>> operation) {
     checkNotNull(operation);
     if (hasLocalCache(cache)) {
       warmUp(cache, 0, 2 * maxSize);

       LocalCache<Integer, Integer> cchm = toLocalCache(cache);
       Segment<?, ?> segment = cchm.segments[0];
       drainRecencyQueue(segment);
       assertEquals(maxSize, accessQueueSize(cache));
       assertEquals(maxSize, cache.size());

       ReferenceEntry<?, ?> originalHead = segment.accessQueue.peek();
       @SuppressWarnings("unchecked")
       ReferenceEntry<Integer, Integer> entry = (ReferenceEntry) originalHead;
       operation.accept(entry);
       drainRecencyQueue(segment);

       assertNotSame(originalHead, segment.accessQueue.peek());
       assertEquals(cache.size(), accessQueueSize(cache));
     }
   }

   /** Warms the given cache by getting all values in {@code [start, end)}, in order. */
   static void warmUp(LoadingCache<Integer, Integer> map, int start, int end) {
     checkNotNull(map);
     for (int i = start; i < end; i++) {
       map.getUnchecked(i);
     }
   }

   static void expireEntries(Cache<?, ?> cache, long expiringTime, FakeTicker ticker) {
     checkNotNull(ticker);
     expireEntries(toLocalCache(cache), expiringTime, ticker);
   }

   static void expireEntries(LocalCache<?, ?> cchm, long expiringTime, FakeTicker ticker) {

     for (Segment<?, ?> segment : cchm.segments) {
       drainRecencyQueue(segment);
     }

     ticker.advance(2 * expiringTime, TimeUnit.MILLISECONDS);

     long now = ticker.read();
     for (Segment<?, ?> segment : cchm.segments) {
       expireEntries(segment, now);
       assertEquals("Expiration queue must be empty by now", 0, writeQueueSize(segment));
       assertEquals("Expiration queue must be empty by now", 0, accessQueueSize(segment));
       assertEquals("Segments must be empty by now", 0, segmentSize(segment));
     }
     cchm.processPendingNotifications();
   }

   static void expireEntries(Segment<?, ?> segment, long now) {
     segment.lock();
     try {
       segment.expireEntries(now);
       segment.cleanUp();
     } finally {
       segment.unlock();
     }
   }

   static void checkEmpty(Cache<?, ?> cache) {
     assertEquals(0, cache.size());
     assertFalse(cache.asMap().containsKey(null));
     assertFalse(cache.asMap().containsKey(6));
     assertFalse(cache.asMap().containsValue(null));
     assertFalse(cache.asMap().containsValue(6));
     checkEmpty(cache.asMap());
   }

   static void checkEmpty(ConcurrentMap<?, ?> map) {
     checkEmpty(map.keySet());
     checkEmpty(map.values());
     checkEmpty(map.entrySet());
     assertEquals(ImmutableMap.of(), map);
     assertEquals(ImmutableMap.of().hashCode(), map.hashCode());
     assertEquals(ImmutableMap.of().toString(), map.toString());

     if (map instanceof LocalCache) {
       LocalCache<?, ?> cchm = (LocalCache<?, ?>) map;

       checkValidState(cchm);
       assertTrue(cchm.isEmpty());
       assertEquals(0, cchm.size());
       for (LocalCache.Segment<?, ?> segment : cchm.segments) {
         assertEquals(0, segment.count);
         assertEquals(0, segmentSize(segment));
         assertTrue(segment.writeQueue.isEmpty());
         assertTrue(segment.accessQueue.isEmpty());
       }
     }
   }

   static void checkEmpty(Collection<?> collection) {
     assertTrue(collection.isEmpty());
     assertEquals(0, collection.size());
     assertFalse(collection.iterator().hasNext());
     assertThat(collection.toArray()).isEmpty();
     assertThat(collection.toArray(new Object[0])).isEmpty();
     if (collection instanceof Set) {
       new EqualsTester()
           .addEqualityGroup(ImmutableSet.of(), collection)
           .addEqualityGroup(ImmutableSet.of(""))
           .testEquals();
     } else if (collection instanceof List) {
       new EqualsTester()
           .addEqualityGroup(ImmutableList.of(), collection)
           .addEqualityGroup(ImmutableList.of(""))
           .testEquals();
     }
   }
 }
	/*
	* Copyright (C) 2011 The Guava Authors
	*
	* Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
	* in compliance with the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software distributed under the License
	* is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
	* or implied. See the License for the specific language governing permissions and limitations under
	* the License.
	*/

	package com.google.common.cache;

	import static com.google.common.base.Preconditions.checkNotNull;
	import static com.google.common.truth.Truth.assertThat;
	import static junit.framework.Assert.assertEquals;
	import static junit.framework.Assert.assertFalse;
	import static junit.framework.Assert.assertNotNull;
	import static junit.framework.Assert.assertNotSame;
	import static junit.framework.Assert.assertNull;
	import static junit.framework.Assert.assertSame;
	import static junit.framework.Assert.assertTrue;

	import com.google.common.base.Preconditions;
	import com.google.common.cache.LocalCache.LocalLoadingCache;
	import com.google.common.cache.LocalCache.Segment;
	import com.google.common.cache.LocalCache.ValueReference;
	import com.google.common.collect.ImmutableList;
	import com.google.common.collect.ImmutableMap;
	import com.google.common.collect.ImmutableSet;
	import com.google.common.collect.Maps;
	import com.google.common.collect.Sets;
	import com.google.common.testing.EqualsTester;
	import com.google.common.testing.FakeTicker;
	import java.lang.ref.Reference;
	import java.util.Collection;
	import java.util.List;
	import java.util.Map;
	import java.util.Map.Entry;
	import java.util.Set;
	import java.util.concurrent.ConcurrentMap;
	import java.util.concurrent.TimeUnit;
	import java.util.concurrent.atomic.AtomicReferenceArray;
	import org.checkerframework.checker.nullness.qual.Nullable;

	/**
	* A collection of utilities for {@link Cache} testing.
	*
	* @author mike nonemacher
	*/
	@SuppressWarnings("GuardedBy") // TODO(b/35466881): Fix or suppress.
	class CacheTesting {

	/**
	* Poke into the Cache internals to simulate garbage collection of the value associated with the
	* given key. This assumes that the associated entry is a WeakValueReference or a
	* SoftValueReference (and not a LoadingValueReference), and throws an IllegalStateException if
	* that assumption does not hold.
	*/
	@SuppressWarnings("unchecked") // the instanceof check and the cast generate this warning
	static <K, V> void simulateValueReclamation(Cache<K, V> cache, K key) {
	ReferenceEntry<K, V> entry = getReferenceEntry(cache, key);
	if (entry != null) {
	ValueReference<K, V> valueRef = entry.getValueReference();
	// fail on strong/computing refs
	Preconditions.checkState(valueRef instanceof Reference);
	Reference<V> ref = (Reference<V>) valueRef;
	if (ref != null) {
	ref.clear();
	}
	}
	}

	/**
	* Poke into the Cache internals to simulate garbage collection of the given key. This assumes
	* that the given entry is a weak or soft reference, and throws an IllegalStateException if that
	* assumption does not hold.
	*/
	@SuppressWarnings("unchecked") // the instanceof check and the cast generate this warning
	static <K, V> void simulateKeyReclamation(Cache<K, V> cache, K key) {
	ReferenceEntry<K, V> entry = getReferenceEntry(cache, key);

	Preconditions.checkState(entry instanceof Reference);
	Reference<?> ref = (Reference<?>) entry;
	if (ref != null) {
	ref.clear();
	}
	}

	static <K, V> ReferenceEntry<K, V> getReferenceEntry(Cache<K, V> cache, K key) {
	checkNotNull(cache);
	checkNotNull(key);
	LocalCache<K, V> map = toLocalCache(cache);
	return map.getEntry(key);
	}

	/**
	* Forces the segment containing the given {@code key} to expand (see {@link Segment#expand()}.
	*/
	static <K, V> void forceExpandSegment(Cache<K, V> cache, K key) {
	checkNotNull(cache);
	checkNotNull(key);
	LocalCache<K, V> map = toLocalCache(cache);
	int hash = map.hash(key);
	Segment<K, V> segment = map.segmentFor(hash);
	segment.expand();
	}

	/**
	* Gets the {@link LocalCache} used by the given {@link Cache}, if any, or throws an
	* IllegalArgumentException if this is a Cache type that doesn't have a LocalCache.
	*/
	static <K, V> LocalCache<K, V> toLocalCache(Cache<K, V> cache) {
	if (cache instanceof LocalLoadingCache) {
	return ((LocalLoadingCache<K, V>) cache).localCache;
	}
	throw new IllegalArgumentException(
	"Cache of type " + cache.getClass() + " doesn't have a LocalCache.");
	}

	/**
	* Determines whether the given cache can be converted to a LocalCache by {@link #toLocalCache}
	* without throwing an exception.
	*/
	static boolean hasLocalCache(Cache<?, ?> cache) {
	return (checkNotNull(cache) instanceof LocalLoadingCache);
	}

	static void drainRecencyQueues(Cache<?, ?> cache) {
	if (hasLocalCache(cache)) {
	LocalCache<?, ?> map = toLocalCache(cache);
	for (Segment<?, ?> segment : map.segments) {
	drainRecencyQueue(segment);
	}
	}
	}

	static void drainRecencyQueue(Segment<?, ?> segment) {
	segment.lock();
	try {
	segment.cleanUp();
	} finally {
	segment.unlock();
	}
	}

	static void drainReferenceQueues(Cache<?, ?> cache) {
	if (hasLocalCache(cache)) {
	drainReferenceQueues(toLocalCache(cache));
	}
	}

	static void drainReferenceQueues(LocalCache<?, ?> cchm) {
	for (LocalCache.Segment<?, ?> segment : cchm.segments) {
	drainReferenceQueue(segment);
	}
	}

	static void drainReferenceQueue(LocalCache.Segment<?, ?> segment) {
	segment.lock();
	try {
	segment.drainReferenceQueues();
	} finally {
	segment.unlock();
	}
	}

	static int getTotalSegmentSize(Cache<?, ?> cache) {
	LocalCache<?, ?> map = toLocalCache(cache);
	int totalSize = 0;
	for (Segment<?, ?> segment : map.segments) {
	totalSize += segment.maxSegmentWeight;
	}
	return totalSize;
	}

	/**
	* Peeks into the cache's internals to check its internal consistency. Verifies that each
	* segment's count matches its #elements (after cleanup), each segment is unlocked, each entry
	* contains a non-null key and value, and the eviction and expiration queues are consistent (see
	* {@link #checkEviction}, {@link #checkExpiration}).
	*/
	static void checkValidState(Cache<?, ?> cache) {
	if (hasLocalCache(cache)) {
	checkValidState(toLocalCache(cache));
	}
	}

	static void checkValidState(LocalCache<?, ?> cchm) {
	for (Segment<?, ?> segment : cchm.segments) {
	segment.cleanUp();
	assertFalse(segment.isLocked());
	Map<?, ?> table = segmentTable(segment);
	// cleanup and then check count after we have a strong reference to all entries
	segment.cleanUp();
	// under high memory pressure keys/values may be nulled out but not yet enqueued
	assertThat(table.size()).isAtMost(segment.count);
	for (Entry<?, ?> entry : table.entrySet()) {
	assertNotNull(entry.getKey());
	assertNotNull(entry.getValue());
	assertSame(entry.getValue(), cchm.get(entry.getKey()));
	}
	}
	checkEviction(cchm);
	checkExpiration(cchm);
	}

	/**
	* Peeks into the cache's internals to verify that its expiration queue is consistent. Verifies
	* that the next/prev links in the expiration queue are correct, and that the queue is ordered by
	* expiration time.
	*/
	static void checkExpiration(Cache<?, ?> cache) {
	if (hasLocalCache(cache)) {
	checkExpiration(toLocalCache(cache));
	}
	}

	static void checkExpiration(LocalCache<?, ?> cchm) {
	for (Segment<?, ?> segment : cchm.segments) {
	if (cchm.usesWriteQueue()) {
	Set<ReferenceEntry<?, ?>> entries = Sets.newIdentityHashSet();

	ReferenceEntry<?, ?> prev = null;
	for (ReferenceEntry<?, ?> current : segment.writeQueue) {
	assertTrue(entries.add(current));
	if (prev != null) {
	assertSame(prev, current.getPreviousInWriteQueue());
	assertSame(prev.getNextInWriteQueue(), current);
	assertThat(prev.getWriteTime()).isAtMost(current.getWriteTime());
	}
	Object key = current.getKey();
	if (key != null) {
	assertSame(current, segment.getEntry(key, current.getHash()));
	}
	prev = current;
	}
	assertEquals(segment.count, entries.size());
	} else {
	assertTrue(segment.writeQueue.isEmpty());
	}

	if (cchm.usesAccessQueue()) {
	Set<ReferenceEntry<?, ?>> entries = Sets.newIdentityHashSet();

	ReferenceEntry<?, ?> prev = null;
	for (ReferenceEntry<?, ?> current : segment.accessQueue) {
	assertTrue(entries.add(current));
	if (prev != null) {
	assertSame(prev, current.getPreviousInAccessQueue());
	assertSame(prev.getNextInAccessQueue(), current);
	// read accesses may be slightly misordered
	assertTrue(
	prev.getAccessTime() <= current.getAccessTime()
	\|\| prev.getAccessTime() - current.getAccessTime() < 1000);
	}
	Object key = current.getKey();
	if (key != null) {
	assertSame(current, segment.getEntry(key, current.getHash()));
	}
	prev = current;
	}
	assertEquals(segment.count, entries.size());
	} else {
	assertTrue(segment.accessQueue.isEmpty());
	}
	}
	}

	/**
	* Peeks into the cache's internals to verify that its eviction queue is consistent. Verifies that
	* the prev/next links are correct, and that all items in each segment are also in that segment's
	* eviction (recency) queue.
	*/
	static void checkEviction(Cache<?, ?> cache) {
	if (hasLocalCache(cache)) {
	checkEviction(toLocalCache(cache));
	}
	}

	static void checkEviction(LocalCache<?, ?> map) {
	if (map.evictsBySize()) {
	for (Segment<?, ?> segment : map.segments) {
	drainRecencyQueue(segment);
	assertEquals(0, segment.recencyQueue.size());
	assertEquals(0, segment.readCount.get());

	ReferenceEntry<?, ?> prev = null;
	for (ReferenceEntry<?, ?> current : segment.accessQueue) {
	if (prev != null) {
	assertSame(prev, current.getPreviousInAccessQueue());
	assertSame(prev.getNextInAccessQueue(), current);
	}
	Object key = current.getKey();
	if (key != null) {
	assertSame(current, segment.getEntry(key, current.getHash()));
	}
	prev = current;
	}
	}
	} else {
	for (Segment<?, ?> segment : map.segments) {
	assertEquals(0, segment.recencyQueue.size());
	}
	}
	}

	static int segmentSize(Segment<?, ?> segment) {
	Map<?, ?> map = segmentTable(segment);
	return map.size();
	}

	static <K, V> Map<K, V> segmentTable(Segment<K, V> segment) {
	AtomicReferenceArray<? extends ReferenceEntry<K, V>> table = segment.table;
	Map<K, V> map = Maps.newLinkedHashMap();
	for (int i = 0; i < table.length(); i++) {
	for (ReferenceEntry<K, V> entry = table.get(i); entry != null; entry = entry.getNext()) {
	K key = entry.getKey();
	V value = entry.getValueReference().get();
	if (key != null && value != null) {
	assertNull(map.put(key, value));
	}
	}
	}
	return map;
	}

	static int writeQueueSize(Cache<?, ?> cache) {
	LocalCache<?, ?> cchm = toLocalCache(cache);

	int size = 0;
	for (Segment<?, ?> segment : cchm.segments) {
	size += writeQueueSize(segment);
	}
	return size;
	}

	static int writeQueueSize(Segment<?, ?> segment) {
	return segment.writeQueue.size();
	}

	static int accessQueueSize(Cache<?, ?> cache) {
	LocalCache<?, ?> cchm = toLocalCache(cache);
	int size = 0;
	for (Segment<?, ?> segment : cchm.segments) {
	size += accessQueueSize(segment);
	}
	return size;
	}

	static int accessQueueSize(Segment<?, ?> segment) {
	return segment.accessQueue.size();
	}

	static int expirationQueueSize(Cache<?, ?> cache) {
	return Math.max(accessQueueSize(cache), writeQueueSize(cache));
	}

	static void processPendingNotifications(Cache<?, ?> cache) {
	if (hasLocalCache(cache)) {
	LocalCache<?, ?> cchm = toLocalCache(cache);
	cchm.processPendingNotifications();
	}
	}

	interface Receiver<T> {
	void accept(@Nullable T object);
	}

	/**
	* Assuming the given cache has maximum size {@code maxSize}, this method populates the cache (by
	* getting a bunch of different keys), then makes sure all the items in the cache are also in the
	* eviction queue. It will invoke the given {@code operation} on the first element in the eviction
	* queue, and then reverify that all items in the cache are in the eviction queue, and verify that
	* the head of the eviction queue has changed as a result of the operation.
	*/
	static void checkRecency(
	LoadingCache<Integer, Integer> cache,
	int maxSize,
	Receiver<ReferenceEntry<Integer, Integer>> operation) {
	checkNotNull(operation);
	if (hasLocalCache(cache)) {
	warmUp(cache, 0, 2 * maxSize);

	LocalCache<Integer, Integer> cchm = toLocalCache(cache);
	Segment<?, ?> segment = cchm.segments[0];
	drainRecencyQueue(segment);
	assertEquals(maxSize, accessQueueSize(cache));
	assertEquals(maxSize, cache.size());

	ReferenceEntry<?, ?> originalHead = segment.accessQueue.peek();
	@SuppressWarnings("unchecked")
	ReferenceEntry<Integer, Integer> entry = (ReferenceEntry) originalHead;
	operation.accept(entry);
	drainRecencyQueue(segment);

	assertNotSame(originalHead, segment.accessQueue.peek());
	assertEquals(cache.size(), accessQueueSize(cache));
	}
	}

	/** Warms the given cache by getting all values in {@code [start, end)}, in order. */
	static void warmUp(LoadingCache<Integer, Integer> map, int start, int end) {
	checkNotNull(map);
	for (int i = start; i < end; i++) {
	map.getUnchecked(i);
	}
	}

	static void expireEntries(Cache<?, ?> cache, long expiringTime, FakeTicker ticker) {
	checkNotNull(ticker);
	expireEntries(toLocalCache(cache), expiringTime, ticker);
	}

	static void expireEntries(LocalCache<?, ?> cchm, long expiringTime, FakeTicker ticker) {

	for (Segment<?, ?> segment : cchm.segments) {
	drainRecencyQueue(segment);
	}

	ticker.advance(2 * expiringTime, TimeUnit.MILLISECONDS);

	long now = ticker.read();
	for (Segment<?, ?> segment : cchm.segments) {
	expireEntries(segment, now);
	assertEquals("Expiration queue must be empty by now", 0, writeQueueSize(segment));
	assertEquals("Expiration queue must be empty by now", 0, accessQueueSize(segment));
	assertEquals("Segments must be empty by now", 0, segmentSize(segment));
	}
	cchm.processPendingNotifications();
	}

	static void expireEntries(Segment<?, ?> segment, long now) {
	segment.lock();
	try {
	segment.expireEntries(now);
	segment.cleanUp();
	} finally {
	segment.unlock();
	}
	}

	static void checkEmpty(Cache<?, ?> cache) {
	assertEquals(0, cache.size());
	assertFalse(cache.asMap().containsKey(null));
	assertFalse(cache.asMap().containsKey(6));
	assertFalse(cache.asMap().containsValue(null));
	assertFalse(cache.asMap().containsValue(6));
	checkEmpty(cache.asMap());
	}

	static void checkEmpty(ConcurrentMap<?, ?> map) {
	checkEmpty(map.keySet());
	checkEmpty(map.values());
	checkEmpty(map.entrySet());
	assertEquals(ImmutableMap.of(), map);
	assertEquals(ImmutableMap.of().hashCode(), map.hashCode());
	assertEquals(ImmutableMap.of().toString(), map.toString());

	if (map instanceof LocalCache) {
	LocalCache<?, ?> cchm = (LocalCache<?, ?>) map;

	checkValidState(cchm);
	assertTrue(cchm.isEmpty());
	assertEquals(0, cchm.size());
	for (LocalCache.Segment<?, ?> segment : cchm.segments) {
	assertEquals(0, segment.count);
	assertEquals(0, segmentSize(segment));
	assertTrue(segment.writeQueue.isEmpty());
	assertTrue(segment.accessQueue.isEmpty());
	}
	}
	}

	static void checkEmpty(Collection<?> collection) {
	assertTrue(collection.isEmpty());
	assertEquals(0, collection.size());
	assertFalse(collection.iterator().hasNext());
	assertThat(collection.toArray()).isEmpty();
	assertThat(collection.toArray(new Object[0])).isEmpty();
	if (collection instanceof Set) {
	new EqualsTester()
	.addEqualityGroup(ImmutableSet.of(), collection)
	.addEqualityGroup(ImmutableSet.of(""))
	.testEquals();
	} else if (collection instanceof List) {
	new EqualsTester()
	.addEqualityGroup(ImmutableList.of(), collection)
	.addEqualityGroup(ImmutableList.of(""))
	.testEquals();
	}
	}
	}