001: /*
002: * Enhydra Java Application Server Project
003: *
004: * The contents of this file are subject to the Enhydra Public License
005: * Version 1.1 (the "License"); you may not use this file except in
006: * compliance with the License. You may obtain a copy of the License on
007: * the Enhydra web site ( http://www.enhydra.org/ ).
008: *
009: * Software distributed under the License is distributed on an "AS IS"
010: * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
011: * the License for the specific terms governing rights and limitations
012: * under the License.
013: *
014: * The Initial Developer of the Enhydra Application Server is Lutris
015: * Technologies, Inc. The Enhydra Application Server and portions created
016: * by Lutris Technologies, Inc. are Copyright Lutris Technologies, Inc.
017: * All Rights Reserved.
018: *
019: * Contributor(s):
020: *
021: * $Id: LRUCache.java,v 1.3 2007-10-19 10:05:39 sinisa Exp $
022: */
023:
024: package com.lutris.util;
025:
026: import java.util.Hashtable;
027:
028: /**
029: * This class implements a fixed size Least-Recently-Used cache.
030: * The cache has a maximum size specified when it is created. When
031: * an item is added to the cache, if the cache is already at the
032: * maximum size the least recently used item is deleted, then the
033: * new item is added. <P>
034: *
035: * The only two methods that count as "using" the object (for the
036: * least-recently-used algorithm) are <CODE>add()</CODE> and
037: * <CODE>get()</CODE>. <P>
038: *
039: * The items cached are refered to by keys, just like a Hashtable.
040: *
041: * @author Andy John
042: * @version $Revision: 1.3 $
043: */
044: public class LRUCache {
045:
046: /*
047: * Maximum allowed size of the cache.
048: */
049: private int maxSize;
050:
051: /*
052: * The current size of the cache.
053: */
054: private int currentSize;
055:
056: /*
057: * This hashtable stores all the items, and does all the searching.
058: */
059: private Hashtable cache;
060:
061: /*
062: * A linked list of these structs defines the ordering from
063: * newest to oldest. The nodes are stored in the hashtable, so
064: * that constant-time access can locate a node.
065: */
066: private static class Node {
067: Node prev, next;
068: Object key;
069: Object item;
070: int size;
071: }
072:
073: /*
074: * The linked list. This is ONLY for keeping an ordering. All
075: * searching is done via the hashtable. All acceses to this linked
076: * list are constant-time.
077: */
078: private Node head, tail;
079:
080: /**
081: * Create a new, empty cache.
082: *
083: * @param maxSize
084: * The maxmimum size of the items allowed to be in the cache.
085: * Since the size of an item defaults to 1, this is normally the
086: * number of items allowed in the cache.
087: * When this limit is reached, the "oldest" items are deleted to
088: * make room for the new item, so the total size of the cache
089: * (the sum of the sizes of all the items it contains)
090: * does not exceed the specified limit.
091: */
092: public LRUCache(int maxSize) {
093: this .maxSize = maxSize;
094: clear();
095: }
096:
097: /**
098: * Returns the total size of the items in the cache.
099: * If all the items were added with the default size of 1,
100: * this is the number of items in the cache.
101: *
102: * @return
103: * The sum of the sizes of the items in the cache.
104: */
105: public synchronized int getSize() {
106: return currentSize;
107: }
108:
109: /**
110: * Returns the maxmimum number of items allowed in the cache.
111: *
112: * @return
113: * The maximum number of items allowed in the cache.
114: */
115: public synchronized int getMaxSize() {
116: return maxSize;
117: }
118:
119: /**
120: * Add an object to the cache, with a default size of 1.
121: * If the cache is full, the oldest items will be deleted to make room.
122: * The item becomes the "newest" item.
123: *
124: * @param key
125: * The key used to refer to the object when calling <CODE>get()</CODE>.
126: * @param item
127: * The item to add to the cache.
128: */
129: public synchronized void add(Object key, Object item) {
130: add(key, item, 1);
131: }
132:
133: /**
134: * Add an object to the cache.
135: * If the cache is full, the oldest items will be deleted to make room.
136: * The item becomes the "newest" item.
137: *
138: * @param key
139: * The key used to refer to the object when calling <CODE>get()</CODE>.
140: * @param item
141: * The item to add to the cache.
142: * @param size
143: * How large is the object? This counts against the maximim size
144: * specified when the cache was created.
145: */
146: public synchronized void add(Object key, Object item, int size) {
147: // Throw out old one if reusing a key.
148: if (cache.containsKey(key))
149: remove(key);
150: // Keep throwing out old items to make space. Stop if empty.
151: while (currentSize + size > maxSize) {
152: if (!deleteLRU())
153: break;
154: }
155: if (currentSize + size > maxSize)
156: // Just not enough room.
157: return;
158: Node node = new Node();
159: node.key = key;
160: node.item = item;
161: node.size = size;
162: cache.put(key, node);
163: insertNode(node);
164: currentSize += size;
165: }
166:
167: /**
168: * Fetch an item from the cache. Returns null if not found.
169: * The item becomes the "newest" item.
170: *
171: * @param key
172: * The key used to refer to the object when <CODE>add()</CODE>
173: * was called.
174: * @return
175: * The item, or null if not found.
176: */
177: public synchronized Object get(Object key) {
178: Node node = (Node) cache.get(key);
179: if (node == null)
180: return null;
181: deleteNode(node);
182: insertNode(node); // Move to the front of the list.
183: return node.item;
184: }
185:
186: /**
187: * Remove an item from the cache.
188: *
189: * @param key
190: * The key used to refer to the object when <CODE>add()</CODE>
191: * was called.
192: * @return
193: * The item that was removed, or null if not found.
194: */
195: public synchronized Object remove(Object key) {
196: Node node = (Node) cache.remove(key);
197: if (node == null)
198: return null;
199: deleteNode(node);
200: currentSize -= node.size;
201: return node.item;
202: }
203:
204: /**
205: * Does the cache contain the given key?
206: *
207: * @param key
208: * The key used to refer to the object when <CODE>add()</CODE>
209: * was called.
210: * @return
211: * true if the key was found.
212: */
213: public synchronized boolean containsKey(Object key) {
214: return cache.containsKey(key);
215: }
216:
217: /**
218: * Delete all the items from the cache.
219: */
220: public synchronized void clear() {
221: cache = new Hashtable();
222: head = tail = null;
223: currentSize = 0;
224: }
225:
226: /*
227: * Insert the node at the front of the linked list.
228: * This only does linked list management.
229: */
230: private void insertNode(Node node) {
231: node.next = head;
232: node.prev = null;
233: if (head != null)
234: head.prev = node;
235: head = node;
236: if (tail == null)
237: tail = node;
238: }
239:
240: /*
241: * Delete the node from anywhere in the linked list.
242: * This only does linked list management.
243: */
244: private void deleteNode(Node node) {
245: if (node.prev != null)
246: node.prev.next = node.next;
247: else
248: head = node.next;
249: if (node.next != null)
250: node.next.prev = node.prev;
251: else
252: tail = node.prev;
253: }
254:
255: /*
256: * Delete the least recently used item. This is the one at the
257: * tail of the list. Returns true if an item was deleted,
258: * or false if the cache is empty.
259: */
260: private boolean deleteLRU() {
261: if (tail == null)
262: return false;
263: currentSize -= tail.size;
264: cache.remove(tail.key);
265: deleteNode(tail);
266: return true;
267: }
268:
269: /**
270: * Returns a string describing the contents of the cache.
271: */
272: public synchronized String toString() {
273: StringBuffer buf = new StringBuffer();
274: buf.append("LRU ");
275: buf.append(currentSize);
276: buf.append("/");
277: buf.append(maxSize);
278: buf.append(" Order: ");
279: Node n = head;
280: while (n != null) {
281: buf.append(n.key);
282: if (n.next != null)
283: buf.append(", ");
284: n = n.next;
285: }
286: return buf.toString();
287: }
288:
289: }
|