LRUCache


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