modules/swfutils/src/java/flash/util/LRUCache.java

/*
 *
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements.  See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You 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 flash.util;

import java.util.HashMap;
import java.util.Set;

/**
 * Caching data structure that uses a Least Recently Used (LRU)
 * algorithm.  This cache has a max size associated with it that is
 * used to determine when objects should be purged from the cache.
 * Once the max size is reached, the least recently used element will
 * be purged.
 * <p>
 * This class is thread-safe.
 */
public abstract class LRUCache extends AbstractCache
{
    private HashMap<Object, LRUListEntry> map;
    private LRUListEntry head;//the MRU element
    private LRUListEntry tail;//the LRU element
    private int maxSize; //the max size of this cache. If this size is exceeded, LRU elements will be purged to free cache space.
    private int purgeSize = 1;//number of objects to purge when the max size is reached.

    /**
     * Create a new LRU cache.
     *
     * @param initialSize the initial size of the IntMap
     * @param maxSize     the maximum number of elements this cache can hold before purging LRU elements.
     */
    public LRUCache(int initialSize, int maxSize)
    {
        this(initialSize, maxSize, 1);
    }

    /**
     * Create a new LRU cache.
     * This constructor takes a purgeSize parameter that is used to increase the number of LRU
     * elements to when the cache exceeds its max size. Increasing the purge size can reduce the
     * overhead of using the cache if the cache size is maxed out frequently.
     *
     * @param initialSize the initial size of the IntMap
     * @param maxSize     the maximum number of elements this cache can hold before purging LRU elements.
     * @param purgeSize   the number of LRU elements to purge once the max size is exceeded.
     */
    public LRUCache(int initialSize, int maxSize, int purgeSize)
    {
        super();
        this.maxSize = maxSize;
        this.purgeSize = purgeSize;
        map = new HashMap<Object, LRUListEntry>(initialSize);
        head = null;
        tail = null;
    }

    /**
     * Retrieve the complete set of entries from this LRUCache.
     *
     * @return a Set of Map.Entry
     */
    public synchronized Set entrySet()
    {
        return map.entrySet();
    }

    /**
     * Retrieve an object from the cache using the specified key.
     * Use of this method will make the retrieved object the
     * most recently used object.
     */
    public Object get(Object key)
    {
        Object value = null;

        synchronized (this)
        {
            //use a fast compare to see if this key matches the head object.
            //This trick improves performance drastically in situations where
            //the same object is looked up consecutively. This trick is especially
            //effective on quoted string keys because the vm optimizes them to use the
            //same memory location and therefore the == operator returns true.
            if (head != null && key == head.key)
            {
                return head.value;
            }

            LRUListEntry entry = map.get(key);

            if (entry != null /* && (value = entry.value) != null */)
            {
                hits++;
                entry.hits++;

                //move this key to the front of the use list
                setMostRecentlyUsed(entry);
                return entry.value;
            }
            else
            {
                // not in cache, go fetch it
                misses++;
                rmStats(entry);
            }
        }

        long before = System.currentTimeMillis();

        // don't hold the lock while fetching
        value = fetch(key);

        int penalty = (int)(System.currentTimeMillis() - before);
        missPenalty += penalty;

        put(key, value);

        return value;
    }

    /**
     * Insert an object into the cache.
     */
    public void put(Object key, Object value)
    {
        //create a new list entry
        LRUListEntry entry = new LRUListEntry();

        //set the entry's value to be the new key.
        entry.value = value;
        entry.key = key;

        synchronized (this)
        {
            //insert the entry into the table
            remove(key);
            map.put(key, entry);

            //move the new entry to the front of the list
            setMostRecentlyUsed(entry);
            if (tail == null)
            {
                tail = entry;
            }

            //purge condition
            if (map.size() > maxSize)
            {
                //purge the LRU elements to free up space for more elements.
                purgeLRUElements();
            }

            rmStats(entry);
        }
    }

    /**
     * Remove an object from the cache.
     */
    public void remove(Object key)
    {
        synchronized (this)
        {
            LRUListEntry entry = map.remove(key);
            if (entry != null)
            {
                if (entry == head)
                {
                    head = entry.next;
                }
                if (entry == tail)
                {
                    tail = entry.prev;
                }
                if (entry.prev != null)
                {
                    entry.prev.next = entry.next;
                    assert (entry.prev.next != entry.prev);
                }
                if (entry.next != null)
                {
                    entry.next.prev = entry.prev;
                    assert (entry.next.prev != entry.next);
                }
            }

            rmStats(entry);
        }
    }

    public void setSize(int size)
    {
//HashMap grows independently, can not control?
    }

    public synchronized void clear()
    {
        map.clear();
        head = null;
        tail = null;
    }

    /**
     * Returns the number of elements currently in the cache.
     */
    public int size()
    {
        int s = map.size();
        LRUListEntry e = head;
        int num = 0;
        while (e != null)
        {
            num += 1;
            e = e.next;
        }
        if (s != num)
        {
            assert false : ("Memory leak in LRUCache!");
        }
        return s;
    }

    /**
     * Returns the number of elements that this cache can hold.
     * Once more than this number of elements is added to the cache,
     * the least recently used element will automatically be removed.
     */
    public int getMaxSize()
    {
        return maxSize;
    }

    /**
     * Returns the number of LRU elements to purge when the max size is reached.
     */
    public int getPurgeSize()
    {
        return purgeSize;
    }

    /**
     * Handler hook to signal subclasses that the LRU element has been purged from the cache.
     * This method is triggered when the cache's max size has been exceeded and the LRU
     * element must be removed from the cache. This method is invoked after the LRU element
     * has been removed from the cache.
     *
     * @param key   the insertion key that was originally used to add value to the cache.
     * @param value the value element bound to the key.
     */
    protected void handleLRUElementPurged(Object key, Object value)
    {
    }

    private void rmStats(LRUListEntry ref)
    {
        if (ref != null)
        {
            hits -= ref.hits;
            misses--;
            if (ref.penalty != -1)
                missPenalty -= ref.penalty;
        }
    }

    /*
     * Remove the least recently used elements to make space for another element.
     * This purge will dump
     */
    private void purgeLRUElements()
    {
        //purge the number of LRU elements specified by the purgeSize.
        for (int i = 0; i < purgeSize && tail != null; i++)
        {
            Object key = tail.key;
            Object value = tail.value;
            remove(tail.key);

            //signal the subclass that the LRU element has been purged.
            handleLRUElementPurged(key, value);
        }
    }


    /*
     * Set the specified entry as the most recently used entry.
     */
    private void setMostRecentlyUsed(LRUListEntry entry)
    {
        if (entry == head) return;

        //replace the current position of the entry with its next entry
        if (entry.prev != null)
        {
            entry.prev.next = entry.next;
            assert (entry.prev.next != entry.prev);
            if (entry == tail)
            {
                tail = entry.prev;
                tail.next = null;
            }
        }

        if (entry.next != null)
        {
            entry.next.prev = entry.prev;
            assert (entry.next.prev != entry.next);
        }

        //set the entry as the head
        entry.prev = null;
        entry.next = head;
        assert (entry.next != entry);
        if (head != null)
        {
            head.prev = entry;
            assert (head.prev != head);
        }
        head = entry;
    }

    /**
     * Linked list element for the LRU list.
     */
    protected class LRUListEntry extends Object
    {
        LRUListEntry next;
        LRUListEntry prev;
        Object value;
        Object key;
        int hits;
        final int penalty = -1;

        public String toString()
        {
            return key + "=" + value;
        }

        public Object getKey()
        {
            return key;
        }

        public Object getValue()
        {
            return value;
        }
    }
}