Source code: com/lutris/util/LRUCache.java
1 /*
2 * Enhydra Java Application Server Project
3 *
4 * The contents of this file are subject to the Enhydra Public License
5 * Version 1.1 (the "License"); you may not use this file except in
6 * compliance with the License. You may obtain a copy of the License on
7 * the Enhydra web site ( http://www.enhydra.org/ ).
8 *
9 * Software distributed under the License is distributed on an "AS IS"
10 * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
11 * the License for the specific terms governing rights and limitations
12 * under the License.
13 *
14 * The Initial Developer of the Enhydra Application Server is Lutris
15 * Technologies, Inc. The Enhydra Application Server and portions created
16 * by Lutris Technologies, Inc. are Copyright Lutris Technologies, Inc.
17 * All Rights Reserved.
18 *
19 * Contributor(s):
20 *
21 * $Id: LRUCache.java,v 1.7.12.1 2000/10/19 17:58:53 jasona Exp $
22 */
23
24
25
26
27
28 package com.lutris.util;
29
30 import java.util.Hashtable;
31
32 /**
33 * This class implements a fixed size Least-Recently-Used cache.
34 * The cache has a maximum size specified when it is created. When
35 * an item is added to the cache, if the cache is already at the
36 * maximum size the least recently used item is deleted, then the
37 * new item is added. <P>
38 *
39 * The only two methods that count as "using" the object (for the
40 * least-recently-used algorithm) are <CODE>add()</CODE> and
41 * <CODE>get()</CODE>. <P>
42 *
43 * The items cached are refered to by keys, just like a Hashtable.
44 *
45 * @author Andy John
46 * @version $Revision: 1.7.12.1 $
47 */
48 public class LRUCache {
49
50 /*
51 * Maximum allowed size of the cache.
52 */
53 private int maxSize;
54
55 /*
56 * The current size of the cache.
57 */
58 private int currentSize;
59
60 /*
61 * This hashtable stores all the items, and does all the searching.
62 */
63 private Hashtable cache;
64
65 /*
66 * A linked list of these structs defines the ordering from
67 * newest to oldest. The nodes are stored in the hashtable, so
68 * that constant-time access can locate a node.
69 */
70 private class Node {
71 Node prev, next;
72 Object key;
73 Object item;
74 int size;
75 }
76
77 /*
78 * The linked list. This is ONLY for keeping an ordering. All
79 * searching is done via the hashtable. All acceses to this linked
80 * list are constant-time.
81 */
82 private Node head, tail;
83
84 /**
85 * Create a new, empty cache.
86 *
87 * @param maxSize
88 * The maxmimum size of the items allowed to be in the cache.
89 * Since the size of an item defaults to 1, this is normally the
90 * number of items allowed in the cache.
91 * When this limit is reached, the "oldest" items are deleted to
92 * make room for the new item, so the total size of the cache
93 * (the sum of the sizes of all the items it contains)
94 * does not exceed the specified limit.
95 */
96 public LRUCache(int maxSize) {
97 this.maxSize = maxSize;
98 clear();
99 }
100
101 /**
102 * Returns the total size of the items in the cache.
103 * If all the items were added with the default size of 1,
104 * this is the number of items in the cache.
105 *
106 * @return
107 * The sum of the sizes of the items in the cache.
108 */
109 public synchronized int getSize() {
110 return currentSize;
111 }
112
113 /**
114 * Returns the maxmimum number of items allowed in the cache.
115 *
116 * @return
117 * The maximum number of items allowed in the cache.
118 */
119 public synchronized int getMaxSize() {
120 return maxSize;
121 }
122
123 /**
124 * Add an object to the cache, with a default size of 1.
125 * If the cache is full, the oldest items will be deleted to make room.
126 * The item becomes the "newest" item.
127 *
128 * @param key
129 * The key used to refer to the object when calling <CODE>get()</CODE>.
130 * @param item
131 * The item to add to the cache.
132 */
133 public synchronized void add(Object key, Object item) {
134 add(key, item , 1);
135 }
136
137 /**
138 * Add an object to the cache.
139 * If the cache is full, the oldest items will be deleted to make room.
140 * The item becomes the "newest" item.
141 *
142 * @param key
143 * The key used to refer to the object when calling <CODE>get()</CODE>.
144 * @param item
145 * The item to add to the cache.
146 * @param size
147 * How large is the object? This counts against the maximim size
148 * specified when the cache was created.
149 */
150 public synchronized void add(Object key, Object item, int size) {
151 // Throw out old one if reusing a key.
152 if (cache.containsKey(key))
153 remove(key);
154 // Keep throwing out old items to make space. Stop if empty.
155 while (currentSize + size > maxSize) {
156 if (!deleteLRU())
157 break;
158 }
159 if (currentSize + size > maxSize)
160 // Just not enough room.
161 return;
162 Node node = new Node();
163 node.key = key;
164 node.item = item;
165 node.size = size;
166 cache.put(key, node);
167 insertNode(node);
168 currentSize += size;
169 }
170
171
172 /**
173 * Fetch an item from the cache. Returns null if not found.
174 * The item becomes the "newest" item.
175 *
176 * @param key
177 * The key used to refer to the object when <CODE>add()</CODE>
178 * was called.
179 * @return
180 * The item, or null if not found.
181 */
182 public synchronized Object get(Object key) {
183 Node node = (Node)cache.get(key);
184 if (node == null)
185 return null;
186 deleteNode(node);
187 insertNode(node); // Move to the front of the list.
188 return node.item;
189 }
190
191
192 /**
193 * Remove an item from the cache.
194 *
195 * @param key
196 * The key used to refer to the object when <CODE>add()</CODE>
197 * was called.
198 * @return
199 * The item that was removed, or null if not found.
200 */
201 public synchronized Object remove(Object key) {
202 Node node = (Node)cache.remove(key);
203 if (node == null)
204 return null;
205 deleteNode(node);
206 currentSize -= node.size;
207 return node.item;
208 }
209
210
211 /**
212 * Does the cache contain the given key?
213 *
214 * @param key
215 * The key used to refer to the object when <CODE>add()</CODE>
216 * was called.
217 * @return
218 * true if the key was found.
219 */
220 public synchronized boolean containsKey(Object key) {
221 return cache.containsKey(key);
222 }
223
224
225 /**
226 * Delete all the items from the cache.
227 */
228 public synchronized void clear() {
229 cache = new Hashtable();
230 head = tail = null;
231 currentSize = 0;
232 }
233
234
235 /*
236 * Insert the node at the front of the linked list.
237 * This only does linked list management.
238 */
239 private void insertNode(Node node) {
240 node.next = head;
241 node.prev = null;
242 if (head != null)
243 head.prev = node;
244 head = node;
245 if (tail == null)
246 tail = node;
247 }
248
249
250 /*
251 * Delete the node from anywhere in the linked list.
252 * This only does linked list management.
253 */
254 private void deleteNode(Node node) {
255 if (node.prev != null)
256 node.prev.next = node.next;
257 else
258 head = node.next;
259 if (node.next != null)
260 node.next.prev = node.prev;
261 else
262 tail = node.prev;
263 }
264
265
266 /*
267 * Delete the least recently used item. This is the one at the
268 * tail of the list. Returns true if an item was deleted,
269 * or false if the cache is empty.
270 */
271 private boolean deleteLRU() {
272 if (tail == null)
273 return false;
274 currentSize -= tail.size;
275 cache.remove(tail.key);
276 deleteNode(tail);
277 return true;
278 }
279
280 /**
281 * Returns a string describing the contents of the cache.
282 */
283 public synchronized String toString() {
284 StringBuffer buf = new StringBuffer();
285 buf.append("LRU ");
286 buf.append(currentSize);
287 buf.append("/");
288 buf.append(maxSize);
289 buf.append(" Order: ");
290 Node n = head;
291 while (n != null) {
292 buf.append(n.key);
293 if (n.next != null)
294 buf.append(", ");
295 n = n.next;
296 }
297 return buf.toString();
298 }
299
300
301 }
302