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