e7d92f2150dd46ad271fabc7a155d5c8c8373c6e
[phpeclipse.git] / net.sourceforge.phpeclipse / src / net / sourceforge / phpdt / internal / core / OverflowingLRUCache.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.internal.core;
12
13 import java.util.Enumeration;
14 import java.util.Iterator;
15
16 import net.sourceforge.phpdt.internal.core.util.LRUCache;
17
18 /**
19  *      The <code>OverflowingLRUCache</code> is an LRUCache which attempts
20  *      to maintain a size equal or less than its <code>fSpaceLimit</code>
21  *      by removing the least recently used elements.
22  *
23  *      <p>The cache will remove elements which successfully close and all
24  *      elements which are explicitly removed.
25  *
26  *      <p>If the cache cannot remove enough old elements to add new elements
27  *      it will grow beyond <code>fSpaceLimit</code>. Later, it will attempt to 
28  *      shink back to the maximum space limit.
29  *
30  *      The method <code>close</code> should attempt to close the element.  If
31  *      the element is successfully closed it will return true and the element will
32  *      be removed from the cache.  Otherwise the element will remain in the cache.
33  *
34  *      <p>The cache implicitly attempts shrinks on calls to <code>put</code>and
35  *      <code>setSpaceLimit</code>.  Explicitly calling the <code>shrink</code> method
36  *      will also cause the cache to attempt to shrink.
37  *
38  *      <p>The cache calculates the used space of all elements which implement 
39  *      <code>ILRUCacheable</code>.  All other elements are assumed to be of size one.
40  *
41  *      <p>Use the <code>#peek(Object)</code> and <code>#disableTimestamps()</code> method to
42  *      circumvent the timestamp feature of the cache.  This feature is intended to be used
43  *      only when the <code>#close(LRUCacheEntry)</code> method causes changes to the cache.  
44  *      For example, if a parent closes its children when </code>#close(LRUCacheEntry)</code> is called, 
45  *      it should be careful not to change the LRU linked list.  It can be sure it is not causing 
46  *      problems by calling <code>#peek(Object)</code> instead of <code>#get(Object)</code> method.
47  *      
48  *      @see LRUCache
49  */
50 public abstract class OverflowingLRUCache extends LRUCache {
51         /**
52          * Indicates if the cache has been over filled and by how much.
53          */
54         protected int fOverflow = 0;
55         /**
56          *      Indicates whether or not timestamps should be updated
57          */
58         protected boolean fTimestampsOn = true;
59         /**
60          *      Indicates how much space should be reclaimed when the cache overflows.
61          *      Inital load factor of one third.
62          */
63         protected double fLoadFactor = 0.333;
64 /**
65  * Creates a OverflowingLRUCache. 
66  * @param size Size limit of cache.
67  */
68 public OverflowingLRUCache(int size) {
69         this(size, 0);
70 }
71 /**
72  * Creates a OverflowingLRUCache. 
73  * @param size Size limit of cache.
74  * @param overflow Size of the overflow.
75  */
76 public OverflowingLRUCache(int size, int overflow) {
77         super(size);
78         fOverflow = overflow;
79 }
80         /**
81          * Returns a new cache containing the same contents.
82          *
83          * @return New copy of this object.
84          */
85         public Object clone() {
86                 
87                 OverflowingLRUCache newCache = (OverflowingLRUCache)newInstance(fSpaceLimit, fOverflow);
88                 LRUCacheEntry qEntry;
89                 
90                 /* Preserve order of entries by copying from oldest to newest */
91                 qEntry = this.fEntryQueueTail;
92                 while (qEntry != null) {
93                         newCache.privateAdd (qEntry._fKey, qEntry._fValue, qEntry._fSpace);
94                         qEntry = qEntry._fPrevious;
95                 }
96                 return newCache;
97         }
98 /**
99  * Returns true if the element is successfully closed and
100  * removed from the cache, otherwise false.
101  *
102  * <p>NOTE: this triggers an external remove from the cache
103  * by closing the obejct.
104  *
105  */
106 protected abstract boolean close(LRUCacheEntry entry);
107         /**
108          *      Returns an enumerator of the values in the cache with the most
109          *      recently used first.
110          */
111         public Enumeration elements() {
112                 if (fEntryQueue == null)
113                         return new LRUCacheEnumerator(null);
114                 LRUCacheEnumerator.LRUEnumeratorElement head = 
115                         new LRUCacheEnumerator.LRUEnumeratorElement(fEntryQueue._fValue);
116                 LRUCacheEntry currentEntry = fEntryQueue._fNext;
117                 LRUCacheEnumerator.LRUEnumeratorElement currentElement = head;
118                 while(currentEntry != null) {
119                         currentElement.fNext = new LRUCacheEnumerator.LRUEnumeratorElement(currentEntry._fValue);
120                         currentElement = currentElement.fNext;
121                         
122                         currentEntry = currentEntry._fNext;
123                 }
124                 return new LRUCacheEnumerator(head);
125         }
126         public double fillingRatio() {
127                 return (fCurrentSpace + fOverflow) * 100.0 / fSpaceLimit;
128         }
129         /**
130          * For internal testing only.
131          * This method exposed only for testing purposes!
132          *
133          * @return Hashtable of entries
134          */
135         public java.util.Hashtable getEntryTable() {
136                 return fEntryTable;
137         }
138 /**
139  * Returns the load factor for the cache.  The load factor determines how 
140  * much space is reclaimed when the cache exceeds its space limit.
141  * @return double
142  */
143 public double getLoadFactor() {
144         return fLoadFactor;
145 }
146         /**
147          *      @return The space by which the cache has overflown.
148          */
149         public int getOverflow() {
150                 return fOverflow;
151         }
152         /**
153          * Ensures there is the specified amount of free space in the receiver,
154          * by removing old entries if necessary.  Returns true if the requested space was
155          * made available, false otherwise.  May not be able to free enough space
156          * since some elements cannot be removed until they are saved.
157          *
158          * @param space Amount of space to free up
159          */
160         protected boolean makeSpace(int space) {
161         
162                 int limit = fSpaceLimit;
163                 if (fOverflow == 0) {
164                         /* if space is already available */
165                         if (fCurrentSpace + space <= limit) {
166                                 return true;
167                         }
168                 }
169         
170                 /* Free up space by removing oldest entries */
171                 int spaceNeeded = (int)((1 - fLoadFactor) * fSpaceLimit);
172                 spaceNeeded = (spaceNeeded > space) ? spaceNeeded : space;
173                 LRUCacheEntry entry = fEntryQueueTail;
174         
175                 while (fCurrentSpace + spaceNeeded > limit && entry != null) {
176                         this.privateRemoveEntry(entry, false, false);
177                         entry = entry._fPrevious;
178                 }
179         
180                 /* check again, since we may have aquired enough space */
181                 if (fCurrentSpace + space <= limit) {
182                         fOverflow = 0;
183                         return true;
184                 }
185         
186                 /* update fOverflow */
187                 fOverflow = fCurrentSpace + space - limit;
188                 return false;
189         }
190         /**
191          * Returns a new instance of the reciever.
192          */
193         protected abstract LRUCache newInstance(int size, int overflow);
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          * This function does not modify timestamps.
199          */
200         public Object peek(Object key) {
201                 
202                 LRUCacheEntry entry = (LRUCacheEntry) fEntryTable.get(key);
203                 if (entry == null) {
204                         return null;
205                 }
206                 return entry._fValue;
207         }
208 /**
209  * For testing purposes only
210  */
211 public void printStats() {
212         int forwardListLength = 0;
213         LRUCacheEntry entry = fEntryQueue;
214         while(entry != null) {
215                 forwardListLength++;
216                 entry = entry._fNext;
217         }
218         System.out.println("Forward length: " + forwardListLength); //$NON-NLS-1$
219         
220         int backwardListLength = 0;
221         entry = fEntryQueueTail;
222         while(entry != null) {
223                 backwardListLength++;
224                 entry = entry._fPrevious;
225         }
226         System.out.println("Backward length: " + backwardListLength); //$NON-NLS-1$
227
228         Enumeration keys = fEntryTable.keys();
229         class Temp {
230                 public Class fClass;
231                 public int fCount;
232                 public Temp(Class aClass) {
233                         fClass = aClass;
234                         fCount = 1;
235                 }
236                 public String toString() {
237                         return "Class: " + fClass + " has " + fCount + " entries."; //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-1$
238                 }
239         }
240         java.util.HashMap h = new java.util.HashMap();
241         while(keys.hasMoreElements()) {
242                 entry = (LRUCacheEntry)fEntryTable.get(keys.nextElement());
243                 Class key = entry._fValue.getClass();
244                 Temp t = (Temp)h.get(key);
245                 if (t == null) {
246                         h.put(key, new Temp(key));
247                 } else {
248                         t.fCount++;
249                 }
250         }
251
252         for (Iterator iter = h.keySet().iterator(); iter.hasNext();){
253                 System.out.println(h.get(iter.next()));
254         }
255 }
256         /**
257          *      Removes the entry from the entry queue.
258          *      Calls <code>privateRemoveEntry</code> with the external functionality enabled.
259          *
260          * @param shuffle indicates whether we are just shuffling the queue 
261          * (in which case, the entry table is not modified).
262          */
263         protected void privateRemoveEntry (LRUCacheEntry entry, boolean shuffle) {
264                 privateRemoveEntry(entry, shuffle, true);
265         }
266 /**
267  *      Removes the entry from the entry queue.  If <i>external</i> is true, the entry is removed
268  *      without checking if it can be removed.  It is assumed that the client has already closed
269  *      the element it is trying to remove (or will close it promptly).
270  *
271  *      If <i>external</i> is false, and the entry could not be closed, it is not removed and the 
272  *      pointers are not changed.
273  *
274  *      @param shuffle indicates whether we are just shuffling the queue 
275  *      (in which case, the entry table is not modified).
276  */
277 protected void privateRemoveEntry(LRUCacheEntry entry, boolean shuffle, boolean external) {
278
279         if (!shuffle) {
280                 if (external) {
281                         fEntryTable.remove(entry._fKey);                        
282                         fCurrentSpace -= entry._fSpace;
283                         privateNotifyDeletionFromCache(entry);
284                 } else {
285                         if (!close(entry)) return;
286                         // buffer close will recursively call #privateRemoveEntry with external==true
287                         // thus entry will already be removed if reaching this point.
288                         if (fEntryTable.get(entry._fKey) == null){
289                                 return;
290                         } else {
291                                 // basic removal
292                                 fEntryTable.remove(entry._fKey);                        
293                                 fCurrentSpace -= entry._fSpace;
294                                 privateNotifyDeletionFromCache(entry);
295                         }
296                 }
297         }
298         LRUCacheEntry previous = entry._fPrevious;
299         LRUCacheEntry next = entry._fNext;
300                 
301         /* if this was the first entry */
302         if (previous == null) {
303                 fEntryQueue = next;
304         } else {
305                 previous._fNext = next;
306         }
307         /* if this was the last entry */
308         if (next == null) {
309                 fEntryQueueTail = previous;
310         } else {
311                 next._fPrevious = previous;
312         }
313 }
314         /**
315          * Sets the value in the cache at the given key. Returns the value.
316          *
317          * @param key Key of object to add.
318          * @param value Value of object to add.
319          * @return added value.
320          */
321         public Object put(Object key, Object value) {
322                 /* attempt to rid ourselves of the overflow, if there is any */
323                 if (fOverflow > 0)
324                         shrink();
325                         
326                 /* Check whether there's an entry in the cache */
327                 int newSpace = spaceFor (key, value);
328                 LRUCacheEntry entry = (LRUCacheEntry) fEntryTable.get (key);
329                 
330                 if (entry != null) {
331                         
332                         /**
333                          * Replace the entry in the cache if it would not overflow
334                          * the cache.  Otherwise flush the entry and re-add it so as 
335                          * to keep cache within budget
336                          */
337                         int oldSpace = entry._fSpace;
338                         int newTotal = fCurrentSpace - oldSpace + newSpace;
339                         if (newTotal <= fSpaceLimit) {
340                                 updateTimestamp (entry);
341                                 entry._fValue = value;
342                                 entry._fSpace = newSpace;
343                                 fCurrentSpace = newTotal;
344                                 fOverflow = 0;
345                                 return value;
346                         } else {
347                                 privateRemoveEntry (entry, false, false);
348                         }
349                 }
350                 
351                 // attempt to make new space
352                 makeSpace(newSpace);
353                 
354                 // add without worring about space, it will
355                 // be handled later in a makeSpace call
356                 privateAdd (key, value, newSpace);
357                 
358                 return value;
359         }
360         /**
361          * Removes and returns the value in the cache for the given key.
362          * If the key is not in the cache, returns null.
363          *
364          * @param key Key of object to remove from cache.
365          * @return Value removed from cache.
366          */
367         public Object remove(Object key) {
368                 return removeKey(key);
369         }
370 /**
371  * Sets the load factor for the cache.  The load factor determines how 
372  * much space is reclaimed when the cache exceeds its space limit.
373  * @param newLoadFactor double
374  * @throws IllegalArgumentException when the new load factor is not in (0.0, 1.0]
375  */
376 public void setLoadFactor(double newLoadFactor) throws IllegalArgumentException {
377         if(newLoadFactor <= 1.0 && newLoadFactor > 0.0)
378                 fLoadFactor = newLoadFactor;
379         else
380                 throw new IllegalArgumentException(Util.bind("cache.invalidLoadFactor")); //$NON-NLS-1$
381 }
382         /**
383          * Sets the maximum amount of space that the cache can store
384          *
385          * @param limit Number of units of cache space
386          */
387         public void setSpaceLimit(int limit) {
388                 if (limit < fSpaceLimit) {
389                         makeSpace(fSpaceLimit - limit);
390                 }
391                 fSpaceLimit = limit;
392         }
393         /**
394          * Attempts to shrink the cache if it has overflown.
395          * Returns true if the cache shrinks to less than or equal to <code>fSpaceLimit</code>.
396          */
397         public boolean shrink() {
398                 if (fOverflow > 0)
399                         return makeSpace(0);
400                 return true;
401         }
402 /**
403  * Returns a String that represents the value of this object.  This method
404  * is for debugging purposes only.
405  */
406 public String toString() {
407         return 
408                 "OverflowingLRUCache " + this.fillingRatio() + "% full\n" + //$NON-NLS-1$ //$NON-NLS-2$
409                 this.toStringContents();
410 }
411 /**
412  * Updates the timestamp for the given entry, ensuring that the queue is 
413  * kept in correct order.  The entry must exist.
414  *
415  * <p>This method will do nothing if timestamps have been disabled.
416  */
417 protected void updateTimestamp(LRUCacheEntry entry) {
418         if (fTimestampsOn) {
419                 entry._fTimestamp = fTimestampCounter++;
420                 if (fEntryQueue != entry) {
421                         this.privateRemoveEntry(entry, true);
422                         this.privateAddEntry(entry, true);
423                 }
424         }
425 }
426 }