KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > core > internal > expressions > util > 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 JavaDoc;
14 import java.util.Hashtable JavaDoc;
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 JavaDoc {
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 JavaDoc _fKey;
36          
37         /**
38          * Hash table value (an LRUCacheEntry object)
39          */

40         public Object JavaDoc _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 JavaDoc key, Object JavaDoc 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 JavaDoc 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 JavaDoc 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 JavaDoc(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 JavaDoc 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 JavaDoc(); // 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 JavaDoc 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 JavaDoc get(Object JavaDoc 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 JavaDoc 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 JavaDoc peek(Object JavaDoc 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 JavaDoc key, Object JavaDoc 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 JavaDoc put(Object JavaDoc key, Object JavaDoc 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 JavaDoc removeKey (Object JavaDoc key) {
411         
412         LRUCacheEntry entry = (LRUCacheEntry) fEntryTable.get(key);
413         if (entry == null) {
414             return null;
415         }
416         Object JavaDoc 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 JavaDoc 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 JavaDoc 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 JavaDoc toStringContents() {
457         StringBuffer JavaDoc result = new StringBuffer JavaDoc();
458         int length = fEntryTable.size();
459         Object JavaDoc[] unsortedKeys = new Object JavaDoc[length];
460         String JavaDoc[] unsortedToStrings = new String JavaDoc[length];
461         Enumeration JavaDoc e = this.keys();
462         for (int i = 0; i < length; i++) {
463             Object JavaDoc 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 JavaDoc toString = sorter.sortedStrings[i];
471             Object JavaDoc 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 JavaDoc toStringFillingRation(String JavaDoc cacheName) {
481         StringBuffer JavaDoc buffer = new StringBuffer JavaDoc(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
Popular Tags