OverflowingLRUCache


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