LRUCache


1   /*
2    * Copyright 1999,2004 The Apache Software Foundation.
3    * 
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    * 
8    *      http://www.apache.org/licenses/LICENSE-2.0
9    * 
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */ 
16  package org.apache.taglibs.cache;
17  
18  import java.util.*;
19  
20  /**
21   * <p>A Map implementing a cache using an LRU cache-replacement algorithm.
22   * Following the general Map contract, this class requires explicit,
23   * outside synchronization in the event of concurrent access.</p>
24   *
25   * <p>Unlike similar LRU-based caches that implement Map (e.g., from Jakarta
26   * Commons), this class has a hard <i>size</i> limit (in characters), not a
27   * limit on the total number of elements.</p>
28   *
29   * <p>This class works like a Map for the methods it implements, but for
30   * simplicity, it is not a full Map.  I'd rather implement the full Map
31   * contract than just pay lip service to its methods.</p>
32   *
33   * @author Shawn Bayern
34   */
35  public class LRUCache {
36  
37    //*********************************************************************
38    // For testing...
39  
40    public static void main(String   args[]) throws Exception   {
41      LRUCache m =
42        new LRUCache(Integer.parseInt(args[0]), Integer.parseInt(args[1]));
43      String   line;
44      java.io.BufferedReader   r =
45        new java.io.BufferedReader  (new java.io.InputStreamReader  (System.in));
46      while ((line = r.readLine()) != null) {
47        m.put(line, line);
48        Iterator i = m.keySet().iterator();
49        System.out.println("  size = " + m.getCurrentSize());
50        while (i.hasNext())
51          System.out.println("  -> " + i.next());
52      }
53    }
54  
55    //*********************************************************************
56    // The cache itself
57  
58    private Map cache = new HashMap();
59    private LinkedList lruList = new LinkedList();
60    private int currentSize = 0, maxSize;
61    private int lifetime;
62  
63  
64    //*********************************************************************
65    // Plumbing
66  
67    /**
68     * Stores data associated with each cache entry.
69     */
70    private class CacheEntry {
71      private long expiration;
72      private String   value;
73      private int size;
74  
75      public CacheEntry(String   value) {
76        this.value = value;
77        this.size = value.length();
78        if (lifetime > 0) {
79          this.expiration = (new Date()).getTime() + lifetime;
80        }
81      }
82      public String   getValue() { return value; }
83      public long getSize() { return size; }
84      public boolean isExpired() { 
85        if (lifetime <= 0)
86          return false;
87        return (expiration < (new Date()).getTime());
88      }
89    }
90  
91  
92    //*********************************************************************
93    // Public, Map-like methods
94  
95    public void clear() {
96      cache = new HashMap();
97      lruList = new LinkedList();
98    }
99  
100   public String   get(Object   key) {
101     // assert invariant
102     if (currentSize > maxSize)
103       throw new AssertionError  ("cache state corrupted");
104 
105     CacheEntry e = (CacheEntry) cache.get(key);
106     if (e == null) {
107       return null;
108     } else if (e.isExpired()) {
109       // if the item's expired, pretend it never existed
110       cache.remove(key);
111       lruList.remove(key);
112       currentSize -= e.getSize();
113       return null;
114     } else {
115       noteUsed(key);
116       return ((CacheEntry) cache.get(key)).getValue();
117     }
118   }
119 
120   public Object   put(Object   key, Object   value) {
121     if (!(value instanceof String  ))
122       throw new IllegalArgumentException  (
123         "this Map only accepts Strings as values");
124 
125     CacheEntry oldEntry = (CacheEntry) cache.get(key);
126     if (oldEntry != null)
127       currentSize -= oldEntry.getSize();
128     CacheEntry e = new CacheEntry((String  ) value);
129     currentSize += e.getSize();
130     cache.put(key, e);
131     noteUsed(key);
132 
133     if (currentSize > maxSize) {
134       removeExpired();
135 
136       // now, if it's still necessary, remove legitimate but old entries
137       while (currentSize > maxSize) {
138     CacheEntry doomedEntry = (CacheEntry) cache.remove(lruList.getLast());
139         lruList.removeLast();
140         currentSize -= doomedEntry.getSize();
141       }
142 
143       // assert invariant
144       if (currentSize > maxSize)
145         throw new AssertionError  ("cache state corrupted");
146     }
147 
148     // return the old value as long as it wasn't expired
149     if (oldEntry == null || oldEntry.isExpired())
150       return null;
151     else
152       return oldEntry.getValue();
153   }
154 
155   public Object   remove(Object   key) {
156     lruList.remove(key);
157 
158     // return the old value as long as it wasn't expired
159     CacheEntry oldEntry = (CacheEntry) cache.remove(key);
160     if (oldEntry != null)
161       currentSize -= oldEntry.getSize();
162     if (oldEntry == null || oldEntry.isExpired())
163       return null;
164     else
165       return oldEntry.getValue();
166   }
167 
168   public Set keySet() {
169     removeExpired();
170     return cache.keySet();
171   }
172 
173   //*********************************************************************
174   // Other public methods
175 
176   public int getCurrentSize() {
177     return currentSize;
178   }
179 
180   //*********************************************************************
181   // Constructor
182 
183   /**
184    * Constructs an LRUCache that holds no more than <tt>size</tt> characters.
185    * Each entry expires after <tt>expiration</tt> seconds, or never
186    * expires if expiration less than or equal to 0.
187    */
188   public LRUCache(int size, int lifetime) {
189     this.maxSize = size;
190     this.lifetime = lifetime * 1000;
191   }
192 
193 
194   //*********************************************************************
195   // Utility methods
196 
197   /** Record the fact that the given object was "most recently" used. */
198   private void noteUsed(Object   key) {
199     lruList.remove(key);
200     lruList.addFirst(key);
201   }
202 
203   private void removeExpired() {
204     // don't bother unless entries in this LRUCache expire
205     if (lifetime >= 0) {
206       // remove all expired entries
207       Iterator i = cache.entrySet().iterator();
208       while (i.hasNext()) {
209     Map.Entry ent = (Map.Entry) i.next();
210         CacheEntry testEntry = (CacheEntry) ent.getValue();
211         if (testEntry.isExpired()) {
212       i.remove();
213       lruList.remove(ent.getKey());
214       currentSize -= testEntry.getSize();
215     }
216       }
217     }
218   }
219 }
220
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags