src/share/classes/com/sun/beans/util/Cache.java - platform/external/jetbrains/jdk8u_jdk - Git at Google

 /*
  * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License version 2 only, as
  * published by the Free Software Foundation.  Oracle designates this
  * particular file as subject to the "Classpath" exception as provided
  * by Oracle in the LICENSE file that accompanied this code.
  *
  * This code is distributed in the hope that it will be useful, but WITHOUT
  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  * version 2 for more details (a copy is included in the LICENSE file that
  * accompanied this code).
  *
  * You should have received a copy of the GNU General Public License version
  * 2 along with this work; if not, write to the Free Software Foundation,
  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  *
  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  * or visit www.oracle.com if you need additional information or have any
  * questions.
  */
 package com.sun.beans.util;

 import java.lang.ref.ReferenceQueue;
 import java.lang.ref.SoftReference;
 import java.lang.ref.WeakReference;
 import java.util.Objects;

 /**
  * Hash table based implementation of the cache,
  * which allows to use weak or soft references for keys and values.
  * An entry in a {@code Cache} will automatically be removed
  * when its key or value is no longer in ordinary use.
  *
  * @author Sergey Malenkov
  * @since 1.8
  */
 public abstract class Cache<K,V> {
     private static final int MAXIMUM_CAPACITY = 1 << 30; // maximum capacity MUST be a power of two <= 1<<30

     private final boolean identity; // defines whether the identity comparison is used
     private final Kind keyKind; // a reference kind for the cache keys
     private final Kind valueKind; // a reference kind for the cache values

     private final ReferenceQueue<Object> queue = new ReferenceQueue<>(); // queue for references to remove

     private volatile CacheEntry<K,V>[] table = newTable(1 << 3); // table's length MUST be a power of two
     private int threshold = 6; // the next size value at which to resize
     private int size; // the number of key-value mappings contained in this map

     /**
      * Creates a corresponding value for the specified key.
      *
      * @param key a key that can be used to create a value
      * @return a corresponding value for the specified key
      */
     public abstract V create(K key);

     /**
      * Constructs an empty {@code Cache}.
      * The default initial capacity is 8.
      * The default load factor is 0.75.
      *
      * @param keyKind   a reference kind for keys
      * @param valueKind a reference kind for values
      *
      * @throws NullPointerException if {@code keyKind} or {@code valueKind} are {@code null}
      */
     public Cache(Kind keyKind, Kind valueKind) {
         this(keyKind, valueKind, false);
     }

     /**
      * Constructs an empty {@code Cache}
      * with the specified comparison method.
      * The default initial capacity is 8.
      * The default load factor is 0.75.
      *
      * @param keyKind   a reference kind for keys
      * @param valueKind a reference kind for values
      * @param identity  defines whether reference-equality
      *                  is used in place of object-equality
      *
      * @throws NullPointerException if {@code keyKind} or {@code valueKind} are {@code null}
      */
     public Cache(Kind keyKind, Kind valueKind, boolean identity) {
         Objects.requireNonNull(keyKind, "keyKind");
         Objects.requireNonNull(valueKind, "valueKind");
         this.keyKind = keyKind;
         this.valueKind = valueKind;
         this.identity = identity;
     }

     /**
      * Returns the value to which the specified key is mapped,
      * or {@code null} if there is no mapping for the key.
      *
      * @param key the key whose cached value is to be returned
      * @return a value to which the specified key is mapped,
      *         or {@code null} if there is no mapping for {@code key}
      *
      * @throws NullPointerException if {@code key} is {@code null}
      *                              or corresponding value is {@code null}
      */
     public final V get(K key) {
         Objects.requireNonNull(key, "key");
         removeStaleEntries();
         int hash = hash(key);
         // unsynchronized search improves performance
         // the null value does not mean that there are no needed entry
         CacheEntry<K,V>[] table = this.table; // unsynchronized access
         V current = getEntryValue(key, hash, table[index(hash, table)]);
         if (current != null) {
             return current;
         }
         synchronized (this.queue) {
             // synchronized search improves stability
             // we must create and add new value if there are no needed entry
             current = getEntryValue(key, hash, this.table[index(hash, this.table)]);
             if (current != null) {
                 return current;
             }
             V value = create(key);
             Objects.requireNonNull(value, "value");
             int index = index(hash, this.table);
             this.table[index] = new CacheEntry<>(hash, key, value, this.table[index]);
             if (++this.size >= this.threshold) {
                 if (this.table.length == MAXIMUM_CAPACITY) {
                     this.threshold = Integer.MAX_VALUE;
                 } else {
                     removeStaleEntries();
                     table = newTable(this.table.length << 1);
                     transfer(this.table, table);
                     // If ignoring null elements and processing ref queue caused massive
                     // shrinkage, then restore old table.  This should be rare, but avoids
                     // unbounded expansion of garbage-filled tables.
                     if (this.size >= this.threshold / 2) {
                         this.table = table;
                         this.threshold <<= 1;
                     } else {
                         transfer(table, this.table);
                     }
                     removeStaleEntries();
                 }
             }
             return value;
         }
     }

     /**
      * Removes the cached value that corresponds to the specified key.
      *
      * @param key the key whose mapping is to be removed from this cache
      */
     public final void remove(K key) {
         if (key != null) {
             synchronized (this.queue) {
                 removeStaleEntries();
                 int hash = hash(key);
                 int index = index(hash, this.table);
                 CacheEntry<K,V> prev = this.table[index];
                 CacheEntry<K,V> entry = prev;
                 while (entry != null) {
                     CacheEntry<K,V> next = entry.next;
                     if (entry.matches(hash, key)) {
                         if (entry == prev) {
                             this.table[index] = next;
                         } else {
                             prev.next = next;
                         }
                         entry.unlink();
                         break;
                     }
                     prev = entry;
                     entry = next;
                 }
             }
         }
     }

     /**
      * Removes all of the mappings from this cache.
      * It will be empty after this call returns.
      */
     public final void clear() {
         synchronized (this.queue) {
             int index = this.table.length;
             while (0 < index--) {
                 CacheEntry<K,V> entry = this.table[index];
                 while (entry != null) {
                     CacheEntry<K,V> next = entry.next;
                     entry.unlink();
                     entry = next;
                 }
                 this.table[index] = null;
             }
             while (null != this.queue.poll()) {
                 // Clear out the reference queue.
             }
         }
     }

     /**
      * Retrieves object hash code and applies a supplemental hash function
      * to the result hash, which defends against poor quality hash functions.
      * This is critical because {@code Cache} uses power-of-two length hash tables,
      * that otherwise encounter collisions for hashCodes that do not differ
      * in lower bits.
      *
      * @param key the object which hash code is to be calculated
      * @return a hash code value for the specified object
      */
     private int hash(Object key) {
         if (this.identity) {
             int hash = System.identityHashCode(key);
             return (hash << 1) - (hash << 8);
         }
         int hash = key.hashCode();
         // This function ensures that hashCodes that differ only by
         // constant multiples at each bit position have a bounded
         // number of collisions (approximately 8 at default load factor).
         hash ^= (hash >>> 20) ^ (hash >>> 12);
         return hash ^ (hash >>> 7) ^ (hash >>> 4);
     }

     /**
      * Returns index of the specified hash code in the given table.
      * Note that the table size must be a power of two.
      *
      * @param hash  the hash code
      * @param table the table
      * @return an index of the specified hash code in the given table
      */
     private static int index(int hash, Object[] table) {
         return hash & (table.length - 1);
     }

     /**
      * Creates a new array for the cache entries.
      *
      * @param size requested capacity MUST be a power of two
      * @return a new array for the cache entries
      */
     @SuppressWarnings("unchecked")
     private CacheEntry<K,V>[] newTable(int size) {
         return (CacheEntry<K,V>[]) new CacheEntry[size];
     }

     private V getEntryValue(K key, int hash, CacheEntry<K,V> entry) {
         while (entry != null) {
             if (entry.matches(hash, key)) {
                 return entry.value.getReferent();
             }
             entry = entry.next;
         }
         return null;
     }

     private void removeStaleEntries() {
         Object reference = this.queue.poll();
         if (reference != null) {
             synchronized (this.queue) {
                 do {
                     if (reference instanceof Ref) {
                         Ref ref = (Ref) reference;
                         @SuppressWarnings("unchecked")
                         CacheEntry<K,V> owner = (CacheEntry<K,V>) ref.getOwner();
                         if (owner != null) {
                             int index = index(owner.hash, this.table);
                             CacheEntry<K,V> prev = this.table[index];
                             CacheEntry<K,V> entry = prev;
                             while (entry != null) {
                                 CacheEntry<K,V> next = entry.next;
                                 if (entry == owner) {
                                     if (entry == prev) {
                                         this.table[index] = next;
                                     } else {
                                         prev.next = next;
                                     }
                                     entry.unlink();
                                     break;
                                 }
                                 prev = entry;
                                 entry = next;
                             }
                         }
                     }
                     reference = this.queue.poll();
                 }
                 while (reference != null);
             }
         }
     }

     private void transfer(CacheEntry<K,V>[] oldTable, CacheEntry<K,V>[] newTable) {
         int oldIndex = oldTable.length;
         while (0 < oldIndex--) {
             CacheEntry<K,V> entry = oldTable[oldIndex];
             oldTable[oldIndex] = null;
             while (entry != null) {
                 CacheEntry<K,V> next = entry.next;
                 if (entry.key.isStale() || entry.value.isStale()) {
                     entry.unlink();
                 } else {
                     int newIndex = index(entry.hash, newTable);
                     entry.next = newTable[newIndex];
                     newTable[newIndex] = entry;
                 }
                 entry = next;
             }
         }
     }

     /**
      * Represents a cache entry (key-value pair).
      */
     private final class CacheEntry<K,V> {
         private final int hash;
         private final Ref<K> key;
         private final Ref<V> value;
         private volatile CacheEntry<K,V> next;

         /**
          * Constructs an entry for the cache.
          *
          * @param hash  the hash code calculated for the entry key
          * @param key   the entry key
          * @param value the initial value of the entry
          * @param next  the next entry in a chain
          */
         private CacheEntry(int hash, K key, V value, CacheEntry<K,V> next) {
             this.hash = hash;
             this.key = Cache.this.keyKind.create(this, key, Cache.this.queue);
             this.value = Cache.this.valueKind.create(this, value, Cache.this.queue);
             this.next = next;
         }

         /**
          * Determines whether the entry has the given key with the given hash code.
          *
          * @param hash   an expected hash code
          * @param object an object to be compared with the entry key
          * @return {@code true} if the entry has the given key with the given hash code;
          *         {@code false} otherwise
          */
         private boolean matches(int hash, Object object) {
             if (this.hash != hash) {
                 return false;
             }
             Object key = this.key.getReferent();
             return (key == object) || !Cache.this.identity && (key != null) && key.equals(object);
         }

         /**
          * Marks the entry as actually removed from the cache.
          */
         private void unlink() {
             this.next = null;
             this.key.removeOwner();
             this.value.removeOwner();
             Cache.this.size--;
         }
     }

     /**
      * Basic interface for references.
      * It defines the operations common for the all kind of references.
      *
      * @param <T> the type of object to refer
      */
     private static interface Ref<T> {
         /**
          * Returns the object that possesses information about the reference.
          *
          * @return the owner of the reference or {@code null} if the owner is unknown
          */
         Object getOwner();

         /**
          * Returns the object to refer.
          *
          * @return the referred object or {@code null} if it was collected
          */
         T getReferent();

         /**
          * Determines whether the referred object was taken by the garbage collector or not.
          *
          * @return {@code true} if the referred object was collected
          */
         boolean isStale();

         /**
          * Marks this reference as removed from the cache.
          */
         void removeOwner();
     }

     /**
      * Represents a reference kind.
      */
     public static enum Kind {
         STRONG {
             <T> Ref<T> create(Object owner, T value, ReferenceQueue<? super T> queue) {
                 return new Strong<>(owner, value);
             }
         },
         SOFT {
             <T> Ref<T> create(Object owner, T referent, ReferenceQueue<? super T> queue) {
                 return (referent == null)
                         ? new Strong<>(owner, referent)
                         : new Soft<>(owner, referent, queue);
             }
         },
         WEAK {
             <T> Ref<T> create(Object owner, T referent, ReferenceQueue<? super T> queue) {
                 return (referent == null)
                         ? new Strong<>(owner, referent)
                         : new Weak<>(owner, referent, queue);
             }
         };

         /**
          * Creates a reference to the specified object.
          *
          * @param <T>      the type of object to refer
          * @param owner    the owner of the reference, if needed
          * @param referent the object to refer
          * @param queue    the queue to register the reference with,
          *                 or {@code null} if registration is not required
          * @return the reference to the specified object
          */
         abstract <T> Ref<T> create(Object owner, T referent, ReferenceQueue<? super T> queue);

         /**
          * This is an implementation of the {@link Cache.Ref} interface
          * that uses the strong references that prevent their referents
          * from being made finalizable, finalized, and then reclaimed.
          *
          * @param <T> the type of object to refer
          */
         private static final class Strong<T> implements Ref<T> {
             private Object owner;
             private final T referent;

             /**
              * Creates a strong reference to the specified object.
              *
              * @param owner    the owner of the reference, if needed
              * @param referent the non-null object to refer
              */
             private Strong(Object owner, T referent) {
                 this.owner = owner;
                 this.referent = referent;
             }

             /**
              * Returns the object that possesses information about the reference.
              *
              * @return the owner of the reference or {@code null} if the owner is unknown
              */
             public Object getOwner() {
                 return this.owner;
             }

             /**
              * Returns the object to refer.
              *
              * @return the referred object
              */
             public T getReferent() {
                 return this.referent;
             }

             /**
              * Determines whether the referred object was taken by the garbage collector or not.
              *
              * @return {@code true} if the referred object was collected
              */
             public boolean isStale() {
                 return false;
             }

             /**
              * Marks this reference as removed from the cache.
              */
             public void removeOwner() {
                 this.owner = null;
             }
         }

         /**
          * This is an implementation of the {@link Cache.Ref} interface
          * that uses the soft references that are cleared at the discretion
          * of the garbage collector in response to a memory request.
          *
          * @param <T> the type of object to refer
          * @see java.lang.ref.SoftReference
          */
         private static final class Soft<T> extends SoftReference<T> implements Ref<T> {
             private Object owner;

             /**
              * Creates a soft reference to the specified object.
              *
              * @param owner    the owner of the reference, if needed
              * @param referent the non-null object to refer
              * @param queue    the queue to register the reference with,
              *                 or {@code null} if registration is not required
              */
             private Soft(Object owner, T referent, ReferenceQueue<? super T> queue) {
                 super(referent, queue);
                 this.owner = owner;
             }

             /**
              * Returns the object that possesses information about the reference.
              *
              * @return the owner of the reference or {@code null} if the owner is unknown
              */
             public Object getOwner() {
                 return this.owner;
             }

             /**
              * Returns the object to refer.
              *
              * @return the referred object or {@code null} if it was collected
              */
             public T getReferent() {
                 return get();
             }

             /**
              * Determines whether the referred object was taken by the garbage collector or not.
              *
              * @return {@code true} if the referred object was collected
              */
             public boolean isStale() {
                 return null == get();
             }

             /**
              * Marks this reference as removed from the cache.
              */
             public void removeOwner() {
                 this.owner = null;
             }
         }

         /**
          * This is an implementation of the {@link Cache.Ref} interface
          * that uses the weak references that do not prevent their referents
          * from being made finalizable, finalized, and then reclaimed.
          *
          * @param <T> the type of object to refer
          * @see java.lang.ref.WeakReference
          */
         private static final class Weak<T> extends WeakReference<T> implements Ref<T> {
             private Object owner;

             /**
              * Creates a weak reference to the specified object.
              *
              * @param owner    the owner of the reference, if needed
              * @param referent the non-null object to refer
              * @param queue    the queue to register the reference with,
              *                 or {@code null} if registration is not required
              */
             private Weak(Object owner, T referent, ReferenceQueue<? super T> queue) {
                 super(referent, queue);
                 this.owner = owner;
             }

             /**
              * Returns the object that possesses information about the reference.
              *
              * @return the owner of the reference or {@code null} if the owner is unknown
              */
             public Object getOwner() {
                 return this.owner;
             }

             /**
              * Returns the object to refer.
              *
              * @return the referred object or {@code null} if it was collected
              */
             public T getReferent() {
                 return get();
             }

             /**
              * Determines whether the referred object was taken by the garbage collector or not.
              *
              * @return {@code true} if the referred object was collected
              */
             public boolean isStale() {
                 return null == get();
             }

             /**
              * Marks this reference as removed from the cache.
              */
             public void removeOwner() {
                 this.owner = null;
             }
         }
     }
 }
	/*
	* Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation. Oracle designates this
	* particular file as subject to the "Classpath" exception as provided
	* by Oracle in the LICENSE file that accompanied this code.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/
	package com.sun.beans.util;

	import java.lang.ref.ReferenceQueue;
	import java.lang.ref.SoftReference;
	import java.lang.ref.WeakReference;
	import java.util.Objects;

	/**
	* Hash table based implementation of the cache,
	* which allows to use weak or soft references for keys and values.
	* An entry in a {@code Cache} will automatically be removed
	* when its key or value is no longer in ordinary use.
	*
	* @author Sergey Malenkov
	* @since 1.8
	*/
	public abstract class Cache<K,V> {
	private static final int MAXIMUM_CAPACITY = 1 << 30; // maximum capacity MUST be a power of two <= 1<<30

	private final boolean identity; // defines whether the identity comparison is used
	private final Kind keyKind; // a reference kind for the cache keys
	private final Kind valueKind; // a reference kind for the cache values

	private final ReferenceQueue<Object> queue = new ReferenceQueue<>(); // queue for references to remove

	private volatile CacheEntry<K,V>[] table = newTable(1 << 3); // table's length MUST be a power of two
	private int threshold = 6; // the next size value at which to resize
	private int size; // the number of key-value mappings contained in this map

	/**
	* Creates a corresponding value for the specified key.
	*
	* @param key a key that can be used to create a value
	* @return a corresponding value for the specified key
	*/
	public abstract V create(K key);

	/**
	* Constructs an empty {@code Cache}.
	* The default initial capacity is 8.
	* The default load factor is 0.75.
	*
	* @param keyKind a reference kind for keys
	* @param valueKind a reference kind for values
	*
	* @throws NullPointerException if {@code keyKind} or {@code valueKind} are {@code null}
	*/
	public Cache(Kind keyKind, Kind valueKind) {
	this(keyKind, valueKind, false);
	}

	/**
	* Constructs an empty {@code Cache}
	* with the specified comparison method.
	* The default initial capacity is 8.
	* The default load factor is 0.75.
	*
	* @param keyKind a reference kind for keys
	* @param valueKind a reference kind for values
	* @param identity defines whether reference-equality
	* is used in place of object-equality
	*
	* @throws NullPointerException if {@code keyKind} or {@code valueKind} are {@code null}
	*/
	public Cache(Kind keyKind, Kind valueKind, boolean identity) {
	Objects.requireNonNull(keyKind, "keyKind");
	Objects.requireNonNull(valueKind, "valueKind");
	this.keyKind = keyKind;
	this.valueKind = valueKind;
	this.identity = identity;
	}

	/**
	* Returns the value to which the specified key is mapped,
	* or {@code null} if there is no mapping for the key.
	*
	* @param key the key whose cached value is to be returned
	* @return a value to which the specified key is mapped,
	* or {@code null} if there is no mapping for {@code key}
	*
	* @throws NullPointerException if {@code key} is {@code null}
	* or corresponding value is {@code null}
	*/
	public final V get(K key) {
	Objects.requireNonNull(key, "key");
	removeStaleEntries();
	int hash = hash(key);
	// unsynchronized search improves performance
	// the null value does not mean that there are no needed entry
	CacheEntry<K,V>[] table = this.table; // unsynchronized access
	V current = getEntryValue(key, hash, table[index(hash, table)]);
	if (current != null) {
	return current;
	}
	synchronized (this.queue) {
	// synchronized search improves stability
	// we must create and add new value if there are no needed entry
	current = getEntryValue(key, hash, this.table[index(hash, this.table)]);
	if (current != null) {
	return current;
	}
	V value = create(key);
	Objects.requireNonNull(value, "value");
	int index = index(hash, this.table);
	this.table[index] = new CacheEntry<>(hash, key, value, this.table[index]);
	if (++this.size >= this.threshold) {
	if (this.table.length == MAXIMUM_CAPACITY) {
	this.threshold = Integer.MAX_VALUE;
	} else {
	removeStaleEntries();
	table = newTable(this.table.length << 1);
	transfer(this.table, table);
	// If ignoring null elements and processing ref queue caused massive
	// shrinkage, then restore old table. This should be rare, but avoids
	// unbounded expansion of garbage-filled tables.
	if (this.size >= this.threshold / 2) {
	this.table = table;
	this.threshold <<= 1;
	} else {
	transfer(table, this.table);
	}
	removeStaleEntries();
	}
	}
	return value;
	}
	}

	/**
	* Removes the cached value that corresponds to the specified key.
	*
	* @param key the key whose mapping is to be removed from this cache
	*/
	public final void remove(K key) {
	if (key != null) {
	synchronized (this.queue) {
	removeStaleEntries();
	int hash = hash(key);
	int index = index(hash, this.table);
	CacheEntry<K,V> prev = this.table[index];
	CacheEntry<K,V> entry = prev;
	while (entry != null) {
	CacheEntry<K,V> next = entry.next;
	if (entry.matches(hash, key)) {
	if (entry == prev) {
	this.table[index] = next;
	} else {
	prev.next = next;
	}
	entry.unlink();
	break;
	}
	prev = entry;
	entry = next;
	}
	}
	}
	}

	/**
	* Removes all of the mappings from this cache.
	* It will be empty after this call returns.
	*/
	public final void clear() {
	synchronized (this.queue) {
	int index = this.table.length;
	while (0 < index--) {
	CacheEntry<K,V> entry = this.table[index];
	while (entry != null) {
	CacheEntry<K,V> next = entry.next;
	entry.unlink();
	entry = next;
	}
	this.table[index] = null;
	}
	while (null != this.queue.poll()) {
	// Clear out the reference queue.
	}
	}
	}

	/**
	* Retrieves object hash code and applies a supplemental hash function
	* to the result hash, which defends against poor quality hash functions.
	* This is critical because {@code Cache} uses power-of-two length hash tables,
	* that otherwise encounter collisions for hashCodes that do not differ
	* in lower bits.
	*
	* @param key the object which hash code is to be calculated
	* @return a hash code value for the specified object
	*/
	private int hash(Object key) {
	if (this.identity) {
	int hash = System.identityHashCode(key);
	return (hash << 1) - (hash << 8);
	}
	int hash = key.hashCode();
	// This function ensures that hashCodes that differ only by
	// constant multiples at each bit position have a bounded
	// number of collisions (approximately 8 at default load factor).
	hash ^= (hash >>> 20) ^ (hash >>> 12);
	return hash ^ (hash >>> 7) ^ (hash >>> 4);
	}

	/**
	* Returns index of the specified hash code in the given table.
	* Note that the table size must be a power of two.
	*
	* @param hash the hash code
	* @param table the table
	* @return an index of the specified hash code in the given table
	*/
	private static int index(int hash, Object[] table) {
	return hash & (table.length - 1);
	}

	/**
	* Creates a new array for the cache entries.
	*
	* @param size requested capacity MUST be a power of two
	* @return a new array for the cache entries
	*/
	@SuppressWarnings("unchecked")
	private CacheEntry<K,V>[] newTable(int size) {
	return (CacheEntry<K,V>[]) new CacheEntry[size];
	}

	private V getEntryValue(K key, int hash, CacheEntry<K,V> entry) {
	while (entry != null) {
	if (entry.matches(hash, key)) {
	return entry.value.getReferent();
	}
	entry = entry.next;
	}
	return null;
	}

	private void removeStaleEntries() {
	Object reference = this.queue.poll();
	if (reference != null) {
	synchronized (this.queue) {
	do {
	if (reference instanceof Ref) {
	Ref ref = (Ref) reference;
	@SuppressWarnings("unchecked")
	CacheEntry<K,V> owner = (CacheEntry<K,V>) ref.getOwner();
	if (owner != null) {
	int index = index(owner.hash, this.table);
	CacheEntry<K,V> prev = this.table[index];
	CacheEntry<K,V> entry = prev;
	while (entry != null) {
	CacheEntry<K,V> next = entry.next;
	if (entry == owner) {
	if (entry == prev) {
	this.table[index] = next;
	} else {
	prev.next = next;
	}
	entry.unlink();
	break;
	}
	prev = entry;
	entry = next;
	}
	}
	}
	reference = this.queue.poll();
	}
	while (reference != null);
	}
	}
	}

	private void transfer(CacheEntry<K,V>[] oldTable, CacheEntry<K,V>[] newTable) {
	int oldIndex = oldTable.length;
	while (0 < oldIndex--) {
	CacheEntry<K,V> entry = oldTable[oldIndex];
	oldTable[oldIndex] = null;
	while (entry != null) {
	CacheEntry<K,V> next = entry.next;
	if (entry.key.isStale() \|\| entry.value.isStale()) {
	entry.unlink();
	} else {
	int newIndex = index(entry.hash, newTable);
	entry.next = newTable[newIndex];
	newTable[newIndex] = entry;
	}
	entry = next;
	}
	}
	}

	/**
	* Represents a cache entry (key-value pair).
	*/
	private final class CacheEntry<K,V> {
	private final int hash;
	private final Ref<K> key;
	private final Ref<V> value;
	private volatile CacheEntry<K,V> next;

	/**
	* Constructs an entry for the cache.
	*
	* @param hash the hash code calculated for the entry key
	* @param key the entry key
	* @param value the initial value of the entry
	* @param next the next entry in a chain
	*/
	private CacheEntry(int hash, K key, V value, CacheEntry<K,V> next) {
	this.hash = hash;
	this.key = Cache.this.keyKind.create(this, key, Cache.this.queue);
	this.value = Cache.this.valueKind.create(this, value, Cache.this.queue);
	this.next = next;
	}

	/**
	* Determines whether the entry has the given key with the given hash code.
	*
	* @param hash an expected hash code
	* @param object an object to be compared with the entry key
	* @return {@code true} if the entry has the given key with the given hash code;
	* {@code false} otherwise
	*/
	private boolean matches(int hash, Object object) {
	if (this.hash != hash) {
	return false;
	}
	Object key = this.key.getReferent();
	return (key == object) \|\| !Cache.this.identity && (key != null) && key.equals(object);
	}

	/**
	* Marks the entry as actually removed from the cache.
	*/
	private void unlink() {
	this.next = null;
	this.key.removeOwner();
	this.value.removeOwner();
	Cache.this.size--;
	}
	}

	/**
	* Basic interface for references.
	* It defines the operations common for the all kind of references.
	*
	* @param <T> the type of object to refer
	*/
	private static interface Ref<T> {
	/**
	* Returns the object that possesses information about the reference.
	*
	* @return the owner of the reference or {@code null} if the owner is unknown
	*/
	Object getOwner();

	/**
	* Returns the object to refer.
	*
	* @return the referred object or {@code null} if it was collected
	*/
	T getReferent();

	/**
	* Determines whether the referred object was taken by the garbage collector or not.
	*
	* @return {@code true} if the referred object was collected
	*/
	boolean isStale();

	/**
	* Marks this reference as removed from the cache.
	*/
	void removeOwner();
	}

	/**
	* Represents a reference kind.
	*/
	public static enum Kind {
	STRONG {
	<T> Ref<T> create(Object owner, T value, ReferenceQueue<? super T> queue) {
	return new Strong<>(owner, value);
	}
	},
	SOFT {
	<T> Ref<T> create(Object owner, T referent, ReferenceQueue<? super T> queue) {
	return (referent == null)
	? new Strong<>(owner, referent)
	: new Soft<>(owner, referent, queue);
	}
	},
	WEAK {
	<T> Ref<T> create(Object owner, T referent, ReferenceQueue<? super T> queue) {
	return (referent == null)
	? new Strong<>(owner, referent)
	: new Weak<>(owner, referent, queue);
	}
	};

	/**
	* Creates a reference to the specified object.
	*
	* @param <T> the type of object to refer
	* @param owner the owner of the reference, if needed
	* @param referent the object to refer
	* @param queue the queue to register the reference with,
	* or {@code null} if registration is not required
	* @return the reference to the specified object
	*/
	abstract <T> Ref<T> create(Object owner, T referent, ReferenceQueue<? super T> queue);

	/**
	* This is an implementation of the {@link Cache.Ref} interface
	* that uses the strong references that prevent their referents
	* from being made finalizable, finalized, and then reclaimed.
	*
	* @param <T> the type of object to refer
	*/
	private static final class Strong<T> implements Ref<T> {
	private Object owner;
	private final T referent;

	/**
	* Creates a strong reference to the specified object.
	*
	* @param owner the owner of the reference, if needed
	* @param referent the non-null object to refer
	*/
	private Strong(Object owner, T referent) {
	this.owner = owner;
	this.referent = referent;
	}

	/**
	* Returns the object that possesses information about the reference.
	*
	* @return the owner of the reference or {@code null} if the owner is unknown
	*/
	public Object getOwner() {
	return this.owner;
	}

	/**
	* Returns the object to refer.
	*
	* @return the referred object
	*/
	public T getReferent() {
	return this.referent;
	}

	/**
	* Determines whether the referred object was taken by the garbage collector or not.
	*
	* @return {@code true} if the referred object was collected
	*/
	public boolean isStale() {
	return false;
	}

	/**
	* Marks this reference as removed from the cache.
	*/
	public void removeOwner() {
	this.owner = null;
	}
	}

	/**
	* This is an implementation of the {@link Cache.Ref} interface
	* that uses the soft references that are cleared at the discretion
	* of the garbage collector in response to a memory request.
	*
	* @param <T> the type of object to refer
	* @see java.lang.ref.SoftReference
	*/
	private static final class Soft<T> extends SoftReference<T> implements Ref<T> {
	private Object owner;

	/**
	* Creates a soft reference to the specified object.
	*
	* @param owner the owner of the reference, if needed
	* @param referent the non-null object to refer
	* @param queue the queue to register the reference with,
	* or {@code null} if registration is not required
	*/
	private Soft(Object owner, T referent, ReferenceQueue<? super T> queue) {
	super(referent, queue);
	this.owner = owner;
	}

	/**
	* Returns the object that possesses information about the reference.
	*
	* @return the owner of the reference or {@code null} if the owner is unknown
	*/
	public Object getOwner() {
	return this.owner;
	}

	/**
	* Returns the object to refer.
	*
	* @return the referred object or {@code null} if it was collected
	*/
	public T getReferent() {
	return get();
	}

	/**
	* Determines whether the referred object was taken by the garbage collector or not.
	*
	* @return {@code true} if the referred object was collected
	*/
	public boolean isStale() {
	return null == get();
	}

	/**
	* Marks this reference as removed from the cache.
	*/
	public void removeOwner() {
	this.owner = null;
	}
	}

	/**
	* This is an implementation of the {@link Cache.Ref} interface
	* that uses the weak references that do not prevent their referents
	* from being made finalizable, finalized, and then reclaimed.
	*
	* @param <T> the type of object to refer
	* @see java.lang.ref.WeakReference
	*/
	private static final class Weak<T> extends WeakReference<T> implements Ref<T> {
	private Object owner;

	/**
	* Creates a weak reference to the specified object.
	*
	* @param owner the owner of the reference, if needed
	* @param referent the non-null object to refer
	* @param queue the queue to register the reference with,
	* or {@code null} if registration is not required
	*/
	private Weak(Object owner, T referent, ReferenceQueue<? super T> queue) {
	super(referent, queue);
	this.owner = owner;
	}

	/**
	* Returns the object that possesses information about the reference.
	*
	* @return the owner of the reference or {@code null} if the owner is unknown
	*/
	public Object getOwner() {
	return this.owner;
	}

	/**
	* Returns the object to refer.
	*
	* @return the referred object or {@code null} if it was collected
	*/
	public T getReferent() {
	return get();
	}

	/**
	* Determines whether the referred object was taken by the garbage collector or not.
	*
	* @return {@code true} if the referred object was collected
	*/
	public boolean isStale() {
	return null == get();
	}

	/**
	* Marks this reference as removed from the cache.
	*/
	public void removeOwner() {
	this.owner = null;
	}
	}
	}
	}