/**
 * $RCSfile: Cache.java,v $
 * $Revision: 1.1.1.1 $
 * $Date: 2002/09/09 13:51:09 $
 *
 * New Jive  from Jdon.com.
 *
 * This software is the proprietary information of CoolServlets, Inc.
 * Use is subject to license terms.
 */

package com.jivesoftware.util;

import java.util.*;
import com.jivesoftware.util.LinkedList;

/**
 * General purpose cache implementation. It stores objects associated with
 * unique keys in memory for fast access. All objects added to the cache must
 * implement the Cacheable interface, which requires objects to know their
 * size in memory. This restrictions allows the cache to never grow larger
 * than a specified amount.<p>
 *
 * If the cache does grow too large, objects will be removed such that those
 * that are accessed least frequently are removed first. Because expiration
 * happens automatically, the cache makes <b>no</b> gaurantee as to how long
 * an object will remain in cache after it is put in. The cache will return
 * null if the requested object is not found.<p>
 *
 * Optionally, a maximum lifetime for all objects can be specified. In that
 * case, objects will be deleted from cache after that amount of time, even
 * if they are frequently accessed. This feature is useful if objects put in
 * cache represent data that should be periodically refreshed; for example,
 * information from a database.<p>
 *
 * Cache is optimized for fast data access. The getObject() method has 0(n)
 * performance regardless of cache size. The other cache operations also
 * perform quite fast.<p>
 *
 * Cache objects are thread safe.<p>
 *
 * The algorithm for cache is as follows: a HashMap is maintained for fast
 * object lookup. Two linked lists are maintained: one keeps objects in the
 * order they are accessed from cache, the other keeps objects in the order
 * they were originally added to cache. When objects are added to cache, they
 * are first wrapped by a CacheObject which maintains the following pieces
 * of information:<ul>
 *    <li> The size of the object (in bytes).
 *    <li> A pointer to the node in the linked list that maintains accessed
 *         order for the object. Keeping a reference to the node lets us avoid
 *         linear scans of the linked list.
 *    <li> A pointer to the node in the linked list that maintains the age
 *         of the object in cache. Keeping a reference to the node lets us avoid
 *         linear scans of the linked list.</ul>
 *
 * To get an object from cache, a hash lookup is performed to get a reference
 * to the CacheObject that wraps the real object we are looking for.
 * The object is subsequently moved to the front of the accessed linked list
 * and any necessary cache cleanups are performed. Cache deletion and expiration
 * is performed as needed.
 *
 * @see Cacheable
 */
public class Cache implements Cacheable {

    /**
     * One of the major potential bottlenecks of the cache is performing
     * System.currentTimeMillis() for every cache get operation. Instead,
     * we maintain a global timestamp that gets updated once a second. This
     * means that cache expirations can be no more than one second accurate.
     */
    protected static long currentTime = CacheTimer.currentTime;

    /**
     * Maintains the hash of cached objects. Hashing provides the best
     * performance for fast lookups.
     */
    protected HashMap cachedObjectsHash;

    /**
     * Linked list to maintain order that cache objects are accessed
     * in, most used to least used.
     */
    protected LinkedList lastAccessedList;

    /**
     * Linked list to maintain time that cache objects were initially added
     * to the cache, most recently added to oldest added.
     */
    protected LinkedList ageList;

   /**
    * Maximum size in bytes that the cache can grow to. Default
    * maximum size is 128 K.
    */
    protected int maxSize =  128 * 1024;

    /**
     * Maintains the current size of the cache in bytes.
     */
    protected int size = 0;

    /**
     * Maximum length of time objects can exist in cache before expiring.
     * Default is that objects have no maximum lifetime.
     */
    protected long maxLifetime = -1;

    /**
     * Maintain the number of cache hits and misses. A cache hit occurs every
     * time the get method is called and the cache contains the requested
     * object. A cache miss represents the opposite occurence.<p>
     *
     * Keeping track of cache hits and misses lets one measure how efficient
     * the cache is; the higher the percentage of hits, the more efficient.
     */
    protected long cacheHits, cacheMisses = 0L;

    /**
     * Create a new cache with default values. Default cache size is 128K with
     * no maximum lifetime.
     */
    public Cache() {
        // Our primary data structure is a hash map. The default capacity of 11
        // is too small in almost all cases, so we set it bigger.
        cachedObjectsHash = new HashMap(103);

        lastAccessedList = new LinkedList();
        ageList = new LinkedList();
    }

    /**
     * Create a new cache and specify the maximum size for the cache in bytes.
     * Items added to the cache will have no maximum lifetime.
     *
     * @param maxSize the maximum size of the cache in bytes.
     */
    public Cache(int maxSize) {
        this();
        this.maxSize = maxSize;
    }

    /**
     * Create a new cache and specify the maximum lifetime of objects. The
     * time should be specified in milleseconds. The minimum lifetime of any
     * cache object is 1000 milleseconds (1 second). Additionally, cache
     * expirations have a 1000 millesecond resolution, which means that all
     * objects are guaranteed to be expired within 1000 milliseconds of their
     * maximum lifetime.
     *
     * @param maxLifetime the maximum amount of time objects can exist in
     *    cache before being deleted.
     */
    public Cache(long maxLifetime) {
        this();
        this.maxLifetime = maxLifetime;
    }

    /**
     * Create a new cache and specify the maximum size of for the cache in
     * bytes, and the maximum lifetime of objects.
     *
     * @param maxSize the maximum size of the cache in bytes.
     * @param maxLifetime the maximum amount of time objects can exist in
     *    cache before being deleted.
     */
    public Cache(int maxSize, long maxLifetime) {
        this();
        this.maxSize = maxSize;
        this.maxLifetime = maxLifetime;
    }

    /**
     * Returns the current size of the cache in bytes.
     *
     * @return the size of the cache in bytes.
     */
    public int getSize() {
        return size;
    }

    /**
     * Returns the maximum size of the cache in bytes. If the cache grows too
     * large, the least frequently used items will automatically be deleted so
     * that the cache size doesn't exceed the maximum.
     *
     * @return the maximum size of the cache in bytes.
     */
    public int getMaxSize() {
        return maxSize;
    }

    /**
     * Sets the maximum size of the cache in bytes. If the cache grows too
     * large, the least frequently used items will automatically be deleted so
     * that the cache size doesn't exceed the maximum.
     *
     * @param maxSize the maximum size of the cache in bytes.
     */
    public void setMaxSize(int maxSize) {
        this.maxSize = maxSize;
        // It's possible that the new max size is smaller than our current cache
        // size. If so, we need to delete infrequently used items.
        cullCache();
    }

    /**
     * Returns the number of objects in the cache.
     *
     * @return the number of objects in the cache.
     */
    public synchronized int getNumElements() {
        return cachedObjectsHash.size();
    }

    /**
     * Adds a new Cacheable object to the cache. The key must be unique.
     *