| /* |
| * 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; |
| } |
| } |
| } |
| } |