/*

    * Copyright (C) 2009 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;

  import static com.google.common.base.Preconditions.checkNotNull;

  import static com.google.common.collect.CollectPreconditions.checkRemove;

  import com.google.common.annotations.VisibleForTesting;

  import com.google.common.base.Equivalence;

  import com.google.common.base.Ticker;

  import com.google.common.collect.GenericMapMaker.NullListener;

  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.primitives.Ints;

  import java.io.IOException;

  import java.io.ObjectInputStream;

  import java.io.ObjectOutputStream;

  import java.io.Serializable;

  import java.lang.ref.Reference;

  import java.lang.ref.ReferenceQueue;

  import java.lang.ref.SoftReference;

  import java.lang.ref.WeakReference;

  import java.util.AbstractCollection;

  import java.util.AbstractMap;

  import java.util.AbstractQueue;

  import java.util.AbstractSet;

  import java.util.Collection;

  import java.util.Iterator;

  import java.util.Map;

  import java.util.NoSuchElementException;

  import java.util.Queue;

  import java.util.Set;

  import java.util.concurrent.CancellationException;

  import java.util.concurrent.ConcurrentLinkedQueue;

  import java.util.concurrent.ConcurrentMap;

  import java.util.concurrent.ExecutionException;

  import java.util.concurrent.TimeUnit;

  import java.util.concurrent.atomic.AtomicInteger;

  import java.util.concurrent.atomic.AtomicReferenceArray;

  import java.util.concurrent.locks.ReentrantLock;

  import java.util.logging.Level;

  import java.util.logging.Logger;

  import  javax.annotation.Nullable;

  import  javax.annotation.concurrent.GuardedBy;

  class MapMakerInternalMap<K, V>

      extends AbstractMap<K, V> implements ConcurrentMap<K, V>, Serializable {

    /*

     * The basic strategy is to subdivide the table among Segments, each of which itself is a

     * concurrently readable hash table. The map supports non-blocking reads and concurrent writes

     * across different segments.

     *

     * If a maximum size is specified, a best-effort bounding is performed per segment, using a

     * page-replacement algorithm to determine which entries to evict when the capacity has been

     * exceeded.

     *

     * The page replacement algorithm's data structures are kept casually consistent with the map. The

     * ordering of writes to a segment is sequentially consistent. An update to the map and recording

     * of reads may not be immediately reflected on the algorithm'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 operation without enforcing the capacity constraint.

     *

     * This implementation uses a per-segment queue to record a memento of the additions, removals,

     * and accesses that were performed on the map. The queue is drained on writes and when it exceeds

     * its capacity threshold.

     *

     * The Least Recently Used page replacement algorithm was chosen due to its simplicity, high hit

     * rate, and ability to be implemented with O(1) time complexity. The initial LRU implementation

     * operates per-segment rather than globally for increased implementation simplicity. We expect

     * the cache hit rate to be similar to that of a global LRU algorithm.

     */

   // Constants

   static final int MAXIMUM_CAPACITY = Ints.MAX_POWER_OF_TWO;

  

   static final int MAX_SEGMENTS = 1 << 16; // slightly conservative

   static final int CONTAINS_VALUE_RETRIES = 3;

  

   static final int DRAIN_THRESHOLD = 0x3F;

  

   // TODO(fry): empirically optimize this

   static final int DRAIN_MAX = 16;

   static final long CLEANUP_EXECUTOR_DELAY_SECS = 60;

   // Fields

   private static final Logger logger = Logger.getLogger(MapMakerInternalMap.class.getName());

  

   final transient int segmentMask;

  

   final transient int segmentShift;

  

   final transient Segment<K, V>[] segments;

  

   final int concurrencyLevel;

  

   final Equivalence<Object> keyEquivalence;

  

   final Equivalence<Object> valueEquivalence;

  

   final Strength keyStrength;

  

   final Strength valueStrength;

  

   final int maximumSize;

  

   final long expireAfterAccessNanos;

  

   final long expireAfterWriteNanos;

  

   // TODO(fry): define a new type which creates event objects and automates the clear logic

   final Queue<RemovalNotification<K, V>> removalNotificationQueue;

  

   final RemovalListener<K, V> removalListener;

  

   final transient EntryFactory entryFactory;

  

   final Ticker ticker;

  

   MapMakerInternalMap(MapMaker builder) {

     concurrencyLevel = Math.min(builder.getConcurrencyLevel(), MAX_SEGMENTS);

     keyStrength = builder.getKeyStrength();

     valueStrength = builder.getValueStrength();

     keyEquivalence = builder.getKeyEquivalence();

     valueEquivalence = valueStrength.defaultEquivalence();

     maximumSize = builder.maximumSize;

     expireAfterAccessNanos = builder.getExpireAfterAccessNanos();

     expireAfterWriteNanos = builder.getExpireAfterWriteNanos();

     entryFactory = EntryFactory.getFactory(keyStrength, expires(), evictsBySize());

     ticker = builder.getTicker();

     removalListener = builder.getRemovalListener();

     removalNotificationQueue = (removalListener == NullListener.INSTANCE)

         ? MapMakerInternalMap.<RemovalNotification<K, V>>discardingQueue()

         : new ConcurrentLinkedQueue<RemovalNotification<K, V>>();

     int initialCapacity = Math.min(builder.getInitialCapacity(), MAXIMUM_CAPACITY);

     if (evictsBySize()) {

       initialCapacity = Math.min(initialCapacity, maximumSize);

     }

     // Find power-of-two sizes best matching arguments. Constraints:

     // (segmentCount <= maximumSize)

     // && (concurrencyLevel > maximumSize || segmentCount > concurrencyLevel)

     int segmentShift = 0;

     int segmentCount = 1;

     while (segmentCount < concurrencyLevel

         && (!evictsBySize() || segmentCount * 2 <= maximumSize)) {

       ++segmentShift;

       segmentCount <<= 1;

     }

     this.segmentShift = 32 - segmentShift;

     segmentMask = segmentCount - 1;

     this.segments = newSegmentArray(segmentCount);

     int segmentCapacity = initialCapacity / segmentCount;

     if (segmentCapacity * segmentCount < initialCapacity) {

       ++segmentCapacity;

     }

     int segmentSize = 1;

     while (segmentSize < segmentCapacity) {

       segmentSize <<= 1;

     }

     if (evictsBySize()) {

       // Ensure sum of segment max sizes = overall max size

       int maximumSegmentSize = maximumSize / segmentCount + 1;

       int remainder = maximumSize % segmentCount;

       for (int i = 0; i < this.segments.length; ++i) {

         if (i == remainder) {

           maximumSegmentSize--;

         }

         this.segments[i] =

             createSegment(segmentSize, maximumSegmentSize);

       }

     } else {

       for (int i = 0; i < this.segments.length; ++i) {

         this.segments[i] =

             createSegment(segmentSize, MapMaker.UNSET_INT);

       }

     }

   }

   boolean evictsBySize() {

     return maximumSize != MapMaker.UNSET_INT;

   }

   boolean expires() {

     return expiresAfterWrite() || expiresAfterAccess();

   }

   boolean expiresAfterWrite() {

     return expireAfterWriteNanos > 0;

   }

   boolean expiresAfterAccess() {

     return expireAfterAccessNanos > 0;

   }

   boolean usesKeyReferences() {

     return keyStrength != Strength.STRONG;

   }

   boolean usesValueReferences() {

     return valueStrength != Strength.STRONG;

   }

   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 Equivalence.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 Equivalence.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 Equivalence.identity();

       }

     };

    

     abstract <K, V> ValueReference<K, V> referenceValue(

         Segment<K, V> segment, ReferenceEntry<K, V> entry, V value);

    

     abstract Equivalence<Object> defaultEquivalence();

   }

  

   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;

       }

     },

     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;

       }

     };

    

     static final int EXPIRABLE_MASK = 1;

     static final int EVICTABLE_MASK = 2;

    

     static final EntryFactory[][] factories = {

       { STRONG, STRONG_EXPIRABLE, STRONG_EVICTABLE, STRONG_EXPIRABLE_EVICTABLE },

       {}, // no support for SOFT keys

       { 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];

     }

    

     abstract <K, V> ReferenceEntry<K, V> newEntry(

         Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next);

    

     @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 ValueReference<K, V> {
    

     V get();

    

     V waitForValue() throws ExecutionException;

    

     ReferenceEntry<K, V> getEntry();

    

     ValueReference<K, V> copyFor(

         ReferenceQueue<V> queue, @Nullable V value, ReferenceEntry<K, V> entry);

    

     void clear(@Nullable ValueReference<K, V> newValue);

    

     boolean isComputingReference();

   }

  

   static final ValueReference<Object, Object> UNSET = new ValueReference<Object, Object>() {

     @Override

     public Object get() {

       return null;

     }

     @Override

     public ReferenceEntry<Object, Object> getEntry() {

       return null;

     }

     @Override

     public ValueReference<Object, Object> copyFor(ReferenceQueue<Object> queue,

         @Nullable Object value, ReferenceEntry<Object, Object> entry) {

       return this;

     }

     @Override

     public boolean isComputingReference() {

       return false;

     }

     @Override

     public Object waitForValue() {

       return null;

     }

     @Override

     public void clear(ValueReference<Object, Object> newValue) {}

   };

  

   @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;

   }

  

   interface ReferenceEntry<K, V> {
    

     ValueReference<K, V> getValueReference();

    

     void setValueReference(ValueReference<K, V> valueReference);

    

     ReferenceEntry<K, V> getNext();

    

     int getHash();

    

     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.

      */

    

     long getExpirationTime();

    

     void setExpirationTime(long time);

    

     ReferenceEntry<K, V> getNextExpirable();

    

     void setNextExpirable(ReferenceEntry<K, V> next);

    

     ReferenceEntry<K, V> getPreviousExpirable();

    

     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.

      */

    

     ReferenceEntry<K, V> getNextEvictable();

    

     void setNextEvictable(ReferenceEntry<K, V> next);

    

     ReferenceEntry<K, V> getPreviousEvictable();

    

     void setPreviousEvictable(ReferenceEntry<K, V> previous);

   }

   private enum NullEntry implements ReferenceEntry<Object, Object> {

     INSTANCE;

     @Override

     public ValueReference<Object, Object> getValueReference() {

       return null;

     }

     @Override

     public void setValueReference(ValueReference<Object, Object> valueReference) {}

     @Override

     public ReferenceEntry<Object, Object> getNext() {

       return null;

     }

     @Override

     public int getHash() {

       return 0;

     }

     @Override

     public Object getKey() {

       return null;

     }

     @Override

     public long getExpirationTime() {

       return 0;

     }

     @Override

     public void setExpirationTime(long time) {}

     @Override

     public ReferenceEntry<Object, Object> getNextExpirable() {

       return this;

     }

     @Override

     public void setNextExpirable(ReferenceEntry<Object, Object> next) {}

     @Override

     public ReferenceEntry<Object, Object> getPreviousExpirable() {

       return this;

     }

     @Override

     public void setPreviousExpirable(ReferenceEntry<Object, Object> previous) {}

     @Override

     public ReferenceEntry<Object, Object> getNextEvictable() {

       return this;

     }

     @Override

     public void setNextEvictable(ReferenceEntry<Object, Object> next) {}

     @Override