jdk-sandbox: comparison jdk/src/share/classes/com/sun/beans/util/Cache.java

equal deleted inserted replaced

-:d2bfa69f5523
+:561ed508292b
+/*
+* 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;
+}
+}
+}
+}

changeset 21793	561ed508292b
child 22577	64bb7e55d3c7