#5326

Committed 15 Mar 2026 08:00PM UTC coverage: 99.861% (-0.08%) from 99.937%

Build # #5326

Build Type

push

github

Committed by

ben-manes

Commit Message

minor edge case handling

Avoid slight bias in the frequency sketch from sentinel keys. If the
access reordering is applied after the node was deleted, while other
operations no-op'd the popularity sketch would still increment for the
key. The key was replaced by a sentinel, so this inflates those hash
locations, which by collisions could inflate the popularity of another
entry.

Better timer wheel rollback on exception handling for the current
timestamp. In that case it would have simply forced a delayed full
sweep, so considered benign. More so, since the cache is not supposed
to throw any exceptions, it only acted as a failsafe in case of a bug
and therefore perfect handling was not necessary. Yet because code
walkthroughs keep flagging it, it's best to fix as the previous
approach was too subtle.

Previously, a failed computation could result in duplicate eviction
notifications. This occurred because the old entry was not removed
before the mapping function's / weigher's / Expiry's exception was
propagated. A repeatedly broken computation might notify the listener
multiple times until the entry was removed by the maintenance cycle.
As the listener is generally used for resource clean up, which is
usually idempotent, this double notification was likely fine. The
notification is still handled prior to running the mapping function to
ensure linearizability, e.g. removing a file prior to recreating it.

Coverage Stats

3847 of 3862 branches covered (99.61%)

65 of 70 new or added lines in 2 files covered. (92.86%)

1 existing line in 1 file now uncovered.

7903 of 7914 relevant lines covered (99.86%)

1.0 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

99.73

/caffeine/src/main/java/com/github/benmanes/caffeine/cache/BoundedLocalCache.java

/*
 * Copyright 2014 Ben Manes. All Rights Reserved.
 *
 * 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.github.benmanes.caffeine.cache;

import static com.github.benmanes.caffeine.cache.Async.ASYNC_EXPIRY;
import static com.github.benmanes.caffeine.cache.Caffeine.calculateHashMapCapacity;
import static com.github.benmanes.caffeine.cache.Caffeine.ceilingPowerOfTwo;
import static com.github.benmanes.caffeine.cache.Caffeine.requireArgument;
import static com.github.benmanes.caffeine.cache.Caffeine.toNanosSaturated;
import static com.github.benmanes.caffeine.cache.LocalLoadingCache.newBulkMappingFunction;
import static com.github.benmanes.caffeine.cache.LocalLoadingCache.newMappingFunction;
import static com.github.benmanes.caffeine.cache.Node.PROBATION;
import static com.github.benmanes.caffeine.cache.Node.PROTECTED;
import static com.github.benmanes.caffeine.cache.Node.WINDOW;
import static java.util.Locale.US;
import static java.util.Objects.requireNonNull;
import static java.util.Spliterator.DISTINCT;
import static java.util.Spliterator.IMMUTABLE;
import static java.util.Spliterator.NONNULL;
import static java.util.Spliterator.ORDERED;

import java.io.InvalidObjectException;
import java.io.ObjectInputStream;
import java.io.Serializable;
import java.lang.System.Logger;
import java.lang.System.Logger.Level;
import java.lang.invoke.MethodHandles;
import java.lang.invoke.VarHandle;
import java.lang.ref.Reference;
import java.lang.ref.ReferenceQueue;
import java.lang.ref.WeakReference;
import java.time.Duration;
import java.util.AbstractCollection;
import java.util.AbstractSet;
import java.util.ArrayDeque;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.Optional;
import java.util.OptionalInt;
import java.util.OptionalLong;
import java.util.Set;
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.concurrent.CancellationException;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.CompletionException;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.Executor;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.TimeoutException;
import java.util.concurrent.locks.ReentrantLock;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

import org.jspecify.annotations.NonNull;
import org.jspecify.annotations.Nullable;

import com.github.benmanes.caffeine.cache.Async.AsyncExpiry;
import com.github.benmanes.caffeine.cache.LinkedDeque.PeekingIterator;
import com.github.benmanes.caffeine.cache.Policy.CacheEntry;
import com.github.benmanes.caffeine.cache.References.InternalReference;
import com.github.benmanes.caffeine.cache.stats.StatsCounter;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import com.google.errorprone.annotations.Var;
import com.google.errorprone.annotations.concurrent.GuardedBy;

/**
 * An in-memory cache implementation that supports full concurrency of retrievals, a high expected
 * concurrency for updates, and multiple ways to bound the cache.
 * <p>
 * This class is abstract and code generated subclasses provide the complete implementation for a
 * particular configuration. This is to ensure that only the fields and execution paths necessary
 * for a given configuration are used.
 *
 * @author ben.manes@gmail.com (Ben Manes)
 * @param <K> the type of keys maintained by this cache
 * @param <V> the type of mapped values
 */
