Cache.java

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