Java > Open Source Codes > org > eclipse > jdt > internal > core > util > LRUCache


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

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags