@GwtCompatible(serializable = true)
public static <E> ArrayList<E> newArrayList() {
  return new ArrayList<E>();
} static final Queue<? extends Object> DISCARDING_QUEUE = new AbstractQueue<Object>() {
  @Override
  public boolean offer(Object o) {
    return true;
  }

  @Override
  public Object peek() {
    return null;
  }

  @Override
  public Object poll() {
    return null;
  }

  @Override
  public int size() {
    return 0;
  }

  @Override
  public Iterator<Object> iterator() {
    return Iterators.emptyIterator();
  }
}; static final int DRAIN_THRESHOLD = 0x3F; @SuppressWarnings("unchecked") // impl never uses a parameter or returns any non-null value
static <K, V> ReferenceEntry<K, V> nullEntry() {
  return (ReferenceEntry<K, V>) NullEntry.INSTANCE;
} @SuppressWarnings("unchecked") // impl never uses a parameter or returns any non-null value
static <K, V> ValueReference<K, V> unset() {
  return (ValueReference<K, V>) UNSET;
} enum RemovalCause {
  /**
   * The entry was manually removed by the user. This can result from the user invoking
   * {@link Map#remove}, {@link ConcurrentMap#remove}, or {@link java.util.Iterator#remove}.
   */
  EXPLICIT {
    @Override
    boolean wasEvicted() {
      return false;
    }
  },

  /**
   * The entry itself was not actually removed, but its value was replaced by the user. This can
   * result from the user invoking {@link Map#put}, {@link Map#putAll},
   * {@link ConcurrentMap#replace(Object, Object)}, or
   * {@link ConcurrentMap#replace(Object, Object, Object)}.
   */
  REPLACED {
    @Override
    boolean wasEvicted() {
      return false;
    }
  },

  /**
   * The entry was removed automatically because its key or value was garbage-collected. This
   * can occur when using {@link #softKeys}, {@link #softValues}, {@link #weakKeys}, or {@link
   * #weakValues}.
   */
  COLLECTED {
    @Override
    boolean wasEvicted() {
      return true;
    }
  },

  /**
   * The entry's expiration timestamp has passed. This can occur when using {@link
   * #expireAfterWrite} or {@link #expireAfterAccess}.
   */
  EXPIRED {
    @Override
    boolean wasEvicted() {
      return true;
    }
  },

  /**
   * The entry was evicted due to size constraints. This can occur when using {@link
   * #maximumSize}.
   */
  SIZE {
    @Override
    boolean wasEvicted() {
      return true;
    }
  };

  /**
   * Returns {@code true} if there was an automatic removal due to eviction (the cause is neither
   * {@link #EXPLICIT} nor {@link #REPLACED}).
   */
  abstract boolean wasEvicted();
} interface RemovalListener<K, V> {
  /**
   * Notifies the listener that a removal occurred at some point in the past.
   */
  void onRemoval(RemovalNotification<K, V> notification);
} static final class RemovalNotification<K, V> extends ImmutableEntry<K, V> {
  private static final long serialVersionUID = 0;

  private final RemovalCause cause;

  RemovalNotification(@Nullable K key, @Nullable V value, RemovalCause cause) {
    super(key, value);
    this.cause = cause;
  }

  /**
   * Returns the cause for which the entry was removed.
   */
  public RemovalCause getCause() {
    return cause;
  }

  /**
   * Returns {@code true} if there was an automatic removal due to eviction (the cause is neither
   * {@link RemovalCause#EXPLICIT} nor {@link RemovalCause#REPLACED}).
   */
  public boolean wasEvicted() {
    return cause.wasEvicted();
  }
} enum EntryFactory {
  STRONG {
    @Override
    <K, V> ReferenceEntry<K, V> newEntry(
        Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
      return new StrongEntry<K, V>(key, hash, next);
    }
  },
  STRONG_EXPIRABLE {
    @Override
    <K, V> ReferenceEntry<K, V> newEntry(
        Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
      return new StrongExpirableEntry<K, V>(key, hash, next);
    }

    @Override
    <K, V> ReferenceEntry<K, V> copyEntry(
        Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
      ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
      copyExpirableEntry(original, newEntry);
      return newEntry;
    }
  },
  STRONG_EVICTABLE {
    @Override
    <K, V> ReferenceEntry<K, V> newEntry(
        Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
      return new StrongEvictableEntry<K, V>(key, hash, next);
    }

    @Override
    <K, V> ReferenceEntry<K, V> copyEntry(
        Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
      ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
      copyEvictableEntry(original, newEntry);
      return newEntry;
    }
  },
  STRONG_EXPIRABLE_EVICTABLE {
    @Override
    <K, V> ReferenceEntry<K, V> newEntry(
        Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
      return new StrongExpirableEvictableEntry<K, V>(key, hash, next);
    }

    @Override
    <K, V> ReferenceEntry<K, V> copyEntry(
        Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
      ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
      copyExpirableEntry(original, newEntry);
      copyEvictableEntry(original, newEntry);
      return newEntry;
    }
  },

  SOFT {
    @Override
    <K, V> ReferenceEntry<K, V> newEntry(
        Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
      return new SoftEntry<K, V>(segment.keyReferenceQueue, key, hash, next);
    }
  },
  SOFT_EXPIRABLE {
    @Override
    <K, V> ReferenceEntry<K, V> newEntry(
        Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
      return new SoftExpirableEntry<K, V>(segment.keyReferenceQueue, key, hash, next);
    }

    @Override
    <K, V> ReferenceEntry<K, V> copyEntry(
        Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
      ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
      copyExpirableEntry(original, newEntry);
      return newEntry;
    }
  },
  SOFT_EVICTABLE {
    @Override
    <K, V> ReferenceEntry<K, V> newEntry(
        Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
      return new SoftEvictableEntry<K, V>(segment.keyReferenceQueue, key, hash, next);
    }

    @Override
    <K, V> ReferenceEntry<K, V> copyEntry(
        Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
      ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
      copyEvictableEntry(original, newEntry);
      return newEntry;
    }
  },
  SOFT_EXPIRABLE_EVICTABLE {
    @Override
    <K, V> ReferenceEntry<K, V> newEntry(
        Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
      return new SoftExpirableEvictableEntry<K, V>(segment.keyReferenceQueue, key, hash, next);
    }

    @Override
    <K, V> ReferenceEntry<K, V> copyEntry(
        Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
      ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
      copyExpirableEntry(original, newEntry);
      copyEvictableEntry(original, newEntry);
      return newEntry;
    }
  },

  WEAK {
    @Override
    <K, V> ReferenceEntry<K, V> newEntry(
        Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
      return new WeakEntry<K, V>(segment.keyReferenceQueue, key, hash, next);
    }
  },
  WEAK_EXPIRABLE {
    @Override
    <K, V> ReferenceEntry<K, V> newEntry(
        Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
      return new WeakExpirableEntry<K, V>(segment.keyReferenceQueue, key, hash, next);
    }

    @Override
    <K, V> ReferenceEntry<K, V> copyEntry(
        Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
      ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
      copyExpirableEntry(original, newEntry);
      return newEntry;
    }
  },
  WEAK_EVICTABLE {
    @Override
    <K, V> ReferenceEntry<K, V> newEntry(
        Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
      return new WeakEvictableEntry<K, V>(segment.keyReferenceQueue, key, hash, next);
    }

    @Override
    <K, V> ReferenceEntry<K, V> copyEntry(
        Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
      ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
      copyEvictableEntry(original, newEntry);
      return newEntry;
    }
  },
  WEAK_EXPIRABLE_EVICTABLE {
    @Override
    <K, V> ReferenceEntry<K, V> newEntry(
        Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
      return new WeakExpirableEvictableEntry<K, V>(segment.keyReferenceQueue, key, hash, next);
    }

    @Override
    <K, V> ReferenceEntry<K, V> copyEntry(
        Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
      ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
      copyExpirableEntry(original, newEntry);
      copyEvictableEntry(original, newEntry);
      return newEntry;
    }
  };

  /**
   * Masks used to compute indices in the following table.
   */
  static final int EXPIRABLE_MASK = 1;
  static final int EVICTABLE_MASK = 2;

  /**
   * Look-up table for factories. First dimension is the reference type. The second dimension is
   * the result of OR-ing the feature masks.
   */
  static final EntryFactory[][] factories = {
    { STRONG, STRONG_EXPIRABLE, STRONG_EVICTABLE, STRONG_EXPIRABLE_EVICTABLE },
    { SOFT, SOFT_EXPIRABLE, SOFT_EVICTABLE, SOFT_EXPIRABLE_EVICTABLE },
    { WEAK, WEAK_EXPIRABLE, WEAK_EVICTABLE, WEAK_EXPIRABLE_EVICTABLE }
  };

  static EntryFactory getFactory(Strength keyStrength, boolean expireAfterWrite,
      boolean evictsBySize) {
    int flags = (expireAfterWrite ? EXPIRABLE_MASK : 0) | (evictsBySize ? EVICTABLE_MASK : 0);
    return factories[keyStrength.ordinal()][flags];
  }

  /**
   * Creates a new entry.
   *
   * @param segment to create the entry for
   * @param key of the entry
   * @param hash of the key
   * @param next entry in the same bucket
   */
  abstract <K, V> ReferenceEntry<K, V> newEntry(
      Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next);

  /**
   * Copies an entry, assigning it a new {@code next} entry.
   *
   * @param original the entry to copy
   * @param newNext entry in the same bucket
   */
  @GuardedBy("Segment.this")
  <K, V> ReferenceEntry<K, V> copyEntry(
      Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
    return newEntry(segment, original.getKey(), original.getHash(), newNext);
  }

  @GuardedBy("Segment.this")
  <K, V> void copyExpirableEntry(ReferenceEntry<K, V> original, ReferenceEntry<K, V> newEntry) {
    // TODO(fry): when we link values instead of entries this method can go
    // away, as can connectExpirables, nullifyExpirable.
    newEntry.setExpirationTime(original.getExpirationTime());

    connectExpirables(original.getPreviousExpirable(), newEntry);
    connectExpirables(newEntry, original.getNextExpirable());

    nullifyExpirable(original);
  }

  @GuardedBy("Segment.this")
  <K, V> void copyEvictableEntry(ReferenceEntry<K, V> original, ReferenceEntry<K, V> newEntry) {
    // TODO(fry): when we link values instead of entries this method can go
    // away, as can connectEvictables, nullifyEvictable.
    connectEvictables(original.getPreviousEvictable(), newEntry);
    connectEvictables(newEntry, original.getNextEvictable());

    nullifyEvictable(original);
  }
} interface ReferenceEntry<K, V> {
  /**
   * Gets the value reference from this entry.
   */
  ValueReference<K, V> getValueReference();

  /**
   * Sets the value reference for this entry.
   */
  void setValueReference(ValueReference<K, V> valueReference);

  /**
   * Gets the next entry in the chain.
   */
  ReferenceEntry<K, V> getNext();

  /**
   * Gets the entry's hash.
   */
  int getHash();

  /**
   * Gets the key for this entry.
   */
  K getKey();

  /*
   * Used by entries that are expirable. Expirable entries are maintained in a doubly-linked list.
   * New entries are added at the tail of the list at write time; stale entries are expired from
   * the head of the list.
   */

  /**
   * Gets the entry expiration time in ns.
   */
  long getExpirationTime();

  /**
   * Sets the entry expiration time in ns.
   */
  void setExpirationTime(long time);

  /**
   * Gets the next entry in the recency list.
   */
  ReferenceEntry<K, V> getNextExpirable();

  /**
   * Sets the next entry in the recency list.
   */
  void setNextExpirable(ReferenceEntry<K, V> next);

  /**
   * Gets the previous entry in the recency list.
   */
  ReferenceEntry<K, V> getPreviousExpirable();

  /**
   * Sets the previous entry in the recency list.
   */
  void setPreviousExpirable(ReferenceEntry<K, V> previous);

  /*
   * Implemented by entries that are evictable. Evictable entries are maintained in a
   * doubly-linked list. New entries are added at the tail of the list at write time and stale
   * entries are expired from the head of the list.
   */

  /**
   * Gets the next entry in the recency list.
   */
  ReferenceEntry<K, V> getNextEvictable();

  /**
   * Sets the next entry in the recency list.
   */
  void setNextEvictable(ReferenceEntry<K, V> next);

  /**
   * Gets the previous entry in the recency list.
   */
  ReferenceEntry<K, V> getPreviousEvictable();

  /**
   * Sets the previous entry in the recency list.
   */
  void setPreviousEvictable(ReferenceEntry<K, V> previous);
} @SuppressWarnings("serial") // This class is never serialized.
static class Segment<K, V> extends ReentrantLock {

