Java example source code file (Cache.java)

This example Java source code file (Cache.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

cacheentry, kind, maximum_capacity, must, object, ref, referencequeue, soft, softreference, strong, suppresswarnings, util, weak

The Cache.java Java example source code

/*
 * 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) 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[] 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 create(Object owner, T value, ReferenceQueue queue) {
                return new Strong<>(owner, value);
            }
        },
        SOFT {
            <T> Ref create(Object owner, T referent, ReferenceQueue queue) {
                return (referent == null)
                        ? new Strong<>(owner, referent)
                        : new Soft<>(owner, referent, queue);
            }
        },
        WEAK {
            <T> Ref create(Object owner, T referent, ReferenceQueue 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 create(Object owner, T referent, ReferenceQueue 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 {
            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 implements Ref {
            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 implements Ref {
            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;
            }
        }
    }
}