@SuppressWarnings({"RedundantSuppression", "ResultOfMethodCallIgnored", "serial", "unused"})
abstract class BoundedLocalCache<K, V> extends BLCHeader.DrainStatusRef
    implements LocalCache<K, V> {

  /*
   * This class performs a best-effort bounding of a ConcurrentHashMap using a page-replacement
   * algorithm to determine which entries to evict when the capacity is exceeded.
   *
   * Concurrency:
   * ------------
   * The page replacement algorithms are kept eventually consistent with the map. An update to the
   * map and recording of reads may not be immediately reflected in the policy's data structures.
   * These structures are guarded by a lock, and operations are applied in batches to avoid lock
   * contention. The penalty of applying the batches is spread across threads, so that the amortized
   * cost is slightly higher than performing just the ConcurrentHashMap operation [1].
   *
   * A memento of the reads and writes that were performed on the map is recorded in buffers. These
   * buffers are drained at the first opportunity after a write or when a read buffer is full. The
   * reads are offered to a buffer that will reject additions if contended on or if it is full. Due
   * to the concurrent nature of the read and write operations, a strict policy ordering is not
   * possible, but it may be observably strict when single-threaded. The buffers are drained
   * asynchronously to minimize the request latency and uses a state machine to determine when to
   * schedule this work on an executor.
   *
   * Due to a lack of a strict ordering guarantee, a task can be executed out-of-order, such as a
   * removal followed by its addition. The state of the entry is encoded using the key field to
   * avoid additional memory usage. An entry is "alive" if it is in both the hash table and the page
   * replacement policy. It is "retired" if it is not in the hash table and is pending removal from
   * the page replacement policy. Finally, an entry transitions to the "dead" state when it is
   * neither in the hash table nor the page replacement policy. Both the retired and dead states are
   * represented by a sentinel key that should not be used for map operations.
   *
   * Eviction:
   * ---------
   * Maximum size is implemented using the Window TinyLfu policy [2] due to its high hit rate, O(1)
   * time complexity, and small footprint. A new entry starts in the admission window and remains
   * there as long as it has high temporal locality (recency). Eventually an entry will slip from
   * the window into the main space. If the main space is already full, then a historic frequency
   * filter determines whether to evict the newly admitted entry or the victim entry chosen by the
   * eviction policy. This process ensures that the entries in the window were very recently used,
   * while entries in the main space are accessed very frequently and remain moderately recent. The
   * windowing allows the policy to have a high hit rate when entries exhibit a bursty access
   * pattern, while the filter ensures that popular items are retained. The admission window uses
   * LRU and the main space uses Segmented LRU.
   *
   * The optimal size of the window vs. main spaces is workload dependent [3]. A large admission
   * window is favored by recency-biased workloads, while a small one favors frequency-biased
   * workloads. When the window is too small, then recent arrivals are prematurely evicted, but when
   * it is too large, then they pollute the cache and force the eviction of more popular entries.
   * The optimal configuration is dynamically determined by using hill climbing to walk the hit rate
   * curve. This is achieved by sampling the hit rate and adjusting the window size in the direction
   * that is improving (making positive or negative steps). At each interval, the step size is
   * decreased until the hit rate climber converges at the optimal setting. The process is restarted
   * when the hit rate changes over a threshold, indicating that the workload altered, and a new
   * setting may be required.
   *
   * The historic usage is retained in a compact popularity sketch, which uses hashing to
   * probabilistically estimate an item's frequency. This exposes a flaw where an adversary could
   * use hash flooding [4] to artificially raise the frequency of the main space's victim and cause
   * all candidates to be rejected. In the worst case, by exploiting hash collisions, an attacker
   * could cause the cache to never hit and hold only worthless items, resulting in a
   * denial-of-service attack against the underlying resource. This is mitigated by introducing
   * jitter, allowing candidates that are at least moderately popular to have a small, random chance
   * of being admitted. This causes the victim to be evicted, but in a way that marginally impacts
   * the hit rate.
   *
   * Expiration:
   * -----------
   * Expiration is implemented in O(1) time complexity. The time-to-idle policy uses an access-order
   * queue, the time-to-live policy uses a write-order queue, and variable expiration uses a
   * hierarchical timer wheel [5]. The queuing policies allow for peeking at the oldest entry to
   * determine if it has expired. If it has not, then the younger entries must not have expired
   * either. If a maximum size is set, then expiration will share the queues, minimizing the
   * per-entry footprint. The timer wheel based policy uses hashing and cascading in a manner that
   * amortizes the penalty of sorting to achieve a similar algorithmic cost.
   *
   * The expiration updates are applied in a best effort fashion. The reordering of variable or
   * access-order expiration may be discarded by the read buffer if it is full or contended.
   * Similarly, the reordering of write expiration may be ignored for an entry if the last update
   * was within a short time window. This is done to avoid overwhelming the write buffer.
   *
   * [1] BP-Wrapper: A Framework Making Any Replacement Algorithms (Almost) Lock Contention Free
   * https://web.njit.edu/~dingxn/papers/BP-Wrapper.pdf
   * [2] TinyLFU: A Highly Efficient Cache Admission Policy
   * https://dl.acm.org/citation.cfm?id=3149371
   * [3] Adaptive Software Cache Management
   * https://dl.acm.org/citation.cfm?id=3274816
   * [4] Denial of Service via Algorithmic Complexity Attack
   * https://www.usenix.org/legacy/events/sec03/tech/full_papers/crosby/crosby.pdf
   * [5] Hashed and Hierarchical Timing Wheels
   * http://www.cs.columbia.edu/~nahum/w6998/papers/ton97-timing-wheels.pdf
   */

  static final Logger logger = System.getLogger(BoundedLocalCache.class.getName());

  /** The number of CPUs */
  static final int NCPU = Runtime.getRuntime().availableProcessors();
  /** The initial capacity of the write buffer. */
  static final int WRITE_BUFFER_MIN = 4;
  /** The maximum capacity of the write buffer. */
  static final int WRITE_BUFFER_MAX = 128 * ceilingPowerOfTwo(NCPU);
  /** The number of attempts to insert into the write buffer before yielding. */
  static final int WRITE_BUFFER_RETRIES = 100;
  /** The maximum weighted capacity of the map. */
  static final long MAXIMUM_CAPACITY = Long.MAX_VALUE - Integer.MAX_VALUE;
  /** The initial percent of the maximum weighted capacity dedicated to the main space. */
  static final double PERCENT_MAIN = 0.99d;
  /** The percent of the maximum weighted capacity dedicated to the main's protected space. */
  static final double PERCENT_MAIN_PROTECTED = 0.80d;
  /** The difference in hit rates that restarts the climber. */
  static final double HILL_CLIMBER_RESTART_THRESHOLD = 0.05d;
  /** The percent of the total size to adapt the window by. */
  static final double HILL_CLIMBER_STEP_PERCENT = 0.0625d;
  /** The rate to decrease the step size to adapt by. */
  static final double HILL_CLIMBER_STEP_DECAY_RATE = 0.98d;
  /** The minimum popularity for allowing randomized admission. */
  static final int ADMIT_HASHDOS_THRESHOLD = 6;
  /** The maximum number of entries that can be transferred between queues. */
  static final int QUEUE_TRANSFER_THRESHOLD = 1_000;
  /** The maximum time window between entry updates before the expiration must be reordered. */
  static final long EXPIRE_WRITE_TOLERANCE = TimeUnit.SECONDS.toNanos(1);
  /** The maximum duration before an entry expires. */
  static final long MAXIMUM_EXPIRY = (Long.MAX_VALUE >> 1); // 150 years
  /** The duration to wait on the eviction lock before warning of a possible misuse. */
  static final long WARN_AFTER_LOCK_WAIT_NANOS = TimeUnit.SECONDS.toNanos(30);
  /** The number of retries before computing to validate the entry's integrity; pow2 modulus. */
  static final int MAX_PUT_SPIN_WAIT_ATTEMPTS = 1024 - 1;
  /** The handle for the in-flight refresh operations. */
  static final VarHandle REFRESHES = findVarHandle(
      BoundedLocalCache.class, "refreshes", ConcurrentMap.class);

  final @Nullable RemovalListener<K, V> evictionListener;
  final @Nullable AsyncCacheLoader<K, V> cacheLoader;

  final MpscGrowableArrayQueue<Runnable> writeBuffer;
  final ConcurrentHashMap<Object, Node<K, V>> data;
  final PerformCleanupTask drainBuffersTask;
  final Consumer<Node<K, V>> accessPolicy;
  final Buffer<Node<K, V>> readBuffer;
  final NodeFactory<K, V> nodeFactory;
  final ReentrantLock evictionLock;
  final Weigher<K, V> weigher;
  final Executor executor;

  final boolean isWeighted;
  final boolean isAsync;

  @Nullable Set<K> keySet;
  @Nullable Collection<V> values;
  @Nullable Set<Entry<K, V>> entrySet;
  volatile @Nullable ConcurrentMap<Object, CompletableFuture<?>> refreshes;

  /** Creates an instance based on the builder's configuration. */
  @SuppressWarnings("GuardedBy")
  protected BoundedLocalCache(Caffeine<K, V> builder,
      @Nullable AsyncCacheLoader<K, V> cacheLoader, boolean isAsync) {
    this.isAsync = isAsync;
    this.cacheLoader = cacheLoader;
    executor = builder.getExecutor();
    isWeighted = builder.isWeighted();
    evictionLock = new ReentrantLock();
    weigher = builder.getWeigher(isAsync);
    drainBuffersTask = new PerformCleanupTask(this);
    nodeFactory = NodeFactory.newFactory(builder, isAsync);
    evictionListener = builder.getEvictionListener(isAsync);
    data = new ConcurrentHashMap<>(builder.getInitialCapacity());
    readBuffer = evicts() || collectKeys() || collectValues() || expiresAfterAccess()
        ? new BoundedBuffer<>()
        : Buffer.disabled();
    accessPolicy = (evicts() || expiresAfterAccess()) ? this::onAccess : e -> {};
    writeBuffer = new MpscGrowableArrayQueue<>(WRITE_BUFFER_MIN, WRITE_BUFFER_MAX);

    if (evicts()) {
      setMaximumSize(builder.getMaximum());
    }
  }

  /** Ensures that the node is alive during the map operation. */
  void requireIsAlive(Object key, Node<?, ?> node) {
    if (!node.isAlive()) {
      throw new IllegalStateException(brokenEqualityMessage(key, node));
    }
  }

  /** Logs if the node cannot be found in the map but is still alive. */
  void logIfAlive(Node<?, ?> node) {
    if (node.isAlive()) {
      String message = brokenEqualityMessage(node.getKeyReference(), node);
      logger.log(Level.ERROR, message, new IllegalStateException());
    }
  }

  /** Returns the formatted broken equality error message. */
  String brokenEqualityMessage(Object key, Node<?, ?> node) {
    return String.format(US, "An invalid state was detected, occurring when the key's equals or "
        + "hashCode was modified while residing in the cache. This violation of the Map "
        + "contract can lead to non-deterministic behavior (key: %s, key type: %s, "
        + "node type: %s, cache type: %s).", key, key.getClass().getName(),
        node.getClass().getSimpleName(), getClass().getSimpleName());
  }

  /** Throws the exception, wrapping checked exceptions in a {@link CompletionException}. */
  static void throwException(Throwable t) {
    if (t instanceof RuntimeException) {
      throw (RuntimeException) t;
    } else if (t instanceof Error) {
      throw (Error) t;
    }
    throw new CompletionException(t);
  }

  /* --------------- Shared --------------- */

  @Override
  public boolean isAsync() {
    return isAsync;
  }

  /** Returns if the node's value is currently being computed asynchronously. */
  final boolean isComputingAsync(@Nullable V value) {
    return isAsync && !Async.isReady((CompletableFuture<?>) value);
  }

  @GuardedBy("evictionLock")
  protected AccessOrderDeque<Node<K, V>> accessOrderWindowDeque() {
    throw new UnsupportedOperationException();
  }

  @GuardedBy("evictionLock")
  protected AccessOrderDeque<Node<K, V>> accessOrderProbationDeque() {
    throw new UnsupportedOperationException();
  }

  @GuardedBy("evictionLock")
  protected AccessOrderDeque<Node<K, V>> accessOrderProtectedDeque() {
    throw new UnsupportedOperationException();
  }

  @GuardedBy("evictionLock")
  protected WriteOrderDeque<Node<K, V>> writeOrderDeque() {
    throw new UnsupportedOperationException();
  }

  @Override
  public final Executor executor() {
    return executor;
  }

  @Override
  public ConcurrentMap<Object, CompletableFuture<?>> refreshes() {
    @Var var pending = refreshes;
    if (pending == null) {
      pending = new ConcurrentHashMap<>();
      if (!REFRESHES.compareAndSet(this, null, pending)) {
        pending = requireNonNull(refreshes);
      }
    }
    return pending;
  }

  /** Invalidate the in-flight refresh. */
  @SuppressWarnings("RedundantCollectionOperation")
  void discardRefresh(Object keyReference) {
    var pending = refreshes;
    if ((pending != null) && pending.containsKey(keyReference)) {
      pending.remove(keyReference);
    }
  }

  @Override
  public Object referenceKey(K key) {
    return nodeFactory.newLookupKey(key);
  }

  @Override
  public boolean isPendingEviction(K key) {
    Node<K, V> node = data.get(nodeFactory.newLookupKey(key));
    return (node != null)
        && ((node.getValue() == null) || hasExpired(node, expirationTicker().read()));
  }

  /* --------------- Stats Support --------------- */

  @Override
  public boolean isRecordingStats() {
    return false;
  }

  @Override
  public StatsCounter statsCounter() {
    return StatsCounter.disabledStatsCounter();
  }

  @Override
  public Ticker statsTicker() {
    return Ticker.disabledTicker();
  }

  /* --------------- Removal Listener Support --------------- */

  protected @Nullable RemovalListener<K, V> removalListener() {
    return null;
  }

  @Override
  public void notifyRemoval(@Nullable K key, @Nullable V value, RemovalCause cause) {
    var removalListener = removalListener();
    if (removalListener == null) {
      return;
    }
    Runnable task = () -> {
      try {
        removalListener.onRemoval(key, value, cause);
      } catch (Throwable t) {
        logger.log(Level.WARNING, "Exception thrown by removal listener", t);
      }
    };
    try {
      executor.execute(task);
    } catch (Throwable t) {
      logger.log(Level.ERROR, "Exception thrown when submitting removal listener", t);
      task.run();
    }
  }

  /* --------------- Eviction Listener Support --------------- */

  void notifyEviction(@Nullable K key, @Nullable V value, RemovalCause cause) {
    if (evictionListener == null) {
      return;
    }
    try {
      evictionListener.onRemoval(key, value, cause);
    } catch (Throwable t) {
      logger.log(Level.WARNING, "Exception thrown by eviction listener", t);
    }
  }

  /* --------------- Reference Support --------------- */

  /** Returns if the keys are weak reference garbage collected. */
  protected boolean collectKeys() {
    return false;
  }

  /** Returns if the values are weak or soft reference garbage collected. */
  protected boolean collectValues() {
    return false;
  }

  @SuppressWarnings({"DataFlowIssue", "NullAway"})
  protected ReferenceQueue<K> keyReferenceQueue() {
    return null;
  }

  @SuppressWarnings({"DataFlowIssue", "NullAway"})
  protected ReferenceQueue<V> valueReferenceQueue() {
    return null;
  }

  /* --------------- Expiration Support --------------- */

  /** Returns the {@link Pacer} used to schedule the maintenance task. */
  protected @Nullable Pacer pacer() {
    return null;
  }

  /** Returns if the cache expires entries after a variable time threshold. */
  protected boolean expiresVariable() {
    return false;
  }

  /** Returns if the cache expires entries after an access time threshold. */
  protected boolean expiresAfterAccess() {
    return false;
  }

  /** Returns how long after the last access to an entry the map will retain that entry. */
  protected long expiresAfterAccessNanos() {
    throw new UnsupportedOperationException();
  }

  protected void setExpiresAfterAccessNanos(long expireAfterAccessNanos) {
    throw new UnsupportedOperationException();
  }

  /** Returns if the cache expires entries after a write time threshold. */
  protected boolean expiresAfterWrite() {
    return false;
  }

  /** Returns how long after the last write to an entry the map will retain that entry. */
  protected long expiresAfterWriteNanos() {
    throw new UnsupportedOperationException();
  }

  protected void setExpiresAfterWriteNanos(long expireAfterWriteNanos) {
    throw new UnsupportedOperationException();
  }

  /** Returns if the cache refreshes entries after a write time threshold. */
  protected boolean refreshAfterWrite() {
    return false;
  }

  /** Returns how long after the last write an entry becomes a candidate for refresh. */
  protected long refreshAfterWriteNanos() {
    throw new UnsupportedOperationException();
  }

  protected void setRefreshAfterWriteNanos(long refreshAfterWriteNanos) {
    throw new UnsupportedOperationException();
  }

  @Override
  @SuppressWarnings({"DataFlowIssue", "NullAway"})
  public Expiry<K, V> expiry() {
    return null;
  }

  /** Returns the {@link Ticker} used by this cache for expiration. */
  public Ticker expirationTicker() {
    return Ticker.disabledTicker();
  }

  protected TimerWheel<K, V> timerWheel() {
    throw new UnsupportedOperationException();
  }

  /* --------------- Eviction Support --------------- */

  /** Returns if the cache evicts entries due to a maximum size or weight threshold. */
  protected boolean evicts() {
    return false;
  }

  /** Returns if entries may be assigned different weights. */
  protected boolean isWeighted() {
    return (weigher != Weigher.singletonWeigher());
  }

  protected FrequencySketch frequencySketch() {
    throw new UnsupportedOperationException();
  }

  /** Returns if an access to an entry can skip notifying the eviction policy. */
  protected boolean fastpath() {
    return false;
  }

  /** Returns the maximum weighted size. */
  protected long maximum() {
    throw new UnsupportedOperationException();
  }

  /** Returns the maximum weighted size. */
  protected long maximumAcquire() {
    throw new UnsupportedOperationException();
  }

  /** Returns the maximum weighted size of the window space. */
  protected long windowMaximum() {
    throw new UnsupportedOperationException();
  }

  /** Returns the maximum weighted size of the main's protected space. */
  protected long mainProtectedMaximum() {
    throw new UnsupportedOperationException();
  }

  @GuardedBy("evictionLock")
  protected void setMaximum(long maximum) {
    throw new UnsupportedOperationException();
  }

  @GuardedBy("evictionLock")
  protected void setWindowMaximum(long maximum) {
    throw new UnsupportedOperationException();
  }

  @GuardedBy("evictionLock")
  protected void setMainProtectedMaximum(long maximum) {
    throw new UnsupportedOperationException();
  }

  /** Returns the combined weight of the values in the cache (may be negative). */
  protected long weightedSize() {
    throw new UnsupportedOperationException();
  }

  /** Returns the combined weight of the values in the cache (may be negative). */
  protected long weightedSizeAcquire() {
    throw new UnsupportedOperationException();
  }

  /** Returns the uncorrected combined weight of the values in the window space. */
  protected long windowWeightedSize() {
    throw new UnsupportedOperationException();
  }

  /** Returns the uncorrected combined weight of the values in the main's protected space. */
  protected long mainProtectedWeightedSize() {
    throw new UnsupportedOperationException();
  }

  @GuardedBy("evictionLock")
  protected void setWeightedSize(long weightedSize) {
    throw new UnsupportedOperationException();
  }

  @GuardedBy("evictionLock")
  protected void setWindowWeightedSize(long weightedSize) {
    throw new UnsupportedOperationException();
  }

  @GuardedBy("evictionLock")
  protected void setMainProtectedWeightedSize(long weightedSize) {
    throw new UnsupportedOperationException();
  }

  protected int hitsInSample() {
    throw new UnsupportedOperationException();
  }

  protected int missesInSample() {
    throw new UnsupportedOperationException();
  }

  protected double stepSize() {
    throw new UnsupportedOperationException();
  }

  protected double previousSampleHitRate() {
    throw new UnsupportedOperationException();
  }

  protected long adjustment() {
    throw new UnsupportedOperationException();
  }

  @GuardedBy("evictionLock")
  protected void setHitsInSample(int hitCount) {
    throw new UnsupportedOperationException();
  }

  @GuardedBy("evictionLock")
  protected void setMissesInSample(int missCount) {
    throw new UnsupportedOperationException();
  }

  @GuardedBy("evictionLock")
  protected void setStepSize(double stepSize) {
    throw new UnsupportedOperationException();
  }

  @GuardedBy("evictionLock")
  protected void setPreviousSampleHitRate(double hitRate) {
    throw new UnsupportedOperationException();
  }

  @GuardedBy("evictionLock")
  protected void setAdjustment(long amount) {
    throw new UnsupportedOperationException();
  }

  /**
   * Sets the maximum weighted size of the cache. The caller may need to perform a maintenance cycle
   * to eagerly evicts entries until the cache shrinks to the appropriate size.
   */
  @GuardedBy("evictionLock")
  @SuppressWarnings({"ConstantValue", "Varifier"})
  void setMaximumSize(long maximum) {
    requireArgument(maximum >= 0, "maximum must not be negative");
    if (maximum == maximum()) {
      return;
    }

    long max = Math.min(maximum, MAXIMUM_CAPACITY);
    long window = max - (long) (PERCENT_MAIN * max);
    long mainProtected = (long) (PERCENT_MAIN_PROTECTED * (max - window));

    setMaximum(max);
    setWindowMaximum(window);
    setMainProtectedMaximum(mainProtected);

    setHitsInSample(0);
    setMissesInSample(0);
    setStepSize(-HILL_CLIMBER_STEP_PERCENT * max);

    if ((frequencySketch() != null) && !isWeighted() && (weightedSize() >= (max >>> 1))) {
      // Lazily initialize when close to the maximum size
      frequencySketch().ensureCapacity(max);
    }
  }

  /** Evicts entries if the cache exceeds the maximum. */
  @GuardedBy("evictionLock")
  void evictEntries() {
    if (!evicts()) {
      return;
    }
    var candidate = evictFromWindow();
    evictFromMain(candidate);
  }

  /**
   * Evicts entries from the window space into the main space while the window size exceeds a
   * maximum.
   *
   * @return the first candidate promoted into the probation space
   */
  @GuardedBy("evictionLock")
  @Nullable Node<K, V> evictFromWindow() {
    @Var Node<K, V> first = null;
    @Var Node<K, V> node = accessOrderWindowDeque().peekFirst();
    while (windowWeightedSize() > windowMaximum()) {
      // The pending operations will adjust the size to reflect the correct weight
      if (node == null) {
        break;
      }

      Node<K, V> next = node.getNextInAccessOrder();
      if (node.getPolicyWeight() != 0) {
        node.makeMainProbation();
        accessOrderWindowDeque().remove(node);
        accessOrderProbationDeque().offerLast(node);
        if (first == null) {
          first = node;
        }

        setWindowWeightedSize(windowWeightedSize() - node.getPolicyWeight());
      }
      node = next;
    }

    return first;
  }

  /**
   * Evicts entries from the main space if the cache exceeds the maximum capacity. The main space
   * determines whether admitting an entry (coming from the window space) is preferable to retaining
   * the eviction policy's victim. This decision is made using a frequency filter so that the
   * least frequently used entry is removed.
   * <p>
   * The window space's candidates were previously promoted to the probation space at its MRU
   * position and the eviction policy's victim starts at the LRU position. The candidates are
   * evaluated in promotion order while an eviction is required, and if exhausted then additional
   * entries are retrieved from the window space. Likewise, if the victim selection exhausts the
   * probation space then additional entries are retrieved from the protected space. The queues are
   * consumed in LRU order and the evicted entry is the one with a lower relative frequency, where
   * the preference is to retain the main space's victims versus the window space's candidates on a
   * tie.
   *
   * @param candidate the first candidate promoted into the probation space
   */
  @GuardedBy("evictionLock")
  void evictFromMain(@Var @Nullable Node<K, V> candidate) {
    @Var int victimQueue = PROBATION;
    @Var int candidateQueue = PROBATION;
    @Var Node<K, V> victim = accessOrderProbationDeque().peekFirst();
    while (weightedSize() > maximum()) {
      // Search the admission window for additional candidates
      if ((candidate == null) && (candidateQueue == PROBATION)) {
        candidate = accessOrderWindowDeque().peekFirst();
        candidateQueue = WINDOW;
      }

      // Try evicting from the protected and window queues
      if ((candidate == null) && (victim == null)) {
        if (victimQueue == PROBATION) {
          victim = accessOrderProtectedDeque().peekFirst();
          victimQueue = PROTECTED;
          continue;
        } else if (victimQueue == PROTECTED) {
          victim = accessOrderWindowDeque().peekFirst();
          victimQueue = WINDOW;
          continue;
        }

        // The pending operations will adjust the size to reflect the correct weight
        break;
      }

      // Skip over entries with zero weight
      if ((victim != null) && (victim.getPolicyWeight() == 0)) {
        victim = victim.getNextInAccessOrder();
        continue;
      } else if ((candidate != null) && (candidate.getPolicyWeight() == 0)) {
        candidate = candidate.getNextInAccessOrder();
        continue;
      }

      // Evict immediately if only one of the entries is present
      if (victim == null) {
        requireNonNull(candidate);
        Node<K, V> previous = candidate.getNextInAccessOrder();
        Node<K, V> evict = candidate;
        candidate = previous;
        evictEntry(evict, RemovalCause.SIZE, 0L);
        continue;
      } else if (candidate == null) {
        Node<K, V> evict = victim;
        victim = victim.getNextInAccessOrder();
        evictEntry(evict, RemovalCause.SIZE, 0L);
        continue;
      }

      // Evict immediately if both selected the same entry
      if (candidate == victim) {
        victim = victim.getNextInAccessOrder();
        evictEntry(candidate, RemovalCause.SIZE, 0L);
        candidate = null;
        continue;
      }

      // Evict immediately if an entry was collected
      var victimKeyRef = victim.getKeyReferenceOrNull();
      var candidateKeyRef = candidate.getKeyReferenceOrNull();
      if (victimKeyRef == null) {
        Node<K, V> evict = victim;
        victim = victim.getNextInAccessOrder();
        evictEntry(evict, RemovalCause.COLLECTED, 0L);
        continue;
      } else if (candidateKeyRef == null) {
        Node<K, V> evict = candidate;
        candidate = candidate.getNextInAccessOrder();
        evictEntry(evict, RemovalCause.COLLECTED, 0L);
        continue;
      }

      // Evict immediately if an entry was removed
      if (!victim.isAlive()) {
        Node<K, V> evict = victim;
        victim = victim.getNextInAccessOrder();
        evictEntry(evict, RemovalCause.SIZE, 0L);
        continue;
      } else if (!candidate.isAlive()) {
        Node<K, V> evict = candidate;
        candidate = candidate.getNextInAccessOrder();
        evictEntry(evict, RemovalCause.SIZE, 0L);
        continue;
      }

      // Evict immediately if the candidate's weight exceeds the maximum
      if (candidate.getPolicyWeight() > maximum()) {
        Node<K, V> evict = candidate;
        candidate = candidate.getNextInAccessOrder();
        evictEntry(evict, RemovalCause.SIZE, 0L);
        continue;
      }

      // Evict the entry with the lowest frequency
      if (admit(candidateKeyRef, victimKeyRef)) {
        Node<K, V> evict = victim;
        victim = victim.getNextInAccessOrder();
        evictEntry(evict, RemovalCause.SIZE, 0L);
        candidate = candidate.getNextInAccessOrder();
      } else {
        Node<K, V> evict = candidate;
        candidate = candidate.getNextInAccessOrder();
        evictEntry(evict, RemovalCause.SIZE, 0L);
      }
    }
  }

  /**
   * Determines if the candidate should be accepted into the main space, as determined by its
   * frequency relative to the victim. A small amount of randomness is used to protect against hash
   * collision attacks, where the victim's frequency is artificially raised so that no new entries
   * are admitted.
   *
   * @param candidateKeyRef the keyRef for the entry being proposed for long term retention
   * @param victimKeyRef the keyRef for the entry chosen by the eviction policy for replacement
   * @return if the candidate should be admitted and the victim ejected
   */
  @GuardedBy("evictionLock")
  boolean admit(Object candidateKeyRef, Object victimKeyRef) {
    int candidateFreq = frequencySketch().frequency(candidateKeyRef);
    int victimFreq = frequencySketch().frequency(victimKeyRef);
    if (candidateFreq > victimFreq) {
      return true;
    } else if (candidateFreq >= ADMIT_HASHDOS_THRESHOLD) {
      // The maximum frequency is 15 and halved to 7 after a reset to age the history. An attack
      // exploits that a hot candidate is rejected in favor of a hot victim. The threshold of a warm
      // candidate reduces the number of random acceptances to minimize the impact on the hit rate.
      int random = ThreadLocalRandom.current().nextInt();
      return ((random & 127) == 0);
    }
    return false;
  }

  /** Expires entries that have expired by access, write, or variable. */
  @GuardedBy("evictionLock")
  void expireEntries() {
    long now = expirationTicker().read();
    expireAfterAccessEntries(now);
    expireAfterWriteEntries(now);
    expireVariableEntries(now);

    Pacer pacer = pacer();
    if (pacer != null) {
      long delay = getExpirationDelay(now);
      if (delay == Long.MAX_VALUE) {
        pacer.cancel();
      } else {
        pacer.schedule(executor, drainBuffersTask, now, delay);
      }
    }
  }

  /** Expires entries in the access-order queue. */
  @GuardedBy("evictionLock")
  void expireAfterAccessEntries(long now) {
    if (!expiresAfterAccess()) {
      return;
    }

    expireAfterAccessEntries(now, accessOrderWindowDeque());
    if (evicts()) {
      expireAfterAccessEntries(now, accessOrderProbationDeque());
      expireAfterAccessEntries(now, accessOrderProtectedDeque());
    }
  }

  /** Expires entries in an access-order queue. */
  @GuardedBy("evictionLock")
  void expireAfterAccessEntries(long now, AccessOrderDeque<Node<K, V>> accessOrderDeque) {
    long duration = expiresAfterAccessNanos();
    for (;;) {
      Node<K, V> node = accessOrderDeque.peekFirst();
      if ((node == null) || ((now - node.getAccessTime()) < duration)
          || !evictEntry(node, RemovalCause.EXPIRED, now)) {
        return;
      }
    }
  }

  /** Expires entries on the write-order queue. */
  @GuardedBy("evictionLock")
  void expireAfterWriteEntries(long now) {
    if (!expiresAfterWrite()) {
      return;
    }
    long duration = expiresAfterWriteNanos();
    for (;;) {
      Node<K, V> node = writeOrderDeque().peekFirst();
      if ((node == null) || ((now - node.getWriteTime()) < duration)
          || !evictEntry(node, RemovalCause.EXPIRED, now)) {
        break;
      }
    }
  }

  /** Expires entries in the timer wheel. */
  @GuardedBy("evictionLock")
  void expireVariableEntries(long now) {
    if (expiresVariable()) {
      timerWheel().advance(this, now);
    }
  }

  /** Returns the duration until the next item expires, or {@link Long#MAX_VALUE} if none. */
  @GuardedBy("evictionLock")
  long getExpirationDelay(long now) {
    @Var long delay = Long.MAX_VALUE;
    if (expiresAfterAccess()) {
      @Var Node<K, V> node = accessOrderWindowDeque().peekFirst();
      if (node != null) {
        delay = Math.min(delay, expiresAfterAccessNanos() - (now - node.getAccessTime()));
      }
      if (evicts()) {
        node = accessOrderProbationDeque().peekFirst();
        if (node != null) {
          delay = Math.min(delay, expiresAfterAccessNanos() - (now - node.getAccessTime()));
        }
        node = accessOrderProtectedDeque().peekFirst();
        if (node != null) {
          delay = Math.min(delay, expiresAfterAccessNanos() - (now - node.getAccessTime()));
        }
      }
    }
    if (expiresAfterWrite()) {
      Node<K, V> node = writeOrderDeque().peekFirst();
      if (node != null) {
        delay = Math.min(delay, expiresAfterWriteNanos() - (now - node.getWriteTime()));
      }
    }
    if (expiresVariable()) {
      delay = Math.min(delay, timerWheel().getExpirationDelay());
    }
    return delay;
  }

  /** Returns if the entry has expired. */
  @SuppressWarnings("ShortCircuitBoolean")
  boolean hasExpired(Node<K, V> node, long now) {
    if (isComputingAsync(node.getValue())) {
      return false;
    }
    return (expiresAfterAccess() && (now - node.getAccessTime() >= expiresAfterAccessNanos()))
        | (expiresAfterWrite() && (now - node.getWriteTime() >= expiresAfterWriteNanos()))
        | (expiresVariable() && (now - node.getVariableTime() >= 0));
  }

  /**
   * Attempts to evict the entry based on the given removal cause. A removal may be ignored if the
   * entry was updated and is no longer eligible for eviction.
   *
   * @param node the entry to evict
   * @param cause the reason to evict
   * @param now the current time, used only if expiring
   * @return if the entry was evicted
   */
  @GuardedBy("evictionLock")
  @SuppressWarnings({"GuardedByChecker", "SynchronizationOnLocalVariableOrMethodParameter"})
  boolean evictEntry(Node<K, V> node, RemovalCause cause, long now) {
    K key = node.getKey();
    @SuppressWarnings({"unchecked", "Varifier"})
    @Nullable V[] value = (V[]) new Object[1];
    var removed = new boolean[1];
    var resurrect = new boolean[1];
    var actualCause = new RemovalCause[1];
    var keyReference = node.getKeyReference();

    data.computeIfPresent(keyReference, (k, n) -> {
      if (n != node) {
        return n;
      }
      synchronized (node) {
        value[0] = node.getValue();

        if ((key == null) || (value[0] == null)) {
          actualCause[0] = RemovalCause.COLLECTED;
        } else if (cause == RemovalCause.COLLECTED) {
          resurrect[0] = true;
          return node;
        } else {
          actualCause[0] = cause;
        }

        if (actualCause[0] == RemovalCause.EXPIRED) {
          @Var boolean expired = false;
          if (expiresAfterAccess()) {
            expired |= ((now - node.getAccessTime()) >= expiresAfterAccessNanos());
          }
          if (expiresAfterWrite()) {
            expired |= ((now - node.getWriteTime()) >= expiresAfterWriteNanos());
          }
          if (expiresVariable()) {
            expired |= ((now - node.getVariableTime()) >= 0);
          }
          if (!expired) {
            resurrect[0] = true;
            return node;
          }
        } else if (actualCause[0] == RemovalCause.SIZE) {
          int weight = node.getWeight();
          if (weight == 0) {
            resurrect[0] = true;
            return node;
          }
        }

        notifyEviction(key, value[0], actualCause[0]);
        discardRefresh(keyReference);
        removed[0] = true;
        node.retire();
        return null;
      }
    });

    // The entry is no longer eligible for eviction
    if (resurrect[0]) {
      return false;
    }

    // If the eviction fails due to a concurrent removal of the victim, that removal may cancel out
    // the addition that triggered this eviction. The victim is eagerly unlinked and the size
    // decremented before the removal task so that if an eviction is still required then a new
    // victim will be chosen for removal.
    if (node.inWindow() && (evicts() || expiresAfterAccess())) {
      accessOrderWindowDeque().remove(node);
    } else if (evicts()) {
      if (node.inMainProbation()) {
        accessOrderProbationDeque().remove(node);
      } else {
        accessOrderProtectedDeque().remove(node);
      }
    }
    if (expiresAfterWrite()) {
      writeOrderDeque().remove(node);
    } else if (expiresVariable()) {
      timerWheel().deschedule(node);
    }

    synchronized (node) {
      logIfAlive(node);
      makeDead(node);
    }

    if (removed[0]) {
      statsCounter().recordEviction(node.getWeight(), actualCause[0]);
      notifyRemoval(key, value[0], actualCause[0]);
    }

    return true;
  }

  /** Adapts the eviction policy to towards the optimal recency / frequency configuration. */
  @GuardedBy("evictionLock")
  @SuppressWarnings("UnnecessaryReturnStatement")
  void climb() {
    if (!evicts()) {
      return;
    }

    determineAdjustment();
    demoteFromMainProtected();
    long amount = adjustment();
    if (amount == 0) {
      return;
    } else if (amount > 0) {
      increaseWindow();
    } else {
      decreaseWindow();
    }
  }

  /** Calculates the amount to adapt the window by and sets {@link #adjustment()} accordingly. */
  @GuardedBy("evictionLock")
  void determineAdjustment() {
    if (frequencySketch().isNotInitialized()) {
      setPreviousSampleHitRate(0.0);
      setMissesInSample(0);
      setHitsInSample(0);
      return;
    }

    int requestCount = hitsInSample() + missesInSample();
    if (requestCount < frequencySketch().sampleSize) {
      return;
    }

    double hitRate = (double) hitsInSample() / requestCount;
    double hitRateChange = hitRate - previousSampleHitRate();
    double amount = (hitRateChange >= 0) ? stepSize() : -stepSize();
    double nextStepSize = (Math.abs(hitRateChange) >= HILL_CLIMBER_RESTART_THRESHOLD)
        ? HILL_CLIMBER_STEP_PERCENT * maximum() * (amount >= 0 ? 1 : -1)
        : HILL_CLIMBER_STEP_DECAY_RATE * amount;
    setPreviousSampleHitRate(hitRate);
    setAdjustment((long) amount);
    setStepSize(nextStepSize);
    setMissesInSample(0);
    setHitsInSample(0);
  }

  /**
   * Increases the size of the admission window by shrinking the portion allocated to the main
   * space. As the main space is partitioned into probation and protected regions (80% / 20%), for
   * simplicity only the protected is reduced. If the regions exceed their maximums, this may cause
   * protected items to be demoted to the probation region and probation items to be demoted to the
   * admission window.
   */
  @GuardedBy("evictionLock")
  void increaseWindow() {
    if (mainProtectedMaximum() == 0) {
      return;
    }

    @Var long quota = Math.min(adjustment(), mainProtectedMaximum());
    setMainProtectedMaximum(mainProtectedMaximum() - quota);
    setWindowMaximum(windowMaximum() + quota);
    demoteFromMainProtected();

    for (int i = 0; i < QUEUE_TRANSFER_THRESHOLD; i++) {
      @Var Node<K, V> candidate = accessOrderProbationDeque().peekFirst();
      @Var boolean probation = true;
      if ((candidate == null) || (quota < candidate.getPolicyWeight())) {
        candidate = accessOrderProtectedDeque().peekFirst();
        probation = false;
      }
      if (candidate == null) {
        break;
      }

      int weight = candidate.getPolicyWeight();
      if (quota < weight) {
        break;
      }

      quota -= weight;
      if (probation) {
        accessOrderProbationDeque().remove(candidate);
      } else {
        setMainProtectedWeightedSize(mainProtectedWeightedSize() - weight);
        accessOrderProtectedDeque().remove(candidate);
      }
      setWindowWeightedSize(windowWeightedSize() + weight);
      accessOrderWindowDeque().offerLast(candidate);
      candidate.makeWindow();
    }

    setMainProtectedMaximum(mainProtectedMaximum() + quota);
    setWindowMaximum(windowMaximum() - quota);
    setAdjustment(quota);
  }

  /** Decreases the size of the admission window and increases the main's protected region. */
  @GuardedBy("evictionLock")
  void decreaseWindow() {
    if (windowMaximum() <= 1) {
      return;
    }

    @Var long quota = Math.min(-adjustment(), Math.max(0, windowMaximum() - 1));
    setMainProtectedMaximum(mainProtectedMaximum() + quota);
    setWindowMaximum(windowMaximum() - quota);

    for (int i = 0; i < QUEUE_TRANSFER_THRESHOLD; i++) {
      Node<K, V> candidate = accessOrderWindowDeque().peekFirst();
      if (candidate == null) {
        break;
      }

      int weight = candidate.getPolicyWeight();
      if (quota < weight) {
        break;
      }

      quota -= weight;
      setWindowWeightedSize(windowWeightedSize() - weight);
      accessOrderWindowDeque().remove(candidate);
      accessOrderProbationDeque().offerLast(candidate);
      candidate.makeMainProbation();
    }

    setMainProtectedMaximum(mainProtectedMaximum() - quota);
    setWindowMaximum(windowMaximum() + quota);
    setAdjustment(-quota);
  }

  /** Transfers the nodes from the protected to the probation region if it exceeds the maximum. */
  @GuardedBy("evictionLock")
  void demoteFromMainProtected() {
    long mainProtectedMaximum = mainProtectedMaximum();
    @Var long mainProtectedWeightedSize = mainProtectedWeightedSize();
    if (mainProtectedWeightedSize <= mainProtectedMaximum) {
      return;
    }

    for (int i = 0; i < QUEUE_TRANSFER_THRESHOLD; i++) {
      if (mainProtectedWeightedSize <= mainProtectedMaximum) {
        break;
      }

      Node<K, V> demoted = accessOrderProtectedDeque().pollFirst();
      if (demoted == null) {
        break;
      }
      demoted.makeMainProbation();
      accessOrderProbationDeque().offerLast(demoted);
      mainProtectedWeightedSize -= demoted.getPolicyWeight();
    }
    setMainProtectedWeightedSize(mainProtectedWeightedSize);
  }

  /**
   * Performs the post-processing work required after a read.
   *
   * @param node the entry in the page replacement policy
   * @param now the current time, in nanoseconds
   * @param recordHit if the hit count should be incremented
   * @return the refreshed value if immediately loaded, else null
   */
  @Nullable V afterRead(Node<K, V> node, long now, boolean recordHit) {
    if (recordHit) {
      statsCounter().recordHits(1);
    }

    boolean delayable = skipReadBuffer() || (readBuffer.offer(node) != Buffer.FULL);
    if (shouldDrainBuffers(delayable)) {
      scheduleDrainBuffers();
    }
    return refreshIfNeeded(node, now);
  }

  /** Returns if the cache should bypass the read buffer. */
  boolean skipReadBuffer() {
    return fastpath() && frequencySketch().isNotInitialized();
  }

  /**
   * Asynchronously refreshes the entry if eligible.
   *
   * @param node the entry in the cache to refresh
   * @param now the current time, in nanoseconds
   * @return the refreshed value if immediately loaded, else null
   */
  @SuppressWarnings("FutureReturnValueIgnored")
  @Nullable V refreshIfNeeded(Node<K, V> node, long now) {
    if (!refreshAfterWrite()) {
      return null;
    }

    K key;
    V oldValue;
    long writeTime = node.getWriteTime();
    long refreshWriteTime = writeTime | 1L;
    Object keyReference = node.getKeyReference();
    ConcurrentMap<Object, CompletableFuture<?>> refreshes;
    if (((now - writeTime) > refreshAfterWriteNanos())
        && ((key = node.getKey()) != null) && ((oldValue = node.getValue()) != null)
        && !isComputingAsync(oldValue) && ((writeTime & 1L) == 0L)
        && !(refreshes = refreshes()).containsKey(keyReference)
        && node.isAlive() && node.casWriteTime(writeTime, refreshWriteTime)) {
      long[] startTime = new long[1];
      @SuppressWarnings({"rawtypes", "unchecked"})
      @Nullable CompletableFuture<? extends @Nullable V>[] refreshFuture = new CompletableFuture[1];
      try {
        refreshes.computeIfAbsent(keyReference, k -> {
          try {
            startTime[0] = statsTicker().read();
            if (isAsync) {
              @SuppressWarnings("unchecked")
              var future = (CompletableFuture<V>) oldValue;
              if (Async.isReady(future)) {
                requireNonNull(cacheLoader);
                var refresh = cacheLoader.asyncReload(key, future.join(), executor);
                refreshFuture[0] = requireNonNull(refresh, "Null future");
              } else {
                // no-op if the future's completion state was modified (e.g. obtrude methods)
                return null;
              }
            } else {
              requireNonNull(cacheLoader);
              var refresh = cacheLoader.asyncReload(key, oldValue, executor);
              refreshFuture[0] = requireNonNull(refresh, "Null future");
            }
            return refreshFuture[0];
          } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
            logger.log(Level.WARNING, "Exception thrown when submitting refresh task", e);
            return null;
          } catch (Throwable e) {
            logger.log(Level.WARNING, "Exception thrown when submitting refresh task", e);
            return null;
          }
        });
      } finally {
        node.casWriteTime(refreshWriteTime, writeTime);
      }

      if (refreshFuture[0] == null) {
        return null;
      }

      var refreshed = refreshFuture[0].handle((newValue, error) -> {
        long loadTime = statsTicker().read() - startTime[0];
        if (error != null) {
          if (!(error instanceof CancellationException) && !(error instanceof TimeoutException)) {
            logger.log(Level.WARNING, "Exception thrown during refresh", error);
          }
          refreshes.remove(keyReference, refreshFuture[0]);
          statsCounter().recordLoadFailure(loadTime);
          return null;
        }

        @SuppressWarnings("unchecked")
        V value = (isAsync && (newValue != null)) ? (V) refreshFuture[0] : newValue;

        @Nullable RemovalCause[] cause = new RemovalCause[1];
        V result = compute(key, (K k, @Nullable V currentValue) -> {
          boolean removed = refreshes.remove(keyReference, refreshFuture[0]);
          if (currentValue == null) {
            // If the entry is absent then discard the refresh and maybe notifying the listener
            if (value != null) {
              cause[0] = RemovalCause.EXPLICIT;
            }
            return null;
          } else if (currentValue == value) {
            // If the reloaded value is the same instance then no-op
            return currentValue;
          } else if (isAsync &&
              (newValue == Async.getIfReady((CompletableFuture<?>) currentValue))) {
            // If the completed futures hold the same value instance then no-op
            return currentValue;
          } else if (removed && (currentValue == oldValue) && (node.getWriteTime() == writeTime)) {
            // If the entry was not modified while in-flight (no ABA) then replace
            return value;
          }
          // Otherwise, a write invalidated the refresh so discard it and notify the listener
          cause[0] = RemovalCause.REPLACED;
          return currentValue;
        }, expiry(), /* recordLoad= */ false, /* recordLoadFailure= */ true);

        if (cause[0] != null) {
          notifyRemoval(key, value, cause[0]);
        }
        if (newValue == null) {
          statsCounter().recordLoadFailure(loadTime);
        } else {
          statsCounter().recordLoadSuccess(loadTime);
        }
        return result;
      });
      return Async.getIfReady(refreshed);
    }

    return null;
  }

  /**
   * Returns the expiration time for the entry after being created.
   *
   * @param key the key of the entry that was created
   * @param value the value of the entry that was created
   * @param expiry the calculator for the expiration time
   * @param now the current time, in nanoseconds
   * @return the expiration time
   */
  long expireAfterCreate(K key, V value, @Nullable Expiry<? super K, ? super V> expiry, long now) {
    if (expiresVariable()) {
      requireNonNull(expiry);
      long duration = Math.max(0L, expiry.expireAfterCreate(key, value, now));
      return isAsync ? (now + duration) : (now + Math.min(duration, MAXIMUM_EXPIRY));
    }
    return 0L;
  }

  /**
   * Returns the expiration time for the entry after being updated.
   *
   * @param node the entry in the page replacement policy
   * @param key the key of the entry that was updated
   * @param value the value of the entry that was updated
   * @param expiry the calculator for the expiration time
   * @param now the current time, in nanoseconds
   * @return the expiration time
   */
  long expireAfterUpdate(Node<K, V> node, K key, V value,
      @Nullable Expiry<? super K, ? super V> expiry, long now) {
    if (expiresVariable()) {
      requireNonNull(expiry);
      long currentDuration = Math.max(1, node.getVariableTime() - now);
      long duration = Math.max(0L, expiry.expireAfterUpdate(key, value, now, currentDuration));
      return isAsync ? (now + duration) : (now + Math.min(duration, MAXIMUM_EXPIRY));
    }
    return 0L;
  }

  /**
   * Returns the access time for the entry after a read.
   *
   * @param node the entry in the page replacement policy
   * @param key the key of the entry that was read
   * @param value the value of the entry that was read
   * @param expiry the calculator for the expiration time
   * @param now the current time, in nanoseconds
   * @return the expiration time
   */
  long expireAfterRead(Node<K, V> node, K key, V value, Expiry<K, V> expiry, long now) {
    if (expiresVariable()) {
      long currentDuration = Math.max(0L, node.getVariableTime() - now);
      long duration = Math.max(0L, expiry.expireAfterRead(key, value, now, currentDuration));
      return isAsync ? (now + duration) : (now + Math.min(duration, MAXIMUM_EXPIRY));
    }
    return 0L;
  }

  /**
   * Attempts to update the access time for the entry after a read.
   *
   * @param node the entry in the page replacement policy
   * @param key the key of the entry that was read
   * @param value the value of the entry that was read
   * @param expiry the calculator for the expiration time
   * @param now the current time, in nanoseconds
   */
  void tryExpireAfterRead(Node<K, V> node, K key, V value, Expiry<K, V> expiry, long now) {
    if (!expiresVariable()) {
      return;
    }

    long variableTime = node.getVariableTime();
    long currentDuration = Math.max(1, variableTime - now);
    if (isAsync && (currentDuration > MAXIMUM_EXPIRY)) {
      // expireAfterCreate has not yet set the duration after completion
      return;
    }

    long duration = Math.max(0L, expiry.expireAfterRead(key, value, now, currentDuration));
    if (duration != currentDuration) {
      long expirationTime = isAsync ? (now + duration) : (now + Math.min(duration, MAXIMUM_EXPIRY));
      node.casVariableTime(variableTime, expirationTime);
    }
  }

  void setVariableTime(Node<K, V> node, long expirationTime) {
    if (expiresVariable()) {
      node.setVariableTime(expirationTime);
    }
  }

  void setWriteTime(Node<K, V> node, long now) {
    if (expiresAfterWrite() || refreshAfterWrite()) {
      node.setWriteTime(now & ~1L);
    }
  }

  void setAccessTime(Node<K, V> node, long now) {
    if (expiresAfterAccess()) {
      node.setAccessTime(now);
    }
  }

  /** Returns if the entry's write time would exceed the minimum expiration reorder threshold. */
  boolean exceedsWriteTimeTolerance(Node<K, V> node, long varTime, long now) {
    long variableTime = node.getVariableTime();
    long tolerance = EXPIRE_WRITE_TOLERANCE;
    long writeTime = node.getWriteTime();
    return
        (expiresAfterWrite()
            && ((expiresAfterWriteNanos() <= tolerance) || (Math.abs(now - writeTime) > tolerance)))
        || (refreshAfterWrite()
            && ((refreshAfterWriteNanos() <= tolerance) || (Math.abs(now - writeTime) > tolerance)))
        || (expiresVariable() && (Math.abs(varTime - variableTime) > tolerance));
  }

  /**
   * Performs the post-processing work required after a write.
   *
   * @param task the pending operation to be applied
   */
  void afterWrite(Runnable task) {
    for (int i = 0; i < WRITE_BUFFER_RETRIES; i++) {
      if (writeBuffer.offer(task)) {
        scheduleAfterWrite();
        return;
      }
      scheduleDrainBuffers();
      Thread.onSpinWait();
    }

    // In scenarios where the writing threads cannot make progress then they attempt to provide
    // assistance by performing the eviction work directly. This can resolve cases where the
    // maintenance task is scheduled but not running. That might occur due to all of the executor's
    // threads being busy (perhaps writing into this cache), the write rate greatly exceeds the
    // consuming rate, priority inversion, or if the executor silently discarded the maintenance
    // task. Unfortunately this cannot resolve when the eviction is blocked waiting on a long-
    // running computation due to an eviction listener, the victim is being computed on by a writer,
    // or the victim residing in the same hash bin as a computing entry. In those cases a warning is
    // logged to encourage the application to decouple these computations from the map operations.
    lock();
    try {
      maintenance(task);
    } catch (RuntimeException e) {
      logger.log(Level.ERROR, "Exception thrown when performing the maintenance task", e);
    } finally {
      evictionLock.unlock();
    }
    rescheduleCleanUpIfIncomplete();
  }

  /** Acquires the eviction lock. */
  void lock() {
    @Var long remainingNanos = WARN_AFTER_LOCK_WAIT_NANOS;
    long end = System.nanoTime() + remainingNanos;
    @Var boolean interrupted = false;
    try {
      for (;;) {
        try {
          if (evictionLock.tryLock(remainingNanos, TimeUnit.NANOSECONDS)) {
            return;
          }
          logger.log(Level.WARNING, "The cache is experiencing excessive wait times for acquiring "
              + "the eviction lock. This may indicate that a long-running computation has halted "
              + "eviction when trying to remove the victim entry. Consider using AsyncCache to "
              + "decouple the computation from the map operation.", new TimeoutException());
          evictionLock.lock();
          return;
        } catch (InterruptedException e) {
          remainingNanos = end - System.nanoTime();
          interrupted = true;
        }
      }
    } finally {
      if (interrupted) {
        Thread.currentThread().interrupt();
      }
    }
  }

  /**
   * Conditionally schedules the asynchronous maintenance task after a write operation. If the
   * task status was IDLE or REQUIRED then the maintenance task is scheduled immediately. If it
   * is already processing then it is set to transition to REQUIRED upon completion so that a new
   * execution is triggered by the next operation.
   */
  void scheduleAfterWrite() {
    @Var int drainStatus = drainStatusOpaque();
    for (;;) {
      switch (drainStatus) {
        case IDLE:
          casDrainStatus(IDLE, REQUIRED);
          scheduleDrainBuffers();
          return;
        case REQUIRED:
          scheduleDrainBuffers();
          return;
        case PROCESSING_TO_IDLE:
          if (casDrainStatus(PROCESSING_TO_IDLE, PROCESSING_TO_REQUIRED)) {
            return;
          }
          drainStatus = drainStatusAcquire();
          continue;
        case PROCESSING_TO_REQUIRED:
          return;
        default:
          throw new IllegalStateException("Invalid drain status: " + drainStatus);
      }
    }
  }

  /**
   * Attempts to schedule an asynchronous task to apply the pending operations to the page
   * replacement policy. If the executor rejects the task then it is run directly.
   */
  void scheduleDrainBuffers() {
    if (drainStatusOpaque() >= PROCESSING_TO_IDLE) {
      return;
    }
    if (evictionLock.tryLock()) {
      try {
        int drainStatus = drainStatusOpaque();
        if (drainStatus >= PROCESSING_TO_IDLE) {
          return;
        }
        setDrainStatusRelease(PROCESSING_TO_IDLE);
        executor.execute(drainBuffersTask);
      } catch (Throwable t) {
        logger.log(Level.WARNING, "Exception thrown when submitting maintenance task", t);
        maintenance(/* ignored */ null);
      } finally {
        evictionLock.unlock();
      }
    }
  }

  @Override
  public void cleanUp() {
    try {
      performCleanUp(/* ignored */ null);
    } catch (RuntimeException e) {
      logger.log(Level.ERROR, "Exception thrown when performing the maintenance task", e);
    }
  }

  /**
   * Performs the maintenance work, blocking until the lock is acquired.
   *
   * @param task an additional pending task to run, or {@code null} if not present
   */
  void performCleanUp(@Nullable Runnable task) {
    evictionLock.lock();
    try {
      maintenance(task);
    } finally {
      evictionLock.unlock();
    }
    rescheduleCleanUpIfIncomplete();
  }

  /**
   * If there remains pending operations that were not handled by the prior clean up then try to
   * schedule an asynchronous maintenance task. This may occur due to a concurrent write after the
   * maintenance work had started or if the amortized threshold of work per clean up was reached.
   */
  @SuppressWarnings("resource")
  void rescheduleCleanUpIfIncomplete() {
    if (drainStatusOpaque() != REQUIRED) {
      return;
    }

    // An immediate scheduling cannot be performed on a custom executor because it may use a
    // caller-runs policy. This could cause the caller's penalty to exceed the amortized threshold,
    // e.g. repeated concurrent writes could result in a retry loop.
    if (executor == ForkJoinPool.commonPool()) {
      scheduleDrainBuffers();
      return;
    }

    // If a scheduler was configured then the maintenance can be deferred onto the custom executor
    // and run in the near future. Otherwise, it will be handled due to other cache activity.
    var pacer = pacer();
    if ((pacer != null) && !pacer.isScheduled() && evictionLock.tryLock()) {
      try {
        if ((drainStatusOpaque() == REQUIRED) && !pacer.isScheduled()) {
          pacer.schedule(executor, drainBuffersTask, expirationTicker().read(), Pacer.TOLERANCE);
        }
      } finally {
        evictionLock.unlock();
      }
    }
  }

  /**
   * Performs the pending maintenance work and sets the state flags during processing to avoid
   * excess scheduling attempts. The read buffer, write buffer, and reference queues are drained,
   * followed by expiration, and size-based eviction.
   *
   * @param task an additional pending task to run, or {@code null} if not present
   */
  @GuardedBy("evictionLock")
  void maintenance(@Nullable Runnable task) {
    setDrainStatusRelease(PROCESSING_TO_IDLE);

    try {
      drainReadBuffer();

      drainWriteBuffer();
      if (task != null) {
        task.run();
      }

      drainKeyReferences();
      drainValueReferences();

      expireEntries();
      evictEntries();

      climb();
    } finally {
      if ((drainStatusOpaque() != PROCESSING_TO_IDLE)
          || !casDrainStatus(PROCESSING_TO_IDLE, IDLE)) {
        setDrainStatusOpaque(REQUIRED);
      }
    }
  }

  /** Drains the weak key references queue. */
  @GuardedBy("evictionLock")
  void drainKeyReferences() {
    if (!collectKeys()) {
      return;
    }
    @Var Reference<? extends K> keyRef;
    while ((keyRef = keyReferenceQueue().poll()) != null) {
      Node<K, V> node = data.get(keyRef);
      if (node != null) {
        evictEntry(node, RemovalCause.COLLECTED, 0L);
      }
    }
  }

  /** Drains the weak / soft value references queue. */
  @GuardedBy("evictionLock")
  void drainValueReferences() {
    if (!collectValues()) {
      return;
    }
    @Var Reference<? extends V> valueRef;
    while ((valueRef = valueReferenceQueue().poll()) != null) {
      @SuppressWarnings("unchecked")
      var ref = (InternalReference<V>) valueRef;
      Node<K, V> node = data.get(ref.getKeyReference());
      if ((node != null) && (valueRef == node.getValueReference())) {
        evictEntry(node, RemovalCause.COLLECTED, 0L);
      }
    }
  }

  /** Drains the read buffer. */
  @GuardedBy("evictionLock")
  void drainReadBuffer() {
    if (!skipReadBuffer()) {
      readBuffer.drainTo(accessPolicy);
    }
  }

  /** Updates the node's location in the page replacement policy. */
  @GuardedBy("evictionLock")
  void onAccess(Node<K, V> node) {
    if (evicts()) {
      var keyRef = node.getKeyReferenceOrNull();
      if ((keyRef == null) || !node.isAlive()) {
        return;
      }
      frequencySketch().increment(keyRef);
      if (node.inWindow()) {
        reorder(accessOrderWindowDeque(), node);
      } else if (node.inMainProbation()) {
        reorderProbation(node);
      } else {
        reorder(accessOrderProtectedDeque(), node);
      }
      setHitsInSample(hitsInSample() + 1);
    } else if (expiresAfterAccess()) {
      reorder(accessOrderWindowDeque(), node);
    }
    if (expiresVariable()) {
      timerWheel().reschedule(node);
    }
  }

  /** Promote the node from probation to protected on an access. */
  @GuardedBy("evictionLock")
  void reorderProbation(Node<K, V> node) {
    if (!accessOrderProbationDeque().contains(node)) {
      // Ignore stale accesses for an entry that is no longer present
      return;
    } else if (node.getPolicyWeight() > mainProtectedMaximum()) {
      reorder(accessOrderProbationDeque(), node);
      return;
    }

    // If the protected space exceeds its maximum, the LRU items are demoted to the probation space.
    // This is deferred to the adaption phase at the end of the maintenance cycle.
    setMainProtectedWeightedSize(mainProtectedWeightedSize() + node.getPolicyWeight());
    accessOrderProbationDeque().remove(node);
    accessOrderProtectedDeque().offerLast(node);
    node.makeMainProtected();
  }

  /** Updates the node's location in the policy's deque. */
  static <K, V> void reorder(LinkedDeque<Node<K, V>> deque, Node<K, V> node) {
    // An entry may be scheduled for reordering despite having been removed. This can occur when the
    // entry was concurrently read while a writer was removing it. If the entry is no longer linked
    // then it does not need to be processed.
    if (deque.contains(node)) {
      deque.moveToBack(node);
    }
  }

  /** Drains the write buffer. */
  @GuardedBy("evictionLock")
  void drainWriteBuffer() {
    for (int i = 0; i <= WRITE_BUFFER_MAX; i++) {
      Runnable task = writeBuffer.poll();
      if (task == null) {
        return;
      }
      task.run();
    }
    setDrainStatusOpaque(PROCESSING_TO_REQUIRED);
  }

  /**
   * Atomically transitions the node to the <code>dead</code> state and decrements the
   * <code>weightedSize</code>.
   *
   * @param node the entry in the page replacement policy
   */
  @GuardedBy("evictionLock")
  @SuppressWarnings("SynchronizationOnLocalVariableOrMethodParameter")
  void makeDead(Node<K, V> node) {
    synchronized (node) {
      if (node.isDead()) {
        return;
      }
      if (evicts()) {
        // The node's policy weight may be out of sync due to a pending update waiting to be
        // processed. At this point the node's weight is finalized, so the weight can be safely
        // taken from the node's perspective and the sizes will be adjusted correctly.
        if (node.inWindow()) {
          setWindowWeightedSize(windowWeightedSize() - node.getWeight());
        } else if (node.inMainProtected()) {
          setMainProtectedWeightedSize(mainProtectedWeightedSize() - node.getWeight());
        }
        setWeightedSize(weightedSize() - node.getWeight());
      }
      node.die();
    }
  }

  /** Adds the node to the page replacement policy. */
  final class AddTask implements Runnable {
    final Node<K, V> node;
    final int weight;

    AddTask(Node<K, V> node, int weight) {
      this.weight = weight;
      this.node = node;
    }

    @Override
    @GuardedBy("evictionLock")
    public void run() {
      if (evicts()) {
        setWeightedSize(weightedSize() + weight);
        setWindowWeightedSize(windowWeightedSize() + weight);
        node.setPolicyWeight(node.getPolicyWeight() + weight);

        long maximum = maximum();
        if (weightedSize() >= (maximum >>> 1)) {
          if (weightedSize() > MAXIMUM_CAPACITY) {
            evictEntries();
          } else {
            // Lazily initialize when close to the maximum
            long capacity = isWeighted() ? data.mappingCount() : maximum;
            frequencySketch().ensureCapacity(capacity);
          }
        }

        var keyRef = node.getKeyReferenceOrNull();
        if (keyRef != null) {
          frequencySketch().increment(keyRef);
        }

        setMissesInSample(missesInSample() + 1);
      }

      // ignore out-of-order write operations
      boolean isAlive;
      synchronized (node) {
        isAlive = node.isAlive();
      }
      if (isAlive) {
        if (expiresAfterWrite()) {
          writeOrderDeque().offerLast(node);
        }
        if (expiresVariable()) {
          timerWheel().schedule(node);
        }
        if (evicts()) {
          if (weight > maximum()) {
            evictEntry(node, RemovalCause.SIZE, expirationTicker().read());
          } else if (weight > windowMaximum()) {
            accessOrderWindowDeque().offerFirst(node);
          } else {
            accessOrderWindowDeque().offerLast(node);
          }
        } else if (expiresAfterAccess()) {
          accessOrderWindowDeque().offerLast(node);
        }
      }
    }
  }

  /** Removes a node from the page replacement policy. */
  final class RemovalTask implements Runnable {
    final Node<K, V> node;

    RemovalTask(Node<K, V> node) {
      this.node = node;
    }

    @Override
    @GuardedBy("evictionLock")
    public void run() {
      // add may not have been processed yet
      if (node.inWindow() && (evicts() || expiresAfterAccess())) {
        accessOrderWindowDeque().remove(node);
      } else if (evicts()) {
        if (node.inMainProbation()) {
          accessOrderProbationDeque().remove(node);
        } else {
          accessOrderProtectedDeque().remove(node);
        }
      }
      if (expiresAfterWrite()) {
        writeOrderDeque().remove(node);
      } else if (expiresVariable()) {
        timerWheel().deschedule(node);
      }
      makeDead(node);
    }
  }

  /** Updates the weighted size. */
  final class UpdateTask implements Runnable {
    final int weightDifference;
    final Node<K, V> node;

    public UpdateTask(Node<K, V> node, int weightDifference) {
      this.weightDifference = weightDifference;
      this.node = node;
    }

    @Override
    @GuardedBy("evictionLock")
    public void run() {
      if (expiresAfterWrite()) {
        reorder(writeOrderDeque(), node);
      } else if (expiresVariable()) {
        timerWheel().reschedule(node);
      }
      if (evicts()) {
        int oldWeightedSize = node.getPolicyWeight();
        node.setPolicyWeight(oldWeightedSize + weightDifference);
        if (node.inWindow()) {
          setWindowWeightedSize(windowWeightedSize() + weightDifference);
          if (node.getPolicyWeight() > maximum()) {
            evictEntry(node, RemovalCause.SIZE, expirationTicker().read());
          } else if (node.getPolicyWeight() <= windowMaximum()) {
            onAccess(node);
          } else if (accessOrderWindowDeque().contains(node)) {
            accessOrderWindowDeque().moveToFront(node);
          }
        } else if (node.inMainProbation()) {
            if (node.getPolicyWeight() <= maximum()) {
              onAccess(node);
            } else {
              evictEntry(node, RemovalCause.SIZE, expirationTicker().read());
            }
        } else {
          setMainProtectedWeightedSize(mainProtectedWeightedSize() + weightDifference);
          if (node.getPolicyWeight() <= maximum()) {
            onAccess(node);
          } else {
            evictEntry(node, RemovalCause.SIZE, expirationTicker().read());
          }
        }

        setWeightedSize(weightedSize() + weightDifference);
        if (weightedSize() > MAXIMUM_CAPACITY) {
          evictEntries();
        }
      } else if (expiresAfterAccess()) {
        onAccess(node);
      }
    }
  }

  /* --------------- Concurrent Map Support --------------- */

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

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

  @Override
  public long estimatedSize() {
    return data.mappingCount();
  }

  @Override
  public void clear() {
    Deque<Node<K, V>> entries;
    evictionLock.lock();
    try {
      // Discard all pending reads
      readBuffer.drainTo(e -> {});

      // Apply all pending writes
      @Var Runnable task;
      while ((task = writeBuffer.poll()) != null) {
        task.run();
      }

      // Cancel the scheduled cleanup
      Pacer pacer = pacer();
      if (pacer != null) {
        pacer.cancel();
      }

      // Discard all entries, falling back to one-by-one to avoid excessive lock hold times
      long now = expirationTicker().read();
      int threshold = (WRITE_BUFFER_MAX / 2);
      entries = new ArrayDeque<>(data.values());
      while (!entries.isEmpty() && (writeBuffer.size() < threshold)) {
        removeNode(entries.pollFirst(), now);
      }
    } finally {
      evictionLock.unlock();
    }

    // Remove any stragglers if released early to more aggressively flush incoming writes
    @Var boolean cleanUp = false;
    for (var node : entries) {
      @Nullable K key = node.getKey();
      if (key == null) {
        cleanUp = true;
      } else {
        remove(key);
      }
    }
    if (collectKeys() && cleanUp) {
      cleanUp();
    }
  }

  @GuardedBy("evictionLock")
  @SuppressWarnings({"GuardedByChecker", "SynchronizationOnLocalVariableOrMethodParameter"})
  void removeNode(Node<K, V> node, long now) {
    K key = node.getKey();
    var cause = new RemovalCause[1];
    var keyReference = node.getKeyReference();
    @SuppressWarnings({"unchecked", "Varifier"})
    @Nullable V[] value = (V[]) new Object[1];

    data.computeIfPresent(keyReference, (k, n) -> {
      if (n != node) {
        return n;
      }
      synchronized (node) {
        value[0] = node.getValue();

        if ((key == null) || (value[0] == null)) {
          cause[0] = RemovalCause.COLLECTED;
        } else if (hasExpired(node, now)) {
          cause[0] = RemovalCause.EXPIRED;
        } else {
          cause[0] = RemovalCause.EXPLICIT;
        }

        if (cause[0].wasEvicted()) {
          notifyEviction(key, value[0], cause[0]);
        }

        discardRefresh(node.getKeyReference());
        node.retire();
        return null;
      }
    });

    if (node.inWindow() && (evicts() || expiresAfterAccess())) {
      accessOrderWindowDeque().remove(node);
    } else if (evicts()) {
      if (node.inMainProbation()) {
        accessOrderProbationDeque().remove(node);
      } else {
        accessOrderProtectedDeque().remove(node);
      }
    }
    if (expiresAfterWrite()) {
      writeOrderDeque().remove(node);
    } else if (expiresVariable()) {
      timerWheel().deschedule(node);
    }

    synchronized (node) {
      logIfAlive(node);
      makeDead(node);
    }

    if (cause[0] != null) {
      notifyRemoval(key, value[0], cause[0]);
    }
  }

  @Override
  public boolean containsKey(Object key) {
    Node<K, V> node = data.get(nodeFactory.newLookupKey(key));
    return (node != null) && (node.getValue() != null)
        && !hasExpired(node, expirationTicker().read());
  }

  @Override
  public boolean containsValue(Object value) {
    requireNonNull(value);

    long now = expirationTicker().read();
    for (Node<K, V> node : data.values()) {
      if (node.containsValue(value) && !hasExpired(node, now) && (node.getKey() != null)) {
        return true;
      }
    }
    return false;
  }

  @Override
  public @Nullable V get(Object key) {
    return getIfPresent(key, /* recordStats= */ false);
  }

  @Override
  public @Nullable V getIfPresent(Object key, boolean recordStats) {
    Node<K, V> node = data.get(nodeFactory.newLookupKey(key));
    if (node == null) {
      if (recordStats) {
        statsCounter().recordMisses(1);
      }
      if (drainStatusOpaque() == REQUIRED) {
        scheduleDrainBuffers();
      }
      return null;
    }

    V value = node.getValue();
    long now = expirationTicker().read();
    if (hasExpired(node, now) || (collectValues() && (value == null))) {
      if (recordStats) {
        statsCounter().recordMisses(1);
      }
      scheduleDrainBuffers();
      return null;
    }

    if ((value != null) && !isComputingAsync(value)) {
      @SuppressWarnings("unchecked")
      var castedKey = (K) key;
      setAccessTime(node, now);
      tryExpireAfterRead(node, castedKey, value, expiry(), now);
    }
    V refreshed = afterRead(node, now, recordStats);
    return (refreshed == null) ? value : refreshed;
  }

  @Override
  public @Nullable V getIfPresentQuietly(Object key) {
    V value;
    Node<K, V> node = data.get(nodeFactory.newLookupKey(key));
    if ((node == null) || ((value = node.getValue()) == null)
        || hasExpired(node, expirationTicker().read())) {
      return null;
    }
    return value;
  }

  /**
   * Returns the key associated with the mapping in this cache, or {@code null} if there is none.
   *
   * @param key the key whose canonical instance is to be returned
   * @return the key used by the mapping, or {@code null} if this cache does not contain a mapping
   *         for the key
   * @throws NullPointerException if the specified key is null
   */
  public @Nullable K getKey(K key) {
    Node<K, V> node = data.get(nodeFactory.newLookupKey(key));
    if (node == null) {
      if (drainStatusOpaque() == REQUIRED) {
        scheduleDrainBuffers();
      }
      return null;
    }
    afterRead(node, /* now= */ 0L, /* recordHit= */ false);
    return node.getKey();
  }

  @Override
  public Map<K, V> getAllPresent(Iterable<? extends K> keys) {
    var result = new LinkedHashMap<K, @Nullable V>(calculateHashMapCapacity(keys));
    for (K key : keys) {
      result.put(key, null);
    }

    int uniqueKeys = result.size();
    long now = expirationTicker().read();
    for (var iter = result.entrySet().iterator(); iter.hasNext();) {
      V value;
      var entry = iter.next();
      Node<K, V> node = data.get(nodeFactory.newLookupKey(entry.getKey()));
      if ((node == null) || ((value = node.getValue()) == null) || hasExpired(node, now)) {
        iter.remove();
      } else {
        setAccessTime(node, now);
        tryExpireAfterRead(node, entry.getKey(), value, expiry(), now);
        V refreshed = afterRead(node, now, /* recordHit= */ false);
        entry.setValue((refreshed == null) ? value : refreshed);
      }
    }
    statsCounter().recordHits(result.size());
    statsCounter().recordMisses(uniqueKeys - result.size());

    @SuppressWarnings("NullableProblems")
    Map<K, V> unmodifiable = Collections.unmodifiableMap(result);
    return unmodifiable;
  }

  @Override
  public void putAll(Map<? extends K, ? extends V> map) {
    map.forEach(this::put);
  }

  @Override
  public @Nullable V put(K key, V value) {
    return put(key, value, expiry(), /* onlyIfAbsent= */ false);
  }

  @Override
  public @Nullable V putIfAbsent(K key, V value) {
    return put(key, value, expiry(), /* onlyIfAbsent= */ true);
  }

  /**
   * Adds a node to the policy and the data store. If an existing node is found, then its value is
   * updated if allowed.
   *
   * @param key key with which the specified value is to be associated
   * @param value value to be associated with the specified key
   * @param expiry the calculator for the write expiration time
   * @param onlyIfAbsent a write is performed only if the key is not already associated with a value
   * @return the prior value in or null if no mapping was found
   */
  @Nullable V put(K key, V value, Expiry<K, V> expiry, boolean onlyIfAbsent) {
    requireNonNull(key);
    requireNonNull(value);

    @Var Node<K, V> node = null;
    long now = expirationTicker().read();
    int newWeight = weigher.weigh(key, value);
    Object lookupKey = nodeFactory.newLookupKey(key);
    for (int attempts = 1; ; attempts++) {
      @Var Node<K, V> prior = data.get(lookupKey);
      if (prior == null) {
        if (node == null) {
          node = nodeFactory.newNode(key, keyReferenceQueue(),
              value, valueReferenceQueue(), newWeight, now);
          long expirationTime = isComputingAsync(value) ? (now + ASYNC_EXPIRY) : now;
          setVariableTime(node, expireAfterCreate(key, value, expiry, now));
          setAccessTime(node, expirationTime);
          setWriteTime(node, expirationTime);
        }
        prior = data.putIfAbsent(node.getKeyReference(), node);
        if (prior == null) {
          afterWrite(new AddTask(node, newWeight));
          return null;
        } else if (onlyIfAbsent) {
          // An optimistic fast path to avoid unnecessary locking
          V currentValue = prior.getValue();
          if ((currentValue != null) && !hasExpired(prior, now)) {
            if (!isComputingAsync(currentValue)) {
              tryExpireAfterRead(prior, key, currentValue, expiry(), now);
              setAccessTime(prior, now);
            }
            afterRead(prior, now, /* recordHit= */ false);
            return currentValue;
          }
        }
      } else if (onlyIfAbsent) {
        // An optimistic fast path to avoid unnecessary locking
        V currentValue = prior.getValue();
        if ((currentValue != null) && !hasExpired(prior, now)) {
          if (!isComputingAsync(currentValue)) {
            tryExpireAfterRead(prior, key, currentValue, expiry(), now);
            setAccessTime(prior, now);
          }
          afterRead(prior, now, /* recordHit= */ false);
          return currentValue;
        }
      }

      // A read may race with the entry's removal, so that after the entry is acquired it may no
      // longer be usable. A retry will reread from the map and either find an absent mapping, a
      // new entry, or a stale entry.
      if (!prior.isAlive()) {
        // A reread of the stale entry may occur if the state transition occurred but the map
        // removal was delayed by a context switch, so that this thread spin waits until resolved.
        if ((attempts & MAX_PUT_SPIN_WAIT_ATTEMPTS) != 0) {
          Thread.onSpinWait();
          continue;
        }

        // If the spin wait attempts are exhausted then fallback to a map computation in order to
        // deschedule this thread until the entry's removal completes. If the key was modified
        // while in the map so that its equals or hashCode changed then the contents may be
        // corrupted, where the cache holds an evicted (dead) entry that could not be removed.
        // That is a violation of the Map contract, so we check that the mapping is in the "alive"
        // state while in the computation.
        data.computeIfPresent(lookupKey, (k, n) -> {
          requireIsAlive(key, n);
          return n;
        });
        continue;
      }

      V oldValue;
      long varTime;
      int oldWeight;
      @Var boolean expired = false;
      @Var boolean mayUpdate = true;
      @Var boolean exceedsTolerance = false;
      synchronized (prior) {
        if (!prior.isAlive()) {
          continue;
        }
        oldValue = prior.getValue();
        oldWeight = prior.getWeight();
        if (oldValue == null) {
          varTime = expireAfterCreate(key, value, expiry, now);
          notifyEviction(key, null, RemovalCause.COLLECTED);
        } else if (hasExpired(prior, now)) {
          expired = true;
          varTime = expireAfterCreate(key, value, expiry, now);
          notifyEviction(key, oldValue, RemovalCause.EXPIRED);
        } else if (onlyIfAbsent) {
          mayUpdate = false;
          varTime = expireAfterRead(prior, key, oldValue, expiry, now);
        } else {
          varTime = expireAfterUpdate(prior, key, value, expiry, now);
        }

        long expirationTime = isComputingAsync(value) ? (now + ASYNC_EXPIRY) : now;
        if (mayUpdate) {
          exceedsTolerance = exceedsWriteTimeTolerance(prior, varTime, now);
          if (expired || exceedsTolerance) {
            setWriteTime(prior, isComputingAsync(value) ? (now + ASYNC_EXPIRY) : now);
          }

          prior.setValue(value, valueReferenceQueue());
          prior.setWeight(newWeight);

          discardRefresh(prior.getKeyReference());
        }

        setVariableTime(prior, varTime);
        setAccessTime(prior, expirationTime);
      }

      if (expired) {
        notifyRemoval(key, oldValue, RemovalCause.EXPIRED);
      } else if (oldValue == null) {
        notifyRemoval(key, /* value= */ null, RemovalCause.COLLECTED);
      } else if (mayUpdate) {
        notifyOnReplace(key, oldValue, value);
      }

      int weightedDifference = mayUpdate ? (newWeight - oldWeight) : 0;
      if ((oldValue == null) || (weightedDifference != 0) || expired) {
        afterWrite(new UpdateTask(prior, weightedDifference));
      } else if (!onlyIfAbsent && exceedsTolerance) {
        afterWrite(new UpdateTask(prior, weightedDifference));
      } else {
        afterRead(prior, now, /* recordHit= */ false);
      }

      return expired ? null : oldValue;
    }
  }

  @Override
  @SuppressWarnings("SynchronizationOnLocalVariableOrMethodParameter")
  public @Nullable V remove(Object key) {
    @SuppressWarnings({"rawtypes", "unchecked"})
    Node<K, V>[] node = new Node[1];
    @SuppressWarnings({"unchecked", "Varifier"})
    @Nullable K[] oldKey = (K[]) new Object[1];
    @SuppressWarnings({"unchecked", "Varifier"})
    @Nullable V[] oldValue = (V[]) new Object[1];
    @Nullable RemovalCause[] cause = new RemovalCause[1];
    Object lookupKey = nodeFactory.newLookupKey(key);

    data.computeIfPresent(lookupKey, (k, n) -> {
      synchronized (n) {
        requireIsAlive(key, n);
        oldKey[0] = n.getKey();
        oldValue[0] = n.getValue();
        RemovalCause actualCause;
        if ((oldKey[0] == null) || (oldValue[0] == null)) {
          actualCause = RemovalCause.COLLECTED;
        } else if (hasExpired(n, expirationTicker().read())) {
          actualCause = RemovalCause.EXPIRED;
        } else {
          actualCause= RemovalCause.EXPLICIT;
        }
        if (actualCause.wasEvicted()) {
          notifyEviction(oldKey[0], oldValue[0], actualCause);
        }
        cause[0] = actualCause;
        discardRefresh(k);
        node[0] = n;
        n.retire();
        return null;
      }
    });

    if (cause[0] != null) {
      afterWrite(new RemovalTask(node[0]));
      notifyRemoval(oldKey[0], oldValue[0], cause[0]);
    }
    return (cause[0] == RemovalCause.EXPLICIT) ? oldValue[0] : null;
  }

  @Override
  @SuppressWarnings("SynchronizationOnLocalVariableOrMethodParameter")
  public boolean remove(Object key, @Nullable Object value) {
    requireNonNull(key);
    if (value == null) {
      return false;
    }

    @SuppressWarnings({"rawtypes", "unchecked"})
    @Nullable Node<K, V>[] removed = new Node[1];
    @SuppressWarnings({"unchecked", "Varifier"})
    @Nullable K[] oldKey = (K[]) new Object[1];
    @SuppressWarnings({"unchecked", "Varifier"})
    @Nullable V[] oldValue = (V[]) new Object[1];
    RemovalCause[] cause = new RemovalCause[1];
    Object lookupKey = nodeFactory.newLookupKey(key);

    data.computeIfPresent(lookupKey, (kR, node) -> {
      synchronized (node) {
        requireIsAlive(key, node);
        oldKey[0] = node.getKey();
        oldValue[0] = node.getValue();
        if ((oldKey[0] == null) || (oldValue[0] == null)) {
          cause[0] = RemovalCause.COLLECTED;
        } else if (hasExpired(node, expirationTicker().read())) {
          cause[0] = RemovalCause.EXPIRED;
        } else if (node.containsValue(value)) {
          cause[0] = RemovalCause.EXPLICIT;
        } else {
          return node;
        }
        if (cause[0].wasEvicted()) {
          notifyEviction(oldKey[0], oldValue[0], cause[0]);
        }
        discardRefresh(kR);
        removed[0] = node;
        node.retire();
        return null;
      }
    });

    if (removed[0] == null) {
      return false;
    }
    afterWrite(new RemovalTask(removed[0]));
    notifyRemoval(oldKey[0], oldValue[0], cause[0]);

    return (cause[0] == RemovalCause.EXPLICIT);
  }

  @Override
  @SuppressWarnings("SynchronizationOnLocalVariableOrMethodParameter")
  public @Nullable V replace(K key, V value) {
    requireNonNull(key);
    requireNonNull(value);

    var now = new long[1];
    var oldWeight = new int[1];
    var exceedsTolerance = new boolean[1];
    @SuppressWarnings({"unchecked", "Varifier"})
    @Nullable K[] nodeKey = (K[]) new Object[1];
    @SuppressWarnings({"unchecked", "Varifier"})
    @Nullable V[] oldValue = (V[]) new Object[1];
    int weight = weigher.weigh(key, value);
    Node<K, V> node = data.computeIfPresent(nodeFactory.newLookupKey(key), (k, n) -> {
      synchronized (n) {
        requireIsAlive(key, n);
        nodeKey[0] = n.getKey();
        oldValue[0] = n.getValue();
        oldWeight[0] = n.getWeight();
        if ((nodeKey[0] == null) || (oldValue[0] == null)
            || hasExpired(n, now[0] = expirationTicker().read())) {
          oldValue[0] = null;
          return n;
        }

        long varTime = expireAfterUpdate(n, key, value, expiry(), now[0]);
        n.setValue(value, valueReferenceQueue());
        n.setWeight(weight);

        long expirationTime = isComputingAsync(value) ? (now[0] + ASYNC_EXPIRY) : now[0];
        exceedsTolerance[0] = exceedsWriteTimeTolerance(n, varTime, expirationTime);
        if (exceedsTolerance[0]) {
          setWriteTime(n, expirationTime);
        }
        setAccessTime(n, expirationTime);
        setVariableTime(n, varTime);
        discardRefresh(k);
        return n;
      }
    });

    if ((node == null) || (nodeKey[0] == null) || (oldValue[0] == null)) {
      return null;
    }

    int weightedDifference = (weight - oldWeight[0]);
    if (exceedsTolerance[0] || (weightedDifference != 0)) {
      afterWrite(new UpdateTask(node, weightedDifference));
    } else {
      afterRead(node, now[0], /* recordHit= */ false);
    }

    notifyOnReplace(nodeKey[0], oldValue[0], value);
    return oldValue[0];
  }

  @Override
  public boolean replace(K key, V oldValue, V newValue) {
    return replace(key, oldValue, newValue, /* shouldDiscardRefresh= */ true);
  }

  @Override
  @SuppressWarnings("SynchronizationOnLocalVariableOrMethodParameter")
  public boolean replace(K key, V oldValue, V newValue, boolean shouldDiscardRefresh) {
    requireNonNull(key);
    requireNonNull(oldValue);
    requireNonNull(newValue);

    var now = new long[1];
    var oldWeight = new int[1];
    var exceedsTolerance = new boolean[1];
    @SuppressWarnings({"unchecked", "Varifier"})
    @Nullable K[] nodeKey = (K[]) new Object[1];
    @SuppressWarnings({"unchecked", "Varifier"})
    @Nullable V[] prevValue = (V[]) new Object[1];

    int weight = weigher.weigh(key, newValue);
    Node<K, V> node = data.computeIfPresent(nodeFactory.newLookupKey(key), (k, n) -> {
      synchronized (n) {
        requireIsAlive(key, n);
        nodeKey[0] = n.getKey();
        prevValue[0] = n.getValue();
        oldWeight[0] = n.getWeight();
        if ((nodeKey[0] == null) || (prevValue[0] == null) || !n.containsValue(oldValue)
            || hasExpired(n, now[0] = expirationTicker().read())) {
          prevValue[0] = null;
          return n;
        }

        long varTime = expireAfterUpdate(n, key, newValue, expiry(), now[0]);
        n.setValue(newValue, valueReferenceQueue());
        n.setWeight(weight);

        long expirationTime = isComputingAsync(newValue) ? (now[0] + ASYNC_EXPIRY) : now[0];
        exceedsTolerance[0] = exceedsWriteTimeTolerance(n, varTime, expirationTime);
        if (exceedsTolerance[0]) {
          setWriteTime(n, expirationTime);
        }
        setAccessTime(n, expirationTime);
        setVariableTime(n, varTime);

        if (shouldDiscardRefresh) {
          discardRefresh(k);
        }
      }
      return n;
    });

    if ((node == null) || (nodeKey[0] == null) || (prevValue[0] == null)) {
      return false;
    }

    int weightedDifference = (weight - oldWeight[0]);
    if (exceedsTolerance[0] || (weightedDifference != 0)) {
      afterWrite(new UpdateTask(node, weightedDifference));
    } else {
      afterRead(node, now[0], /* recordHit= */ false);
    }

    notifyOnReplace(nodeKey[0], prevValue[0], newValue);
    return true;
  }

  @Override
  public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
    requireNonNull(function);

    BiFunction<K, V, V> remappingFunction = (key, oldValue) ->
        requireNonNull(function.apply(key, oldValue));
    for (K key : keySet()) {
      long[] now = { expirationTicker().read() };
      Object lookupKey = nodeFactory.newLookupKey(key);
      remap(key, lookupKey, remappingFunction, expiry(), now, /* computeIfAbsent= */ false);
    }
  }

  @Override
  public @Nullable V computeIfAbsent(K key,
      @Var Function<? super K, ? extends @Nullable V> mappingFunction,
      boolean recordStats, boolean recordLoad) {
    requireNonNull(key);
    requireNonNull(mappingFunction);
    long now = expirationTicker().read();

    // An optimistic fast path to avoid unnecessary locking
    Node<K, V> node = data.get(nodeFactory.newLookupKey(key));
    if (node != null) {
      V value = node.getValue();
      if ((value != null) && !hasExpired(node, now)) {
        if (!isComputingAsync(value)) {
          tryExpireAfterRead(node, key, value, expiry(), now);
          setAccessTime(node, now);
        }
        @Nullable V refreshed = afterRead(node, now, /* recordHit= */ recordStats);
        return (refreshed == null) ? value : refreshed;
      }
    }
    if (recordStats) {
      mappingFunction = statsAware(mappingFunction, recordLoad);
    }
    Object keyRef = nodeFactory.newReferenceKey(key, keyReferenceQueue());
    return doComputeIfAbsent(key, keyRef, mappingFunction, new long[] { now }, recordStats);
  }

  /** Returns the current value from a computeIfAbsent invocation. */
  @SuppressWarnings("SynchronizationOnLocalVariableOrMethodParameter")
  @Nullable V doComputeIfAbsent(K key, Object keyRef,
      Function<? super K, ? extends @Nullable V> mappingFunction, long[/* 1 */] now,
      boolean recordStats) {
    @SuppressWarnings({"unchecked", "Varifier"})
    @Nullable V[] oldValue = (V[]) new Object[1];
    @SuppressWarnings({"unchecked", "Varifier"})
    @Nullable V[] newValue = (V[]) new Object[1];
    @SuppressWarnings({"unchecked", "Varifier"})
    @Nullable K[] nodeKey = (K[]) new Object[1];
    @SuppressWarnings({"rawtypes", "unchecked"})
    @Nullable Node<K, V>[] removed = new Node[1];
    @Nullable Throwable[] exception = new Throwable[1];

    int[] weight = new int[2]; // old, new
    @Nullable RemovalCause[] cause = new RemovalCause[1];
    Node<K, V> node = data.compute(keyRef, (k, n) -> {
      if (n == null) {
        newValue[0] = mappingFunction.apply(key);
        if (newValue[0] == null) {
          discardRefresh(k);
          return null;
        }
        now[0] = expirationTicker().read();
        weight[1] = weigher.weigh(key, newValue[0]);
        var created = nodeFactory.newNode(key, keyReferenceQueue(),
            newValue[0], valueReferenceQueue(), weight[1], now[0]);
        long expirationTime = isComputingAsync(newValue[0]) ? (now[0] + ASYNC_EXPIRY) : now[0];
        setVariableTime(created, expireAfterCreate(key, newValue[0], expiry(), now[0]));
        setAccessTime(created, expirationTime);
        setWriteTime(created, expirationTime);
        discardRefresh(k);
        return created;
      }

      synchronized (n) {
        requireIsAlive(key, n);
        nodeKey[0] = n.getKey();
        weight[0] = n.getWeight();
        oldValue[0] = n.getValue();
        RemovalCause actualCause;
        if ((nodeKey[0] == null) || (oldValue[0] == null)) {
          actualCause = RemovalCause.COLLECTED;
        } else if (hasExpired(n, now[0])) {
          actualCause = RemovalCause.EXPIRED;
        } else {
          return n;
        }

        cause[0] = actualCause;
        notifyEviction(nodeKey[0], oldValue[0], actualCause);

        try {
          newValue[0] = mappingFunction.apply(key);
          if (newValue[0] == null) {
            discardRefresh(k);
            removed[0] = n;
            n.retire();
            return null;
          }
          now[0] = expirationTicker().read();
          weight[1] = weigher.weigh(key, newValue[0]);
          long varTime = expireAfterCreate(key, newValue[0], expiry(), now[0]);

          n.setValue(newValue[0], valueReferenceQueue());
          n.setWeight(weight[1]);

          long expirationTime = isComputingAsync(newValue[0]) ? (now[0] + ASYNC_EXPIRY) : now[0];
          setAccessTime(n, expirationTime);
          setWriteTime(n, expirationTime);
          setVariableTime(n, varTime);
          discardRefresh(k);
          return n;
        } catch (Throwable e) {
          newValue[0] = null;
          discardRefresh(k);
          exception[0] = e;
          removed[0] = n;
          n.retire();
          return null;
        }
      }
    });

    if (cause[0] != null) {
      statsCounter().recordEviction(weight[0], cause[0]);
      notifyRemoval(nodeKey[0], oldValue[0], cause[0]);
    }
    if (node == null) {
      if (removed[0] != null) {
        afterWrite(new RemovalTask(removed[0]));
      }
      if (exception[0] != null) {
        throwException(exception[0]);
      }
      return null;
    }
    if ((oldValue[0] != null) && (newValue[0] == null)) {
      if (!isComputingAsync(oldValue[0])) {
        tryExpireAfterRead(node, key, oldValue[0], expiry(), now[0]);
        setAccessTime(node, now[0]);
      }

      afterRead(node, now[0], /* recordHit= */ recordStats);
      return oldValue[0];
    }
    if ((oldValue[0] == null) && (cause[0] == null)) {
      afterWrite(new AddTask(node, weight[1]));
    } else {
      int weightedDifference = (weight[1] - weight[0]);
      afterWrite(new UpdateTask(node, weightedDifference));
    }

    return newValue[0];
  }

  @Override
  public @Nullable V computeIfPresent(K key,
      BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
    requireNonNull(key);
    requireNonNull(remappingFunction);

    // An optimistic fast path to avoid unnecessary locking
    Object lookupKey = nodeFactory.newLookupKey(key);
    @Nullable Node<K, V> node = data.get(lookupKey);
    long now;
    if (node == null) {
      return null;
    } else if ((node.getValue() == null) || hasExpired(node, (now = expirationTicker().read()))) {
      scheduleDrainBuffers();
      return null;
    }

    BiFunction<? super K, ? super V, ? extends V> statsAwareRemappingFunction =
        statsAware(remappingFunction, /* recordLoad= */ true, /* recordLoadFailure= */ true);
    return remap(key, lookupKey, statsAwareRemappingFunction,
        expiry(), new long[] { now }, /* computeIfAbsent= */ false);
  }

  @Override
  public @Nullable V compute(K key,
      BiFunction<? super K, ? super V, ? extends @Nullable V> remappingFunction,
      @Nullable Expiry<? super K, ? super V> expiry, boolean recordLoad,
      boolean recordLoadFailure) {
    requireNonNull(key);
    requireNonNull(remappingFunction);

    long[] now = { expirationTicker().read() };
    Object keyRef = nodeFactory.newReferenceKey(key, keyReferenceQueue());
    BiFunction<? super K, ? super V, ? extends V> statsAwareRemappingFunction =
        statsAware(remappingFunction, recordLoad, recordLoadFailure);
    return remap(key, keyRef, statsAwareRemappingFunction,
        expiry, now, /* computeIfAbsent= */ true);
  }

  @Override
  public @Nullable V merge(K key, V value,
      BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
    requireNonNull(key);
    requireNonNull(value);
    requireNonNull(remappingFunction);

    long[] now = { expirationTicker().read() };
    Object keyRef = nodeFactory.newReferenceKey(key, keyReferenceQueue());
    BiFunction<? super K, ? super @Nullable V, ? extends @Nullable V> mergeFunction =
        (k, oldValue) -> (oldValue == null)
          ? value
          : statsAware(remappingFunction).apply(oldValue, value);
    return remap(key, keyRef, mergeFunction, expiry(), now, /* computeIfAbsent= */ true);
  }

  /**
   * Attempts to compute a mapping for the specified key and its current mapped value (or
   * {@code null} if there is no current mapping).
   * <p>
   * An entry that has expired or been reference collected is evicted and the computation continues
   * as if the entry had not been present. This method does not pre-screen and does not wrap the
   * remappingFunction to be statistics aware.
   *
   * @param key key with which the specified value is to be associated
   * @param keyRef the key to associate with or a lookup only key if not {@code computeIfAbsent}
   * @param remappingFunction the function to compute a value
   * @param expiry the calculator for the expiration time
   * @param now the current time, according to the ticker
   * @param computeIfAbsent if an absent entry can be computed
   * @return the new value associated with the specified key, or null if none
   */
  @SuppressWarnings({"StatementWithEmptyBody", "SynchronizationOnLocalVariableOrMethodParameter"})
  @Nullable V remap(K key, Object keyRef,
      BiFunction<? super K, ? super V, ? extends @Nullable V> remappingFunction,
      @Nullable Expiry<? super K, ? super V> expiry, long[/* 1 */] now, boolean computeIfAbsent) {
    @SuppressWarnings({"unchecked", "Varifier"})
    @Nullable K[] nodeKey = (K[]) new Object[1];
    @SuppressWarnings({"unchecked", "Varifier"})
    @Nullable V[] oldValue = (V[]) new Object[1];
    @SuppressWarnings({"unchecked", "Varifier"})
    @Nullable V[] newValue = (V[]) new Object[1];
    @SuppressWarnings({"rawtypes", "unchecked"})
    @Nullable Node<K, V>[] removed = new Node[1];
    @Nullable Throwable[] exception = new Throwable[1];

    var weight = new int[2]; // old, new
    var cause = new RemovalCause[1];
    var exceedsTolerance = new boolean[1];

    Node<K, V> node = data.compute(keyRef, (kr, n) -> {
      if (n == null) {
        if (!computeIfAbsent) {
          return null;
        }
        newValue[0] = remappingFunction.apply(key, null);
        if (newValue[0] == null) {
          return null;
        }
        now[0] = expirationTicker().read();
        weight[1] = weigher.weigh(key, newValue[0]);
        long varTime = expireAfterCreate(key, newValue[0], expiry, now[0]);
        var created = nodeFactory.newNode(keyRef, newValue[0],
            valueReferenceQueue(), weight[1], now[0]);

        long expirationTime = isComputingAsync(newValue[0]) ? (now[0] + ASYNC_EXPIRY) : now[0];
        setAccessTime(created, expirationTime);
        setWriteTime(created, expirationTime);
        setVariableTime(created, varTime);
        discardRefresh(kr);
        return created;
      }

      synchronized (n) {
        requireIsAlive(key, n);
        nodeKey[0] = n.getKey();
        oldValue[0] = n.getValue();
        if ((nodeKey[0] == null) || (oldValue[0] == null)) {
          cause[0] = RemovalCause.COLLECTED;
        } else if (hasExpired(n, expirationTicker().read())) {
          cause[0] = RemovalCause.EXPIRED;
        }
        if (cause[0] != null) {
          notifyEviction(nodeKey[0], oldValue[0], cause[0]);
          if (!computeIfAbsent) {
            removed[0] = n;
            n.retire();
            return null;
          }
        }

        boolean wasEvicted = (cause[0] != null);
        try {
          newValue[0] = remappingFunction.apply(nodeKey[0],
              (cause[0] == null) ? oldValue[0] : null);

          if (newValue[0] == null) {
            if (cause[0] == null) {
              cause[0] = RemovalCause.EXPLICIT;
              discardRefresh(kr);
            }
            removed[0] = n;
            n.retire();
            return null;
          }

          long varTime;
          weight[0] = n.getWeight();
          weight[1] = weigher.weigh(key, newValue[0]);
          now[0] = expirationTicker().read();
          if (cause[0] == null) {
            if (newValue[0] != oldValue[0]) {
              cause[0] = RemovalCause.REPLACED;
            }
            varTime = expireAfterUpdate(n, key, newValue[0], expiry, now[0]);
          } else {
            varTime = expireAfterCreate(key, newValue[0], expiry, now[0]);
          }

          n.setValue(newValue[0], valueReferenceQueue());
          n.setWeight(weight[1]);

          long expirationTime = isComputingAsync(newValue[0]) ? (now[0] + ASYNC_EXPIRY) : now[0];
          exceedsTolerance[0] = exceedsWriteTimeTolerance(n, varTime, expirationTime);
          if (((cause[0] != null) && cause[0].wasEvicted()) || exceedsTolerance[0]) {
            setWriteTime(n, expirationTime);
          }
          setAccessTime(n, expirationTime);
          setVariableTime(n, varTime);
          discardRefresh(kr);
          return n;
        } catch (Throwable e) {
          if (!wasEvicted) {
            throw e;
          }
          newValue[0] = null;
          exception[0] = e;
          removed[0] = n;
          n.retire();
          return null;
        }
      }
    });

    if (cause[0] != null) {
      if (cause[0] == RemovalCause.REPLACED) {
        requireNonNull(newValue[0]);
        notifyOnReplace(key, oldValue[0], newValue[0]);
      } else {
        if (cause[0].wasEvicted()) {
          statsCounter().recordEviction(weight[0], cause[0]);
        }
        notifyRemoval(nodeKey[0], oldValue[0], cause[0]);
      }
    }

    if (removed[0] != null) {
      afterWrite(new RemovalTask(removed[0]));
    } else if (node == null) {
      // absent and not computable
    } else if ((oldValue[0] == null) && (cause[0] == null)) {
      afterWrite(new AddTask(node, weight[1]));
    } else {
      int weightedDifference = weight[1] - weight[0];
      if (exceedsTolerance[0] || (weightedDifference != 0)) {
        afterWrite(new UpdateTask(node, weightedDifference));
      } else {
        afterRead(node, now[0], /* recordHit= */ false);
        if ((cause[0] != null) && cause[0].wasEvicted()) {
          scheduleDrainBuffers();
        }
      }
    }

    if (exception[0] != null) {
      throwException(exception[0]);
    }
    return newValue[0];
  }

  @Override
  public void forEach(BiConsumer<? super K, ? super V> action) {
    requireNonNull(action);

    for (var iterator = new EntryIterator<>(this); iterator.hasNext();) {
      action.accept(iterator.key, iterator.value);
      iterator.advance();
    }
  }

  @Override
  public Set<K> keySet() {
    Set<K> ks = keySet;
    return (ks == null) ? (keySet = new KeySetView<>(this)) : ks;
  }

  @Override
  public Collection<V> values() {
    Collection<V> vs = values;
    return (vs == null) ? (values = new ValuesView<>(this)) : vs;
  }

  @Override
  public Set<Entry<K, V>> entrySet() {
    Set<Entry<K, V>> es = entrySet;
    return (es == null) ? (entrySet = new EntrySetView<>(this)) : es;
  }

  /**
   * Object equality requires reflexive, symmetric, transitive, and consistency properties. Of
   * these, symmetry and consistency require further clarification for how they are upheld.
   * <p>
   * The <i>consistency</i> property between invocations requires that the results are the same if
   * there are no modifications to the information used. Therefore, usages should expect that this
   * operation may return misleading results if either the maps or the data held by them is modified
   * during the execution of this method. This characteristic allows for comparing the map sizes and
   * assuming stable mappings, as done by {@link java.util.AbstractMap}-based maps.
   * <p>
   * The <i>symmetric</i> property requires that the result is the same for all implementations of
   * {@link Map#equals(Object)}. That contract is defined in terms of the stable mappings provided
   * by {@link #entrySet()}, meaning that the {@link #size()} optimization forces that the count is
   * consistent with the mappings when used for an equality check.
   * <p>
   * The cache's {@link #size()} method may include entries that have expired or have been reference
   * collected, but have not yet been removed from the backing map. An iteration over the map may
   * trigger the removal of these dead entries when skipped over during traversal. To ensure
   * consistency and symmetry, usages should call {@link #cleanUp()} before this method while no
   * other concurrent operations are being performed on this cache. This is not done implicitly by
   * {@link #size()} as many usages assume it to be instantaneous and lock-free.
   */
  @Override
  public boolean equals(@Nullable Object o) {
    if (o == this) {
      return true;
    } else if (!(o instanceof Map)) {
      return false;
    }

    var map = (Map<?, ?>) o;
    if (size() != map.size()) {
      return false;
    }

    long now = expirationTicker().read();
    for (var node : data.values()) {
      K key = node.getKey();
      V value = node.getValue();
      if ((key == null) || (value == null)
          || !node.isAlive() || hasExpired(node, now)) {
        scheduleDrainBuffers();
        return false;
      } else {
        var val = map.get(key);
        if ((val == null) || ((val != value) && !val.equals(value))) {
          return false;
        }
      }
    }
    return true;
  }

  @Override
  public int hashCode() {
    @Var int hash = 0;
    long now = expirationTicker().read();
    for (var node : data.values()) {
      K key = node.getKey();
      V value = node.getValue();
      if ((key == null) || (value == null)
          || !node.isAlive() || hasExpired(node, now)) {
        scheduleDrainBuffers();
      } else {
        hash += key.hashCode() ^ value.hashCode();
      }
    }
    return hash;
  }

  @Override
  public String toString() {
    var result = new StringBuilder().append('{');
    long now = expirationTicker().read();
    for (var node : data.values()) {
      K key = node.getKey();
      V value = node.getValue();
      if ((key == null) || (value == null)
          || !node.isAlive() || hasExpired(node, now)) {
        scheduleDrainBuffers();
      } else {
        if (result.length() != 1) {
          result.append(',').append(' ');
        }
        result.append((key == this) ? "(this Map)" : key);
        result.append('=');
        result.append((value == this) ? "(this Map)" : value);
      }
    }
    return result.append('}').toString();
  }

  /**
   * Returns the computed result from the ordered traversal of the cache entries.
   *
   * @param hottest the coldest or hottest iteration order
   * @param transformer a function that unwraps the value
   * @param mappingFunction the mapping function to compute a value
   * @return the computed value
   */
  @SuppressWarnings("GuardedByChecker")
  <T> T evictionOrder(boolean hottest, Function<@Nullable V, @Nullable V> transformer,
      Function<Stream<CacheEntry<K, V>>, T> mappingFunction) {
    Comparator<Node<K, V>> comparator = Comparator.comparingInt(node -> {
      var keyRef = node.getKeyReferenceOrNull();
      return (keyRef == null) ? 0 : frequencySketch().frequency(keyRef);
    });
    Iterable<Node<K, V>> iterable;
    if (hottest) {
      iterable = () -> {
        var secondary = PeekingIterator.comparing(
            accessOrderProbationDeque().descendingIterator(),
            accessOrderWindowDeque().descendingIterator(), comparator);
        return PeekingIterator.concat(
            accessOrderProtectedDeque().descendingIterator(), secondary);
      };
    } else {
      iterable = () -> {
        var primary = PeekingIterator.comparing(
            accessOrderWindowDeque().iterator(), accessOrderProbationDeque().iterator(),
            comparator.reversed());
        return PeekingIterator.concat(primary, accessOrderProtectedDeque().iterator());
      };
    }
    return snapshot(iterable, transformer, mappingFunction);
  }

  /**
   * Returns the computed result from the ordered traversal of the cache entries.
   *
   * @param oldest the youngest or oldest iteration order
   * @param transformer a function that unwraps the value
   * @param mappingFunction the mapping function to compute a value
   * @return the computed value
   */
  @SuppressWarnings("GuardedByChecker")
  <T> T expireAfterAccessOrder(boolean oldest, Function<@Nullable V, @Nullable V> transformer,
      Function<Stream<CacheEntry<K, V>>, T> mappingFunction) {
    Iterable<Node<K, V>> iterable;
    if (evicts()) {
      iterable = () -> {
        @Var Comparator<Node<K, V>> comparator = Comparator.comparingLong(Node::getAccessTime);
        PeekingIterator<Node<K, V>> first;
        PeekingIterator<Node<K, V>> second;
        PeekingIterator<Node<K, V>> third;
        if (oldest) {
          first = accessOrderWindowDeque().iterator();
          second = accessOrderProbationDeque().iterator();
          third = accessOrderProtectedDeque().iterator();
        } else {
          comparator = comparator.reversed();
          first = accessOrderWindowDeque().descendingIterator();
          second = accessOrderProbationDeque().descendingIterator();
          third = accessOrderProtectedDeque().descendingIterator();
        }
        return PeekingIterator.comparing(
            PeekingIterator.comparing(first, second, comparator), third, comparator);
      };
    } else {
      iterable = oldest
          ? accessOrderWindowDeque()
          : accessOrderWindowDeque()::descendingIterator;
    }
    return snapshot(iterable, transformer, mappingFunction);
  }

  /**
   * Returns the computed result from the ordered traversal of the cache entries.
   *
   * @param iterable the supplier of the entries in the cache
   * @param transformer a function that unwraps the value
   * @param mappingFunction the mapping function to compute a value
   * @return the computed value
   */
  <T> T snapshot(Iterable<Node<K, V>> iterable, Function<@Nullable V, @Nullable V> transformer,
      Function<Stream<CacheEntry<K, V>>, T> mappingFunction) {
    requireNonNull(mappingFunction);
    requireNonNull(transformer);
    requireNonNull(iterable);

    evictionLock.lock();
    try {
      maintenance(/* ignored */ null);

      // Obtain the iterator as late as possible for modification count checking
      try (var stream = StreamSupport.stream(Spliterators.spliteratorUnknownSize(
           iterable.iterator(), DISTINCT | ORDERED | NONNULL | IMMUTABLE), /* parallel= */ false)) {
        return mappingFunction.apply(stream
            .map(node -> nodeToCacheEntry(node, transformer))
            .filter(Objects::nonNull));
      }
    } finally {
      evictionLock.unlock();
      rescheduleCleanUpIfIncomplete();
    }
  }

  /** Returns an entry for the given node if it can be used externally, else null. */
  @Nullable CacheEntry<K, V> nodeToCacheEntry(
      Node<K, V> node, Function<@Nullable V, @Nullable V> transformer) {
    V value = transformer.apply(node.getValue());
    K key = node.getKey();
    long now;
    if ((key == null) || (value == null) || !node.isAlive()
        || hasExpired(node, (now = expirationTicker().read()))) {
      return null;
    }

    @Var long expiresAfter = Long.MAX_VALUE;
    if (expiresAfterAccess()) {
      expiresAfter = Math.min(expiresAfter,
          expiresAfterAccessNanos() - (now - node.getAccessTime()));
    }
    if (expiresAfterWrite()) {
      expiresAfter = Math.min(expiresAfter,
          expiresAfterWriteNanos() - ((now & ~1L) - (node.getWriteTime() & ~1L)));
    }
    if (expiresVariable()) {
      expiresAfter = node.getVariableTime() - now;
    }

    long refreshableAt = refreshAfterWrite()
        ? (node.getWriteTime() & ~1L) + refreshAfterWriteNanos()
        : now + Long.MAX_VALUE;
    int weight = node.getPolicyWeight();
    return SnapshotEntry.forEntry(key, value, now, weight, now + expiresAfter, refreshableAt);
  }

  /** A function that produces an unmodifiable map up to the limit in stream order. */
  static final class SizeLimiter<K, V> implements Function<Stream<CacheEntry<K, V>>, Map<K, V>> {
    private final int expectedSize;
    private final long limit;

    SizeLimiter(int expectedSize, long limit) {
      requireArgument(limit >= 0);
      this.expectedSize = expectedSize;
      this.limit = limit;
    }

    @Override
    public Map<K, V> apply(Stream<CacheEntry<K, V>> stream) {
      var map = new LinkedHashMap<K, V>(calculateHashMapCapacity(expectedSize));
      stream.limit(limit).forEach(entry -> map.put(entry.getKey(), entry.getValue()));
      return Collections.unmodifiableMap(map);
    }
  }

  /** A function that produces an unmodifiable map up to the weighted limit in stream order. */
  static final class WeightLimiter<K, V> implements Function<Stream<CacheEntry<K, V>>, Map<K, V>> {
    private final long weightLimit;

    private long weightedSize;

    WeightLimiter(long weightLimit) {
      requireArgument(weightLimit >= 0);
      this.weightLimit = weightLimit;
    }

    @Override
    public Map<K, V> apply(Stream<CacheEntry<K, V>> stream) {
      var map = new LinkedHashMap<K, V>();
      stream.takeWhile(entry -> {
        weightedSize = Math.addExact(weightedSize, entry.weight());
        return (weightedSize <= weightLimit);
      }).forEach(entry -> map.put(entry.getKey(), entry.getValue()));
      return Collections.unmodifiableMap(map);
    }
  }

  /** An adapter to safely externalize the keys. */
  static final class KeySetView<K, V> extends AbstractSet<K> {
    final BoundedLocalCache<K, V> cache;

    KeySetView(BoundedLocalCache<K, V> cache) {
      this.cache = requireNonNull(cache);
    }

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

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

    @Override
    @SuppressWarnings("SuspiciousMethodCalls")
    public boolean contains(Object o) {
      return cache.containsKey(o);
    }

    @Override
    public boolean removeAll(Collection<?> collection) {
      requireNonNull(collection);
      @Var boolean modified = false;
      if ((collection instanceof Set<?>) && (collection.size() > size())) {
        for (K key : this) {
          if (collection.contains(key)) {
            modified |= remove(key);
          }
        }
      } else {
        for (var item : collection) {
          modified |= (item != null) && remove(item);
        }
      }
      return modified;
    }

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

    @Override
    public boolean removeIf(Predicate<? super K> filter) {
      requireNonNull(filter);
      @Var boolean modified = false;
      for (K key : this) {
        if (filter.test(key) && remove(key)) {
          modified = true;
        }
      }
      return modified;
    }

    @Override
    public boolean retainAll(Collection<?> collection) {
      requireNonNull(collection);
      @Var boolean modified = false;
      for (K key : this) {
        if (!collection.contains(key) && remove(key)) {
          modified = true;
        }
      }
      return modified;
    }

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

    @Override
    public Spliterator<K> spliterator() {
      return new KeySpliterator<>(cache);
    }
  }

  /** An adapter to safely externalize the key iterator. */
  static final class KeyIterator<K, V> implements Iterator<K> {
    final EntryIterator<K, V> iterator;

    KeyIterator(BoundedLocalCache<K, V> cache) {
      this.iterator = new EntryIterator<>(cache);
    }

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

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

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

  /** An adapter to safely externalize the key spliterator. */
  static final class KeySpliterator<K, V> implements Spliterator<K> {
    final Spliterator<Node<K, V>> spliterator;
    final BoundedLocalCache<K, V> cache;

    KeySpliterator(BoundedLocalCache<K, V> cache) {
      this(cache, cache.data.values().spliterator());
    }

    KeySpliterator(BoundedLocalCache<K, V> cache, Spliterator<Node<K, V>> spliterator) {
      this.spliterator = requireNonNull(spliterator);
      this.cache = requireNonNull(cache);
    }

    @Override
    public void forEachRemaining(Consumer<? super K> action) {
      requireNonNull(action);
      Consumer<Node<K, V>> consumer = node -> {
        K key = node.getKey();
        V value = node.getValue();
        long now = cache.expirationTicker().read();
        if ((key != null) && (value != null) && node.isAlive() && !cache.hasExpired(node, now)) {
          action.accept(key);
        }
      };
      spliterator.forEachRemaining(consumer);
    }

    @Override
    public boolean tryAdvance(Consumer<? super K> action) {
      requireNonNull(action);
      boolean[] advanced = { false };
      Consumer<Node<K, V>> consumer = node -> {
        K key = node.getKey();
        V value = node.getValue();
        long now = cache.expirationTicker().read();
        if ((key != null) && (value != null) && node.isAlive() && !cache.hasExpired(node, now)) {
          action.accept(key);
          advanced[0] = true;
        }
      };
      while (spliterator.tryAdvance(consumer)) {
        if (advanced[0]) {
          return true;
        }
      }
      return false;
    }

    @Override
    public @Nullable Spliterator<K> trySplit() {
      Spliterator<Node<K, V>> split = spliterator.trySplit();
      return (split == null) ? null : new KeySpliterator<>(cache, split);
    }

    @Override
    public long estimateSize() {
      return spliterator.estimateSize();
    }

    @Override
    public int characteristics() {
      return DISTINCT | CONCURRENT | NONNULL;
    }
  }

  /** An adapter to safely externalize the values. */
  static final class ValuesView<K, V> extends AbstractCollection<V> {
    final BoundedLocalCache<K, V> cache;

    ValuesView(BoundedLocalCache<K, V> cache) {
      this.cache = requireNonNull(cache);
    }

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

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

    @Override
    @SuppressWarnings("SuspiciousMethodCalls")
    public boolean contains(Object o) {
      return cache.containsValue(o);
    }

    @Override
    public boolean removeAll(Collection<?> collection) {
      requireNonNull(collection);
      @Var boolean modified = false;
      for (var iterator = new EntryIterator<>(cache); iterator.hasNext();) {
        var key = requireNonNull(iterator.key);
        var value = requireNonNull(iterator.value);
        if (collection.contains(value) && cache.remove(key, value)) {
          modified = true;
        }
        iterator.advance();
      }
      return modified;
    }

    @Override
    public boolean remove(@Nullable Object o) {
      if (o == null) {
        return false;
      }
      for (var iterator = new EntryIterator<>(cache); iterator.hasNext();) {
        var key = requireNonNull(iterator.key);
        var value = requireNonNull(iterator.value);
        if (o.equals(value) && cache.remove(key, value)) {
          return true;
        }
        iterator.advance();
      }
      return false;
    }

    @Override
    public boolean removeIf(Predicate<? super V> filter) {
      requireNonNull(filter);
      @Var boolean modified = false;
      for (var iterator = new EntryIterator<>(cache); iterator.hasNext();) {
        var value = requireNonNull(iterator.value);
        if (filter.test(value)) {
          var key = requireNonNull(iterator.key);
          modified |= cache.remove(key, value);
        }
        iterator.advance();
      }
      return modified;
    }

    @Override
    public boolean retainAll(Collection<?> collection) {
      requireNonNull(collection);
      @Var boolean modified = false;
      for (var iterator = new EntryIterator<>(cache); iterator.hasNext();) {
        var key = requireNonNull(iterator.key);
        var value = requireNonNull(iterator.value);
        if (!collection.contains(value) && cache.remove(key, value)) {
          modified = true;
        }
        iterator.advance();
      }
      return modified;
    }

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

    @Override
    public Spliterator<V> spliterator() {
      return new ValueSpliterator<>(cache);
    }
  }

  /** An adapter to safely externalize the value iterator. */
  static final class ValueIterator<K, V> implements Iterator<V> {
    final EntryIterator<K, V> iterator;

    ValueIterator(BoundedLocalCache<K, V> cache) {
      this.iterator = new EntryIterator<>(cache);
    }

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

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

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

  /** An adapter to safely externalize the value spliterator. */
  static final class ValueSpliterator<K, V> implements Spliterator<V> {
    final Spliterator<Node<K, V>> spliterator;
    final BoundedLocalCache<K, V> cache;

    ValueSpliterator(BoundedLocalCache<K, V> cache) {
      this(cache, cache.data.values().spliterator());
    }

    ValueSpliterator(BoundedLocalCache<K, V> cache, Spliterator<Node<K, V>> spliterator) {
      this.spliterator = requireNonNull(spliterator);
      this.cache = requireNonNull(cache);
    }

    @Override
    public void forEachRemaining(Consumer<? super V> action) {
      requireNonNull(action);
      Consumer<Node<K, V>> consumer = node -> {
        K key = node.getKey();
        V value = node.getValue();
        long now = cache.expirationTicker().read();
        if ((key != null) && (value != null) && node.isAlive() && !cache.hasExpired(node, now)) {
          action.accept(value);
        }
      };
      spliterator.forEachRemaining(consumer);
    }

    @Override
    public boolean tryAdvance(Consumer<? super V> action) {
      requireNonNull(action);
      boolean[] advanced = { false };
      Consumer<Node<K, V>> consumer = node -> {
        K key = node.getKey();
        V value = node.getValue();
        long now = cache.expirationTicker().read();
        if ((key != null) && (value != null) && node.isAlive() && !cache.hasExpired(node, now)) {
          action.accept(value);
          advanced[0] = true;
        }
      };
      while (spliterator.tryAdvance(consumer)) {
        if (advanced[0]) {
          return true;
        }
      }
      return false;
    }

    @Override
    public @Nullable Spliterator<V> trySplit() {
      Spliterator<Node<K, V>> split = spliterator.trySplit();
      return (split == null) ? null : new ValueSpliterator<>(cache, split);
    }

    @Override
    public long estimateSize() {
      return spliterator.estimateSize();
    }

    @Override
    public int characteristics() {
      return CONCURRENT | NONNULL;
    }
  }

  /** An adapter to safely externalize the entries. */
  static final class EntrySetView<K, V> extends AbstractSet<Entry<K, V>> {
    final BoundedLocalCache<K, V> cache;

    EntrySetView(BoundedLocalCache<K, V> cache) {
      this.cache = requireNonNull(cache);
    }

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

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

    @Override
    public boolean contains(Object o) {
      if (!(o instanceof Entry<?, ?>)) {
        return false;
      }
      var entry = (Entry<?, ?>) o;
      var key = entry.getKey();
      var value = entry.getValue();
      if ((key == null) || (value == null)) {
        return false;
      }
      Node<K, V> node = cache.data.get(cache.nodeFactory.newLookupKey(key));
      return (node != null) && node.containsValue(value)
           && !cache.hasExpired(node, cache.expirationTicker().read());
    }

    @Override
    public boolean removeAll(Collection<?> collection) {
      requireNonNull(collection);
      @Var boolean modified = false;
      if ((collection instanceof Set<?>) && (collection.size() > size())) {
        for (var entry : this) {
          if (collection.contains(entry)) {
            modified |= remove(entry);
          }
        }
      } else {
        for (var item : collection) {
          modified |= (item != null) && remove(item);
        }
      }
      return modified;
    }

    @Override
    @SuppressWarnings("SuspiciousMethodCalls")
    public boolean remove(Object o) {
      if (!(o instanceof Entry<?, ?>)) {
        return false;
      }
      var entry = (Entry<?, ?>) o;
      var key = entry.getKey();
      return (key != null) && cache.remove(key, entry.getValue());
    }

    @Override
    public boolean removeIf(Predicate<? super Entry<K, V>> filter) {
      requireNonNull(filter);
      @Var boolean modified = false;
      for (Entry<K, V> entry : this) {
        if (filter.test(entry)) {
          modified |= cache.remove(entry.getKey(), entry.getValue());
        }
      }
      return modified;
    }

    @Override
    public boolean retainAll(Collection<?> collection) {
      requireNonNull(collection);
      @Var boolean modified = false;
      for (var entry : this) {
        if (!collection.contains(entry) && remove(entry)) {
          modified = true;
        }
      }
      return modified;
    }

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

    @Override
    public Spliterator<Entry<K, V>> spliterator() {
      return new EntrySpliterator<>(cache);
    }
  }

  /** An adapter to safely externalize the entry iterator. */
  static final class EntryIterator<K, V> implements Iterator<Entry<K, V>> {
    final BoundedLocalCache<K, V> cache;
    final Iterator<Node<K, V>> iterator;

    @Nullable K key;
    @Nullable V value;
    @Nullable K removalKey;
    @Nullable Node<K, V> next;

    EntryIterator(BoundedLocalCache<K, V> cache) {
      this.iterator = cache.data.values().iterator();
      this.cache = cache;
    }

    @Override
    public boolean hasNext() {
      if (next != null) {
        return true;
      }

      long now = cache.expirationTicker().read();
      while (iterator.hasNext()) {
        next = iterator.next();
        value = next.getValue();
        key = next.getKey();

        boolean evictable = (key == null) || (value == null) || cache.hasExpired(next, now);
        if (evictable || !next.isAlive()) {
          if (evictable) {
            cache.scheduleDrainBuffers();
          }
          advance();
          continue;
        }
        return true;
      }
      return false;
    }

    /** Invalidates the current position so that the iterator may compute the next position. */
    void advance() {
      value = null;
      next = null;
      key = null;
    }

    K nextKey() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      removalKey = key;
      advance();
      return requireNonNull(removalKey);
    }

    V nextValue() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      removalKey = key;
      V val = value;
      advance();
      return requireNonNull(val);
    }

    @Override
    public Entry<K, V> next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      var entry = new WriteThroughEntry<K, @NonNull V>(
          cache, requireNonNull(key), requireNonNull(value));
      removalKey = key;
      advance();
      return entry;
    }

    @Override
    public void remove() {
      if (removalKey == null) {
        throw new IllegalStateException();
      }
      cache.remove(removalKey);
      removalKey = null;
    }
  }

  /** An adapter to safely externalize the entry spliterator. */
  static final class EntrySpliterator<K, V> implements Spliterator<Entry<K, V>> {
    final Spliterator<Node<K, V>> spliterator;
    final BoundedLocalCache<K, V> cache;

    EntrySpliterator(BoundedLocalCache<K, V> cache) {
      this(cache, cache.data.values().spliterator());
    }

    EntrySpliterator(BoundedLocalCache<K, V> cache, Spliterator<Node<K, V>> spliterator) {
      this.spliterator = requireNonNull(spliterator);
      this.cache = requireNonNull(cache);
    }

    @Override
    public void forEachRemaining(Consumer<? super Entry<K, V>> action) {
      requireNonNull(action);
      Consumer<Node<K, V>> consumer = node -> {
        K key = node.getKey();
        V value = node.getValue();
        long now = cache.expirationTicker().read();
        if ((key != null) && (value != null) && node.isAlive() && !cache.hasExpired(node, now)) {
          action.accept(new WriteThroughEntry<>(cache, key, value));
        }
      };
      spliterator.forEachRemaining(consumer);
    }

    @Override
    public boolean tryAdvance(Consumer<? super Entry<K, V>> action) {
      requireNonNull(action);
      boolean[] advanced = { false };
      Consumer<Node<K, V>> consumer = node -> {
        K key = node.getKey();
        V value = node.getValue();
        long now = cache.expirationTicker().read();
        if ((key != null) && (value != null) && node.isAlive() && !cache.hasExpired(node, now)) {
          action.accept(new WriteThroughEntry<>(cache, key, value));
          advanced[0] = true;
        }
      };
      while (spliterator.tryAdvance(consumer)) {
        if (advanced[0]) {
          return true;
        }
      }
      return false;
    }

    @Override
    public @Nullable Spliterator<Entry<K, V>> trySplit() {
      Spliterator<Node<K, V>> split = spliterator.trySplit();
      return (split == null) ? null : new EntrySpliterator<>(cache, split);
    }

    @Override
    public long estimateSize() {
      return spliterator.estimateSize();
    }

    @Override
    public int characteristics() {
      return DISTINCT | CONCURRENT | NONNULL;
    }
  }

  /** A reusable task that performs the maintenance work; used to avoid wrapping by ForkJoinPool. */
  static final class PerformCleanupTask extends ForkJoinTask<@Nullable Void> implements Runnable {
    private static final long serialVersionUID = 1L;

    final WeakReference<BoundedLocalCache<?, ?>> reference;

    PerformCleanupTask(BoundedLocalCache<?, ?> cache) {
      reference = new WeakReference<>(cache);
    }

    @Override
    public boolean exec() {
      try {
        run();
      } catch (Throwable t) {
        logger.log(Level.ERROR, "Exception thrown when performing the maintenance task", t);
      }

      // Indicates that the task has not completed to allow subsequent submissions to execute
      return false;
    }

    @Override
    public void run() {
      BoundedLocalCache<?, ?> cache = reference.get();
      if (cache != null) {
        cache.performCleanUp(/* ignored */ null);
      }
    }

    /**
     * This method cannot be ignored due to being final, so a hostile user supplied Executor could
     * forcibly complete the task and halt future executions. There are easier ways to intentionally
     * harm a system, so this is assumed to not happen in practice.
     */
    // public final void quietlyComplete() {}

    @Override public void complete(@Nullable Void value) {}
    @Override public void setRawResult(@Nullable Void value) {}
    @Override public @Nullable Void getRawResult() { return null; }
    @Override public void completeExceptionally(@Nullable Throwable t) {}
    @Override public boolean cancel(boolean mayInterruptIfRunning) { return false; }
  }

  /** Creates a serialization proxy based on the common configuration shared by all cache types. */
  static <K, V> SerializationProxy<K, V> makeSerializationProxy(BoundedLocalCache<?, ?> cache) {
    var proxy = new SerializationProxy<K, V>();
    proxy.weakKeys = cache.collectKeys();
    proxy.weakValues = cache.nodeFactory.weakValues();
    proxy.softValues = cache.nodeFactory.softValues();
    proxy.isRecordingStats = cache.isRecordingStats();
    proxy.evictionListener = cache.evictionListener;
    proxy.removalListener = cache.removalListener();
    proxy.ticker = cache.expirationTicker();
    if (cache.expiresAfterAccess()) {
      proxy.expiresAfterAccessNanos = cache.expiresAfterAccessNanos();
    }
    if (cache.expiresAfterWrite()) {
      proxy.expiresAfterWriteNanos = cache.expiresAfterWriteNanos();
    }
    if (cache.expiresVariable()) {
      proxy.expiry = cache.expiry();
    }
    if (cache.refreshAfterWrite()) {
      proxy.refreshAfterWriteNanos = cache.refreshAfterWriteNanos();
    }
    if (cache.evicts()) {
      if (cache.isWeighted) {
        proxy.weigher = cache.weigher;
        proxy.maximumWeight = cache.maximum();
      } else {
        proxy.maximumSize = cache.maximum();
      }
    }
    proxy.cacheLoader = cache.cacheLoader;
    proxy.async = cache.isAsync;
    return proxy;
  }

  /* --------------- Manual Cache --------------- */

  static class BoundedLocalManualCache<K, V> implements LocalManualCache<K, V>, Serializable {
    private static final long serialVersionUID = 1;

    final BoundedLocalCache<K, V> cache;

    @Nullable Policy<K, V> policy;

    BoundedLocalManualCache(Caffeine<K, V> builder) {
      this(builder, null);
    }

    BoundedLocalManualCache(Caffeine<K, V> builder, @Nullable CacheLoader<? super K, V> loader) {
      cache = LocalCacheFactory.newBoundedLocalCache(builder, loader, /* isAsync= */ false);
    }

    @Override
    public final BoundedLocalCache<K, V> cache() {
      return cache;
    }

    @Override
    public final Policy<K, V> policy() {
      if (policy == null) {
        Function<@Nullable V, @Nullable V> identity = v -> v;
        policy = new BoundedPolicy<>(cache, identity, cache.isWeighted);
      }
      return policy;
    }

    private void readObject(ObjectInputStream stream) throws InvalidObjectException {
      throw new InvalidObjectException("Proxy required");
    }

    private Object writeReplace() {
      return makeSerializationProxy(cache);
    }
  }

  @SuppressWarnings({"NullableOptional",
    "OptionalAssignedToNull", "OptionalUsedAsFieldOrParameterType"})
  static final class BoundedPolicy<K, V> implements Policy<K, V> {
    final Function<@Nullable V, @Nullable V> transformer;
    final BoundedLocalCache<K, V> cache;
    final boolean isWeighted;

    @Nullable Optional<Eviction<K, V>> eviction;
    @Nullable Optional<FixedRefresh<K, V>> refreshes;
    @Nullable Optional<FixedExpiration<K, V>> afterWrite;
    @Nullable Optional<FixedExpiration<K, V>> afterAccess;
    @Nullable Optional<VarExpiration<K, V>> variable;

    BoundedPolicy(BoundedLocalCache<K, V> cache,
        Function<@Nullable V, @Nullable V> transformer, boolean isWeighted) {
      this.transformer = transformer;
      this.isWeighted = isWeighted;
      this.cache = cache;
    }

    @Override public boolean isRecordingStats() {
      return cache.isRecordingStats();
    }
    @Override public @Nullable V getIfPresentQuietly(K key) {
      return transformer.apply(cache.getIfPresentQuietly(key));
    }
    @Override public @Nullable CacheEntry<K, V> getEntryIfPresentQuietly(K key) {
      Node<K, V> node = cache.data.get(cache.nodeFactory.newLookupKey(key));
      return (node == null) ? null : cache.nodeToCacheEntry(node, transformer);
    }
    @SuppressWarnings("Java9CollectionFactory")
    @Override public Map<K, CompletableFuture<V>> refreshes() {
      var refreshes = cache.refreshes;
      if ((refreshes == null) || refreshes.isEmpty()) {
        @SuppressWarnings({"ImmutableMapOf", "RedundantUnmodifiable"})
        Map<K, CompletableFuture<V>> emptyMap = Collections.unmodifiableMap(Collections.emptyMap());
        return emptyMap;
      } else if (cache.collectKeys()) {
        var inFlight = new IdentityHashMap<K, CompletableFuture<V>>(refreshes.size());
        for (var entry : refreshes.entrySet()) {
          @SuppressWarnings("unchecked")
          @Nullable K key = ((InternalReference<K>) entry.getKey()).get();
          @SuppressWarnings("unchecked")
          var future = (CompletableFuture<V>) entry.getValue();
          if (key != null) {
            inFlight.put(key, future);
          }
        }
        return Collections.unmodifiableMap(inFlight);
      }
      @SuppressWarnings("unchecked")
      var castedRefreshes = (Map<K, CompletableFuture<V>>) (Object) refreshes;
      return Collections.unmodifiableMap(new HashMap<>(castedRefreshes));
    }
    @Override public Optional<Eviction<K, V>> eviction() {
      return cache.evicts()
          ? (eviction == null) ? (eviction = Optional.of(new BoundedEviction())) : eviction
          : Optional.empty();
    }
    @Override public Optional<FixedExpiration<K, V>> expireAfterAccess() {
      if (!cache.expiresAfterAccess()) {
        return Optional.empty();
      }
      return (afterAccess == null)
          ? (afterAccess = Optional.of(new BoundedExpireAfterAccess()))
          : afterAccess;
    }
    @Override public Optional<FixedExpiration<K, V>> expireAfterWrite() {
      if (!cache.expiresAfterWrite()) {
        return Optional.empty();
      }
      return (afterWrite == null)
          ? (afterWrite = Optional.of(new BoundedExpireAfterWrite()))
          : afterWrite;
    }
    @Override public Optional<VarExpiration<K, V>> expireVariably() {
      if (!cache.expiresVariable()) {
        return Optional.empty();
      }
      return (variable == null)
          ? (variable = Optional.of(new BoundedVarExpiration()))
          : variable;
    }
    @Override public Optional<FixedRefresh<K, V>> refreshAfterWrite() {
      if (!cache.refreshAfterWrite()) {
        return Optional.empty();
      }
      return (refreshes == null)
          ? (refreshes = Optional.of(new BoundedRefreshAfterWrite()))
          : refreshes;
    }

    final class BoundedEviction implements Eviction<K, V> {
      @Override public boolean isWeighted() {
        return isWeighted;
      }
      @Override public OptionalInt weightOf(K key) {
        requireNonNull(key);
        if (!isWeighted) {
          return OptionalInt.empty();
        }
        Node<K, V> node = cache.data.get(cache.nodeFactory.newLookupKey(key));
        if ((node == null) || cache.hasExpired(node, cache.expirationTicker().read())) {
          return OptionalInt.empty();
        }
        synchronized (node) {
          return node.isAlive() ? OptionalInt.of(node.getWeight()) : OptionalInt.empty();
        }
      }
      @Override public OptionalLong weightedSize() {
        return isWeighted
            ? OptionalLong.of(Math.max(0, cache.weightedSizeAcquire()))
            : OptionalLong.empty();
      }
      @Override public long getMaximum() {
        return cache.maximumAcquire();
      }
      @Override public void setMaximum(long maximum) {
        cache.evictionLock.lock();
        try {
          cache.setMaximumSize(maximum);
          cache.maintenance(/* ignored */ null);
        } finally {
          cache.evictionLock.unlock();
          cache.rescheduleCleanUpIfIncomplete();
        }
      }
      @Override public Map<K, V> coldest(int limit) {
        int expectedSize = Math.min(limit, cache.size());
        var limiter = new SizeLimiter<K, V>(expectedSize, limit);
        return cache.evictionOrder(/* hottest= */ false, transformer, limiter);
      }
      @Override public Map<K, V> coldestWeighted(long weightLimit) {
        var limiter = isWeighted()
            ? new WeightLimiter<K, V>(weightLimit)
            : new SizeLimiter<K, V>((int) Math.min(weightLimit, cache.size()), weightLimit);
        return cache.evictionOrder(/* hottest= */ false, transformer, limiter);
      }
      @Override
      public <T> T coldest(Function<Stream<CacheEntry<K, V>>, T> mappingFunction) {
        requireNonNull(mappingFunction);
        return cache.evictionOrder(/* hottest= */ false, transformer, mappingFunction);
      }
      @Override public Map<K, V> hottest(int limit) {
        int expectedSize = Math.min(limit, cache.size());
        var limiter = new SizeLimiter<K, V>(expectedSize, limit);
        return cache.evictionOrder(/* hottest= */ true, transformer, limiter);
      }
      @Override public Map<K, V> hottestWeighted(long weightLimit) {
        var limiter = isWeighted()
            ? new WeightLimiter<K, V>(weightLimit)
            : new SizeLimiter<K, V>((int) Math.min(weightLimit, cache.size()), weightLimit);
        return cache.evictionOrder(/* hottest= */ true, transformer, limiter);
      }
      @Override
      public <T> T hottest(Function<Stream<CacheEntry<K, V>>, T> mappingFunction) {
        requireNonNull(mappingFunction);
        return cache.evictionOrder(/* hottest= */ true, transformer, mappingFunction);
      }
    }

    @SuppressWarnings("PreferJavaTimeOverload")
    final class BoundedExpireAfterAccess implements FixedExpiration<K, V> {
      @Override public OptionalLong ageOf(K key, TimeUnit unit) {
        requireNonNull(key);
        requireNonNull(unit);
        Object lookupKey = cache.nodeFactory.newLookupKey(key);
        Node<K, V> node = cache.data.get(lookupKey);
        if (node == null) {
          return OptionalLong.empty();
        }
        long now = cache.expirationTicker().read();
        return cache.hasExpired(node, now)
            ? OptionalLong.empty()
            : OptionalLong.of(unit.convert(now - node.getAccessTime(), TimeUnit.NANOSECONDS));
      }
      @Override public long getExpiresAfter(TimeUnit unit) {
        return unit.convert(cache.expiresAfterAccessNanos(), TimeUnit.NANOSECONDS);
      }
      @Override public void setExpiresAfter(long duration, TimeUnit unit) {
        requireArgument(duration >= 0);
        cache.setExpiresAfterAccessNanos(unit.toNanos(duration));
        cache.scheduleAfterWrite();
      }
      @Override public Map<K, V> oldest(int limit) {
        return oldest(new SizeLimiter<>(Math.min(limit, cache.size()), limit));
      }
      @Override public <T> T oldest(Function<Stream<CacheEntry<K, V>>, T> mappingFunction) {
        return cache.expireAfterAccessOrder(/* oldest= */ true, transformer, mappingFunction);
      }
      @Override public Map<K, V> youngest(int limit) {
        return youngest(new SizeLimiter<>(Math.min(limit, cache.size()), limit));
      }
      @Override public <T> T youngest(Function<Stream<CacheEntry<K, V>>, T> mappingFunction) {
        return cache.expireAfterAccessOrder(/* oldest= */ false, transformer, mappingFunction);
      }
    }

    @SuppressWarnings("PreferJavaTimeOverload")
    final class BoundedExpireAfterWrite implements FixedExpiration<K, V> {
      @Override public OptionalLong ageOf(K key, TimeUnit unit) {
        requireNonNull(key);
        requireNonNull(unit);
        Object lookupKey = cache.nodeFactory.newLookupKey(key);
        Node<K, V> node = cache.data.get(lookupKey);
        if (node == null) {
          return OptionalLong.empty();
        }
        long now = cache.expirationTicker().read();
        return cache.hasExpired(node, now)
            ? OptionalLong.empty()
            : OptionalLong.of(unit.convert(now - node.getWriteTime(), TimeUnit.NANOSECONDS));
      }
      @Override public long getExpiresAfter(TimeUnit unit) {
        return unit.convert(cache.expiresAfterWriteNanos(), TimeUnit.NANOSECONDS);
      }
      @Override public void setExpiresAfter(long duration, TimeUnit unit) {
        requireArgument(duration >= 0);
        cache.setExpiresAfterWriteNanos(unit.toNanos(duration));
        cache.scheduleAfterWrite();
      }
      @Override public Map<K, V> oldest(int limit) {
        return oldest(new SizeLimiter<>(Math.min(limit, cache.size()), limit));
      }
      @SuppressWarnings("GuardedByChecker")
      @Override public <T> T oldest(Function<Stream<CacheEntry<K, V>>, T> mappingFunction) {
        return cache.snapshot(cache.writeOrderDeque(), transformer, mappingFunction);
      }
      @Override public Map<K, V> youngest(int limit) {
        return youngest(new SizeLimiter<>(Math.min(limit, cache.size()), limit));
      }
      @SuppressWarnings("GuardedByChecker")
      @Override public <T> T youngest(Function<Stream<CacheEntry<K, V>>, T> mappingFunction) {
        return cache.snapshot(cache.writeOrderDeque()::descendingIterator,
            transformer, mappingFunction);
      }
    }

    @SuppressWarnings("PreferJavaTimeOverload")
    final class BoundedVarExpiration implements VarExpiration<K, V> {
      @Override public OptionalLong getExpiresAfter(K key, TimeUnit unit) {
        requireNonNull(key);
        requireNonNull(unit);
        Object lookupKey = cache.nodeFactory.newLookupKey(key);
        Node<K, V> node = cache.data.get(lookupKey);
        if (node == null) {
          return OptionalLong.empty();
        }
        long now = cache.expirationTicker().read();
        return cache.hasExpired(node, now)
            ? OptionalLong.empty()
            : OptionalLong.of(unit.convert(node.getVariableTime() - now, TimeUnit.NANOSECONDS));
      }
      @Override public void setExpiresAfter(K key, long duration, TimeUnit unit) {
        requireNonNull(key);
        requireNonNull(unit);
        requireArgument(duration >= 0);
        Object lookupKey = cache.nodeFactory.newLookupKey(key);
        Node<K, V> node = cache.data.get(lookupKey);
        if (node != null) {
          long now;
          long durationNanos = TimeUnit.NANOSECONDS.convert(duration, unit);
          synchronized (node) {
            now = cache.expirationTicker().read();
            if (cache.isComputingAsync(node.getValue()) || cache.hasExpired(node, now)) {
              return;
            }
            node.setVariableTime(now + Math.min(durationNanos, MAXIMUM_EXPIRY));
          }
          cache.afterRead(node, now, /* recordHit= */ false);
        }
      }
      @Override public @Nullable V put(K key, V value, long duration, TimeUnit unit) {
        requireNonNull(unit);
        requireNonNull(value);
        requireArgument(duration >= 0);
        return cache.isAsync
            ? putAsync(key, value, duration, unit)
            : putSync(key, value, duration, unit, /* onlyIfAbsent= */ false);
      }
      @Override public @Nullable V putIfAbsent(K key, V value, long duration, TimeUnit unit) {
        requireNonNull(unit);
        requireNonNull(value);
        requireArgument(duration >= 0);
        return cache.isAsync
            ? putIfAbsentAsync(key, value, duration, unit)
            : putSync(key, value, duration, unit, /* onlyIfAbsent= */ true);
      }
      @Nullable V putSync(K key, V value, long duration, TimeUnit unit, boolean onlyIfAbsent) {
        var expiry = new FixedExpireAfterWrite<K, V>(duration, unit);
        return cache.put(key, value, expiry, onlyIfAbsent);
      }
      @SuppressWarnings("unchecked")
      @Nullable V putIfAbsentAsync(K key, V value, long duration, TimeUnit unit) {
        // Keep in sync with LocalAsyncCache.AsMapView#putIfAbsent(key, value)
        var expiry = (Expiry<K, V>) new AsyncExpiry<>(new FixedExpireAfterWrite<>(duration, unit));
        var asyncValue = (V) CompletableFuture.completedFuture(value);

        for (;;) {
          var priorFuture = (CompletableFuture<V>) cache.getIfPresent(
              key, /* recordStats= */ false);
          if (priorFuture != null) {
            if (!priorFuture.isDone()) {
              Async.getWhenSuccessful(priorFuture);
              continue;
            }

            V prior = Async.getWhenSuccessful(priorFuture);
            if (prior != null) {
              return prior;
            }
          }

          boolean[] added = { false };
          var computed = (CompletableFuture<V>) cache.compute(key, (K k, @Nullable V oldValue) -> {
            var oldValueFuture = (CompletableFuture<V>) oldValue;
            added[0] = (oldValueFuture == null)
                || (oldValueFuture.isDone() && (Async.getIfReady(oldValueFuture) == null));
            return added[0] ? asyncValue : oldValue;
          }, expiry, /* recordLoad= */ false, /* recordLoadFailure= */ false);

          if (added[0]) {
            return null;
          } else {
            V prior = Async.getWhenSuccessful(computed);
            if (prior != null) {
              return prior;
            }
          }
        }
      }
      @SuppressWarnings("unchecked")
      @Nullable V putAsync(K key, V value, long duration, TimeUnit unit) {
        var expiry = (Expiry<K, V>) new AsyncExpiry<>(new FixedExpireAfterWrite<>(duration, unit));
        var asyncValue = (V) CompletableFuture.completedFuture(value);

        var oldValueFuture = (CompletableFuture<V>) cache.put(
            key, asyncValue, expiry, /* onlyIfAbsent= */ false);
        return Async.getWhenSuccessful(oldValueFuture);
      }
      @Override public @Nullable V compute(K key,
          BiFunction<? super K, ? super V, ? extends V> remappingFunction,
          Duration duration) {
        requireNonNull(key);
        requireNonNull(duration);
        requireNonNull(remappingFunction);
        requireArgument(!duration.isNegative(), "duration cannot be negative: %s", duration);
        var expiry = new FixedExpireAfterWrite<K, V>(
            toNanosSaturated(duration), TimeUnit.NANOSECONDS);

        return cache.isAsync
            ? computeAsync(key, remappingFunction, expiry)
            : cache.compute(key, remappingFunction, expiry,
                /* recordLoad= */ true, /* recordLoadFailure= */ true);
      }
      @Nullable V computeAsync(K key,
          BiFunction<? super K, ? super V, ? extends V> remappingFunction,
          Expiry<? super K, ? super V> expiry) {
        // Keep in sync with LocalAsyncCache.AsMapView#compute(key, remappingFunction)
        @SuppressWarnings("unchecked")
        var delegate = (LocalCache<K, CompletableFuture<V>>) cache;

        @SuppressWarnings({"rawtypes", "unchecked", "Varifier"})
        @Nullable V[] newValue = (@Nullable V[]) new Object[1];
        for (;;) {
          Async.getWhenSuccessful(delegate.getIfPresentQuietly(key));

          CompletableFuture<V> valueFuture = delegate.compute(
              key, (K k, @Nullable CompletableFuture<V> oldValueFuture) -> {
                if ((oldValueFuture != null) && !oldValueFuture.isDone()) {
                  return oldValueFuture;
                }

                V oldValue = Async.getIfReady(oldValueFuture);
                BiFunction<? super K, ? super V, ? extends @Nullable V> function =
                    delegate.statsAware(remappingFunction,
                        /* recordLoad= */ true, /* recordLoadFailure= */ true);
                newValue[0] = function.apply(key, oldValue);
                return (newValue[0] == null) ? null
                    : CompletableFuture.completedFuture(newValue[0]);
              }, new AsyncExpiry<>(expiry), /* recordLoad= */ false,
              /* recordLoadFailure= */ false);

          if (newValue[0] != null) {
            return newValue[0];
          } else if (valueFuture == null) {
            return null;
          }
        }
      }
      @Override public Map<K, V> oldest(int limit) {
        return oldest(new SizeLimiter<>(Math.min(limit, cache.size()), limit));
      }
      @Override public <T> T oldest(Function<Stream<CacheEntry<K, V>>, T> mappingFunction) {
        return cache.snapshot(cache.timerWheel(), transformer, mappingFunction);
      }
      @Override public Map<K, V> youngest(int limit) {
        return youngest(new SizeLimiter<>(Math.min(limit, cache.size()), limit));
      }
      @Override public <T> T youngest(Function<Stream<CacheEntry<K, V>>, T> mappingFunction) {
        return cache.snapshot(cache.timerWheel()::descendingIterator, transformer, mappingFunction);
      }
    }

    static final class FixedExpireAfterWrite<K, V> implements Expiry<K, V> {
      final long duration;
      final TimeUnit unit;

      FixedExpireAfterWrite(long duration, TimeUnit unit) {
        this.duration = duration;
        this.unit = unit;
      }
      @Override public long expireAfterCreate(K key, V value, long currentTime) {
        return unit.toNanos(duration);
      }
      @Override public long expireAfterUpdate(
          K key, V value, long currentTime, long currentDuration) {
        return unit.toNanos(duration);
      }
      @CanIgnoreReturnValue
      @Override public long expireAfterRead(
          K key, V value, long currentTime, long currentDuration) {
        return currentDuration;
      }
    }

    @SuppressWarnings("PreferJavaTimeOverload")
    final class BoundedRefreshAfterWrite implements FixedRefresh<K, V> {
      @Override public OptionalLong ageOf(K key, TimeUnit unit) {
        requireNonNull(key);
        requireNonNull(unit);
        Object lookupKey = cache.nodeFactory.newLookupKey(key);
        Node<K, V> node = cache.data.get(lookupKey);
        if (node == null) {
          return OptionalLong.empty();
        }
        long now = cache.expirationTicker().read();
        return cache.hasExpired(node, now)
            ? OptionalLong.empty()
            : OptionalLong.of(unit.convert(now - node.getWriteTime(), TimeUnit.NANOSECONDS));
      }
      @Override public long getRefreshesAfter(TimeUnit unit) {
        return unit.convert(cache.refreshAfterWriteNanos(), TimeUnit.NANOSECONDS);
      }
      @Override public void setRefreshesAfter(long duration, TimeUnit unit) {
        requireArgument(duration >= 0);
        cache.setRefreshAfterWriteNanos(unit.toNanos(duration));
        cache.scheduleAfterWrite();
      }
    }
  }

  /* --------------- Loading Cache --------------- */

  static final class BoundedLocalLoadingCache<K, V>
      extends BoundedLocalManualCache<K, V> implements LocalLoadingCache<K, V> {
    private static final long serialVersionUID = 1;

    final Function<K, @Nullable V> mappingFunction;
    final @Nullable Function<Set<? extends K>, Map<K, V>> bulkMappingFunction;

    BoundedLocalLoadingCache(Caffeine<K, V> builder, CacheLoader<? super K, V> loader) {
      super(builder, loader);
      requireNonNull(loader);
      mappingFunction = newMappingFunction(loader);
      bulkMappingFunction = newBulkMappingFunction(loader);
    }

    @Override
    @SuppressWarnings({"DataFlowIssue", "NullAway"})
    public AsyncCacheLoader<? super K, V> cacheLoader() {
      return cache.cacheLoader;
    }

    @Override
    public Function<K, @Nullable V> mappingFunction() {
      return mappingFunction;
    }

    @Override
    public @Nullable Function<Set<? extends K>, Map<K, V>> bulkMappingFunction() {
      return bulkMappingFunction;
    }

    private void readObject(ObjectInputStream stream) throws InvalidObjectException {
      throw new InvalidObjectException("Proxy required");
    }

    private Object writeReplace() {
      return makeSerializationProxy(cache);
    }
  }

  /* --------------- Async Cache --------------- */

  static final class BoundedLocalAsyncCache<K, V> implements LocalAsyncCache<K, V>, Serializable {
    private static final long serialVersionUID = 1;

    final BoundedLocalCache<K, CompletableFuture<V>> cache;
    final boolean isWeighted;

    @Nullable ConcurrentMap<K, CompletableFuture<V>> mapView;
    @Nullable CacheView<K, V> cacheView;
    @Nullable Policy<K, V> policy;

    @SuppressWarnings("unchecked")
    BoundedLocalAsyncCache(Caffeine<K, V> builder) {
      cache = (BoundedLocalCache<K, CompletableFuture<V>>) LocalCacheFactory
          .newBoundedLocalCache(builder, /* cacheLoader= */ null, /* isAsync= */ true);
      isWeighted = builder.isWeighted();
    }

    @Override
    public BoundedLocalCache<K, CompletableFuture<V>> cache() {
      return cache;
    }

    @Override
    public ConcurrentMap<K, CompletableFuture<V>> asMap() {
      return (mapView == null) ? (mapView = new AsyncAsMapView<>(this)) : mapView;
    }

    @Override
    public Cache<K, V> synchronous() {
      return (cacheView == null) ? (cacheView = new CacheView<>(this)) : cacheView;
    }

    @Override
    public Policy<K, V> policy() {
      if (policy == null) {
        @SuppressWarnings("unchecked")
        var castCache = (BoundedLocalCache<K, V>) cache;
        Function<CompletableFuture<V>, @Nullable V> transformer = Async::getIfReady;
        @SuppressWarnings("unchecked")
        var castTransformer = (Function<@Nullable V, @Nullable V>) transformer;
        policy = new BoundedPolicy<>(castCache, castTransformer, isWeighted);
      }
      return policy;
    }

    private void readObject(ObjectInputStream stream) throws InvalidObjectException {
      throw new InvalidObjectException("Proxy required");
    }

    private Object writeReplace() {
      return makeSerializationProxy(cache);
    }
  }

  /* --------------- Async Loading Cache --------------- */

  static final class BoundedLocalAsyncLoadingCache<K, V>
      extends LocalAsyncLoadingCache<K, V> implements Serializable {
    private static final long serialVersionUID = 1;

    final BoundedLocalCache<K, CompletableFuture<V>> cache;
    final boolean isWeighted;

    @Nullable ConcurrentMap<K, CompletableFuture<V>> mapView;
    @Nullable Policy<K, V> policy;

    @SuppressWarnings("unchecked")
    BoundedLocalAsyncLoadingCache(Caffeine<K, V> builder, AsyncCacheLoader<? super K, V> loader) {
      super(loader);
      isWeighted = builder.isWeighted();
      cache = (BoundedLocalCache<K, CompletableFuture<V>>) LocalCacheFactory
          .newBoundedLocalCache(builder, loader, /* isAsync= */ true);
    }

    @Override
    public BoundedLocalCache<K, CompletableFuture<V>> cache() {
      return cache;
    }

    @Override
    public ConcurrentMap<K, CompletableFuture<V>> asMap() {
      return (mapView == null) ? (mapView = new AsyncAsMapView<>(this)) : mapView;
    }

    @Override
    public Policy<K, V> policy() {
      if (policy == null) {
        @SuppressWarnings("unchecked")
        var castCache = (BoundedLocalCache<K, V>) cache;
        Function<CompletableFuture<V>, @Nullable V> transformer = Async::getIfReady;
        @SuppressWarnings("unchecked")
        var castTransformer = (Function<@Nullable V, @Nullable V>) transformer;
        policy = new BoundedPolicy<>(castCache, castTransformer, isWeighted);
      }
      return policy;
    }

    private void readObject(ObjectInputStream stream) throws InvalidObjectException {
      throw new InvalidObjectException("Proxy required");
    }

    private Object writeReplace() {
      return makeSerializationProxy(cache);
    }
  }
}