  /*
   * TODO(fry): Consider copying variables (like evictsBySize) from outer class into this class.
   * It will require more memory but will reduce indirection.
   */

  /*
   * Segments maintain a table of entry lists that are ALWAYS kept in a consistent state, so can
   * be read without locking. Next fields of nodes are immutable (final). All list additions are
   * performed at the front of each bin. This makes it easy to check changes, and also fast to
   * traverse. When nodes would otherwise be changed, new nodes are created to replace them. This
   * works well for hash tables since the bin lists tend to be short. (The average length is less
   * than two.)
   *
   * Read operations can thus proceed without locking, but rely on selected uses of volatiles to
   * ensure that completed write operations performed by other threads are noticed. For most
   * purposes, the "count" field, tracking the number of elements, serves as that volatile
   * variable ensuring visibility. This is convenient because this field needs to be read in many
   * read operations anyway:
   *
   * - All (unsynchronized) read operations must first read the "count" field, and should not
   * look at table entries if it is 0.
   *
   * - All (synchronized) write operations should write to the "count" field after structurally
   * changing any bin. The operations must not take any action that could even momentarily
   * cause a concurrent read operation to see inconsistent data. This is made easier by the
   * nature of the read operations in Map. For example, no operation can reveal that the table
   * has grown but the threshold has not yet been updated, so there are no atomicity requirements
   * for this with respect to reads.
   *
   * As a guide, all critical volatile reads and writes to the count field are marked in code
   * comments.
   */

  final MapMakerInternalMap<K, V> map;

  /**
   * The number of live elements in this segment's region. This does not include unset elements
   * which are awaiting cleanup.
   */
  volatile int count;

  /**
   * Number of updates that alter the size of the table. This is used during bulk-read methods to
   * make sure they see a consistent snapshot: If modCounts change during a traversal of segments
   * computing size or checking containsValue, then we might have an inconsistent view of state
   * so (usually) must retry.
   */
  int modCount;

  /**
   * The table is expanded when its size exceeds this threshold. (The value of this field is
   * always {@code (int)(capacity * 0.75)}.)
   */
  int threshold;

  /**
   * The per-segment table.
   */
  volatile AtomicReferenceArray<ReferenceEntry<K, V>> table;

  /**
   * The maximum size of this map. MapMaker.UNSET_INT if there is no maximum.
   */
  final int maxSegmentSize;

  /**
   * The key reference queue contains entries whose keys have been garbage collected, and which
   * need to be cleaned up internally.
   */
  final ReferenceQueue<K> keyReferenceQueue;

