/*
 * 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 Cache will automatically be removed when its key or value is no longer in ordinary use.
Author:Sergey Malenkov
Since:1.8
/** * 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.
Params:
  • key – a key that can be used to create a value
Returns:a corresponding value for the specified key
/** * 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 Cache. The default initial capacity is 8. The default load factor is 0.75.
Params:
  • keyKind – a reference kind for keys
  • valueKind – a reference kind for values
Throws:
/** * 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 Cache with the specified comparison method. The default initial capacity is 8. The default load factor is 0.75.
Params:
  • keyKind – a reference kind for keys
  • valueKind – a reference kind for values
  • identity – defines whether reference-equality is used in place of object-equality
Throws:
/** * 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 null if there is no mapping for the key.
Params:
  • key – the key whose cached value is to be returned
Throws:
Returns:a value to which the specified key is mapped, or null if there is no mapping for key
/** * 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.
Params:
  • key – the key whose mapping is to be removed from this cache
/** * 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.
/** * 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 Cache uses power-of-two length hash tables, that otherwise encounter collisions for hashCodes that do not differ in lower bits.
Params:
  • key – the object which hash code is to be calculated
Returns:a hash code value for the specified object
/** * 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.
Params:
  • hash – the hash code
  • table – the table
Returns:an index of the specified hash code in the given table
/** * 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.
Params:
  • size – requested capacity MUST be a power of two
Returns:a new array for the cache entries
/** * 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).
/** * 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.
Params:
  • hash – the hash code calculated for the entry key
  • key – the entry key
  • value – the initial value of the entry
  • next – the next entry in a chain
/** * 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.
Params:
  • hash – an expected hash code
  • object – an object to be compared with the entry key
Returns:true if the entry has the given key with the given hash code; false otherwise
/** * 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.
/** * 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.
Type parameters:
  • <T> – the type of object to refer
/** * 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.
Returns:the owner of the reference or null if the owner is unknown
/** * 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.
Returns:the referred object or null if it was collected
/** * 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.
Returns:true if the referred object was collected
/** * 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.
/** * Marks this reference as removed from the cache. */
void removeOwner(); }
Represents a reference kind.
/** * 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.
Params:
  • owner – the owner of the reference, if needed
  • referent – the object to refer
  • queue – the queue to register the reference with, or null if registration is not required
Type parameters:
  • <T> – the type of object to refer
Returns:the reference to the specified object
/** * 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 Ref interface that uses the strong references that prevent their referents from being made finalizable, finalized, and then reclaimed.
Type parameters:
  • <T> – the type of object to refer
/** * 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.
Params:
  • owner – the owner of the reference, if needed
  • referent – the non-null object to refer
/** * 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.
Returns:the owner of the reference or null if the owner is unknown
/** * 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.
Returns:the referred object
/** * 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.
Returns:true if the referred object was collected
/** * 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.
/** * Marks this reference as removed from the cache. */
public void removeOwner() { this.owner = null; } }
This is an implementation of the Ref interface that uses the soft references that are cleared at the discretion of the garbage collector in response to a memory request.
Type parameters:
  • <T> – the type of object to refer
See Also:
/** * 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.
Params:
  • owner – the owner of the reference, if needed
  • referent – the non-null object to refer
  • queue – the queue to register the reference with, or null if registration is not required
/** * 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.
Returns:the owner of the reference or null if the owner is unknown
/** * 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.
Returns:the referred object or null if it was collected
/** * 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.
Returns:true if the referred object was collected
/** * 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.
/** * Marks this reference as removed from the cache. */
public void removeOwner() { this.owner = null; } }
This is an implementation of the Ref interface that uses the weak references that do not prevent their referents from being made finalizable, finalized, and then reclaimed.
Type parameters:
  • <T> – the type of object to refer
See Also:
/** * 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.
Params:
  • owner – the owner of the reference, if needed
  • referent – the non-null object to refer
  • queue – the queue to register the reference with, or null if registration is not required
/** * 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.
Returns:the owner of the reference or null if the owner is unknown
/** * 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.
Returns:the referred object or null if it was collected
/** * 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.
Returns:true if the referred object was collected
/** * 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.
/** * Marks this reference as removed from the cache. */
public void removeOwner() { this.owner = null; } } } }