Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
   /*
    * 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.base.Preconditions.checkState;
  
  
  import java.util.Map;
  import java.util.Queue;
  import java.util.Set;
  
The concurrent hash map implementation built by MapMaker.

This implementation is heavily derived from revision 1.96 of ConcurrentHashMap.java.

Author(s):
Bob Lee
Charles Fry
Doug Lea (ConcurrentHashMap)
  
  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
 
  
The maximum capacity, used if a higher value is implicitly specified by either of the constructors with arguments. MUST be a power of two <= 1<<30 to ensure that entries are indexable using ints.
 
   static final int MAXIMUM_CAPACITY = .;

  
The maximum number of segments to allow; used to bound constructor arguments.
 
   static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
 
  
Number of (unsynchronized) retries in the containsValue method.
 
   static final int CONTAINS_VALUE_RETRIES = 3;

  
Number of cache access operations that can be buffered per segment before the cache's recency ordering information is updated. This is used to avoid lock contention by recording a memento of reads and delaying a lock acquisition until the threshold is crossed or a mutation occurs.

This must be a (2^n)-1 as it is used as a mask.

 
   static final int DRAIN_THRESHOLD = 0x3F;

  
Maximum number of entries to be drained in a single cleanup run. This applies independently to the cleanup queue and both reference queues.
 
   // 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());

  
Mask value for indexing into segments. The upper bits of a key's hash code are used to choose the segment.
 
   final transient int segmentMask;

  
Shift value for indexing within segments. Helps prevent entries that end up in the same segment from also ending up in the same bucket.
 
   final transient int segmentShift;

  
The segments, each of which is a specialized hash table.
 
   final transient Segment<K, V>[] segments;

  
The concurrency level.
 
   final int concurrencyLevel;

  
Strategy for comparing keys.
 
Strategy for comparing values.
 
Strategy for referencing keys.
 
   final Strength keyStrength;

  
Strategy for referencing values.
 
   final Strength valueStrength;

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

  
How long after the last access to an entry the map will retain that entry.
 
   final long expireAfterAccessNanos;

  
How long after the last write to an entry the map will retain that entry.
 
   final long expireAfterWriteNanos;

  
Entries waiting to be consumed by the removal listener.
 
   // TODO(fry): define a new type which creates event objects and automates the clear logic
A listener that is invoked when an entry is removed due to expiration or garbage collection of soft/weak entries.
 
   final RemovalListener<K, V> removalListener;

  
Factory used to create new entries.
 
   final transient EntryFactory entryFactory;

  
Measures time in a testable way.
 
   final Ticker ticker;

  
Creates a new, empty map with the specified strategy, initial capacity and concurrency level.
 
   MapMakerInternalMap(MapMaker builder) {
      = Math.min(builder.getConcurrencyLevel(), );
 
      = builder.getKeyStrength();
      = builder.getValueStrength();
 
      = builder.getKeyEquivalence();
 
      = builder.maximumSize;
 
      = EntryFactory.getFactory(expires(), evictsBySize());
      = builder.getTicker();
 
      = builder.getRemovalListener();
         ? MapMakerInternalMap.<RemovalNotification<K, V>>discardingQueue()
         : new ConcurrentLinkedQueue<RemovalNotification<K, V>>();
 
     int initialCapacity = Math.min(builder.getInitialCapacity(), );
     if (evictsBySize()) {
       initialCapacity = Math.min(initialCapacity);
     }
 
     // Find power-of-two sizes best matching arguments. Constraints:
     // (segmentCount <= maximumSize)
     // && (concurrencyLevel > maximumSize || segmentCount > concurrencyLevel)
     int segmentShift = 0;
     int segmentCount = 1;
     while (segmentCount < 
         && (!evictsBySize() || segmentCount * 2 <= )) {
       ++segmentShift;
       segmentCount <<= 1;
     }
     this. = 32 - segmentShift;
      = segmentCount - 1;
 
     this. = 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 =  / segmentCount + 1;
       int remainder =  % segmentCount;
       for (int i = 0; i < this..length; ++i) {
         if (i == remainder) {
           maximumSegmentSize--;
         }
         this.[i] =
             createSegment(segmentSizemaximumSegmentSize);
       }
     } else {
       for (int i = 0; i < this..length; ++i) {
         this.[i] =
             createSegment(segmentSize.);
       }
     }
   }
 
   boolean evictsBySize() {
     return  != .;
   }
 
   boolean expires() {
     return expiresAfterWrite() || expiresAfterAccess();
   }
 
   boolean expiresAfterWrite() {
     return  > 0;
   }
 
   boolean expiresAfterAccess() {
     return  > 0;
   }
 
   boolean usesKeyReferences() {
     return  != .;
   }
 
   boolean usesValueReferences() {
     return  != .;
   }
 
   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> segmentReferenceEntry<K, V> entry, V value) {
         return new StrongValueReference<K, V>(value);
       }
 
       @Override
         return Equivalence.equals();
       }
     },
 
     SOFT {
       @Override
       <K, V> ValueReference<K, V> referenceValue(
           Segment<K, V> segmentReferenceEntry<K, V> entry, V value) {
         return new SoftValueReference<K, V>(segment.valueReferenceQueuevalueentry);
       }
 
       @Override
         return Equivalence.identity();
       }
     },
 
     WEAK {
       @Override
       <K, V> ValueReference<K, V> referenceValue(
           Segment<K, V> segmentReferenceEntry<K, V> entry, V value) {
         return new WeakValueReference<K, V>(segment.valueReferenceQueuevalueentry);
       }
 
       @Override
         return Equivalence.identity();
       }
     };

    
Creates a reference for the given value according to this value strength.
 
     abstract <K, V> ValueReference<K, V> referenceValue(
         Segment<K, V> segmentReferenceEntry<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<ObjectdefaultEquivalence();
   }

  
Creates new entries.
 
   enum EntryFactory {
     STRONG {
       @Override
       <K, V> ReferenceEntry<K, V> newEntry(
           Segment<K, V> segment, K keyint hash, @Nullable ReferenceEntry<K, V> next) {
         return new StrongEntry<K, V>(keyhashnext);
       }
     },
     STRONG_EXPIRABLE {
       @Override
       <K, V> ReferenceEntry<K, V> newEntry(
           Segment<K, V> segment, K keyint hash, @Nullable ReferenceEntry<K, V> next) {
         return new StrongExpirableEntry<K, V>(keyhashnext);
       }
 
       @Override
       <K, V> ReferenceEntry<K, V> copyEntry(
           Segment<K, V> segmentReferenceEntry<K, V> originalReferenceEntry<K, V> newNext) {
         ReferenceEntry<K, V> newEntry = super.copyEntry(segmentoriginalnewNext);
         copyExpirableEntry(originalnewEntry);
         return newEntry;
       }
     },
     STRONG_EVICTABLE {
       @Override
       <K, V> ReferenceEntry<K, V> newEntry(
           Segment<K, V> segment, K keyint hash, @Nullable ReferenceEntry<K, V> next) {
         return new StrongEvictableEntry<K, V>(keyhashnext);
       }
 
       @Override
       <K, V> ReferenceEntry<K, V> copyEntry(
           Segment<K, V> segmentReferenceEntry<K, V> originalReferenceEntry<K, V> newNext) {
         ReferenceEntry<K, V> newEntry = super.copyEntry(segmentoriginalnewNext);
         copyEvictableEntry(originalnewEntry);
         return newEntry;
       }
     },
     STRONG_EXPIRABLE_EVICTABLE {
       @Override
       <K, V> ReferenceEntry<K, V> newEntry(
           Segment<K, V> segment, K keyint hash, @Nullable ReferenceEntry<K, V> next) {
         return new StrongExpirableEvictableEntry<K, V>(keyhashnext);
       }
 
       @Override
       <K, V> ReferenceEntry<K, V> copyEntry(
           Segment<K, V> segmentReferenceEntry<K, V> originalReferenceEntry<K, V> newNext) {
         ReferenceEntry<K, V> newEntry = super.copyEntry(segmentoriginalnewNext);
         copyExpirableEntry(originalnewEntry);
         copyEvictableEntry(originalnewEntry);
         return newEntry;
       }
     },
 
     SOFT {
       @Override
       <K, V> ReferenceEntry<K, V> newEntry(
           Segment<K, V> segment, K keyint hash, @Nullable ReferenceEntry<K, V> next) {
         return new SoftEntry<K, V>(segment.keyReferenceQueuekeyhashnext);
       }
     },
     SOFT_EXPIRABLE {
       @Override
       <K, V> ReferenceEntry<K, V> newEntry(
           Segment<K, V> segment, K keyint hash, @Nullable ReferenceEntry<K, V> next) {
         return new SoftExpirableEntry<K, V>(segment.keyReferenceQueuekeyhashnext);
       }
 
       @Override
       <K, V> ReferenceEntry<K, V> copyEntry(
           Segment<K, V> segmentReferenceEntry<K, V> originalReferenceEntry<K, V> newNext) {
         ReferenceEntry<K, V> newEntry = super.copyEntry(segmentoriginalnewNext);
         copyExpirableEntry(originalnewEntry);
         return newEntry;
       }
     },
     SOFT_EVICTABLE {
       @Override
       <K, V> ReferenceEntry<K, V> newEntry(
           Segment<K, V> segment, K keyint hash, @Nullable ReferenceEntry<K, V> next) {
         return new SoftEvictableEntry<K, V>(segment.keyReferenceQueuekeyhashnext);
       }
 
       @Override
       <K, V> ReferenceEntry<K, V> copyEntry(
           Segment<K, V> segmentReferenceEntry<K, V> originalReferenceEntry<K, V> newNext) {
         ReferenceEntry<K, V> newEntry = super.copyEntry(segmentoriginalnewNext);
         copyEvictableEntry(originalnewEntry);
         return newEntry;
       }
     },
     SOFT_EXPIRABLE_EVICTABLE {
       @Override
       <K, V> ReferenceEntry<K, V> newEntry(
           Segment<K, V> segment, K keyint hash, @Nullable ReferenceEntry<K, V> next) {
         return new SoftExpirableEvictableEntry<K, V>(segment.keyReferenceQueuekeyhashnext);
       }
 
       @Override
       <K, V> ReferenceEntry<K, V> copyEntry(
           Segment<K, V> segmentReferenceEntry<K, V> originalReferenceEntry<K, V> newNext) {
         ReferenceEntry<K, V> newEntry = super.copyEntry(segmentoriginalnewNext);
         copyExpirableEntry(originalnewEntry);
         copyEvictableEntry(originalnewEntry);
         return newEntry;
       }
     },
 
     WEAK {
       @Override
       <K, V> ReferenceEntry<K, V> newEntry(
           Segment<K, V> segment, K keyint hash, @Nullable ReferenceEntry<K, V> next) {
         return new WeakEntry<K, V>(segment.keyReferenceQueuekeyhashnext);
       }
     },
     WEAK_EXPIRABLE {
       @Override
       <K, V> ReferenceEntry<K, V> newEntry(
           Segment<K, V> segment, K keyint hash, @Nullable ReferenceEntry<K, V> next) {
         return new WeakExpirableEntry<K, V>(segment.keyReferenceQueuekeyhashnext);
       }
 
       @Override
       <K, V> ReferenceEntry<K, V> copyEntry(
           Segment<K, V> segmentReferenceEntry<K, V> originalReferenceEntry<K, V> newNext) {
         ReferenceEntry<K, V> newEntry = super.copyEntry(segmentoriginalnewNext);
         copyExpirableEntry(originalnewEntry);
         return newEntry;
       }
     },
     WEAK_EVICTABLE {
       @Override
       <K, V> ReferenceEntry<K, V> newEntry(
           Segment<K, V> segment, K keyint hash, @Nullable ReferenceEntry<K, V> next) {
         return new WeakEvictableEntry<K, V>(segment.keyReferenceQueuekeyhashnext);
       }
 
       @Override
       <K, V> ReferenceEntry<K, V> copyEntry(
           Segment<K, V> segmentReferenceEntry<K, V> originalReferenceEntry<K, V> newNext) {
         ReferenceEntry<K, V> newEntry = super.copyEntry(segmentoriginalnewNext);
         copyEvictableEntry(originalnewEntry);
         return newEntry;
       }
     },
     WEAK_EXPIRABLE_EVICTABLE {
       @Override
       <K, V> ReferenceEntry<K, V> newEntry(
           Segment<K, V> segment, K keyint hash, @Nullable ReferenceEntry<K, V> next) {
         return new WeakExpirableEvictableEntry<K, V>(segment.keyReferenceQueuekeyhashnext);
       }
 
       @Override
       <K, V> ReferenceEntry<K, V> copyEntry(
           Segment<K, V> segmentReferenceEntry<K, V> originalReferenceEntry<K, V> newNext) {
         ReferenceEntry<K, V> newEntry = super.copyEntry(segmentoriginalnewNext);
         copyExpirableEntry(originalnewEntry);
         copyEvictableEntry(originalnewEntry);
         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 = {
     };
 
     static EntryFactory getFactory(Strength keyStrengthboolean expireAfterWrite,
         boolean evictsBySize) {
       int flags = (expireAfterWrite ?  : 0) | (evictsBySize ?  : 0);
       return [keyStrength.ordinal()][flags];
     }

    
Creates a new entry.

Parameters:
segment to create the entry for
key of the entry
hash of the key
next entry in the same bucket
 
     abstract <K, V> ReferenceEntry<K, V> newEntry(
         Segment<K, V> segment, K keyint hash, @Nullable ReferenceEntry<K, V> next);

    
Copies an entry, assigning it a new next entry.

Parameters:
original the entry to copy
newNext entry in the same bucket
 
     @GuardedBy("Segment.this")
     <K, V> ReferenceEntry<K, V> copyEntry(
         Segment<K, V> segmentReferenceEntry<K, V> originalReferenceEntry<K, V> newNext) {
       return newEntry(segmentoriginal.getKey(), original.getHash(), newNext);
     }
 
     @GuardedBy("Segment.this")
     <K, V> void copyExpirableEntry(ReferenceEntry<K, V> originalReferenceEntry<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(newEntryoriginal.getNextExpirable());
 
       nullifyExpirable(original);
     }
 
     @GuardedBy("Segment.this")
     <K, V> void copyEvictableEntry(ReferenceEntry<K, V> originalReferenceEntry<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(newEntryoriginal.getNextEvictable());
 
       nullifyEvictable(original);
     }
   }

  
A reference to a value.
 
   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:
java.util.concurrent.ExecutionException if the computing thread throws an exception
 
     V waitForValue() throws ExecutionException;

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

    
Creates a copy of this reference for the given entry.

value may be null only for a loading reference.

 
     ValueReference<K, V> copyFor(
         ReferenceQueue<V> queue, @Nullable V valueReferenceEntry<K, V> entry);

    
Clears this reference object.

Parameters:
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 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();
   }

  
Placeholder. Indicates that the value hasn't been set yet.
 
   static final ValueReference<ObjectObjectUNSET = new ValueReference<ObjectObject>() {
     @Override
     public Object get() {
       return null;
     }
 
     @Override
     public ReferenceEntry<ObjectObjectgetEntry() {
       return null;
     }
 
     @Override
         @Nullable Object valueReferenceEntry<ObjectObjectentry) {
       return this;
     }
 
     @Override
     public boolean isComputingReference() {
       return false;
     }
 
     @Override
     public Object waitForValue() {
       return null;
     }
 
     @Override
     public void clear(ValueReference<ObjectObjectnewValue) {}
   };

  
Singleton placeholder that indicates a value is being computed.
 
   @SuppressWarnings("unchecked"// impl never uses a parameter or returns any non-null value
   static <K, V> ValueReference<K, V> unset() {
     return (ValueReference<K, V>) ;
   }

  
An entry in a reference map. Entries in the map can be in the following states: Valid: - Live: valid key/value are set - Computing: computation is pending Invalid: - Expired: time expired (key/value may still be set) - Collected: key/value was partially collected, but not yet cleaned up
 
   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);
   }
 
   private enum NullEntry implements ReferenceEntry<ObjectObject> {
     INSTANCE;
 
     @Override
       return null;
     }
 
     @Override
     public void setValueReference(ValueReference<ObjectObjectvalueReference) {}
 
     @Override
     public ReferenceEntry<ObjectObjectgetNext() {
       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<ObjectObjectgetNextExpirable() {
       return this;
     }
 
     @Override
     public void setNextExpirable(ReferenceEntry<ObjectObjectnext) {}
 
     @Override
       return this;
     }
 
     @Override
     public void setPreviousExpirable(ReferenceEntry<ObjectObjectprevious) {}
 
     @Override
     public ReferenceEntry<ObjectObjectgetNextEvictable() {
       return this;
     }
 
     @Override
     public void setNextEvictable(ReferenceEntry<ObjectObjectnext) {}
 
     @Override
       return this;
     }
 
     @Override
     public void setPreviousEvictable(ReferenceEntry<ObjectObjectprevious) {}
   }
 
   abstract static class AbstractReferenceEntry<K, V> implements ReferenceEntry<K, V> {
     @Override
     public ValueReference<K, V> getValueReference() {
       throw new UnsupportedOperationException();
     }
 
     @Override
     public void setValueReference(ValueReference<K, V> valueReference) {
       throw new UnsupportedOperationException();
     }
 
     @Override
     public ReferenceEntry<K, V> getNext() {
       throw new UnsupportedOperationException();
     }
 
     @Override
     public int getHash() {
       throw new UnsupportedOperationException();
     }
 
     @Override
     public K getKey() {
       throw new UnsupportedOperationException();
     }
 
     @Override
     public long getExpirationTime() {
       throw new UnsupportedOperationException();
     }
 
     @Override
     public void setExpirationTime(long time) {
       throw new UnsupportedOperationException();
     }
 
     @Override
     public ReferenceEntry<K, V> getNextExpirable() {
       throw new UnsupportedOperationException();
     }
 
     @Override
     public void setNextExpirable(ReferenceEntry<K, V> next) {
       throw new UnsupportedOperationException();
     }
 
     @Override
     public ReferenceEntry<K, V> getPreviousExpirable() {
       throw new UnsupportedOperationException();
     }
 
     @Override
     public void setPreviousExpirable(ReferenceEntry<K, V> previous) {
       throw new UnsupportedOperationException();
     }
 
     @Override
     public ReferenceEntry<K, V> getNextEvictable() {
       throw new UnsupportedOperationException();
     }
 
     @Override
     public void setNextEvictable(ReferenceEntry<K, V> next) {
       throw new UnsupportedOperationException();
     }
 
     @Override
     public ReferenceEntry<K, V> getPreviousEvictable() {
       throw new UnsupportedOperationException();
     }
 
     @Override
     public void setPreviousEvictable(ReferenceEntry<K, V> previous) {
       throw new UnsupportedOperationException();
     }
   }
 
   @SuppressWarnings("unchecked"// impl never uses a parameter or returns any non-null value
   static <K, V> ReferenceEntry<K, V> nullEntry() {
     return (ReferenceEntry<K, V>) .;
   }
 
   static final Queue<? extends ObjectDISCARDING_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<Objectiterator() {
       return Iterators.emptyIterator();
     }
   };

  
Queue that discards all elements.
 
   @SuppressWarnings("unchecked"// impl never uses a parameter or returns any non-null value
   static <E> Queue<E> discardingQueue() {
     return (Queue;
   }
 
   /*
    * Note: All of this duplicate code sucks, but it saves a lot of memory. If only Java had mixins!
    * To maintain this code, make a change for the strong reference type. Then, cut and paste, and
    * replace "Strong" with "Soft" or "Weak" within the pasted text. The primary difference is that
    * strong entries store the key reference directly while soft and weak entries delegate to their
    * respective superclasses.
    */

  