  /**
   * The value reference queue contains value references whose values have been garbage collected,
   * and which need to be cleaned up internally.
   */
  final ReferenceQueue<V> valueReferenceQueue;

  /**
   * The recency queue is used to record which entries were accessed for updating the eviction
   * list's ordering. It is drained as a batch operation when either the DRAIN_THRESHOLD is
   * crossed or a write occurs on the segment.
   */
  final Queue<ReferenceEntry<K, V>> recencyQueue;

  /**
   * A counter of the number of reads since the last write, used to drain queues on a small
   * fraction of read operations.
   */
  final AtomicInteger readCount = new AtomicInteger();

  /**
   * A queue of elements currently in the map, ordered by access time. Elements are added to the
   * tail of the queue on access/write.
   */
  @GuardedBy("Segment.this")
  final Queue<ReferenceEntry<K, V>> evictionQueue;

  /**
   * A queue of elements currently in the map, ordered by expiration time (either access or write
   * time). Elements are added to the tail of the queue on access/write.
   */
  @GuardedBy("Segment.this")
  final Queue<ReferenceEntry<K, V>> expirationQueue;

  Segment(MapMakerInternalMap<K, V> map, int initialCapacity, int maxSegmentSize) {
    this.map = map;
    this.maxSegmentSize = maxSegmentSize;
    initTable(newEntryArray(initialCapacity));

    keyReferenceQueue = map.usesKeyReferences()
         ? new ReferenceQueue<K>() : null;

    valueReferenceQueue = map.usesValueReferences()
         ? new ReferenceQueue<V>() : null;

    recencyQueue = (map.evictsBySize() || map.expiresAfterAccess())
        ? new ConcurrentLinkedQueue<ReferenceEntry<K, V>>()
        : MapMakerInternalMap.<ReferenceEntry<K, V>>discardingQueue();

    evictionQueue = map.evictsBySize()
        ? new EvictionQueue<K, V>()
        : MapMakerInternalMap.<ReferenceEntry<K, V>>discardingQueue();

    expirationQueue = map.expires()
        ? new ExpirationQueue<K, V>()
        : MapMakerInternalMap.<ReferenceEntry<K, V>>discardingQueue();
  }

  AtomicReferenceArray<ReferenceEntry<K, V>> newEntryArray(int size) {
    return new AtomicReferenceArray<ReferenceEntry<K, V>>(size);
  }

  void initTable(AtomicReferenceArray<ReferenceEntry<K, V>> newTable) {
    this.threshold = newTable.length() * 3 / 4; // 0.75
    if (this.threshold == maxSegmentSize) {
      // prevent spurious expansion before eviction
      this.threshold++;
    }
    this.table = newTable;
  }

  @GuardedBy("Segment.this")
  ReferenceEntry<K, V> newEntry(K key, int hash, @Nullable ReferenceEntry<K, V> next) {
    return map.entryFactory.newEntry(this, key, hash, next);
  }

  @GuardedBy("Segment.this")
  ReferenceEntry<K, V> copyEntry(ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
    ValueReference<K, V> valueReference = original.getValueReference();
    ReferenceEntry<K, V> newEntry = map.entryFactory.copyEntry(this, original, newNext);
    newEntry.setValueReference(valueReference.copyFor(this.valueReferenceQueue, newEntry));
    return newEntry;
  }

  /**
   * Sets a new value of an entry. Adds newly created entries at the end of the expiration queue.
   */
  @GuardedBy("Segment.this")
  void setValue(ReferenceEntry<K, V> entry, V value) {
    ValueReference<K, V> valueReference = map.valueStrength.referenceValue(this, entry, value);
    entry.setValueReference(valueReference);
    recordWrite(entry);
  }

  // reference queues, for garbage collection cleanup

  /**
   * Cleanup collected entries when the lock is available.
   */
  void tryDrainReferenceQueues() {
    if (tryLock()) {
      try {
        drainReferenceQueues();
      } finally {
        unlock();
      }
    }
  }

  /**
   * Drain the key and value reference queues, cleaning up internal entries containing garbage
   * collected keys or values.
   */
  @GuardedBy("Segment.this")
  void drainReferenceQueues() {
    if (map.usesKeyReferences()) {
      drainKeyReferenceQueue();
    }
    if (map.usesValueReferences()) {
      drainValueReferenceQueue();
    }
  }

  @GuardedBy("Segment.this")
  void drainKeyReferenceQueue() {
    Reference<? extends K> ref;
    int i = 0;
    while ((ref = keyReferenceQueue.poll()) != null) {
      @SuppressWarnings("unchecked")
      ReferenceEntry<K, V> entry = (ReferenceEntry<K, V>) ref;
      map.reclaimKey(entry);
      if (++i == DRAIN_MAX) {
        break;
      }
    }
  }

  @GuardedBy("Segment.this")
  void drainValueReferenceQueue() {
    Reference<? extends V> ref;
    int i = 0;
    while ((ref = valueReferenceQueue.poll()) != null) {
      @SuppressWarnings("unchecked")
      ValueReference<K, V> valueReference = (ValueReference<K, V>) ref;
      map.reclaimValue(valueReference);
      if (++i == DRAIN_MAX) {
        break;
      }
    }
  }

  /**
   * Clears all entries from the key and value reference queues.
   */
  void clearReferenceQueues() {
    if (map.usesKeyReferences()) {
      clearKeyReferenceQueue();
    }
    if (map.usesValueReferences()) {
      clearValueReferenceQueue();
    }
  }

  void clearKeyReferenceQueue() {
    while (keyReferenceQueue.poll() != null) {}
  }

  void clearValueReferenceQueue() {
    while (valueReferenceQueue.poll() != null) {}
  }

  // recency queue, shared by expiration and eviction

  /**
   * Records the relative order in which this read was performed by adding {@code entry} to the
   * recency queue. At write-time, or when the queue is full past the threshold, the queue will
   * be drained and the entries therein processed.
   *
   * <p>Note: locked reads should use {@link #recordLockedRead}.
   */
  void recordRead(ReferenceEntry<K, V> entry) {
    if (map.expiresAfterAccess()) {
      recordExpirationTime(entry, map.expireAfterAccessNanos);
    }
    recencyQueue.add(entry);
  }

  /**
   * Updates the eviction metadata that {@code entry} was just read. This currently amounts to
   * adding {@code entry} to relevant eviction lists.
   *
   * <p>Note: this method should only be called under lock, as it directly manipulates the
   * eviction queues. Unlocked reads should use {@link #recordRead}.
   */
  @GuardedBy("Segment.this")
  void recordLockedRead(ReferenceEntry<K, V> entry) {
    evictionQueue.add(entry);
    if (map.expiresAfterAccess()) {
      recordExpirationTime(entry, map.expireAfterAccessNanos);
      expirationQueue.add(entry);
    }
  }

  /**
   * Updates eviction metadata that {@code entry} was just written. This currently amounts to
   * adding {@code entry} to relevant eviction lists.
   */
  @GuardedBy("Segment.this")
  void recordWrite(ReferenceEntry<K, V> entry) {
    // we are already under lock, so drain the recency queue immediately
    drainRecencyQueue();
    evictionQueue.add(entry);
    if (map.expires()) {
      // currently MapMaker ensures that expireAfterWrite and
      // expireAfterAccess are mutually exclusive
      long expiration = map.expiresAfterAccess()
          ? map.expireAfterAccessNanos
          : map.expireAfterWriteNanos;
      recordExpirationTime(entry, expiration);
      expirationQueue.add(entry);
    }
  }

