guava-gwt/src-super/com/google/common/cache/super/com/google/common/cache/LocalCache.java - platform/external/guava - Git at Google

 /*
  * Copyright (C) 2012 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.MoreObjects.firstNonNull;
 import static com.google.common.base.Preconditions.checkNotNull;
 import static com.google.common.base.Preconditions.checkState;

 import com.google.common.base.Equivalence;
 import com.google.common.base.Ticker;
 import com.google.common.cache.AbstractCache.StatsCounter;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.util.concurrent.ExecutionError;
 import com.google.common.util.concurrent.UncheckedExecutionException;
 import java.util.AbstractCollection;
 import java.util.AbstractSet;
 import java.util.Collection;
 import java.util.HashMap;
 import java.util.Iterator;
 import java.util.LinkedHashMap;
 import java.util.Map;
 import java.util.Map.Entry;
 import java.util.NoSuchElementException;
 import java.util.Set;
 import java.util.concurrent.Callable;
 import java.util.concurrent.ConcurrentMap;
 import java.util.concurrent.ExecutionException;
 import org.checkerframework.checker.nullness.qual.Nullable;

 /**
  * LocalCache emulation for GWT.
  *
  * @param <K> the base key type
  * @param <V> the base value type
  * @author Charles Fry
  * @author Jon Donovan
  */
 public class LocalCache<K, V> implements ConcurrentMap<K, V> {
   private static final int UNSET_INT = CacheBuilder.UNSET_INT;

   private final LinkedHashMap<K, Timestamped<V>> cachingHashMap;
   private final CacheLoader<? super K, V> loader;
   private final RemovalListener removalListener;
   private final StatsCounter statsCounter;
   private final Ticker ticker;
   private final long expireAfterWrite;
   private final long expireAfterAccess;

   LocalCache(CacheBuilder<? super K, ? super V> builder, CacheLoader<? super K, V> loader) {
     this.loader = loader;
     this.removalListener = builder.removalListener;
     this.expireAfterAccess = builder.expireAfterAccessNanos;
     this.expireAfterWrite = builder.expireAfterWriteNanos;
     this.statsCounter = builder.getStatsCounterSupplier().get();

     /* Implements size-capped LinkedHashMap */
     final long maximumSize = builder.maximumSize;
     this.cachingHashMap =
         new CapacityEnforcingLinkedHashMap<K, V>(
             builder.getInitialCapacity(),
             0.75f,
             (builder.maximumSize != UNSET_INT),
             builder.maximumSize,
             statsCounter,
             removalListener);

     this.ticker = firstNonNull(builder.ticker, Ticker.systemTicker());
   }

   @Override
   public int size() {
     return cachingHashMap.size();
   }

   @Override
   public boolean isEmpty() {
     return cachingHashMap.isEmpty();
   }

   @Override
   public V get(Object key) {
     checkNotNull(key);
     Timestamped<V> value = cachingHashMap.get(key);

     if (value == null) {
       statsCounter.recordMisses(1);
       return null;
     } else if (!isExpired(value)) {
       statsCounter.recordHits(1);
       value.updateTimestamp();
       return value.getValue();
     } else {
       statsCounter.recordEviction();
       statsCounter.recordMisses(1);
       alertListenerIfPresent(key, value.getValue(), RemovalCause.EXPIRED);
       cachingHashMap.remove(key);
       return null;
     }
   }

   @Override
   public V put(K key, V value) {
     checkNotNull(key);
     checkNotNull(value);
     Timestamped<V> oldValue = cachingHashMap.put(key, new Timestamped<V>(value, ticker));
     if (oldValue == null) {
       return null;
     }
     alertListenerIfPresent(key, oldValue.getValue(), RemovalCause.REPLACED);
     return oldValue.getValue();
   }

   @Override
   public V remove(Object key) {
     Timestamped<V> stamped = cachingHashMap.remove(key);
     if (stamped != null) {
       V value = stamped.getValue();

       if (!isExpired(stamped)) {
         alertListenerIfPresent(key, value, RemovalCause.EXPLICIT);
         return value;
       }

       alertListenerIfPresent(key, value, RemovalCause.EXPIRED);
     }
     return null;
   }

   @Override
   public void putAll(Map<? extends K, ? extends V> m) {
     for (Entry<? extends K, ? extends V> entry : m.entrySet()) {
       put(entry.getKey(), entry.getValue());
     }
   }

   @Override
   public void clear() {
     if (removalListener != null) {
       for (Entry<K, Timestamped<V>> entry : cachingHashMap.entrySet()) {
         alertListenerIfPresent(entry.getKey(), entry.getValue().getValue(), RemovalCause.EXPLICIT);
       }
     }
     cachingHashMap.clear();
   }

   @Override
   public V putIfAbsent(K key, V value) {
     V currentValue = get(key);
     if (currentValue != null) {
       return currentValue;
     }
     return put(key, value);
   }

   @Override
   public boolean remove(Object key, Object value) {
     if (value.equals(get(key))) {
       alertListenerIfPresent(key, value, RemovalCause.EXPLICIT);
       remove(key);
       return true;
     }
     return false;
   }

   @Override
   public boolean replace(K key, V oldValue, V newValue) {
     if (oldValue.equals(get(key))) {
       alertListenerIfPresent(key, oldValue, RemovalCause.REPLACED);
       put(key, newValue);
       return true;
     }
     return false;
   }

   @Override
   public V replace(K key, V value) {
     V currentValue = get(key);
     if (currentValue != null) {
       alertListenerIfPresent(key, currentValue, RemovalCause.REPLACED);
       return put(key, value);
     }
     return null;
   }

   @Override
   public boolean containsKey(Object key) {
     return cachingHashMap.containsKey(key) && !isExpired(cachingHashMap.get(key));
   }

   @Override
   public boolean containsValue(Object value) {
     for (Timestamped<V> val : cachingHashMap.values()) {
       if (val.getValue().equals(value)) {
         if (!isExpired(val)) {
           return true;
         }
       }
     }
     return false;
   }

   private boolean isExpired(Timestamped<V> stamped) {
     if ((expireAfterAccess == UNSET_INT) && (expireAfterWrite == UNSET_INT)) {
       return false;
     }

     boolean expireWrite = (stamped.getWriteTimestamp() + expireAfterWrite <= currentTimeNanos());
     boolean expireAccess = (stamped.getAccessTimestamp() + expireAfterAccess <= currentTimeNanos());

     if (expireAfterAccess == UNSET_INT) {
       return expireWrite;
     }
     if (expireAfterWrite == UNSET_INT) {
       return expireAccess;
     }

     return expireWrite || expireAccess;
   }

   @SuppressWarnings("GoodTime")
   private long currentTimeNanos() {
     return ticker.read();
   }

   private void alertListenerIfPresent(Object key, Object value, RemovalCause cause) {
     if (removalListener != null) {
       removalListener.onRemoval(RemovalNotification.create(key, value, cause));
     }
   }

   @SuppressWarnings("GoodTime") // timestamps as numeric primitives
   private V load(Object key) throws ExecutionException {
     long startTime = ticker.read();
     V calculatedValue;
     try {
       /*
        * This cast isn't safe, but we can rely on the fact that K is almost always passed to
        * Map.get(), and tools like IDEs and Findbugs can catch situations where this isn't the
        * case.
        *
        * The alternative is to add an overloaded method, but the chances of a user calling get()
        * instead of the new API and the risks inherent in adding a new API outweigh this little
        * hole.
        */
       K castKey = (K) key;
       calculatedValue = loader.load(castKey);
       put(castKey, calculatedValue);
     } catch (RuntimeException e) {
       statsCounter.recordLoadException(ticker.read() - startTime);
       throw new UncheckedExecutionException(e);
     } catch (Exception e) {
       statsCounter.recordLoadException(ticker.read() - startTime);
       throw new ExecutionException(e);
     } catch (Error e) {
       statsCounter.recordLoadException(ticker.read() - startTime);
       throw new ExecutionError(e);
     }

     if (calculatedValue == null) {
       String message = loader + " returned null for key " + key + ".";
       throw new CacheLoader.InvalidCacheLoadException(message);
     }
     statsCounter.recordLoadSuccess(ticker.read() - startTime);
     return calculatedValue;
   }

   private V getIfPresent(Object key) {
     checkNotNull(key);
     Timestamped<V> value = cachingHashMap.get(key);

     if (value == null) {
       return null;
     } else if (!isExpired(value)) {
       value.updateTimestamp();
       return value.getValue();
     } else {
       alertListenerIfPresent(key, value.getValue(), RemovalCause.EXPIRED);
       cachingHashMap.remove(key);
       return null;
     }
   }

   private V getOrLoad(K key) throws ExecutionException {
     V value = get(key);
     if (value != null) {
       return value;
     }
     return load(key);
   }

   @SuppressWarnings("GoodTime") // timestamps as numeric primitives
   private static class Timestamped<V> {
     private final V value;
     private final Ticker ticker;
     private long writeTimestamp;
     private long accessTimestamp;

     public Timestamped(V value, Ticker ticker) {
       this.value = checkNotNull(value);
       this.ticker = checkNotNull(ticker);
       this.writeTimestamp = ticker.read();
       this.accessTimestamp = this.writeTimestamp;
     }

     public V getValue() {
       return value;
     }

     public void updateTimestamp() {
       accessTimestamp = ticker.read();
     }

     public long getAccessTimestamp() {
       return accessTimestamp;
     }

     public long getWriteTimestamp() {
       return writeTimestamp;
     }

     public boolean equals(Object o) {
       return value.equals(o);
     }

     public int hashCode() {
       return value.hashCode();
     }
   }

   /**
    * LocalManualCache is a wrapper around LocalCache for a cache without loading.
    *
    * @param <K> the base key type
    * @param <V> the base value type
    */
   public static class LocalManualCache<K, V> extends AbstractCache<K, V> {
     final LocalCache<K, V> localCache;

     LocalManualCache(CacheBuilder<? super K, ? super V> builder) {
       this(builder, null);
     }

     protected LocalManualCache(
         CacheBuilder<? super K, ? super V> builder, CacheLoader<? super K, V> loader) {
       this.localCache = new LocalCache<K, V>(builder, loader);
     }

     // Cache methods

     @Override
     public V get(K key, Callable<? extends V> valueLoader) throws ExecutionException {
       V value = localCache.get(key);
       if (value != null) {
         return value;
       }

       try {
         V newValue = valueLoader.call();
         localCache.put(key, newValue);
         return newValue;
       } catch (Exception e) {
         throw new ExecutionException(e);
       }
     }

     @Override
     public @Nullable V getIfPresent(Object key) {
       return localCache.getIfPresent(key);
     }

     @Override
     public void put(K key, V value) {
       localCache.put(key, value);
     }

     @Override
     public void invalidate(Object key) {
       checkNotNull(key);
       localCache.remove(key);
     }

     @Override
     public void invalidateAll() {
       localCache.clear();
     }

     @Override
     public long size() {
       return localCache.size();
     }

     @Override
     public ConcurrentMap<K, V> asMap() {
       return localCache;
     }
   }

   /**
    * LocalLoadingCache is a wrapper around LocalCache for a cache with loading.
    *
    * @param <K> the base key type
    * @param <V> the base value type
    */
   public static class LocalLoadingCache<K, V> extends LocalManualCache<K, V>
       implements LoadingCache<K, V> {

     LocalLoadingCache(
         CacheBuilder<? super K, ? super V> builder, CacheLoader<? super K, V> loader) {
       super(builder, checkNotNull(loader));
     }

     // Cache methods

     @Override
     public V get(K key) throws ExecutionException {
       return localCache.getOrLoad(key);
     }

     @Override
     public V getUnchecked(K key) {
       try {
         return get(key);
       } catch (ExecutionException e) {
         throw new UncheckedExecutionException(e.getCause());
       }
     }

     @Override
     public final V apply(K key) {
       return getUnchecked(key);
     }

     @Override
     public ImmutableMap<K, V> getAll(Iterable<? extends K> keys) throws ExecutionException {
       Map<K, V> map = new HashMap<K, V>();
       for (K key : keys) {
         map.put(key, localCache.getOrLoad(key));
       }
       return ImmutableMap.copyOf(map);
     }

     @Override
     public void refresh(K key) {
       throw new UnsupportedOperationException();
     }
   }

   /**
    * LinkedHashMap that enforces it's maximum size and logs events in a StatsCounter object and an
    * optional RemovalListener.
    *
    * @param <K> the base key type
    * @param <V> the base value type
    */
   private class CapacityEnforcingLinkedHashMap<K, V> extends LinkedHashMap<K, Timestamped<V>> {

     private final StatsCounter statsCounter;
     private final RemovalListener removalListener;
     private final long maximumSize;

     public CapacityEnforcingLinkedHashMap(
         int initialCapacity,
         float loadFactor,
         boolean accessOrder,
         long maximumSize,
         StatsCounter statsCounter,
         @Nullable RemovalListener removalListener) {
       super(initialCapacity, loadFactor, accessOrder);
       this.maximumSize = maximumSize;
       this.statsCounter = statsCounter;
       this.removalListener = removalListener;
     }

     @Override
     protected boolean removeEldestEntry(Entry<K, Timestamped<V>> ignored) {
       boolean removal = (maximumSize == UNSET_INT) ? false : (size() > maximumSize);
       if ((removalListener != null) && removal) {
         removalListener.onRemoval(
             RemovalNotification.create(
                 ignored.getKey(), ignored.getValue().getValue(), RemovalCause.SIZE));
       }
       statsCounter.recordEviction();
       return removal;
     }
   }

   /**
    * Any updates to LocalCache.Strength used in CacheBuilder need to be matched in this class for
    * compilation purposes.
    */
   enum Strength {
     /*
      * TODO(kevinb): If we strongly reference the value and aren't loading, we needn't wrap the
      * value. This could save ~8 bytes per entry.
      */

     STRONG {
       @Override
       Equivalence<Object> defaultEquivalence() {
         return Equivalence.equals();
       }
     },

     SOFT {
       @Override
       Equivalence<Object> defaultEquivalence() {
         return Equivalence.identity();
       }
     },

     WEAK {
       @Override
       Equivalence<Object> defaultEquivalence() {
         return Equivalence.identity();
       }
     };

     abstract Equivalence<Object> defaultEquivalence();
   }

   /**
    * Implementation for the EntryIterator, which is used to build Key and Value iterators.
    *
    * <p>Expiration is only checked on hasNext(), so as to ensure that a next() call never returns
    * null when hasNext() has already been called.
    */
   class EntryIterator implements Iterator<Entry<K, V>> {
     Iterator<Entry<K, Timestamped<V>>> iterator;
     Entry<K, Timestamped<V>> lastEntry;
     Entry<K, Timestamped<V>> nextEntry;

     EntryIterator() {
       this.iterator = LocalCache.this.cachingHashMap.entrySet().iterator();
     }

     @Override
     public Entry<K, V> next() {
       if (nextEntry == null) {
         hasNext();

         if (nextEntry == null) {
           throw new NoSuchElementException();
         }
       }

       lastEntry = nextEntry;
       nextEntry = null;
       return new WriteThroughEntry(lastEntry.getKey(), lastEntry.getValue().getValue());
     }

     @Override
     public boolean hasNext() {
       if (nextEntry == null) {
         while (iterator.hasNext()) {
           Entry<K, Timestamped<V>> next = iterator.next();
           if (!isExpired(next.getValue())) {
             nextEntry = next;
             return true;
           }
         }
         return false;
       }
       return true;
     }

     @Override
     public void remove() {
       checkState(lastEntry != null);
       LocalCache.this.remove(lastEntry.getKey(), lastEntry.getValue());
       lastEntry = null;
     }
   }

   /** KeyIterator build on top of EntryIterator. */
   final class KeyIterator implements Iterator<K> {
     private EntryIterator iterator;

     KeyIterator() {
       iterator = new EntryIterator();
     }

     @Override
     public boolean hasNext() {
       return iterator.hasNext();
     }

     @Override
     public K next() {
       return iterator.next().getKey();
     }

     @Override
     public void remove() {
       iterator.remove();
     }
   }

   /** ValueIterator build on top of EntryIterator. */
   final class ValueIterator implements Iterator<V> {
     private EntryIterator iterator;

     ValueIterator() {
       iterator = new EntryIterator();
     }

     @Override
     public boolean hasNext() {
       return iterator.hasNext();
     }

     @Override
     public V next() {
       return iterator.next().getValue();
     }

     @Override
     public void remove() {
       iterator.remove();
     }
   }

   Set<K> keySet;

   @Override
   public Set<K> keySet() {
     // does not impact recency ordering
     Set<K> ks = keySet;
     return (ks != null) ? ks : (keySet = new KeySet(this));
   }

   Collection<V> values;

   @Override
   public Collection<V> values() {
     // does not impact recency ordering
     Collection<V> vs = values;
     return (vs != null) ? vs : (values = new Values(this));
   }

   Set<Entry<K, V>> entrySet;

   @Override
   public Set<Entry<K, V>> entrySet() {
     // does not impact recency ordering
     Set<Entry<K, V>> es = entrySet;
     return (es != null) ? es : (entrySet = new EntrySet(this));
   }

   /**
    * Custom Entry class used by EntryIterator.next(), that relays setValue changes to the underlying
    * map.
    */
   private final class WriteThroughEntry implements Entry<K, V> {
     final K key;
     V value;

     WriteThroughEntry(K key, V value) {
       this.key = checkNotNull(key);
       this.value = checkNotNull(value);
     }

     @Override
     public K getKey() {
       return key;
     }

     @Override
     public V getValue() {
       return value;
     }

     @Override
     public boolean equals(@Nullable Object object) {
       // Cannot use key and value equivalence
       if (object instanceof Entry) {
         Entry<?, ?> that = (Entry<?, ?>) object;
         return key.equals(that.getKey()) && value.equals(that.getValue());
       }
       return false;
     }

     @Override
     public int hashCode() {
       // Cannot use key and value equivalence
       return key.hashCode() ^ value.hashCode();
     }

     @Override
     public V setValue(V newValue) {
       throw new UnsupportedOperationException();
     }

     @Override
     public String toString() {
       return getKey() + "=" + getValue();
     }
   }

   // 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;
     }

     @Override
     public int size() {
       return map.size();
     }

     @Override
     public boolean isEmpty() {
       return map.isEmpty();
     }

     @Override
     public void clear() {
       map.clear();
     }
   }

   private final class KeySet extends AbstractCacheSet<K> {

     KeySet(ConcurrentMap<?, ?> map) {
       super(map);
     }

     @Override
     public Iterator<K> iterator() {
       return new KeyIterator();
     }

     @Override
     public boolean contains(Object o) {
       return map.containsKey(o);
     }

     @Override
     public boolean remove(Object o) {
       return map.remove(o) != null;
     }
   }

   private final class Values extends AbstractCollection<V> {
     final ConcurrentMap<?, ?> map;

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

     @Override
     public Iterator<V> iterator() {
       return new ValueIterator();
     }

     @Override
     public boolean contains(Object o) {
       return map.containsValue(o);
     }

     @Override
     public int size() {
       return map.size();
     }

     @Override
     public boolean isEmpty() {
       return map.isEmpty();
     }

     @Override
     public void clear() {
       map.clear();
     }
   }

   private final class EntrySet extends AbstractCacheSet<Entry<K, V>> {

     EntrySet(ConcurrentMap<?, ?> map) {
       super(map);
     }

     @Override
     public Iterator<Entry<K, V>> iterator() {
       return new EntryIterator();
     }

     @Override
     public boolean contains(Object o) {
       if (!(o instanceof Entry)) {
         return false;
       }
       Entry<?, ?> e = (Entry<?, ?>) o;
       Object key = e.getKey();
       if (key == null) {
         return false;
       }
       V v = LocalCache.this.get(key);

       return (v != null) && e.getValue().equals(v);
     }

     @Override
     public boolean remove(Object o) {
       if (!(o instanceof Entry)) {
         return false;
       }
       Entry<?, ?> e = (Entry<?, ?>) o;
       Object key = e.getKey();
       return (key != null) && LocalCache.this.remove(key, e.getValue());
     }
   }
 }
	/*
	* Copyright (C) 2012 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.MoreObjects.firstNonNull;
	import static com.google.common.base.Preconditions.checkNotNull;
	import static com.google.common.base.Preconditions.checkState;

	import com.google.common.base.Equivalence;
	import com.google.common.base.Ticker;
	import com.google.common.cache.AbstractCache.StatsCounter;
	import com.google.common.collect.ImmutableMap;
	import com.google.common.util.concurrent.ExecutionError;
	import com.google.common.util.concurrent.UncheckedExecutionException;
	import java.util.AbstractCollection;
	import java.util.AbstractSet;
	import java.util.Collection;
	import java.util.HashMap;
	import java.util.Iterator;
	import java.util.LinkedHashMap;
	import java.util.Map;
	import java.util.Map.Entry;
	import java.util.NoSuchElementException;
	import java.util.Set;
	import java.util.concurrent.Callable;
	import java.util.concurrent.ConcurrentMap;
	import java.util.concurrent.ExecutionException;
	import org.checkerframework.checker.nullness.qual.Nullable;

	/**
	* LocalCache emulation for GWT.
	*
	* @param <K> the base key type
	* @param <V> the base value type
	* @author Charles Fry
	* @author Jon Donovan
	*/
	public class LocalCache<K, V> implements ConcurrentMap<K, V> {
	private static final int UNSET_INT = CacheBuilder.UNSET_INT;

	private final LinkedHashMap<K, Timestamped<V>> cachingHashMap;
	private final CacheLoader<? super K, V> loader;
	private final RemovalListener removalListener;
	private final StatsCounter statsCounter;
	private final Ticker ticker;
	private final long expireAfterWrite;
	private final long expireAfterAccess;

	LocalCache(CacheBuilder<? super K, ? super V> builder, CacheLoader<? super K, V> loader) {
	this.loader = loader;
	this.removalListener = builder.removalListener;
	this.expireAfterAccess = builder.expireAfterAccessNanos;
	this.expireAfterWrite = builder.expireAfterWriteNanos;
	this.statsCounter = builder.getStatsCounterSupplier().get();

	/* Implements size-capped LinkedHashMap */
	final long maximumSize = builder.maximumSize;
	this.cachingHashMap =
	new CapacityEnforcingLinkedHashMap<K, V>(
	builder.getInitialCapacity(),
	0.75f,
	(builder.maximumSize != UNSET_INT),
	builder.maximumSize,
	statsCounter,
	removalListener);

	this.ticker = firstNonNull(builder.ticker, Ticker.systemTicker());
	}

	@Override
	public int size() {
	return cachingHashMap.size();
	}

	@Override
	public boolean isEmpty() {
	return cachingHashMap.isEmpty();
	}

	@Override
	public V get(Object key) {
	checkNotNull(key);
	Timestamped<V> value = cachingHashMap.get(key);

	if (value == null) {
	statsCounter.recordMisses(1);
	return null;
	} else if (!isExpired(value)) {
	statsCounter.recordHits(1);
	value.updateTimestamp();
	return value.getValue();
	} else {
	statsCounter.recordEviction();
	statsCounter.recordMisses(1);
	alertListenerIfPresent(key, value.getValue(), RemovalCause.EXPIRED);
	cachingHashMap.remove(key);
	return null;
	}
	}

	@Override
	public V put(K key, V value) {
	checkNotNull(key);
	checkNotNull(value);
	Timestamped<V> oldValue = cachingHashMap.put(key, new Timestamped<V>(value, ticker));
	if (oldValue == null) {
	return null;
	}
	alertListenerIfPresent(key, oldValue.getValue(), RemovalCause.REPLACED);
	return oldValue.getValue();
	}

	@Override
	public V remove(Object key) {
	Timestamped<V> stamped = cachingHashMap.remove(key);
	if (stamped != null) {
	V value = stamped.getValue();

	if (!isExpired(stamped)) {
	alertListenerIfPresent(key, value, RemovalCause.EXPLICIT);
	return value;
	}

	alertListenerIfPresent(key, value, RemovalCause.EXPIRED);
	}
	return null;
	}

	@Override
	public void putAll(Map<? extends K, ? extends V> m) {
	for (Entry<? extends K, ? extends V> entry : m.entrySet()) {
	put(entry.getKey(), entry.getValue());
	}
	}

	@Override
	public void clear() {
	if (removalListener != null) {
	for (Entry<K, Timestamped<V>> entry : cachingHashMap.entrySet()) {
	alertListenerIfPresent(entry.getKey(), entry.getValue().getValue(), RemovalCause.EXPLICIT);
	}
	}
	cachingHashMap.clear();
	}

	@Override
	public V putIfAbsent(K key, V value) {
	V currentValue = get(key);
	if (currentValue != null) {
	return currentValue;
	}
	return put(key, value);
	}

	@Override
	public boolean remove(Object key, Object value) {
	if (value.equals(get(key))) {
	alertListenerIfPresent(key, value, RemovalCause.EXPLICIT);
	remove(key);
	return true;
	}
	return false;
	}

	@Override
	public boolean replace(K key, V oldValue, V newValue) {
	if (oldValue.equals(get(key))) {
	alertListenerIfPresent(key, oldValue, RemovalCause.REPLACED);
	put(key, newValue);
	return true;
	}
	return false;
	}

	@Override
	public V replace(K key, V value) {
	V currentValue = get(key);
	if (currentValue != null) {
	alertListenerIfPresent(key, currentValue, RemovalCause.REPLACED);
	return put(key, value);
	}
	return null;
	}

	@Override
	public boolean containsKey(Object key) {
	return cachingHashMap.containsKey(key) && !isExpired(cachingHashMap.get(key));
	}

	@Override
	public boolean containsValue(Object value) {
	for (Timestamped<V> val : cachingHashMap.values()) {
	if (val.getValue().equals(value)) {
	if (!isExpired(val)) {
	return true;
	}
	}
	}
	return false;
	}

	private boolean isExpired(Timestamped<V> stamped) {
	if ((expireAfterAccess == UNSET_INT) && (expireAfterWrite == UNSET_INT)) {
	return false;
	}

	boolean expireWrite = (stamped.getWriteTimestamp() + expireAfterWrite <= currentTimeNanos());
	boolean expireAccess = (stamped.getAccessTimestamp() + expireAfterAccess <= currentTimeNanos());

	if (expireAfterAccess == UNSET_INT) {
	return expireWrite;
	}
	if (expireAfterWrite == UNSET_INT) {
	return expireAccess;
	}

	return expireWrite \|\| expireAccess;
	}

	@SuppressWarnings("GoodTime")
	private long currentTimeNanos() {
	return ticker.read();
	}

	private void alertListenerIfPresent(Object key, Object value, RemovalCause cause) {
	if (removalListener != null) {
	removalListener.onRemoval(RemovalNotification.create(key, value, cause));
	}
	}

	@SuppressWarnings("GoodTime") // timestamps as numeric primitives
	private V load(Object key) throws ExecutionException {
	long startTime = ticker.read();
	V calculatedValue;
	try {
	/*
	* This cast isn't safe, but we can rely on the fact that K is almost always passed to
	* Map.get(), and tools like IDEs and Findbugs can catch situations where this isn't the
	* case.
	*
	* The alternative is to add an overloaded method, but the chances of a user calling get()
	* instead of the new API and the risks inherent in adding a new API outweigh this little
	* hole.
	*/
	K castKey = (K) key;
	calculatedValue = loader.load(castKey);
	put(castKey, calculatedValue);
	} catch (RuntimeException e) {
	statsCounter.recordLoadException(ticker.read() - startTime);
	throw new UncheckedExecutionException(e);
	} catch (Exception e) {
	statsCounter.recordLoadException(ticker.read() - startTime);
	throw new ExecutionException(e);
	} catch (Error e) {
	statsCounter.recordLoadException(ticker.read() - startTime);
	throw new ExecutionError(e);
	}

	if (calculatedValue == null) {
	String message = loader + " returned null for key " + key + ".";
	throw new CacheLoader.InvalidCacheLoadException(message);
	}
	statsCounter.recordLoadSuccess(ticker.read() - startTime);
	return calculatedValue;
	}

	private V getIfPresent(Object key) {
	checkNotNull(key);
	Timestamped<V> value = cachingHashMap.get(key);

	if (value == null) {
	return null;
	} else if (!isExpired(value)) {
	value.updateTimestamp();
	return value.getValue();
	} else {
	alertListenerIfPresent(key, value.getValue(), RemovalCause.EXPIRED);
	cachingHashMap.remove(key);
	return null;
	}
	}

	private V getOrLoad(K key) throws ExecutionException {
	V value = get(key);
	if (value != null) {
	return value;
	}
	return load(key);
	}

	@SuppressWarnings("GoodTime") // timestamps as numeric primitives
	private static class Timestamped<V> {
	private final V value;
	private final Ticker ticker;
	private long writeTimestamp;
	private long accessTimestamp;

	public Timestamped(V value, Ticker ticker) {
	this.value = checkNotNull(value);
	this.ticker = checkNotNull(ticker);
	this.writeTimestamp = ticker.read();
	this.accessTimestamp = this.writeTimestamp;
	}

	public V getValue() {
	return value;
	}

	public void updateTimestamp() {
	accessTimestamp = ticker.read();
	}

	public long getAccessTimestamp() {
	return accessTimestamp;
	}

	public long getWriteTimestamp() {
	return writeTimestamp;
	}

	public boolean equals(Object o) {
	return value.equals(o);
	}

	public int hashCode() {
	return value.hashCode();
	}
	}

	/**
	* LocalManualCache is a wrapper around LocalCache for a cache without loading.
	*
	* @param <K> the base key type
	* @param <V> the base value type
	*/
	public static class LocalManualCache<K, V> extends AbstractCache<K, V> {
	final LocalCache<K, V> localCache;

	LocalManualCache(CacheBuilder<? super K, ? super V> builder) {
	this(builder, null);
	}

	protected LocalManualCache(
	CacheBuilder<? super K, ? super V> builder, CacheLoader<? super K, V> loader) {
	this.localCache = new LocalCache<K, V>(builder, loader);
	}

	// Cache methods

	@Override
	public V get(K key, Callable<? extends V> valueLoader) throws ExecutionException {
	V value = localCache.get(key);
	if (value != null) {
	return value;
	}

	try {
	V newValue = valueLoader.call();
	localCache.put(key, newValue);
	return newValue;
	} catch (Exception e) {
	throw new ExecutionException(e);
	}
	}

	@Override
	public @Nullable V getIfPresent(Object key) {
	return localCache.getIfPresent(key);
	}

	@Override
	public void put(K key, V value) {
	localCache.put(key, value);
	}

	@Override
	public void invalidate(Object key) {
	checkNotNull(key);
	localCache.remove(key);
	}

	@Override
	public void invalidateAll() {
	localCache.clear();
	}

	@Override
	public long size() {
	return localCache.size();
	}

	@Override
	public ConcurrentMap<K, V> asMap() {
	return localCache;
	}
	}

	/**
	* LocalLoadingCache is a wrapper around LocalCache for a cache with loading.
	*
	* @param <K> the base key type
	* @param <V> the base value type
	*/
	public static class LocalLoadingCache<K, V> extends LocalManualCache<K, V>
	implements LoadingCache<K, V> {

	LocalLoadingCache(
	CacheBuilder<? super K, ? super V> builder, CacheLoader<? super K, V> loader) {
	super(builder, checkNotNull(loader));
	}

	// Cache methods

	@Override
	public V get(K key) throws ExecutionException {
	return localCache.getOrLoad(key);
	}

	@Override
	public V getUnchecked(K key) {
	try {
	return get(key);
	} catch (ExecutionException e) {
	throw new UncheckedExecutionException(e.getCause());
	}
	}

	@Override
	public final V apply(K key) {
	return getUnchecked(key);
	}

	@Override
	public ImmutableMap<K, V> getAll(Iterable<? extends K> keys) throws ExecutionException {
	Map<K, V> map = new HashMap<K, V>();
	for (K key : keys) {
	map.put(key, localCache.getOrLoad(key));
	}
	return ImmutableMap.copyOf(map);
	}

	@Override
	public void refresh(K key) {
	throw new UnsupportedOperationException();
	}
	}

	/**
	* LinkedHashMap that enforces it's maximum size and logs events in a StatsCounter object and an
	* optional RemovalListener.
	*
	* @param <K> the base key type
	* @param <V> the base value type
	*/
	private class CapacityEnforcingLinkedHashMap<K, V> extends LinkedHashMap<K, Timestamped<V>> {

	private final StatsCounter statsCounter;
	private final RemovalListener removalListener;
	private final long maximumSize;

	public CapacityEnforcingLinkedHashMap(
	int initialCapacity,
	float loadFactor,
	boolean accessOrder,
	long maximumSize,
	StatsCounter statsCounter,
	@Nullable RemovalListener removalListener) {
	super(initialCapacity, loadFactor, accessOrder);
	this.maximumSize = maximumSize;
	this.statsCounter = statsCounter;
	this.removalListener = removalListener;
	}

	@Override
	protected boolean removeEldestEntry(Entry<K, Timestamped<V>> ignored) {
	boolean removal = (maximumSize == UNSET_INT) ? false : (size() > maximumSize);
	if ((removalListener != null) && removal) {
	removalListener.onRemoval(
	RemovalNotification.create(
	ignored.getKey(), ignored.getValue().getValue(), RemovalCause.SIZE));
	}
	statsCounter.recordEviction();
	return removal;
	}
	}

	/**
	* Any updates to LocalCache.Strength used in CacheBuilder need to be matched in this class for
	* compilation purposes.
	*/
	enum Strength {
	/*
	* TODO(kevinb): If we strongly reference the value and aren't loading, we needn't wrap the
	* value. This could save ~8 bytes per entry.
	*/

	STRONG {
	@Override
	Equivalence<Object> defaultEquivalence() {
	return Equivalence.equals();
	}
	},

	SOFT {
	@Override
	Equivalence<Object> defaultEquivalence() {
	return Equivalence.identity();
	}
	},

	WEAK {
	@Override
	Equivalence<Object> defaultEquivalence() {
	return Equivalence.identity();
	}
	};

	abstract Equivalence<Object> defaultEquivalence();
	}

	/**
	* Implementation for the EntryIterator, which is used to build Key and Value iterators.
	*
	* <p>Expiration is only checked on hasNext(), so as to ensure that a next() call never returns
	* null when hasNext() has already been called.
	*/
	class EntryIterator implements Iterator<Entry<K, V>> {
	Iterator<Entry<K, Timestamped<V>>> iterator;
	Entry<K, Timestamped<V>> lastEntry;
	Entry<K, Timestamped<V>> nextEntry;

	EntryIterator() {
	this.iterator = LocalCache.this.cachingHashMap.entrySet().iterator();
	}

	@Override
	public Entry<K, V> next() {
	if (nextEntry == null) {
	hasNext();

	if (nextEntry == null) {
	throw new NoSuchElementException();
	}
	}

	lastEntry = nextEntry;
	nextEntry = null;
	return new WriteThroughEntry(lastEntry.getKey(), lastEntry.getValue().getValue());
	}

	@Override
	public boolean hasNext() {
	if (nextEntry == null) {
	while (iterator.hasNext()) {
	Entry<K, Timestamped<V>> next = iterator.next();
	if (!isExpired(next.getValue())) {
	nextEntry = next;
	return true;
	}
	}
	return false;
	}
	return true;
	}

	@Override
	public void remove() {
	checkState(lastEntry != null);
	LocalCache.this.remove(lastEntry.getKey(), lastEntry.getValue());
	lastEntry = null;
	}
	}

	/** KeyIterator build on top of EntryIterator. */
	final class KeyIterator implements Iterator<K> {
	private EntryIterator iterator;

	KeyIterator() {
	iterator = new EntryIterator();
	}

	@Override
	public boolean hasNext() {
	return iterator.hasNext();
	}

	@Override
	public K next() {
	return iterator.next().getKey();
	}

	@Override
	public void remove() {
	iterator.remove();
	}
	}

	/** ValueIterator build on top of EntryIterator. */
	final class ValueIterator implements Iterator<V> {
	private EntryIterator iterator;

	ValueIterator() {
	iterator = new EntryIterator();
	}

	@Override
	public boolean hasNext() {
	return iterator.hasNext();
	}

	@Override
	public V next() {
	return iterator.next().getValue();
	}

	@Override
	public void remove() {
	iterator.remove();
	}
	}

	Set<K> keySet;

	@Override
	public Set<K> keySet() {
	// does not impact recency ordering
	Set<K> ks = keySet;
	return (ks != null) ? ks : (keySet = new KeySet(this));
	}

	Collection<V> values;

	@Override
	public Collection<V> values() {
	// does not impact recency ordering
	Collection<V> vs = values;
	return (vs != null) ? vs : (values = new Values(this));
	}

	Set<Entry<K, V>> entrySet;

	@Override
	public Set<Entry<K, V>> entrySet() {
	// does not impact recency ordering
	Set<Entry<K, V>> es = entrySet;
	return (es != null) ? es : (entrySet = new EntrySet(this));
	}

	/**
	* Custom Entry class used by EntryIterator.next(), that relays setValue changes to the underlying
	* map.
	*/
	private final class WriteThroughEntry implements Entry<K, V> {
	final K key;
	V value;

	WriteThroughEntry(K key, V value) {
	this.key = checkNotNull(key);
	this.value = checkNotNull(value);
	}

	@Override
	public K getKey() {
	return key;
	}

	@Override
	public V getValue() {
	return value;
	}

	@Override
	public boolean equals(@Nullable Object object) {
	// Cannot use key and value equivalence
	if (object instanceof Entry) {
	Entry<?, ?> that = (Entry<?, ?>) object;
	return key.equals(that.getKey()) && value.equals(that.getValue());
	}
	return false;
	}

	@Override
	public int hashCode() {
	// Cannot use key and value equivalence
	return key.hashCode() ^ value.hashCode();
	}

	@Override
	public V setValue(V newValue) {
	throw new UnsupportedOperationException();
	}

	@Override
	public String toString() {
	return getKey() + "=" + getValue();
	}
	}

	// 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;
	}

	@Override
	public int size() {
	return map.size();
	}

	@Override
	public boolean isEmpty() {
	return map.isEmpty();
	}

	@Override
	public void clear() {
	map.clear();
	}
	}

	private final class KeySet extends AbstractCacheSet<K> {

	KeySet(ConcurrentMap<?, ?> map) {
	super(map);
	}

	@Override
	public Iterator<K> iterator() {
	return new KeyIterator();
	}

	@Override
	public boolean contains(Object o) {
	return map.containsKey(o);
	}

	@Override
	public boolean remove(Object o) {
	return map.remove(o) != null;
	}
	}

	private final class Values extends AbstractCollection<V> {
	final ConcurrentMap<?, ?> map;

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

	@Override
	public Iterator<V> iterator() {
	return new ValueIterator();
	}

	@Override
	public boolean contains(Object o) {
	return map.containsValue(o);
	}

	@Override
	public int size() {
	return map.size();
	}

	@Override
	public boolean isEmpty() {
	return map.isEmpty();
	}

	@Override
	public void clear() {
	map.clear();
	}
	}

	private final class EntrySet extends AbstractCacheSet<Entry<K, V>> {

	EntrySet(ConcurrentMap<?, ?> map) {
	super(map);
	}

	@Override
	public Iterator<Entry<K, V>> iterator() {
	return new EntryIterator();
	}

	@Override
	public boolean contains(Object o) {
	if (!(o instanceof Entry)) {
	return false;
	}
	Entry<?, ?> e = (Entry<?, ?>) o;
	Object key = e.getKey();
	if (key == null) {
	return false;
	}
	V v = LocalCache.this.get(key);

	return (v != null) && e.getValue().equals(v);
	}

	@Override
	public boolean remove(Object o) {
	if (!(o instanceof Entry)) {
	return false;
	}
	Entry<?, ?> e = (Entry<?, ?>) o;
	Object key = e.getKey();
	return (key != null) && LocalCache.this.remove(key, e.getValue());
	}
	}
	}