LRUCache


1   /*******************************************************************************
2    * Copyright (c) 2000, 2006 IBM Corporation and others.
3    * All rights reserved. This program and the accompanying materials
4    * are made available under the terms of the Eclipse Public License v1.0
5    * which accompanies this distribution, and is available at
6    * http://www.eclipse.org/legal/epl-v10.html
7    *
8    * Contributors:
9    *     IBM Corporation - initial API and implementation
10   *******************************************************************************/
11  package org.eclipse.core.internal.expressions.util;
12  
13  import java.util.Enumeration  ;
14  import java.util.Hashtable  ;
15  
16  /**
17   * Copied from JDT/Core to get a cache which is independent from
18   * JDK 1.4. 
19   */
20  public class LRUCache implements Cloneable   {
21  
22      /**
23       * This type is used internally by the LRUCache to represent entries 
24       * stored in the cache.
25       * It is static because it does not require a pointer to the cache
26       * which contains it.
27       *
28       * @see LRUCache
29       */
30      protected static class LRUCacheEntry {
31          
32          /**
33           * Hash table key
34           */
35          public Object   _fKey;
36           
37          /**
38           * Hash table value (an LRUCacheEntry object)
39           */
40          public Object   _fValue;       
41  
42          /**
43           * Time value for queue sorting
44           */
45          public int _fTimestamp;
46          
47          /**
48           * Cache footprint of this entry
49           */
50          public int _fSpace;
51          
52          /**
53           * Previous entry in queue
54           */
55          public LRUCacheEntry _fPrevious;
56              
57          /**
58           * Next entry in queue
59           */
60          public LRUCacheEntry _fNext;
61              
62          /**
63           * Creates a new instance of the receiver with the provided values
64           * for key, value, and space.
65           * @param key 
66           * @param value 
67           * @param space 
68           */
69          public LRUCacheEntry (Object   key, Object   value, int space) {
70              _fKey = key;
71              _fValue = value;
72              _fSpace = space;
73          }
74  
75          /**
76           * Returns a String that represents the value of this object.
77           * @return a string
78           */
79          public String   toString() {
80  
81              return "LRUCacheEntry [" + _fKey + "-->" + _fValue + "]"; //$NON-NLS-3$ //$NON-NLS-1$ //$NON-NLS-2$
82          }
83      }   
84  
85      /**
86       * Amount of cache space used so far
87       */
88      protected int fCurrentSpace;
89      
90      /**
91       * Maximum space allowed in cache
92       */
93      protected int fSpaceLimit;
94      
95      /**
96       * Counter for handing out sequential timestamps
97       */
98      protected int   fTimestampCounter;
99      
100     /**
101      * Hash table for fast random access to cache entries
102      */
103     protected Hashtable   fEntryTable;
104 
105     /**
106      * Start of queue (most recently used entry) 
107      */ 
108     protected LRUCacheEntry fEntryQueue;
109 
110     /**
111      * End of queue (least recently used entry)
112      */ 
113     protected LRUCacheEntry fEntryQueueTail;
114         
115     /**
116      * Default amount of space in the cache
117      */
118     protected static final int DEFAULT_SPACELIMIT = 100;
119     /**
120      * Creates a new cache.  Size of cache is defined by 
121      * <code>DEFAULT_SPACELIMIT</code>.
122      */
123     public LRUCache() {
124         
125         this(DEFAULT_SPACELIMIT);
126     }
127     /**
128      * Creates a new cache.
129      * @param size Size of Cache
130      */
131     public LRUCache(int size) {
132         
133         fTimestampCounter = fCurrentSpace = 0;
134         fEntryQueue = fEntryQueueTail = null;
135         fEntryTable = new Hashtable  (size);
136         fSpaceLimit = size;
137     }
138     /**
139      * Returns a new cache containing the same contents.
140      *
141      * @return New copy of object.
142      */
143     public Object   clone() {
144         
145         LRUCache newCache = newInstance(fSpaceLimit);
146         LRUCacheEntry qEntry;
147         
148         /* Preserve order of entries by copying from oldest to newest */
149         qEntry = this.fEntryQueueTail;
150         while (qEntry != null) {
151             newCache.privateAdd (qEntry._fKey, qEntry._fValue, qEntry._fSpace);
152             qEntry = qEntry._fPrevious;
153         }
154         return newCache;
155     }
156     public double fillingRatio() {
157         return (fCurrentSpace) * 100.0 / fSpaceLimit;
158     }
159     /**
160      * Flushes all entries from the cache.
161      */
162     public void flush() {
163 
164         fCurrentSpace = 0;
165         LRUCacheEntry entry = fEntryQueueTail; // Remember last entry
166         fEntryTable = new Hashtable  ();  // Clear it out
167         fEntryQueue = fEntryQueueTail = null;  
168         while (entry != null) {  // send deletion notifications in LRU order
169             privateNotifyDeletionFromCache(entry);
170             entry = entry._fPrevious;
171         }
172     }
173     /**
174      * Flushes the given entry from the cache.  Does nothing if entry does not
175      * exist in cache.
176      *
177      * @param key Key of object to flush
178      */
179     public void flush (Object   key) {
180         
181         LRUCacheEntry entry;
182         
183         entry = (LRUCacheEntry) fEntryTable.get(key);
184 
185         /* If entry does not exist, return */
186         if (entry == null) return;
187 
188         this.privateRemoveEntry (entry, false);
189     }
190     /**
191      * Answers the value in the cache at the given key.
192      * If the value is not in the cache, returns null
193      *
194      * @param key Hash table key of object to retrieve
195      * @return Retreived object, or null if object does not exist
196      */
197     public Object   get(Object   key) {
198         
199         LRUCacheEntry entry = (LRUCacheEntry) fEntryTable.get(key);
200         if (entry == null) {
201             return null;
202         }
203         
204         this.updateTimestamp (entry);
205         return entry._fValue;
206     }
207     /**
208      * Returns the amount of space that is current used in the cache.
209      * @return an int
210      */
211     public int getCurrentSpace() {
212         return fCurrentSpace;
213     }
214     /**
215      * Returns the maximum amount of space available in the cache.
216      * @return an int
217      */
218     public int getSpaceLimit() {
219         return fSpaceLimit;
220     }
221     /**
222      * Returns an Enumeration of the keys currently in the cache.
223      * @return an enumeration
224      */
225     public Enumeration   keys() {
226         return fEntryTable.keys();
227     }
228     /**
229      * Ensures there is the specified amount of free space in the receiver,
230      * by removing old entries if necessary.  Returns true if the requested space was
231      * made available, false otherwise.
232      *
233      * @param space Amount of space to free up
234      * @return a boolean
235      */
236     protected boolean makeSpace (int space) {
237         
238         int limit;
239         
240         limit = this.getSpaceLimit();
241         
242         /* if space is already available */
243         if (fCurrentSpace + space <= limit) {
244             return true;
245         }
246         
247         /* if entry is too big for cache */
248         if (space > limit) {
249             return false;
250         }
251         
252         /* Free up space by removing oldest entries */
253         while (fCurrentSpace + space > limit && fEntryQueueTail != null) {
254             this.privateRemoveEntry (fEntryQueueTail, false);
255         }
256         return true;
257     }
258     /**
259      * Returns a new LRUCache instance
260      * @param size the size
261      * @return a cache
262      */
263     protected LRUCache newInstance(int size) {
264         return new LRUCache(size);
265     }
266     /**
267      * Answers the value in the cache at the given key.
268      * If the value is not in the cache, returns null
269      *
270      * This function does not modify timestamps.
271      * @param key the key
272      * @return the object
273      */
274     public Object   peek(Object   key) {
275         
276         LRUCacheEntry entry = (LRUCacheEntry) fEntryTable.get(key);
277         if (entry == null) {
278             return null;
279         }
280         return entry._fValue;
281     }
282     /**
283      * Adds an entry for the given key/value/space.
284      * @param key 
285      * @param value 
286      * @param space 
287      */
288     protected void privateAdd (Object   key, Object   value, int space) {
289         
290         LRUCacheEntry entry;
291         
292         entry = new LRUCacheEntry(key, value, space);
293         this.privateAddEntry (entry, false);
294     }
295     /**
296      * Adds the given entry from the receiver.
297      * @param entry 
298      * @param shuffle Indicates whether we are just shuffling the queue 
299      * (in which case, the entry table is not modified).
300      */
301     protected void privateAddEntry (LRUCacheEntry entry, boolean shuffle) {
302         
303         if (!shuffle) {
304             fEntryTable.put (entry._fKey, entry);
305             fCurrentSpace += entry._fSpace;
306         }
307         
308         entry._fTimestamp = fTimestampCounter++;
309         entry._fNext = this.fEntryQueue;
310         entry._fPrevious = null;
311         
312         if (fEntryQueue == null) {
313             /* this is the first and last entry */
314             fEntryQueueTail = entry;
315         } else {
316             fEntryQueue._fPrevious = entry;
317         }
318         
319         fEntryQueue = entry;
320     }
321     /**
322      * An entry has been removed from the cache, for example because it has 
323      * fallen off the bottom of the LRU queue.  
324      * Subclasses could over-ride this to implement a persistent cache below the LRU cache.
325      * @param entry 
326      */
327     protected void privateNotifyDeletionFromCache(LRUCacheEntry entry) {
328         // Default is NOP.
329     }
330     /**
331      * Removes the entry from the entry queue.  
332      * @param entry 
333      * @param shuffle indicates whether we are just shuffling the queue 
334      * (in which case, the entry table is not modified).
335      */
336     protected void privateRemoveEntry (LRUCacheEntry entry, boolean shuffle) {
337         
338         LRUCacheEntry previous, next;
339         
340         previous = entry._fPrevious;
341         next = entry._fNext;
342         
343         if (!shuffle) {
344             fEntryTable.remove(entry._fKey);
345             fCurrentSpace -= entry._fSpace;
346             privateNotifyDeletionFromCache(entry);
347         }
348 
349         /* if this was the first entry */
350         if (previous == null) {
351             fEntryQueue = next;
352         } else {
353             previous._fNext = next;
354         }
355 
356         /* if this was the last entry */
357         if (next == null) {
358             fEntryQueueTail = previous;
359         } else {
360             next._fPrevious = previous;
361         }
362     }
363     /**
364      * Sets the value in the cache at the given key. Returns the value.
365      *
366      * @param key Key of object to add.
367      * @param value Value of object to add.
368      * @return added value.
369      */
370     public Object   put(Object   key, Object   value) {
371         
372         int newSpace, oldSpace, newTotal;
373         LRUCacheEntry entry;
374         
375         /* Check whether there's an entry in the cache */
376         newSpace = spaceFor(value);
377         entry = (LRUCacheEntry) fEntryTable.get (key);
378         
379         if (entry != null) {
380             
381             /**
382              * Replace the entry in the cache if it would not overflow
383              * the cache.  Otherwise flush the entry and re-add it so as 
384              * to keep cache within budget
385              */
386             oldSpace = entry._fSpace;
387             newTotal = getCurrentSpace() - oldSpace + newSpace;
388             if (newTotal <= getSpaceLimit()) {
389                 updateTimestamp (entry);
390                 entry._fValue = value;
391                 entry._fSpace = newSpace;
392                 this.fCurrentSpace = newTotal;
393                 return value;
394             } else {
395                 privateRemoveEntry (entry, false);
396             }
397         }
398         if (makeSpace(newSpace)) {
399             privateAdd (key, value, newSpace);
400         }
401         return value;
402     }
403     /**
404      * Removes and returns the value in the cache for the given key.
405      * If the key is not in the cache, returns null.
406      *
407      * @param key Key of object to remove from cache.
408      * @return Value removed from cache.
409      */
410     public Object   removeKey (Object   key) {
411         
412         LRUCacheEntry entry = (LRUCacheEntry) fEntryTable.get(key);
413         if (entry == null) {
414             return null;
415         }
416         Object   value = entry._fValue;
417         this.privateRemoveEntry (entry, false);
418         return value;
419     }
420     /**
421      * Sets the maximum amount of space that the cache can store
422      *
423      * @param limit Number of units of cache space
424      */
425     public void setSpaceLimit(int limit) {
426         if (limit < fSpaceLimit) {
427             makeSpace(fSpaceLimit - limit);
428         }
429         fSpaceLimit = limit;
430     }
431     /**
432      * Returns the space taken by the given value.
433      * @param value 
434      * @return an int
435      */
436     protected int spaceFor (Object   value) {
437             return 1;
438     }
439     
440     /**
441      * Returns a String that represents the value of this object.  This method
442      * is for debugging purposes only.
443      * @return a string
444      */
445     public String   toString() {
446         return 
447             toStringFillingRation("LRUCache") + //$NON-NLS-1$
448             toStringContents();
449     }
450     
451     /**
452      * Returns a String that represents the contents of this object.  This method
453      * is for debugging purposes only.
454      * @return a string
455      */
456     protected String   toStringContents() {
457         StringBuffer   result = new StringBuffer  ();
458         int length = fEntryTable.size();
459         Object  [] unsortedKeys = new Object  [length];
460         String  [] unsortedToStrings = new String  [length];
461         Enumeration   e = this.keys();
462         for (int i = 0; i < length; i++) {
463             Object   key = e.nextElement();
464             unsortedKeys[i] = key;
465             unsortedToStrings[i] = key.toString();
466         }
467         ToStringSorter sorter = new ToStringSorter();
468         sorter.sort(unsortedKeys, unsortedToStrings);
469         for (int i = 0; i < length; i++) {
470             String   toString = sorter.sortedStrings[i];
471             Object   value = this.get(sorter.sortedObjects[i]);
472             result.append(toString);        
473             result.append(" -> "); //$NON-NLS-1$
474             result.append(value);
475             result.append("\n"); //$NON-NLS-1$
476         }
477         return result.toString();
478     }
479     
480     public String   toStringFillingRation(String   cacheName) {
481         StringBuffer   buffer = new StringBuffer  (cacheName);
482         buffer.append('[');
483         buffer.append(getSpaceLimit());
484         buffer.append("]: "); //$NON-NLS-1$
485         buffer.append(fillingRatio());
486         buffer.append("% full"); //$NON-NLS-1$
487         return buffer.toString();
488     }
489 
490     /**
491      * Updates the timestamp for the given entry, ensuring that the queue is 
492      * kept in correct order.  The entry must exist
493      * @param entry 
494      */
495     protected void updateTimestamp (LRUCacheEntry entry) {
496         
497         entry._fTimestamp = fTimestampCounter++;
498         if (fEntryQueue != entry) {
499             this.privateRemoveEntry (entry, true);
500             this.privateAddEntry (entry, true);
501         }
502         return;
503     }
504 }
505
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags