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
9 * IBM Corporation - initial API and implementation
10 *******************************************************************************/
11 package net.sourceforge.phpdt.internal.core;
13 import java.util.Enumeration;
14 import java.util.Iterator;
16 import net.sourceforge.phpdt.internal.core.util.LRUCache;
17 import net.sourceforge.phpdt.internal.core.util.Util;
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.
24 * <p>The cache will remove elements which successfully close and all
25 * elements which are explicitly removed.
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.
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.
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.
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.
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.
51 public abstract class OverflowingLRUCache extends LRUCache {
53 * Indicates if the cache has been over filled and by how much.
55 protected int fOverflow = 0;
57 * Indicates whether or not timestamps should be updated
59 protected boolean fTimestampsOn = true;
61 * Indicates how much space should be reclaimed when the cache overflows.
62 * Inital load factor of one third.
64 protected double fLoadFactor = 0.333;
66 * Creates a OverflowingLRUCache.
67 * @param size Size limit of cache.
69 public OverflowingLRUCache(int size) {
73 * Creates a OverflowingLRUCache.
74 * @param size Size limit of cache.
75 * @param overflow Size of the overflow.
77 public OverflowingLRUCache(int size, int overflow) {
82 * Returns a new cache containing the same contents.
84 * @return New copy of this object.
86 public Object clone() {
88 OverflowingLRUCache newCache = (OverflowingLRUCache)newInstance(fSpaceLimit, fOverflow);
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;
100 * Returns true if the element is successfully closed and
101 * removed from the cache, otherwise false.
103 * <p>NOTE: this triggers an external remove from the cache
104 * by closing the obejct.
107 protected abstract boolean close(LRUCacheEntry entry);
109 * Returns an enumerator of the values in the cache with the most
110 * recently used first.
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;
123 currentEntry = currentEntry._fNext;
125 return new LRUCacheEnumerator(head);
127 public double fillingRatio() {
128 return (fCurrentSpace + fOverflow) * 100.0 / fSpaceLimit;
131 * For internal testing only.
132 * This method exposed only for testing purposes!
134 * @return Hashtable of entries
136 public java.util.Hashtable getEntryTable() {
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.
144 public double getLoadFactor() {
148 * @return The space by which the cache has overflown.
150 public int getOverflow() {
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.
159 * @param space Amount of space to free up
161 protected boolean makeSpace(int space) {
163 int limit = fSpaceLimit;
164 if (fOverflow == 0) {
165 /* if space is already available */
166 if (fCurrentSpace + space <= limit) {
171 /* Free up space by removing oldest entries */
172 int spaceNeeded = (int)((1 - fLoadFactor) * fSpaceLimit);
173 spaceNeeded = (spaceNeeded > space) ? spaceNeeded : space;
174 LRUCacheEntry entry = fEntryQueueTail;
176 while (fCurrentSpace + spaceNeeded > limit && entry != null) {
177 this.privateRemoveEntry(entry, false, false);
178 entry = entry._fPrevious;
181 /* check again, since we may have aquired enough space */
182 if (fCurrentSpace + space <= limit) {
187 /* update fOverflow */
188 fOverflow = fCurrentSpace + space - limit;
192 * Returns a new instance of the reciever.
194 protected abstract LRUCache newInstance(int size, int overflow);
196 * Answers the value in the cache at the given key.
197 * If the value is not in the cache, returns null
199 * This function does not modify timestamps.
201 public Object peek(Object key) {
203 LRUCacheEntry entry = (LRUCacheEntry) fEntryTable.get(key);
207 return entry._fValue;
210 * For testing purposes only
212 public void printStats() {
213 int forwardListLength = 0;
214 LRUCacheEntry entry = fEntryQueue;
215 while(entry != null) {
217 entry = entry._fNext;
219 System.out.println("Forward length: " + forwardListLength); //$NON-NLS-1$
221 int backwardListLength = 0;
222 entry = fEntryQueueTail;
223 while(entry != null) {
224 backwardListLength++;
225 entry = entry._fPrevious;
227 System.out.println("Backward length: " + backwardListLength); //$NON-NLS-1$
229 Enumeration keys = fEntryTable.keys();
233 public Temp(Class aClass) {
237 public String toString() {
238 return "Class: " + fClass + " has " + fCount + " entries."; //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-1$
241 java.util.HashMap h = new java.util.HashMap();
242 while(keys.hasMoreElements()) {
243 entry = (LRUCacheEntry)fEntryTable.get(keys.nextElement());
244 Class key = entry._fValue.getClass();
245 Temp t = (Temp)h.get(key);
247 h.put(key, new Temp(key));
253 for (Iterator iter = h.keySet().iterator(); iter.hasNext();){
254 System.out.println(h.get(iter.next()));
258 * Removes the entry from the entry queue.
259 * Calls <code>privateRemoveEntry</code> with the external functionality enabled.
261 * @param shuffle indicates whether we are just shuffling the queue
262 * (in which case, the entry table is not modified).
264 protected void privateRemoveEntry (LRUCacheEntry entry, boolean shuffle) {
265 privateRemoveEntry(entry, shuffle, true);
268 * Removes the entry from the entry queue. If <i>external</i> is true, the entry is removed
269 * without checking if it can be removed. It is assumed that the client has already closed
270 * the element it is trying to remove (or will close it promptly).
272 * If <i>external</i> is false, and the entry could not be closed, it is not removed and the
273 * pointers are not changed.
275 * @param shuffle indicates whether we are just shuffling the queue
276 * (in which case, the entry table is not modified).
278 protected void privateRemoveEntry(LRUCacheEntry entry, boolean shuffle, boolean external) {
282 fEntryTable.remove(entry._fKey);
283 fCurrentSpace -= entry._fSpace;
284 privateNotifyDeletionFromCache(entry);
286 if (!close(entry)) return;
287 // buffer close will recursively call #privateRemoveEntry with external==true
288 // thus entry will already be removed if reaching this point.
289 if (fEntryTable.get(entry._fKey) == null){
293 fEntryTable.remove(entry._fKey);
294 fCurrentSpace -= entry._fSpace;
295 privateNotifyDeletionFromCache(entry);
299 LRUCacheEntry previous = entry._fPrevious;
300 LRUCacheEntry next = entry._fNext;
302 /* if this was the first entry */
303 if (previous == null) {
306 previous._fNext = next;
308 /* if this was the last entry */
310 fEntryQueueTail = previous;
312 next._fPrevious = previous;
316 * Sets the value in the cache at the given key. Returns the value.
318 * @param key Key of object to add.
319 * @param value Value of object to add.
320 * @return added value.
322 public Object put(Object key, Object value) {
323 /* attempt to rid ourselves of the overflow, if there is any */
327 /* Check whether there's an entry in the cache */
328 int newSpace = spaceFor (key, value);
329 LRUCacheEntry entry = (LRUCacheEntry) fEntryTable.get (key);
334 * Replace the entry in the cache if it would not overflow
335 * the cache. Otherwise flush the entry and re-add it so as
336 * to keep cache within budget
338 int oldSpace = entry._fSpace;
339 int newTotal = fCurrentSpace - oldSpace + newSpace;
340 if (newTotal <= fSpaceLimit) {
341 updateTimestamp (entry);
342 entry._fValue = value;
343 entry._fSpace = newSpace;
344 fCurrentSpace = newTotal;
348 privateRemoveEntry (entry, false, false);
352 // attempt to make new space
355 // add without worring about space, it will
356 // be handled later in a makeSpace call
357 privateAdd (key, value, newSpace);
362 * Removes and returns the value in the cache for the given key.
363 * If the key is not in the cache, returns null.
365 * @param key Key of object to remove from cache.
366 * @return Value removed from cache.
368 public Object remove(Object key) {
369 return removeKey(key);
372 * Sets the load factor for the cache. The load factor determines how
373 * much space is reclaimed when the cache exceeds its space limit.
374 * @param newLoadFactor double
375 * @throws IllegalArgumentException when the new load factor is not in (0.0, 1.0]
377 public void setLoadFactor(double newLoadFactor) throws IllegalArgumentException {
378 if(newLoadFactor <= 1.0 && newLoadFactor > 0.0)
379 fLoadFactor = newLoadFactor;
381 throw new IllegalArgumentException(Util.bind("cache.invalidLoadFactor")); //$NON-NLS-1$
384 * Sets the maximum amount of space that the cache can store
386 * @param limit Number of units of cache space
388 public void setSpaceLimit(int limit) {
389 if (limit < fSpaceLimit) {
390 makeSpace(fSpaceLimit - limit);
395 * Attempts to shrink the cache if it has overflown.
396 * Returns true if the cache shrinks to less than or equal to <code>fSpaceLimit</code>.
398 public boolean shrink() {
404 * Returns a String that represents the value of this object. This method
405 * is for debugging purposes only.
407 public String toString() {
409 "OverflowingLRUCache " + this.fillingRatio() + "% full\n" + //$NON-NLS-1$ //$NON-NLS-2$
410 this.toStringContents();
413 * Updates the timestamp for the given entry, ensuring that the queue is
414 * kept in correct order. The entry must exist.
416 * <p>This method will do nothing if timestamps have been disabled.
418 protected void updateTimestamp(LRUCacheEntry entry) {
420 entry._fTimestamp = fTimestampCounter++;
421 if (fEntryQueue != entry) {
422 this.privateRemoveEntry(entry, true);
423 this.privateAddEntry(entry, true);