/*
* Enhydra Java Application Server Project
*
* The contents of this file are subject to the Enhydra Public License
* Version 1.1 (the "License"); you may not use this file except in
* compliance with the License. You may obtain a copy of the License on
* the Enhydra web site ( http://www.enhydra.org/ ).
*
* Software distributed under the License is distributed on an "AS IS"
* basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
* the License for the specific terms governing rights and limitations
* under the License.
*
* The Initial Developer of the Enhydra Application Server is Lutris
* Technologies, Inc. The Enhydra Application Server and portions created
* by Lutris Technologies, Inc. are Copyright Lutris Technologies, Inc.
* All Rights Reserved.
*
* Contributor(s):
*
* $Id: LRUCache.java,v 1.15 2005/06/13 09:26:06 draganr Exp $
*/
package com.lutris.util;
import java.util.Hashtable;
/**
* This class implements a fixed size Least-Recently-Used cache.
* The cache has a maximum size specified when it is created. When
* an item is added to the cache, if the cache is already at the
* maximum size the least recently used item is deleted, then the
* new item is added. <P>
*
* The only two methods that count as "using" the object (for the
* least-recently-used algorithm) are <CODE>add()</CODE> and
* <CODE>get()</CODE>. <P>
*
* The items cached are refered to by keys, just like a Hashtable.
*
* @author Andy John
* @version $Revision: 1.15 $
*/
public class LRUCache {
/*
* Maximum allowed size of the cache.
*/
private int maxSize;
/*
* The current size of the cache.
*/
private int currentSize;
/*
* This hashtable stores all the items, and does all the searching.
*/
private Hashtable cache;
/*
* A linked list of these structs defines the ordering from
* newest to oldest. The nodes are stored in the hashtable, so
* that constant-time access can locate a node.
*/
private class Node {
Node prev, next;
Object key;
Object item;
int size;
}
/*
* The linked list. This is ONLY for keeping an ordering. All
* searching is done via the hashtable. All acceses to this linked
* list are constant-time.
*/
private Node head, tail;
/**
* Create a new, empty cache.
*
* @param maxSize
* The maxmimum size of the items allowed to be in the cache.
* Since the size of an item defaults to 1, this is normally the
* number of items allowed in the cache.
* When this limit is reached, the "oldest" items are deleted to
* make room for the new item, so the total size of the cache
* (the sum of the sizes of all the items it contains)
* does not exceed the specified limit.
*/
public LRUCache(int maxSize) {
this.maxSize = maxSize;
clear();
}
/**
* Returns the total size of the items in the cache.
* If all the items were added with the default size of 1,
* this is the number of items in the cache.
*
* @return
* The sum of the sizes of the items in the cache.
*/
public synchronized int getSize() {
return currentSize;
}
/**
* Returns the maxmimum number of items allowed in the cache.
*
* @return
* The maximum number of items allowed in the cache.
*/
public synchronized int getMaxSize() {
return maxSize;
}
/**
* Add an object to the cache, with a default size of 1.
* If the cache is full, the oldest items will be deleted to make room.
* The item becomes the "newest" item.
*
* @param key
* The key used to refer to the object when calling <CODE>get()</CODE>.
* @param item
* The item to add to the cache.
*/
public synchronized void add(Object key, Object item) {
add(key, item , 1);
}
/**
* Add an object to the cache.
* If the cache is full, the oldest items will be deleted to make room.
* The item becomes the "newest" item.
*
* @param key
* The key used to refer to the object when calling <CODE>get()</CODE>.
* @param item
* The item to add to the cache.
* @param size
* How large is the object? This counts against the maximim size
* specified when the cache was created.
*/
public synchronized void add(Object key, Object item, int size) {
// Throw out old one if reusing a key.
if (cache.containsKey(key))
remove(key);
// Keep throwing out old items to make space. Stop if empty.
while (currentSize + size > maxSize) {
if (!deleteLRU())
break;
}
if (currentSize + size > maxSize)
// Just not enough room.
return;
Node node = new Node();
node.key = key;
node.item = item;
node.size = size;
cache.put(key, node);
insertNode(node);
currentSize += size;
}
/**
* Fetch an item from the cache. Returns null if not found.
* The item becomes the "newest" item.
*
* @param key
* The key used to refer to the object when <CODE>add()</CODE>
* was called.
* @return
* The item, or null if not found.
*/
public synchronized Object get(Object key) {
Node node = (Node)cache.get(key);
if (node == null)
return null;
deleteNode(node);
insertNode(node); // Move to the front of the list.
return node.item;
}
/**
* Remove an item from the cache.
*
* @param key
* The key used to refer to the object when <CODE>add()</CODE>
* was called.
* @return
* The item that was removed, or null if not found.
*/
public synchronized Object remove(Object key) {
Node node = (Node)cache.remove(key);
if (node == null)
return null;
deleteNode(node);
currentSize -= node.size;
return node.item;
}
/**
* Does the cache contain the given key?
*
* @param key
* The key used to refer to the object when <CODE>add()</CODE>
* was called.
* @return
* true if the key was found.
*/
public synchronized boolean containsKey(Object key) {
return cache.containsKey(key);
}
/**
* Delete all the items from the cache.
*/
public synchronized void clear() {
cache = new Hashtable();
head = tail = null;
currentSize = 0;
}
/*
* Insert the node at the front of the linked list.
* This only does linked list management.
*/
private void insertNode(Node node) {
node.next = head;
node.prev = null;
if (head != null)
head.prev = node;
head = node;
if (tail == null)
tail = node;
}
/*
* Delete the node from anywhere in the linked list.
* This only does linked list management.
*/
private void deleteNode(Node node) {
if (node.prev != null)
node.prev.next = node.next;
else
head = node.next;
if (node.next != null)
node.next.prev = node.prev;
else
tail = node.prev;
}
/*
* Delete the least recently used item. This is the one at the
* tail of the list. Returns true if an item was deleted,
* or false if the cache is empty.
*/
private boolean deleteLRU() {
if (tail == null)
return false;
currentSize -= tail.size;
cache.remove(tail.key);
deleteNode(tail);
return true;
}
/**
* Returns a string describing the contents of the cache.
*/
public synchronized String toString() {
StringBuffer buf = new StringBuffer();
buf.append("LRU ");
buf.append(currentSize);
buf.append("/");
buf.append(maxSize);
buf.append(" Order: ");
Node n = head;
while (n != null) {
buf.append(n.key);
if (n.next != null)
buf.append(", ");
n = n.next;
}
return buf.toString();
}
}
