cache.java

jive Study

     * 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.
     *
     * @param key a unique key for the object being put into cache.
     * @param object the Cacheable object to put into cache.
     */
    public synchronized void add(Object key, Cacheable object) {
        //DEBUG
        //System.err.println("Adding object with key " + key + " to hash " + this);

        //Don't add an object with the same key multiple times.
        if (cachedObjectsHash.containsKey(key)) {
            return;
        }
        int objectSize = object.getSize();
        //If the object is bigger than the entire cache, simply don't add it.
        if (objectSize > maxSize * .90) {
            return;
        }
        size += objectSize;
        CacheObject cacheObject = new CacheObject(object, objectSize);
        cachedObjectsHash.put(key, cacheObject);
        //Make an entry into the cache order list.
        LinkedListNode lastAccessedNode = lastAccessedList.addFirst(key);
        //Store the cache order list entry so that we can get back to it
        //during later lookups.
        cacheObject.lastAccessedListNode = lastAccessedNode;
        //Add the object to the age list
        LinkedListNode ageNode = ageList.addFirst(key);
        //We make an explicit call to currentTimeMillis() so that total accuracy
        //of lifetime calculations is better than one second.
        ageNode.timestamp = System.currentTimeMillis();
        cacheObject.ageListNode = ageNode;

        //If cache is too full, remove least used cache entries until it is
        //not too full.
        cullCache();
    }

    /**
     * Gets an object from cache. This method will return null under two
     * conditions:<ul>
     *    <li>The object referenced by the key was never added to cache.
     *    <li>The object referenced by the key has expired from cache.</ul>
     *
     * @param key the unique key of the object to get.
     * @return the Cacheable object corresponding to unique key.
     */
    public synchronized Cacheable get(Object key) {
        //First, clear all entries that have been in cache longer than the
        //maximum defined age.
        deleteExpiredEntries();

        CacheObject cacheObject = (CacheObject)cachedObjectsHash.get(key);
        if (cacheObject == null) {
            //The object didn't exist in cache, so increment cache misses.
            cacheMisses++;
            return null;
        }

        //The object exists in cache, so increment cache hits.
        cacheHits++;

        //Remove the object from it's current place in the cache order list,
        //and re-insert it at the front of the list.
        cacheObject.lastAccessedListNode.remove();
        lastAccessedList.addFirst(cacheObject.lastAccessedListNode);

        return cacheObject.object;
    }

    /**
     * Removes an object from cache.
     *
     * @param key the unique key of the object to remove.
     */
    public synchronized void remove(Object key) {
        //DEBUG
        //System.err.println("Removing object with key: " + key + " from hash " + this);

        CacheObject cacheObject = (CacheObject)cachedObjectsHash.get(key);
        //If the object is not in cache, stop trying to remove it.
        if (cacheObject == null) {
            return;
        }
        //remove from the hash map
        cachedObjectsHash.remove(key);
        //remove from the cache order list
        cacheObject.lastAccessedListNode.remove();
        cacheObject.ageListNode.remove();
        //remove references to linked list nodes
        cacheObject.ageListNode = null;
        cacheObject.lastAccessedListNode = null;
        //removed the object, so subtract its size from the total.
        size -= cacheObject.size;
    }

    /**
     * Clears the cache of all objects. The size of the cache is reset to 0.
     */
    public synchronized void clear() {
        //DEBUG
        //System.err.println("Clearing cache " + this);

        Object [] keys = cachedObjectsHash.keySet().toArray();
        for (int i=0; i<keys.length; i++) {
            remove(keys[i]);
        }

        //Now, reset all containers.
        cachedObjectsHash.clear();
        cachedObjectsHash = new HashMap(103);
        lastAccessedList.clear();
        lastAccessedList = new LinkedList();
        ageList.clear();
        ageList = new LinkedList();

        size = 0;
        cacheHits = 0;
        cacheMisses = 0;
    }

    /**
     * Returns a collection view of the values contained in the cache.
     * The Collection is unmodifiable to prevent cache integrity issues.
     *
     * @return a Collection of the cache entries.
     */
    public Collection values() {
        return Collections.unmodifiableCollection(cachedObjectsHash.values());
    }

    /**
     * Returns the number of cache hits. A cache hit occurs every
     * time the get method is called and the cache contains the requested
     * object.<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.
     *
     * @return the number of cache hits.
     */
    public long getCacheHits() {
        return cacheHits;
    }

    /**
     * Returns the number of cache misses. A cache miss occurs every
     * time the get method is called and the cache does not contain the
     * requested object.<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.
     *
     * @return the number of cache hits.
     */
    public long getCacheMisses() {
        return cacheMisses;
    }

    /**
     * Clears all entries out of cache where the entries are older than the
     * maximum defined age.
     */
    private final void deleteExpiredEntries() {
        //Check if expiration is turned on.
        if (maxLifetime <= 0) {
            return;
        }

        //Remove all old entries. To do this, we remove objects from the end
        //of the linked list until they are no longer too old. We get to avoid
        //any hash lookups or looking at any more objects than is strictly
        //neccessary.
        LinkedListNode node = ageList.getLast();
        //If there are no entries in the age list, return.
        if (node == null) {
            return;
        }

        //Determine the expireTime, which is the moment in time that elements
        //should expire from cache. Then, we can do an easy to check to see
        //if the expire time is greater than the expire time.
        long expireTime = currentTime - maxLifetime;

        while(expireTime > node.timestamp) {
            //DEBUG
            //System.err.println("Object with key " + node.object + " expired.");

            //Remove the object
            remove(node.object);

            //Get the next node.
            node = ageList.getLast();
            //If there are no more entries in the age list, return.
            if (node == null) {
                return;
            }
        }
    }

    /**
     * Removes objects from cache if the cache is too full. "Too full" is
     * defined as within 3% of the maximum cache size. Whenever the cache is
     * is too big, the least frequently used elements are deleted until the
     * cache is at least 10% empty.
     */
    private final void cullCache() {
        //See if the cache size is within 3% of being too big. If so, clean out
        //cache until it's 10% free.
        if (size >= maxSize * .97) {
            //First, delete any old entries to see how much memory that frees.
            deleteExpiredEntries();
            int desiredSize = (int)(maxSize * .90);
            while (size > desiredSize) {
                //Get the key and invoke the remove method on it.
                remove(lastAccessedList.getLast().object);
            }
        }
    }
}