  /**
   * Drains the recency queue, updating eviction metadata that the entries therein were read in
   * the specified relative order. This currently amounts to adding them to relevant eviction
   * lists (accounting for the fact that they could have been removed from the map since being
   * added to the recency queue).
   */
  @GuardedBy("Segment.this")
  void drainRecencyQueue() {
    ReferenceEntry<K, V> e;
    while ((e = recencyQueue.poll()) != null) {
      // An entry may be in the recency queue despite it being removed from
      // the map . This can occur when the entry was concurrently read while a
      // writer is removing it from the segment or after a clear has removed
      // all of the segment's entries.
      if (evictionQueue.contains(e)) {
        evictionQueue.add(e);
      }
      if (map.expiresAfterAccess() && expirationQueue.contains(e)) {
        expirationQueue.add(e);
      }
    }
  }

  // expiration

  void recordExpirationTime(ReferenceEntry<K, V> entry, long expirationNanos) {
    // might overflow, but that's okay (see isExpired())
    entry.setExpirationTime(map.ticker.read() + expirationNanos);
  }

  /**
   * Cleanup expired entries when the lock is available.
   */
  void tryExpireEntries() {
    if (tryLock()) {
      try {
        expireEntries();
      } finally {
        unlock();
        // don't call postWriteCleanup as we're in a read
      }
    }
  }

  @GuardedBy("Segment.this")
  void expireEntries() {
    drainRecencyQueue();

    if (expirationQueue.isEmpty()) {
      // There's no point in calling nanoTime() if we have no entries to
      // expire.
      return;
    }
    long now = map.ticker.read();
    ReferenceEntry<K, V> e;
    while ((e = expirationQueue.peek()) != null && map.isExpired(e, now)) {
      if (!removeEntry(e, e.getHash(), RemovalCause.EXPIRED)) {
        throw new AssertionError();
      }
    }
  }

  // eviction

  void enqueueNotification(ReferenceEntry<K, V> entry, RemovalCause cause) {
    enqueueNotification(entry.getKey(), entry.getHash(), entry.getValueReference().get(), cause);
  }

  void enqueueNotification(@Nullable K key, int hash, @Nullable V value, RemovalCause cause) {
    if (map.removalNotificationQueue != DISCARDING_QUEUE) {
      RemovalNotification<K, V> notification = new RemovalNotification<K, V>(key, value, cause);
      map.removalNotificationQueue.offer(notification);
    }
  }

  /**
   * Performs eviction if the segment is full. This should only be called prior to adding a new
   * entry and increasing {@code count}.
   *
   * @return {@code true} if eviction occurred
   */
  @GuardedBy("Segment.this")
  boolean evictEntries() {
    if (map.evictsBySize() && count >= maxSegmentSize) {
      drainRecencyQueue();

      ReferenceEntry<K, V> e = evictionQueue.remove();
      if (!removeEntry(e, e.getHash(), RemovalCause.SIZE)) {
        throw new AssertionError();
      }
      return true;
    }
    return false;
  }

  /**
   * Returns first entry of bin for given hash.
   */
  ReferenceEntry<K, V> getFirst(int hash) {
    // read this volatile field only once
    AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
    return table.get(hash & (table.length() - 1));
  }

  // Specialized implementations of map methods

  ReferenceEntry<K, V> getEntry(Object key, int hash) {
    if (count != 0) { // read-volatile
      for (ReferenceEntry<K, V> e = getFirst(hash); e != null; e = e.getNext()) {
        if (e.getHash() != hash) {
          continue;
        }

        K entryKey = e.getKey();
        if (entryKey == null) {
          tryDrainReferenceQueues();
          continue;
        }

        if (map.keyEquivalence.equivalent(key, entryKey)) {
          return e;
        }
      }
    }

    return null;
  }

  ReferenceEntry<K, V> getLiveEntry(Object key, int hash) {
    ReferenceEntry<K, V> e = getEntry(key, hash);
    if (e == null) {
      return null;
    } else if (map.expires() && map.isExpired(e)) {
      tryExpireEntries();
      return null;
    }
    return e;
  }

  V get(Object key, int hash) {
    try {
      ReferenceEntry<K, V> e = getLiveEntry(key, hash);
      if (e == null) {
        return null;
      }

      V value = e.getValueReference().get();
      if (value != null) {
        recordRead(e);
      } else {
        tryDrainReferenceQueues();
      }
      return value;
    } finally {
      postReadCleanup();
    }
  }

  boolean containsKey(Object key, int hash) {
    try {
      if (count != 0) { // read-volatile
        ReferenceEntry<K, V> e = getLiveEntry(key, hash);
        if (e == null) {
          return false;
        }
        return e.getValueReference().get() != null;
      }

      return false;
    } finally {
      postReadCleanup();
    }
  }

  /**
   * This method is a convenience for testing. Code should call {@link
   * MapMakerInternalMap#containsValue} directly.
   */
  @VisibleForTesting
  boolean containsValue(Object value) {
    try {
      if (count != 0) { // read-volatile
        AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
        int length = table.length();
        for (int i = 0; i < length; ++i) {
          for (ReferenceEntry<K, V> e = table.get(i); e != null; e = e.getNext()) {
            V entryValue = getLiveValue(e);
            if (entryValue == null) {
              continue;
            }
            if (map.valueEquivalence.equivalent(value, entryValue)) {
              return true;
            }
          }
        }
      }

      return false;
    } finally {
      postReadCleanup();
    }
  }