Used for strongly-referenced keys.
 
   static class StrongEntry<K, V> implements ReferenceEntry<K, V> {
     final K key;
 
     StrongEntry(K keyint hash, @Nullable ReferenceEntry<K, V> next) {
       this. = key;
       this. = hash;
       this. = next;
     }
 
     @Override
     public K getKey() {
       return this.;
     }
 
     // null expiration
 
     @Override
     public long getExpirationTime() {
       throw new UnsupportedOperationException();
     }
 
     @Override
     public void setExpirationTime(long time) {
       throw new UnsupportedOperationException();
     }
 
     @Override
     public ReferenceEntry<K, V> getNextExpirable() {
       throw new UnsupportedOperationException();
     }
 
     @Override
    public void setNextExpirable(ReferenceEntry<K, V> next) {
      throw new UnsupportedOperationException();
    }
    @Override
    public ReferenceEntry<K, V> getPreviousExpirable() {
      throw new UnsupportedOperationException();
    }
    @Override
    public void setPreviousExpirable(ReferenceEntry<K, V> previous) {
      throw new UnsupportedOperationException();
    }
    // null eviction
    @Override
    public ReferenceEntry<K, V> getNextEvictable() {
      throw new UnsupportedOperationException();
    }
    @Override
    public void setNextEvictable(ReferenceEntry<K, V> next) {
      throw new UnsupportedOperationException();
    }
    @Override
    public ReferenceEntry<K, V> getPreviousEvictable() {
      throw new UnsupportedOperationException();
    }
    @Override
    public void setPreviousEvictable(ReferenceEntry<K, V> previous) {
      throw new UnsupportedOperationException();
    }
    // The code below is exactly the same for each entry type.
    final int hash;
    final ReferenceEntry<K, V> next;
    volatile ValueReference<K, V> valueReference = unset();
    @Override
    public ValueReference<K, V> getValueReference() {
      return ;
    }
    @Override
    public void setValueReference(ValueReference<K, V> valueReference) {
      ValueReference<K, V> previous = this.;
      this. = valueReference;
      previous.clear(valueReference);
    }
    @Override
    public int getHash() {
      return ;
    }
    @Override
    public ReferenceEntry<K, V> getNext() {
      return ;
    }
  }
  static final class StrongExpirableEntry<K, V> extends StrongEntry<K, V>
      implements ReferenceEntry<K, V> {
    StrongExpirableEntry(K keyint hash, @Nullable ReferenceEntry<K, V> next) {
      super(keyhashnext);
    }
    // The code below is exactly the same for each expirable entry type.
    volatile long time = .;
    @Override
    public long getExpirationTime() {
      return ;
    }
    @Override
    public void setExpirationTime(long time) {
      this. = time;
    }
    @GuardedBy("Segment.this")
    @Override
    public ReferenceEntry<K, V> getNextExpirable() {
      return ;
    }
    @Override
    public void setNextExpirable(ReferenceEntry<K, V> next) {
      this. = next;
    }
    @GuardedBy("Segment.this")
    @Override
    public ReferenceEntry<K, V> getPreviousExpirable() {
      return ;
    }
    @Override
    public void setPreviousExpirable(ReferenceEntry<K, V> previous) {
      this. = previous;
    }
  }
  static final class StrongEvictableEntry<K, V>
      extends StrongEntry<K, V> implements ReferenceEntry<K, V> {
    StrongEvictableEntry(K keyint hash, @Nullable ReferenceEntry<K, V> next) {
      super(keyhashnext);
    }
    // The code below is exactly the same for each evictable entry type.
    @GuardedBy("Segment.this")
    @Override
    public ReferenceEntry<K, V> getNextEvictable() {
      return ;
    }
    @Override
    public void setNextEvictable(ReferenceEntry<K, V> next) {
      this. = next;
    }
    @GuardedBy("Segment.this")
    @Override
    public ReferenceEntry<K, V> getPreviousEvictable() {
      return ;
    }
    @Override
    public void setPreviousEvictable(ReferenceEntry<K, V> previous) {
      this. = previous;
    }
  }
  static final class StrongExpirableEvictableEntry<K, V>
      extends StrongEntry<K, V> implements ReferenceEntry<K, V> {
    StrongExpirableEvictableEntry(K keyint hash, @Nullable ReferenceEntry<K, V> next) {
      super(keyhashnext);
    }
    // The code below is exactly the same for each expirable entry type.
    volatile long time = .;
    @Override
    public long getExpirationTime() {
      return ;
    }
    @Override
    public void setExpirationTime(long time) {
      this. = time;
    }
    @GuardedBy("Segment.this")
    @Override
    public ReferenceEntry<K, V> getNextExpirable() {
      return ;
    }
    @Override
    public void setNextExpirable(ReferenceEntry<K, V> next) {
      this. = next;
    }
    @GuardedBy("Segment.this")
    @Override
    public ReferenceEntry<K, V> getPreviousExpirable() {
      return ;
    }
    @Override
    public void setPreviousExpirable(ReferenceEntry<K, V> previous) {
      this. = previous;