/** The namespace for field padding through inheritance. */
@SuppressWarnings({"IdentifierName", "MultiVariableDeclaration"})
final class BLCHeader {

  private BLCHeader() {}

  @SuppressWarnings("unused")
  static class PadDrainStatus {
    byte p000, p001, p002, p003, p004, p005, p006, p007;
    byte p008, p009, p010, p011, p012, p013, p014, p015;
    byte p016, p017, p018, p019, p020, p021, p022, p023;
    byte p024, p025, p026, p027, p028, p029, p030, p031;
    byte p032, p033, p034, p035, p036, p037, p038, p039;
    byte p040, p041, p042, p043, p044, p045, p046, p047;
    byte p048, p049, p050, p051, p052, p053, p054, p055;
    byte p056, p057, p058, p059, p060, p061, p062, p063;
    byte p064, p065, p066, p067, p068, p069, p070, p071;
    byte p072, p073, p074, p075, p076, p077, p078, p079;
    byte p080, p081, p082, p083, p084, p085, p086, p087;
    byte p088, p089, p090, p091, p092, p093, p094, p095;
    byte p096, p097, p098, p099, p100, p101, p102, p103;
    byte p104, p105, p106, p107, p108, p109, p110, p111;
    byte p112, p113, p114, p115, p116, p117, p118, p119;
  }