  V put(K key, int hash, V value, boolean onlyIfAbsent) {
    lock();
    try {
      preWriteCleanup();

      int newCount = this.count + 1;
      if (newCount > this.threshold) { // ensure capacity
        expand();
        newCount = this.count + 1;
      }

      AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
      int index = hash & (table.length() - 1);
      ReferenceEntry<K, V> first = table.get(index);

      // Look for an existing entry.
      for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
        K entryKey = e.getKey();
        if (e.getHash() == hash && entryKey != null
            && map.keyEquivalence.equivalent(key, entryKey)) {
          // We found an existing entry.

          ValueReference<K, V> valueReference = e.getValueReference();
          V entryValue = valueReference.get();

          if (entryValue == null) {
            ++modCount;
            setValue(e, value);
            if (!valueReference.isComputingReference()) {
              enqueueNotification(key, hash, entryValue, RemovalCause.COLLECTED);
              newCount = this.count; // count remains unchanged
            } else if (evictEntries()) { // evictEntries after setting new value
              newCount = this.count + 1;
            }
            this.count = newCount; // write-volatile
            return null;
          } else if (onlyIfAbsent) {
            // Mimic
            // "if (!map.containsKey(key)) ...
            // else return map.get(key);
            recordLockedRead(e);
            return entryValue;
          } else {
            // clobber existing entry, count remains unchanged
            ++modCount;
            enqueueNotification(key, hash, entryValue, RemovalCause.REPLACED);
            setValue(e, value);
            return entryValue;
          }
        }
      }

      // Create a new entry.
      ++modCount;
      ReferenceEntry<K, V> newEntry = newEntry(key, hash, first);
      setValue(newEntry, value);
      table.set(index, newEntry);
      if (evictEntries()) { // evictEntries after setting new value
        newCount = this.count + 1;
      }
      this.count = newCount; // write-volatile
      return null;
    } finally {
      unlock();
      postWriteCleanup();
    }
  }

  /**
   * Expands the table if possible.
   */
  @GuardedBy("Segment.this")
  void expand() {
    AtomicReferenceArray<ReferenceEntry<K, V>> oldTable = table;
    int oldCapacity = oldTable.length();
    if (oldCapacity >= MAXIMUM_CAPACITY) {
      return;
    }

    /*
     * Reclassify nodes in each list to new Map. Because we are using power-of-two expansion, the
     * elements from each bin must either stay at same index, or move with a power of two offset.
     * We eliminate unnecessary node creation by catching cases where old nodes can be reused
     * because their next fields won't change. Statistically, at the default threshold, only
     * about one-sixth of them need cloning when a table doubles. The nodes they replace will be
     * garbage collectable as soon as they are no longer referenced by any reader thread that may
     * be in the midst of traversing table right now.
     */

    int newCount = count;
    AtomicReferenceArray<ReferenceEntry<K, V>> newTable = newEntryArray(oldCapacity << 1);
    threshold = newTable.length() * 3 / 4;
    int newMask = newTable.length() - 1;
    for (int oldIndex = 0; oldIndex < oldCapacity; ++oldIndex) {
      // We need to guarantee that any existing reads of old Map can
      // proceed. So we cannot yet null out each bin.
      ReferenceEntry<K, V> head = oldTable.get(oldIndex);

      if (head != null) {
        ReferenceEntry<K, V> next = head.getNext();
        int headIndex = head.getHash() & newMask;

        // Single node on list
        if (next == null) {
          newTable.set(headIndex, head);
        } else {
          // Reuse the consecutive sequence of nodes with the same target
          // index from the end of the list. tail points to the first
          // entry in the reusable list.
          ReferenceEntry<K, V> tail = head;
          int tailIndex = headIndex;
          for (ReferenceEntry<K, V> e = next; e != null; e = e.getNext()) {
            int newIndex = e.getHash() & newMask;
            if (newIndex != tailIndex) {
              // The index changed. We'll need to copy the previous entry.
              tailIndex = newIndex;
              tail = e;
            }
          }
          newTable.set(tailIndex, tail);

          // Clone nodes leading up to the tail.
          for (ReferenceEntry<K, V> e = head; e != tail; e = e.getNext()) {
            if (isCollected(e)) {
              removeCollectedEntry(e);
              newCount--;
            } else {
              int newIndex = e.getHash() & newMask;
              ReferenceEntry<K, V> newNext = newTable.get(newIndex);
              ReferenceEntry<K, V> newFirst = copyEntry(e, newNext);
              newTable.set(newIndex, newFirst);
            }
          }
        }
      }
    }
    table = newTable;
    this.count = newCount;
  }

  boolean replace(K key, int hash, V oldValue, V newValue) {
    lock();
    try {
      preWriteCleanup();

      AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
      int index = hash & (table.length() - 1);
      ReferenceEntry<K, V> first = table.get(index);

      for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
        K entryKey = e.getKey();
        if (e.getHash() == hash && entryKey != null
            && map.keyEquivalence.equivalent(key, entryKey)) {
          // If the value disappeared, this entry is partially collected,
          // and we should pretend like it doesn't exist.
          ValueReference<K, V> valueReference = e.getValueReference();
          V entryValue = valueReference.get();
          if (entryValue == null) {
            if (isCollected(valueReference)) {
              int newCount = this.count - 1;
              ++modCount;
              enqueueNotification(entryKey, hash, entryValue, RemovalCause.COLLECTED);
              ReferenceEntry<K, V> newFirst = removeFromChain(first, e);
              newCount = this.count - 1;
              table.set(index, newFirst);
              this.count = newCount; // write-volatile
            }
            return false;
          }

          if (map.valueEquivalence.equivalent(oldValue, entryValue)) {
            ++modCount;
            enqueueNotification(key, hash, entryValue, RemovalCause.REPLACED);
            setValue(e, newValue);
            return true;
          } else {
            // Mimic
            // "if (map.containsKey(key) && map.get(key).equals(oldValue))..."
            recordLockedRead(e);
            return false;
          }
        }
      }

      return false;
    } finally {
      unlock();
      postWriteCleanup();
    }
  }

  V replace(K key, int hash, V newValue) {
    lock();
    try {
      preWriteCleanup();

      AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
      int index = hash & (table.length() - 1);
      ReferenceEntry<K, V> first = table.get(index);

      for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
        K entryKey = e.getKey();
        if (e.getHash() == hash && entryKey != null
            && map.keyEquivalence.equivalent(key, entryKey)) {
          // If the value disappeared, this entry is partially collected,
          // and we should pretend like it doesn't exist.
          ValueReference<K, V> valueReference = e.getValueReference();
          V entryValue = valueReference.get();
          if (entryValue == null) {
            if (isCollected(valueReference)) {
              int newCount = this.count - 1;
              ++modCount;
              enqueueNotification(entryKey, hash, entryValue, RemovalCause.COLLECTED);
              ReferenceEntry<K, V> newFirst = removeFromChain(first, e);
              newCount = this.count - 1;
              table.set(index, newFirst);
              this.count = newCount; // write-volatile
            }
            return null;
          }

          ++modCount;
          enqueueNotification(key, hash, entryValue, RemovalCause.REPLACED);
          setValue(e, newValue);
          return entryValue;
        }
      }

      return null;
    } finally {
      unlock();
      postWriteCleanup();
    }
  }

  V remove(Object key, int hash) {
    lock();
    try {
      preWriteCleanup();

      int newCount = this.count - 1;
      AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
      int index = hash & (table.length() - 1);
      ReferenceEntry<K, V> first = table.get(index);

      for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
        K entryKey = e.getKey();
        if (e.getHash() == hash && entryKey != null
            && map.keyEquivalence.equivalent(key, entryKey)) {
          ValueReference<K, V> valueReference = e.getValueReference();
          V entryValue = valueReference.get();

          RemovalCause cause;
          if (entryValue != null) {
            cause = RemovalCause.EXPLICIT;
          } else if (isCollected(valueReference)) {
            cause = RemovalCause.COLLECTED;
          } else {
            return null;
          }

          ++modCount;
          enqueueNotification(entryKey, hash, entryValue, cause);
          ReferenceEntry<K, V> newFirst = removeFromChain(first, e);
          newCount = this.count - 1;
          table.set(index, newFirst);
          this.count = newCount; // write-volatile
          return entryValue;
        }
      }

      return null;
    } finally {
      unlock();
      postWriteCleanup();
    }
  }

  boolean remove(Object key, int hash, Object value) {
    lock();
    try {
      preWriteCleanup();

      int newCount = this.count - 1;
      AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
      int index = hash & (table.length() - 1);
      ReferenceEntry<K, V> first = table.get(index);

      for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
        K entryKey = e.getKey();
        if (e.getHash() == hash && entryKey != null
            && map.keyEquivalence.equivalent(key, entryKey)) {
          ValueReference<K, V> valueReference = e.getValueReference();
          V entryValue = valueReference.get();

          RemovalCause cause;
          if (map.valueEquivalence.equivalent(value, entryValue)) {
            cause = RemovalCause.EXPLICIT;
          } else if (isCollected(valueReference)) {
            cause = RemovalCause.COLLECTED;
          } else {
            return false;
          }

          ++modCount;
          enqueueNotification(entryKey, hash, entryValue, cause);
          ReferenceEntry<K, V> newFirst = removeFromChain(first, e);
          newCount = this.count - 1;
          table.set(index, newFirst);
          this.count = newCount; // write-volatile
          return (cause == RemovalCause.EXPLICIT);
        }
      }

      return false;
    } finally {
      unlock();
      postWriteCleanup();
    }
  }

  void clear() {
    if (count != 0) {
      lock();
      try {
        AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
        if (map.removalNotificationQueue != DISCARDING_QUEUE) {
          for (int i = 0; i < table.length(); ++i) {
            for (ReferenceEntry<K, V> e = table.get(i); e != null; e = e.getNext()) {
              // Computing references aren't actually in the map yet.
              if (!e.getValueReference().isComputingReference()) {
                enqueueNotification(e, RemovalCause.EXPLICIT);
              }
            }
          }
        }
        for (int i = 0; i < table.length(); ++i) {
          table.set(i, null);
        }
        clearReferenceQueues();
        evictionQueue.clear();
        expirationQueue.clear();
        readCount.set(0);

        ++modCount;
        count = 0; // write-volatile
      } finally {
        unlock();
        postWriteCleanup();
      }
    }
  }

  /**
   * Removes an entry from within a table. All entries following the removed node can stay, but
   * all preceding ones need to be cloned.
   *
   * <p>This method does not decrement count for the removed entry, but does decrement count for
   * all partially collected entries which are skipped. As such callers which are modifying count
   * must re-read it after calling removeFromChain.
   *
   * @param first the first entry of the table
   * @param entry the entry being removed from the table
   * @return the new first entry for the table
   */
  @GuardedBy("Segment.this")
  ReferenceEntry<K, V> removeFromChain(ReferenceEntry<K, V> first, ReferenceEntry<K, V> entry) {
    evictionQueue.remove(entry);
    expirationQueue.remove(entry);

    int newCount = count;
    ReferenceEntry<K, V> newFirst = entry.getNext();
    for (ReferenceEntry<K, V> e = first; e != entry; e = e.getNext()) {
      if (isCollected(e)) {
        removeCollectedEntry(e);
        newCount--;
      } else {
        newFirst = copyEntry(e, newFirst);
      }
    }
    this.count = newCount;
    return newFirst;
  }

  void removeCollectedEntry(ReferenceEntry<K, V> entry) {
    enqueueNotification(entry, RemovalCause.COLLECTED);
    evictionQueue.remove(entry);
    expirationQueue.remove(entry);
  }

  /**
   * Removes an entry whose key has been garbage collected.
   */
  boolean reclaimKey(ReferenceEntry<K, V> entry, int hash) {
    lock();
    try {
      int newCount = count - 1;
      AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
      int index = hash & (table.length() - 1);
      ReferenceEntry<K, V> first = table.get(index);

      for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
        if (e == entry) {
          ++modCount;
          enqueueNotification(
              e.getKey(), hash, e.getValueReference().get(), RemovalCause.COLLECTED);
          ReferenceEntry<K, V> newFirst = removeFromChain(first, e);
          newCount = this.count - 1;
          table.set(index, newFirst);
          this.count = newCount; // write-volatile
          return true;
        }
      }

      return false;
    } finally {
      unlock();
      postWriteCleanup();
    }
  }

  /**
   * Removes an entry whose value has been garbage collected.
   */
  boolean reclaimValue(K key, int hash, ValueReference<K, V> valueReference) {
    lock();
    try {
      int newCount = this.count - 1;
      AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
      int index = hash & (table.length() - 1);
      ReferenceEntry<K, V> first = table.get(index);

      for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
        K entryKey = e.getKey();
        if (e.getHash() == hash && entryKey != null
            && map.keyEquivalence.equivalent(key, entryKey)) {
          ValueReference<K, V> v = e.getValueReference();
          if (v == valueReference) {
            ++modCount;
            enqueueNotification(key, hash, valueReference.get(), RemovalCause.COLLECTED);
            ReferenceEntry<K, V> newFirst = removeFromChain(first, e);
            newCount = this.count - 1;
            table.set(index, newFirst);
            this.count = newCount; // write-volatile
            return true;
          }
          return false;
        }
      }

      return false;
    } finally {
      unlock();
      if (!isHeldByCurrentThread()) { // don't cleanup inside of put
        postWriteCleanup();
      }
    }
  }

  /**
   * Clears a value that has not yet been set, and thus does not require count to be modified.
   */
  boolean clearValue(K key, int hash, ValueReference<K, V> valueReference) {
    lock();
    try {
      AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
      int index = hash & (table.length() - 1);
      ReferenceEntry<K, V> first = table.get(index);

      for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
        K entryKey = e.getKey();
        if (e.getHash() == hash && entryKey != null
            && map.keyEquivalence.equivalent(key, entryKey)) {
          ValueReference<K, V> v = e.getValueReference();
          if (v == valueReference) {
            ReferenceEntry<K, V> newFirst = removeFromChain(first, e);
            table.set(index, newFirst);
            return true;
          }
          return false;
        }
      }

      return false;
    } finally {
      unlock();
      postWriteCleanup();
    }
  }

  @GuardedBy("Segment.this")
  boolean removeEntry(ReferenceEntry<K, V> entry, int hash, RemovalCause cause) {
    int newCount = this.count - 1;
    AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
    int index = hash & (table.length() - 1);
    ReferenceEntry<K, V> first = table.get(index);

    for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
      if (e == entry) {
        ++modCount;
        enqueueNotification(e.getKey(), hash, e.getValueReference().get(), cause);
        ReferenceEntry<K, V> newFirst = removeFromChain(first, e);
        newCount = this.count - 1;
        table.set(index, newFirst);
        this.count = newCount; // write-volatile
        return true;
      }
    }

    return false;
  }

  /**
   * Returns {@code true} if the entry has been partially collected, meaning that either the key
   * is null, or the value is null and it is not computing.
   */
  boolean isCollected(ReferenceEntry<K, V> entry) {
    if (entry.getKey() == null) {
      return true;
    }
    return isCollected(entry.getValueReference());
  }

  /**
   * Returns {@code true} if the value has been partially collected, meaning that the value is
   * null and it is not computing.
   */
  boolean isCollected(ValueReference<K, V> valueReference) {
    if (valueReference.isComputingReference()) {
      return false;
    }
    return (valueReference.get() == null);
  }

  /**
   * Gets the value from an entry. Returns {@code null} if the entry is invalid,
   * partially-collected, computing, or expired.
   */
  V getLiveValue(ReferenceEntry<K, V> entry) {
    if (entry.getKey() == null) {
      tryDrainReferenceQueues();
      return null;
    }
    V value = entry.getValueReference().get();
    if (value == null) {
      tryDrainReferenceQueues();
      return null;
    }

    if (map.expires() && map.isExpired(entry)) {
      tryExpireEntries();
      return null;
    }
    return value;
  }

  /**
   * Performs routine cleanup following a read. Normally cleanup happens during writes, or from
   * the cleanupExecutor. If cleanup is not observed after a sufficient number of reads, try
   * cleaning up from the read thread.
   */
  void postReadCleanup() {
    if ((readCount.incrementAndGet() & DRAIN_THRESHOLD) == 0) {
      runCleanup();
    }
  }

  /**
   * Performs routine cleanup prior to executing a write. This should be called every time a
   * write thread acquires the segment lock, immediately after acquiring the lock.
   *
   * <p>Post-condition: expireEntries has been run.
   */
  @GuardedBy("Segment.this")
  void preWriteCleanup() {
    runLockedCleanup();
  }

  /**
   * Performs routine cleanup following a write.
   */
  void postWriteCleanup() {
    runUnlockedCleanup();
  }

  void runCleanup() {
    runLockedCleanup();
    runUnlockedCleanup();
  }

  void runLockedCleanup() {
    if (tryLock()) {
      try {
        drainReferenceQueues();
        expireEntries(); // calls drainRecencyQueue
        readCount.set(0);
      } finally {
        unlock();
      }
    }
  }

  void runUnlockedCleanup() {
    // locked cleanup may generate notifications we can send unlocked
    if (!isHeldByCurrentThread()) {
      map.processPendingNotifications();
    }
  }

} enum Strength {
  /*
   * TODO(kevinb): If we strongly reference the value and aren't computing, we needn't wrap the
   * value. This could save ~8 bytes per entry.
   */

  STRONG {
    @Override
    <K, V> ValueReference<K, V> referenceValue(
        Segment<K, V> segment, ReferenceEntry<K, V> entry, V value) {
      return new StrongValueReference<K, V>(value);
    }

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

  SOFT {
    @Override
    <K, V> ValueReference<K, V> referenceValue(
        Segment<K, V> segment, ReferenceEntry<K, V> entry, V value) {
      return new SoftValueReference<K, V>(segment.valueReferenceQueue, value, entry);
    }

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

  WEAK {
    @Override
    <K, V> ValueReference<K, V> referenceValue(
        Segment<K, V> segment, ReferenceEntry<K, V> entry, V value) {
      return new WeakValueReference<K, V>(segment.valueReferenceQueue, value, entry);
    }

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

  /**
   * Creates a reference for the given value according to this value strength.
   */
  abstract <K, V> ValueReference<K, V> referenceValue(
      Segment<K, V> segment, ReferenceEntry<K, V> entry, V value);

  /**
   * Returns the default equivalence strategy used to compare and hash keys or values referenced
   * at this strength. This strategy will be used unless the user explicitly specifies an
   * alternate strategy.
   */
  abstract Equivalence<Object> defaultEquivalence();
} interface ValueReference<K, V> {
  /**
   * Gets the value. Does not block or throw exceptions.
   */
  V get();

  /**
   * Waits for a value that may still be computing. Unlike get(), this method can block (in the
   * case of FutureValueReference).
   *
   * @throws ExecutionException if the computing thread throws an exception
   */
  V waitForValue() throws ExecutionException;

  /**
   * Returns the entry associated with this value reference, or {@code null} if this value
   * reference is independent of any entry.
   */
  ReferenceEntry<K, V> getEntry();

  /**
   * Creates a copy of this reference for the given entry.
   */
  ValueReference<K, V> copyFor(ReferenceQueue<V> queue, ReferenceEntry<K, V> entry);

  /**
   * Clears this reference object.
   *
   * @param newValue the new value reference which will replace this one; this is only used during
   *     computation to immediately notify blocked threads of the new value
   */
  void clear(@Nullable ValueReference<K, V> newValue);

  /**
   * Returns {@code true} if the value type is a computing reference (regardless of whether or not
   * computation has completed). This is necessary to distiguish between partially-collected
   * entries and computing entries, which need to be cleaned up differently.
   */
  boolean isComputingReference();
} @Beta
public final class NullPointerTester {

  private final ClassToInstanceMap<Object> defaults =
      MutableClassToInstanceMap.create();
  private final List<Member> ignoredMembers = Lists.newArrayList();

  public NullPointerTester() {
    setCommonDefaults();
  }

  private final void setCommonDefaults() {
    // mutable types
    setDefault(Appendable.class, new StringBuilder());
    setDefault(Throwable.class, new Exception());
  }

  /**
   * Sets a default value that can be used for any parameter of type
   * {@code type}. Returns this object.
   */
  public <T> NullPointerTester setDefault(Class<T> type, T value) {
    defaults.put(type, value);
    return this;
  }

  /**
   * Ignore a member (constructor or method) in testAllXxx methods. Returns
   * this object.
   */
  public NullPointerTester ignore(Member member) {
    ignoredMembers.add(member);
    return this;
  }

  /**
   * Runs {@link #testConstructor} on every constructor in class {@code c} that
   * has at least {@code minimalVisibility}.
   */
  public void testConstructors(Class<?> c, Visibility minimalVisibility) {
    for (Constructor<?> constructor : c.getDeclaredConstructors()) {
      if (minimalVisibility.isVisible(constructor) && !isIgnored(constructor)) {
        testConstructor(constructor);
      }
    }
  }

  /**
   * Runs {@link #testConstructor} on every public constructor in class {@code
   * c}.
   */
  public void testAllPublicConstructors(Class<?> c) {
    testConstructors(c, Visibility.PUBLIC);
  }

  /**
   * Runs {@link #testMethod} on every static method declared in class {@code c}
   * that has at least {@code minimalVisibility}.
   */
  public void testStaticMethods(Class<?> c, Visibility minimalVisibility) {
    for (Method method : c.getDeclaredMethods()) {
      if (minimalVisibility.isVisible(method)
          && isStatic(method)
          && !isIgnored(method)) {
        testMethod(null, method);
      }
    }
  }

  /**
   * Runs {@link #testMethod} on every public static method declared by class
   * {@code c}.
   */
  public void testAllPublicStaticMethods(Class<?> c) {
    testStaticMethods(c, Visibility.PUBLIC);
  }

  /**
   * Runs {@link #testMethod} on every instance method declared by the class
   * of {@code instance} with at least {@code minimalVisibility}.
   */
  public void testInstanceMethods(
      Object instance, Visibility minimalVisibility) {
    Class<?> c = instance.getClass();
    for (Method method : c.getDeclaredMethods()) {
      if (minimalVisibility.isVisible(method)
          && !isStatic(method)
          && !isIgnored(method)) {
        testMethod(instance, method);
      }
    }
  }

  /**
   * Runs {@link #testMethod} on every public instance method declared by the
   * class of {@code instance}.
   */
  public void testAllPublicInstanceMethods(Object instance) {
    testInstanceMethods(instance, Visibility.PUBLIC);
  }

  /**
   * Verifies that {@code method} produces a {@link NullPointerException}
   * or {@link UnsupportedOperationException} whenever <i>any</i> of its
   * non-{@link Nullable} parameters are null.
   *
   * @param instance the instance to invoke {@code method} on, or null if
   *     {@code method} is static
   */
  public void testMethod(Object instance, Method method) {
    Class<?>[] types = method.getParameterTypes();
    for (int nullIndex = 0; nullIndex < types.length; nullIndex++) {
      testMethodParameter(instance, method, nullIndex);
    }
  }

  /**
   * Verifies that {@code ctor} produces a {@link NullPointerException} or
   * {@link UnsupportedOperationException} whenever <i>any</i> of its
   * non-{@link Nullable} parameters are null.
   */
  public void testConstructor(Constructor<?> ctor) {
    Class<?>[] types = ctor.getParameterTypes();
    for (int nullIndex = 0; nullIndex < types.length; nullIndex++) {
      testConstructorParameter(ctor, nullIndex);
    }
  }

  /**
   * Verifies that {@code method} produces a {@link NullPointerException} or
   * {@link UnsupportedOperationException} when the parameter in position {@code
   * paramIndex} is null.  If this parameter is marked {@link Nullable}, this
   * method does nothing.
   *
   * @param instance the instance to invoke {@code method} on, or null if
   *     {@code method} is static
   */
  public void testMethodParameter(Object instance, final Method method,
      int paramIndex) {
    method.setAccessible(true);
    testFunctorParameter(instance, new Functor() {
        @Override public Type[] getParameterTypes() {
          return method.getGenericParameterTypes();
        }
        @Override public Annotation[][] getParameterAnnotations() {
          return method.getParameterAnnotations();
        }
        @Override public void invoke(Object object, Object[] params)
            throws InvocationTargetException, IllegalAccessException {
          method.invoke(object, params);
        }
        @Override public String toString() {
          return method.getName()
              + "(" + Arrays.toString(getParameterTypes()) + ")";
        }
      }, paramIndex, method.getDeclaringClass());
  }

  /**
   * Verifies that {@code ctor} produces a {@link NullPointerException} or
   * {@link UnsupportedOperationException} when the parameter in position {@code
   * paramIndex} is null.  If this parameter is marked {@link Nullable}, this
   * method does nothing.
   */
  public void testConstructorParameter(final Constructor<?> ctor,
      int paramIndex) {
    ctor.setAccessible(true);
    testFunctorParameter(null, new Functor() {
        @Override public Type[] getParameterTypes() {
          return ctor.getGenericParameterTypes();
        }
        @Override public Annotation[][] getParameterAnnotations() {
          return ctor.getParameterAnnotations();
        }
        @Override public void invoke(Object instance, Object[] params)
            throws InvocationTargetException, IllegalAccessException,
            InstantiationException {
          ctor.newInstance(params);
        }
      }, paramIndex, ctor.getDeclaringClass());
  }

  /** Visibility of any method or constructor. */
  public enum Visibility {

    PACKAGE {
      @Override boolean isVisible(int modifiers) {
        return !Modifier.isPrivate(modifiers);
      }
    },

    PROTECTED {
      @Override boolean isVisible(int modifiers) {
        return Modifier.isPublic(modifiers) || Modifier.isProtected(modifiers);
      }
    },

    PUBLIC {
      @Override boolean isVisible(int modifiers) {
        return Modifier.isPublic(modifiers);
      }
    };

    abstract boolean isVisible(int modifiers);

    /**
     * Returns {@code true} if {@code member} is visible under {@code this}
     * visibility.
     */
    final boolean isVisible(Member member) {
      return isVisible(member.getModifiers());
    }
  }

  /**
   * Verifies that {@code func} produces a {@link NullPointerException} or
   * {@link UnsupportedOperationException} when the parameter in position {@code
   * paramIndex} is null.  If this parameter is marked {@link Nullable}, this
   * method does nothing.
   *
   * @param instance the instance to invoke {@code func} on, or null if
   *     {@code func} is static
   */
  private void testFunctorParameter(Object instance, Functor func,
      int paramIndex, Class<?> testedClass) {
    if (parameterIsPrimitiveOrNullable(func, paramIndex)) {
      return; // there's nothing to test
    }
    Object[] params = buildParamList(func, paramIndex);
    try {
      func.invoke(instance, params);
      Assert.fail("No exception thrown from " + func +
          Arrays.toString(params) + " for " + testedClass);
    } catch (InvocationTargetException e) {
      Throwable cause = e.getCause();
      if (cause instanceof NullPointerException ||
          cause instanceof UnsupportedOperationException) {
        return;
      }
      AssertionFailedError error = new AssertionFailedError(
          "wrong exception thrown from " + func + ": " + cause);
      error.initCause(cause);
      throw error;
    } catch (IllegalAccessException e) {
      throw new RuntimeException(e);
    } catch (InstantiationException e) {
      throw new RuntimeException(e);
    }
  }

  private static boolean parameterIsPrimitiveOrNullable(
      Functor func, int paramIndex) {
    if (TypeToken.of(func.getParameterTypes()[paramIndex]).getRawType()
        .isPrimitive()) {
      return true;
    }
    Annotation[] annotations = func.getParameterAnnotations()[paramIndex];
    for (Annotation annotation : annotations) {
      if (annotation instanceof Nullable) {
        return true;
      }
    }
    return false;
  }

  private Object[] buildParamList(Functor func, int indexOfParamToSetToNull) {
    Type[] types = func.getParameterTypes();
    Object[] params = new Object[types.length];

    for (int i = 0; i < types.length; i++) {
      if (i != indexOfParamToSetToNull) {
        TypeToken<?> type = TypeToken.of(types[i]);
        params[i] = getDefaultValue(type);
        if (!parameterIsPrimitiveOrNullable(func, i)) {
          Assert.assertTrue("No default value found for " + type,
              params[i] != null);
        }
      }
    }
    return params;
  }

  private <T> T getDefaultValue(TypeToken<T> type) {
    // We assume that all defaults are generics-safe, even if they aren't,
    // we take the risk.
    @SuppressWarnings("unchecked")
    T defaultValue = (T) defaults.getInstance(type.getRawType());
    if (defaultValue != null) {
      return defaultValue;
    }
    @SuppressWarnings("unchecked") // All null values are generics-safe
    T nullValue = (T) NullValues.get(type.getRawType());
    if (nullValue != null) {
      return nullValue;
    }
    if (type.getRawType() == Class.class) {
      // If parameter is Class<? extends Foo>, we return Foo.class
      @SuppressWarnings("unchecked")
      T defaultClass = (T) getFirstTypeParameter(type.getType()).getRawType();
      return defaultClass;
    }
    if (type.getRawType() == TypeToken.class) {
      // If parameter is TypeToken<? extends Foo>, we return TypeToken<Foo>.
      @SuppressWarnings("unchecked")
      T defaultType = (T) getFirstTypeParameter(type.getType());
      return defaultType;
    }
    if (type.getRawType().isInterface()) {
      return newDefaultReturningProxy(type);
    }
    return null;
  }

  private static TypeToken<?> getFirstTypeParameter(Type type) {
    if (type instanceof ParameterizedType) {
      return TypeToken.of(
          ((ParameterizedType) type).getActualTypeArguments()[0]);
    } else {
      return TypeToken.of(Object.class);
    }
  }

  @SuppressWarnings("unchecked") // T implemented with dynamic proxy.
  private <T> T newDefaultReturningProxy(final TypeToken<T> type) {
    Set<Class<? super T>> interfaceClasses =
        type.getTypes().interfaces().rawTypes();
    return (T) Proxy.newProxyInstance(
        interfaceClasses.iterator().next().getClassLoader(),
        interfaceClasses.toArray(new Class<?>[interfaceClasses.size()]),
        new AbstractInvocationHandler() {
          @Override protected Object handleInvocation(
              Object proxy, Method method, Object[] args) {
            return getDefaultValue(
                type.resolveType(method.getGenericReturnType()));
          }
          @Override public String toString() {
            return "NullPointerTester proxy for " + type;
          }
        });
  }

  private interface Functor {
    Type[] getParameterTypes();
    Annotation[][] getParameterAnnotations();
    void invoke(Object o, Object[] params)
        throws InvocationTargetException, IllegalAccessException,
            InstantiationException;
  }

  private static boolean isStatic(Member member) {
    return Modifier.isStatic(member.getModifiers());
  }

  private boolean isIgnored(Member member) {
    return member.isSynthetic() || ignoredMembers.contains(member);
  }
}
import static com.google.common.collect.Lists.newArrayList;
import static com.google.common.collect.MapMakerInternalMap.DISCARDING_QUEUE;
import static com.google.common.collect.MapMakerInternalMap.DRAIN_THRESHOLD;
import static com.google.common.collect.MapMakerInternalMap.nullEntry;
import static com.google.common.collect.MapMakerInternalMap.unset;
import static java.util.concurrent.TimeUnit.SECONDS;
import com.google.common.base.Equivalence;
import com.google.common.base.Ticker;
import com.google.common.collect.MapMaker.RemovalCause;
import com.google.common.collect.MapMaker.RemovalListener;
import com.google.common.collect.MapMaker.RemovalNotification;
import com.google.common.collect.MapMakerInternalMap.EntryFactory;
import com.google.common.collect.MapMakerInternalMap.ReferenceEntry;
import com.google.common.collect.MapMakerInternalMap.Segment;
import com.google.common.collect.MapMakerInternalMap.Strength;
import com.google.common.collect.MapMakerInternalMap.ValueReference;
import com.google.common.testing.NullPointerTester;
import junit.framework.TestCase;
import java.lang.ref.Reference;
import java.lang.ref.ReferenceQueue;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReferenceArray;
/*
 * Copyright (C) 2011 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.collect;





/**
 * @author Charles Fry
 */
@SuppressWarnings("deprecation") // many tests of deprecated methods
public class MapMakerInternalMapTest extends TestCase {

  static final int SMALL_MAX_SIZE = DRAIN_THRESHOLD * 5;