--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/src/share/classes/com/sun/beans/util/Cache.java Tue Nov 26 13:30:44 2013 +0400
@@ -0,0 +1,613 @@
+/*
+ * 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
+ int index = index(hash, this.table);
+ current = getEntryValue(key, hash, this.table[index]);
+ if (current != null) {
+ return current;
+ }
+ V value = create(key);
+ Objects.requireNonNull(value, "value");
+ 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;
+ }
+ }
+ }
+}