  /** Enforces a memory layout to avoid false sharing by padding the drain status. */
  abstract static class DrainStatusRef extends PadDrainStatus {
    static final VarHandle DRAIN_STATUS = findVarHandle(
        DrainStatusRef.class, "drainStatus", int.class);

    /** A drain is not taking place. */
    static final int IDLE = 0;
    /** A drain is required due to a pending write modification. */
    static final int REQUIRED = 1;
    /** A drain is in progress and will transition to idle. */
    static final int PROCESSING_TO_IDLE = 2;
    /** A drain is in progress and will transition to required. */
    static final int PROCESSING_TO_REQUIRED = 3;

    /** The draining status of the buffers. */
    volatile int drainStatus = IDLE;

    /**
     * Returns whether maintenance work is needed.
     *
     * @param delayable if draining the read buffer can be delayed
     */
    @SuppressWarnings("StatementSwitchToExpressionSwitch")
    boolean shouldDrainBuffers(boolean delayable) {
      switch (drainStatusOpaque()) {
        case IDLE:
          return !delayable;
        case REQUIRED:
          return true;
        case PROCESSING_TO_IDLE:
        case PROCESSING_TO_REQUIRED:
          return false;
        default:
          throw new IllegalStateException("Invalid drain status: " + drainStatus);
      }
    }

    int drainStatusOpaque() {
      return (int) DRAIN_STATUS.getOpaque(this);
    }

    int drainStatusAcquire() {
      return (int) DRAIN_STATUS.getAcquire(this);
    }

    void setDrainStatusOpaque(int drainStatus) {
      DRAIN_STATUS.setOpaque(this, drainStatus);
    }

    void setDrainStatusRelease(int drainStatus) {
      DRAIN_STATUS.setRelease(this, drainStatus);
    }

    boolean casDrainStatus(int expect, int update) {
      return DRAIN_STATUS.compareAndSet(this, expect, update);
    }

    static VarHandle findVarHandle(Class<?> recv, String name, Class<?> type) {
      try {
        return MethodHandles.lookup().findVarHandle(recv, name, type);
      } catch (ReflectiveOperationException e) {
        throw new ExceptionInInitializerError(e);
      }
    }
  }
}

ben-manes / caffeine / #5326

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous