processing/memory/LruPool.java

/*
 * Copyright (C) 2015 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.camera.processing.memory;

import com.google.common.base.Preconditions;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

import javax.annotation.concurrent.GuardedBy;

/**
 * LruPool that will evict items from the pool after reaching maximum size in
 * order of Least Recently Used (LRU). This code is based on the Android
 * Lru implementation but removes the hard requirement that keys must only
 * exist once. Different values may be returned for the same key, and there is
 * no guarantee that adding and then immediately acquiring the same key will
 * return the same value instance.
 *
 * The size of the pool is generally equal to the number of items, but can be
 * reconfigured by a subclass to be proportional to some other computed value.
 *
 * This class has multiple moving parts and should only be use to track and
 * reuse objects that are expensive to create or re-create.
 *
 * WARNING:
 * {@link #acquire(TKey)} is currently linear time, pending a better
 * implementation.
 *
 * TODO: Build a constant time acquire(TKey) method implementation.
 *
 */
public class LruPool<TKey, TValue> {
    public static class Configuration<TKey, TValue> {
        /**
         * Called for entries that have been evicted or removed. This method is
         * invoked when a value is evicted to make space, but NOT when an item is
         * removed via {@link #acquire}. The default
         * implementation does nothing.
         *
         * <p>The method is called without synchronization: other threads may
         * access the cache while this method is executing.
         */
        void entryEvicted(TKey key, TValue value) { }

        /**
         * Called after a cache miss to compute a value for the corresponding key.
         * Returns the computed value or null if no value can be computed. The
         * default implementation returns null.
         *
         * <p>The method is called without synchronization: other threads may
         * access the cache while this method is executing.
         */
        TValue create(TKey key) {
            return null;
        }

        /**
         * Returns the size of the entry for {@code key} and {@code value} in
         * user-defined units.  The default implementation returns 1 so that size
         * is the number of entries and max size is the maximum number of entries.
         *
         * <p>An entry's size must not change while it is in the cache.
         */
        int sizeOf(TKey key, TValue value) {
            return 1;
        }
    }

    private final Object mLock;

    /**
     * Maintains an ordered list of keys by "most recently added". Duplicate
     * keys can exist in the list.
     */
    @GuardedBy("mLock")
    private final LinkedList<TKey> mLruKeyList;

    /**
     * Maintains individual pools for each distinct key type.
     */
    @GuardedBy("mLock")
    private final HashMap<TKey, Queue<TValue>> mValuePool;
    private final Configuration<TKey, TValue> mConfiguration;

    private final int mMaxSize;

    /**
     * Size may be configured to represent quantities other than the number of
     * items in the pool. By default, it represents the number of items
     * in the pool.
     */
    @GuardedBy("mLock")
    private int mSize;

    /**
     * Creates and sets the size of the Lru Pool
     *
     * @param maxSize Sets the size of the Lru Pool.
     */
    public LruPool(int maxSize) {
        this(maxSize, new Configuration<TKey, TValue>());
    }

    public LruPool(int maxSize, Configuration<TKey, TValue> configuration) {
        Preconditions.checkArgument(maxSize > 0, "maxSize must be > 0.");

        mMaxSize = maxSize;
        mConfiguration = configuration;

        mLock = new Object();
        mLruKeyList = new LinkedList<>();
        mValuePool = new HashMap<>();
    }

    /**
     * Acquire a value from the pool, or attempt to create a new one if the create
     * method is overridden. If an item cannot be retrieved or created, this method
     * will return null.
     *
     * WARNING:
     * This implementation is currently linear time, pending a better
     * implementation.
     *
     * TODO: Build a constant time acquire(TKey) method implementation.
     *
     * @param key the type of object to retrieve from the pool.
     * @return a value or null if none exists or can be created.
     */
    public final TValue acquire(TKey key) {
        Preconditions.checkNotNull(key);

        // We must remove the item we acquire from the list
        TValue value;

        synchronized (mLock) {
            if (mLruKeyList.removeLastOccurrence(key)) {
                value = mValuePool.get(key).remove();
                mSize -= checkedSizeOf(key, value);
            } else {
                value = mConfiguration.create(key);
            }
        }

        return value;
    }

    /**
     * Add a new or previously existing value to the pool. The most recently added
     * item will be placed at the top of the Lru list, and will trim existing items
     * off the list, if the list exceeds the maximum size.
     *
     * @param key the type of object to add to the pool.
     * @param value the object to add into the pool.
     */
    public final void add(TKey key, TValue value) {
        Preconditions.checkNotNull(key);
        Preconditions.checkNotNull(value);

        synchronized (mLock) {
            final Queue<TValue> pool;

            mLruKeyList.push(key);
            if (!mValuePool.containsKey(key)) {
                pool = new LinkedList<>();
                mValuePool.put(key, pool);
            } else {
                pool = mValuePool.get(key);
            }
            pool.add(value);
            mSize += checkedSizeOf(key, value);

            unsafeTrimToSize(mMaxSize);
        }
    }

    /**
     * Remove the oldest entries until the total of remaining entries is at or
     * below the configured size.
     *
     * @param trimToSize the maximum size of the cache before returning. May
     *                   be -1 to evict even 0-sized elements.
     */
    public final void trimToSize(int trimToSize) {
        synchronized (mLock) {
            unsafeTrimToSize(trimToSize);
        }
    }

    /**
     * For pools that do not override {@link Configuration#sizeOf}, this
     * returns the number of items in the pool. For custom sizes, this returns
     * the sum of the sizes of the entries in this pool.
     */
    public final int getSize() {
        synchronized (mLock) {
            return mSize;
        }
    }

    /**
     * For pools that do not override {@link Configuration#sizeOf}, this
     * returns the maximum number of entries in the pool. For all other pools,
     * this returns the maximum sum of the sizes of the entries in this pool.
     */
    public final int getMaxSize() {
        return mMaxSize;
    }

    @GuardedBy("mLock")
    private void unsafeTrimToSize(int trimToSize) {
        while (mSize > trimToSize && !mLruKeyList.isEmpty()) {
            TKey key = mLruKeyList.removeLast();
            if (key == null) {
                break;
            }

            Queue<TValue> pool = mValuePool.get(key);
            TValue value = pool.remove();

            if (pool.size() <= 0) {
                mValuePool.remove(key);
            }

            mSize = mSize - checkedSizeOf(key, value);
            mConfiguration.entryEvicted(key, value);
        }

        if (mSize < 0 || (mLruKeyList.isEmpty() && mSize != 0)) {
            throw new IllegalStateException("LruPool.sizeOf() is reporting "
                  + "inconsistent results!");
        }
    }

    private int checkedSizeOf(TKey key, TValue value) {
        int result = mConfiguration.sizeOf(key, value);
        Preconditions.checkArgument(result >= 0, "Size was < 0.");
        return result;
    }
}