OverflowingLRUCache is an LRUCache which attempts
- * to maintain a size equal or less than its fSpaceLimit
- * by removing the least recently used elements.
- *
- * The cache will remove elements which successfully close and all - * elements which are explicitly removed. - * - *
If the cache cannot remove enough old elements to add new elements
- * it will grow beyond fSpaceLimit. Later, it will attempt to
- * shink back to the maximum space limit.
- *
- * The method close should attempt to close the element. If
- * the element is successfully closed it will return true and the element will
- * be removed from the cache. Otherwise the element will remain in the cache.
- *
- *
The cache implicitly attempts shrinks on calls to putand
- * setSpaceLimit. Explicitly calling the shrink method
- * will also cause the cache to attempt to shrink.
- *
- *
The cache calculates the used space of all elements which implement
- * ILRUCacheable. All other elements are assumed to be of size one.
- *
- *
Use the #peek(Object) and #disableTimestamps() method to
- * circumvent the timestamp feature of the cache. This feature is intended to be used
- * only when the #close(LRUCacheEntry) method causes changes to the cache.
- * For example, if a parent closes its children when #close(LRUCacheEntry) is called,
- * it should be careful not to change the LRU linked list. It can be sure it is not causing
- * problems by calling #peek(Object) instead of #get(Object) method.
- *
- * @see LRUCache
+ * The OverflowingLRUCache is an LRUCache which attempts to
+ * maintain a size equal or less than its fSpaceLimit by removing
+ * the least recently used elements.
+ *
+ *
+ * The cache will remove elements which successfully close and all elements + * which are explicitly removed. + * + *
+ * If the cache cannot remove enough old elements to add new elements it will
+ * grow beyond fSpaceLimit. Later, it will attempt to shink back
+ * to the maximum space limit.
+ *
+ * The method close should attempt to close the element. If the
+ * element is successfully closed it will return true and the element will be
+ * removed from the cache. Otherwise the element will remain in the cache.
+ *
+ *
+ * The cache implicitly attempts shrinks on calls to putand
+ * setSpaceLimit. Explicitly calling the shrink
+ * method will also cause the cache to attempt to shrink.
+ *
+ *
+ * The cache calculates the used space of all elements which implement
+ * ILRUCacheable. All other elements are assumed to be of size
+ * one.
+ *
+ *
+ * Use the #peek(Object) and #disableTimestamps()
+ * method to circumvent the timestamp feature of the cache. This feature is
+ * intended to be used only when the #close(LRUCacheEntry) method
+ * causes changes to the cache. For example, if a parent closes its children
+ * when #close(LRUCacheEntry) is called, it should be careful
+ * not to change the LRU linked list. It can be sure it is not causing problems
+ * by calling #peek(Object) instead of #get(Object)
+ * method.
+ *
+ * @see LRUCache
*/
public abstract class OverflowingLRUCache extends LRUCache {
/**
* Indicates if the cache has been over filled and by how much.
*/
protected int fOverflow = 0;
+
/**
- * Indicates whether or not timestamps should be updated
+ * Indicates whether or not timestamps should be updated
*/
protected boolean fTimestampsOn = true;
+
/**
- * Indicates how much space should be reclaimed when the cache overflows.
- * Inital load factor of one third.
+ * Indicates how much space should be reclaimed when the cache overflows.
+ * Inital load factor of one third.
*/
protected double fLoadFactor = 0.333;
-/**
- * Creates a OverflowingLRUCache.
- * @param size Size limit of cache.
- */
-public OverflowingLRUCache(int size) {
- this(size, 0);
-}
-/**
- * Creates a OverflowingLRUCache.
- * @param size Size limit of cache.
- * @param overflow Size of the overflow.
- */
-public OverflowingLRUCache(int size, int overflow) {
- super(size);
- fOverflow = overflow;
-}
+
+ /**
+ * Creates a OverflowingLRUCache.
+ *
+ * @param size
+ * Size limit of cache.
+ */
+ public OverflowingLRUCache(int size) {
+ this(size, 0);
+ }
+
+ /**
+ * Creates a OverflowingLRUCache.
+ *
+ * @param size
+ * Size limit of cache.
+ * @param overflow
+ * Size of the overflow.
+ */
+ public OverflowingLRUCache(int size, int overflow) {
+ super(size);
+ fOverflow = overflow;
+ }
+
/**
* Returns a new cache containing the same contents.
- *
+ *
* @return New copy of this object.
*/
public Object clone() {
-
- OverflowingLRUCache newCache = (OverflowingLRUCache)newInstance(fSpaceLimit, fOverflow);
+
+ OverflowingLRUCache newCache = (OverflowingLRUCache) newInstance(
+ fSpaceLimit, fOverflow);
LRUCacheEntry qEntry;
-
+
/* Preserve order of entries by copying from oldest to newest */
qEntry = this.fEntryQueueTail;
while (qEntry != null) {
- newCache.privateAdd (qEntry._fKey, qEntry._fValue, qEntry._fSpace);
+ newCache.privateAdd(qEntry._fKey, qEntry._fValue, qEntry._fSpace);
qEntry = qEntry._fPrevious;
}
return newCache;
}
-/**
- * Returns true if the element is successfully closed and
- * removed from the cache, otherwise false.
- *
- *
NOTE: this triggers an external remove from the cache - * by closing the obejct. - * - */ -protected abstract boolean close(LRUCacheEntry entry); + + /** + * Returns true if the element is successfully closed and removed from the + * cache, otherwise false. + * + *
+ * NOTE: this triggers an external remove from the cache by closing the
+ * obejct.
+ *
+ */
+ protected abstract boolean close(LRUCacheEntry entry);
+
/**
- * Returns an enumerator of the values in the cache with the most
- * recently used first.
+ * Returns an enumerator of the values in the cache with the most recently
+ * used first.
*/
public Enumeration elements() {
if (fEntryQueue == null)
return new LRUCacheEnumerator(null);
- LRUCacheEnumerator.LRUEnumeratorElement head =
- new LRUCacheEnumerator.LRUEnumeratorElement(fEntryQueue._fValue);
+ LRUCacheEnumerator.LRUEnumeratorElement head = new LRUCacheEnumerator.LRUEnumeratorElement(
+ fEntryQueue._fValue);
LRUCacheEntry currentEntry = fEntryQueue._fNext;
LRUCacheEnumerator.LRUEnumeratorElement currentElement = head;
- while(currentEntry != null) {
- currentElement.fNext = new LRUCacheEnumerator.LRUEnumeratorElement(currentEntry._fValue);
+ while (currentEntry != null) {
+ currentElement.fNext = new LRUCacheEnumerator.LRUEnumeratorElement(
+ currentEntry._fValue);
currentElement = currentElement.fNext;
-
+
currentEntry = currentEntry._fNext;
}
return new LRUCacheEnumerator(head);
}
+
public double fillingRatio() {
return (fCurrentSpace + fOverflow) * 100.0 / fSpaceLimit;
}
+
/**
- * For internal testing only.
- * This method exposed only for testing purposes!
- *
+ * For internal testing only. This method exposed only for testing purposes!
+ *
* @return Hashtable of entries
*/
public java.util.Hashtable getEntryTable() {
return fEntryTable;
}
-/**
- * Returns the load factor for the cache. The load factor determines how
- * much space is reclaimed when the cache exceeds its space limit.
- * @return double
- */
-public double getLoadFactor() {
- return fLoadFactor;
-}
+
/**
- * @return The space by which the cache has overflown.
+ * Returns the load factor for the cache. The load factor determines how
+ * much space is reclaimed when the cache exceeds its space limit.
+ *
+ * @return double
+ */
+ public double getLoadFactor() {
+ return fLoadFactor;
+ }
+
+ /**
+ * @return The space by which the cache has overflown.
*/
public int getOverflow() {
return fOverflow;
}
+
/**
- * Ensures there is the specified amount of free space in the receiver,
- * by removing old entries if necessary. Returns true if the requested space was
- * made available, false otherwise. May not be able to free enough space
+ * Ensures there is the specified amount of free space in the receiver, by
+ * removing old entries if necessary. Returns true if the requested space
+ * was made available, false otherwise. May not be able to free enough space
* since some elements cannot be removed until they are saved.
- *
- * @param space Amount of space to free up
+ *
+ * @param space
+ * Amount of space to free up
*/
protected boolean makeSpace(int space) {
-
+
int limit = fSpaceLimit;
if (fOverflow == 0) {
/* if space is already available */
@@ -167,223 +196,251 @@ public double getLoadFactor() {
return true;
}
}
-
+
/* Free up space by removing oldest entries */
- int spaceNeeded = (int)((1 - fLoadFactor) * fSpaceLimit);
+ int spaceNeeded = (int) ((1 - fLoadFactor) * fSpaceLimit);
spaceNeeded = (spaceNeeded > space) ? spaceNeeded : space;
LRUCacheEntry entry = fEntryQueueTail;
-
+
while (fCurrentSpace + spaceNeeded > limit && entry != null) {
this.privateRemoveEntry(entry, false, false);
entry = entry._fPrevious;
}
-
+
/* check again, since we may have aquired enough space */
if (fCurrentSpace + space <= limit) {
fOverflow = 0;
return true;
}
-
+
/* update fOverflow */
fOverflow = fCurrentSpace + space - limit;
return false;
}
+
/**
* Returns a new instance of the reciever.
*/
protected abstract LRUCache newInstance(int size, int overflow);
+
/**
- * Answers the value in the cache at the given key.
- * If the value is not in the cache, returns null
- *
+ * Answers the value in the cache at the given key. If the value is not in
+ * the cache, returns null
+ *
* This function does not modify timestamps.
*/
public Object peek(Object key) {
-
+
LRUCacheEntry entry = (LRUCacheEntry) fEntryTable.get(key);
if (entry == null) {
return null;
}
return entry._fValue;
}
-/**
- * For testing purposes only
- */
-public void printStats() {
- int forwardListLength = 0;
- LRUCacheEntry entry = fEntryQueue;
- while(entry != null) {
- forwardListLength++;
- entry = entry._fNext;
- }
- System.out.println("Forward length: " + forwardListLength); //$NON-NLS-1$
-
- int backwardListLength = 0;
- entry = fEntryQueueTail;
- while(entry != null) {
- backwardListLength++;
- entry = entry._fPrevious;
- }
- System.out.println("Backward length: " + backwardListLength); //$NON-NLS-1$
-
- Enumeration keys = fEntryTable.keys();
- class Temp {
- public Class fClass;
- public int fCount;
- public Temp(Class aClass) {
- fClass = aClass;
- fCount = 1;
+
+ /**
+ * For testing purposes only
+ */
+ public void printStats() {
+ int forwardListLength = 0;
+ LRUCacheEntry entry = fEntryQueue;
+ while (entry != null) {
+ forwardListLength++;
+ entry = entry._fNext;
}
- public String toString() {
- return "Class: " + fClass + " has " + fCount + " entries."; //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-1$
+ System.out.println("Forward length: " + forwardListLength); //$NON-NLS-1$
+
+ int backwardListLength = 0;
+ entry = fEntryQueueTail;
+ while (entry != null) {
+ backwardListLength++;
+ entry = entry._fPrevious;
}
- }
- java.util.HashMap h = new java.util.HashMap();
- while(keys.hasMoreElements()) {
- entry = (LRUCacheEntry)fEntryTable.get(keys.nextElement());
- Class key = entry._fValue.getClass();
- Temp t = (Temp)h.get(key);
- if (t == null) {
- h.put(key, new Temp(key));
- } else {
- t.fCount++;
+ System.out.println("Backward length: " + backwardListLength); //$NON-NLS-1$
+
+ Enumeration keys = fEntryTable.keys();
+ class Temp {
+ public Class fClass;
+
+ public int fCount;
+
+ public Temp(Class aClass) {
+ fClass = aClass;
+ fCount = 1;
+ }
+
+ public String toString() {
+ return "Class: " + fClass + " has " + fCount + " entries."; //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-1$
+ }
+ }
+ java.util.HashMap h = new java.util.HashMap();
+ while (keys.hasMoreElements()) {
+ entry = (LRUCacheEntry) fEntryTable.get(keys.nextElement());
+ Class key = entry._fValue.getClass();
+ Temp t = (Temp) h.get(key);
+ if (t == null) {
+ h.put(key, new Temp(key));
+ } else {
+ t.fCount++;
+ }
}
- }
- for (Iterator iter = h.keySet().iterator(); iter.hasNext();){
- System.out.println(h.get(iter.next()));
+ for (Iterator iter = h.keySet().iterator(); iter.hasNext();) {
+ System.out.println(h.get(iter.next()));
+ }
}
-}
+
/**
- * Removes the entry from the entry queue.
- * Calls privateRemoveEntry with the external functionality enabled.
- *
- * @param shuffle indicates whether we are just shuffling the queue
- * (in which case, the entry table is not modified).
+ * Removes the entry from the entry queue. Calls
+ * privateRemoveEntry with the external functionality
+ * enabled.
+ *
+ * @param shuffle
+ * indicates whether we are just shuffling the queue (in which
+ * case, the entry table is not modified).
*/
- protected void privateRemoveEntry (LRUCacheEntry entry, boolean shuffle) {
+ protected void privateRemoveEntry(LRUCacheEntry entry, boolean shuffle) {
privateRemoveEntry(entry, shuffle, true);
}
-/**
- * Removes the entry from the entry queue. If external is true, the entry is removed
- * without checking if it can be removed. It is assumed that the client has already closed
- * the element it is trying to remove (or will close it promptly).
- *
- * If external is false, and the entry could not be closed, it is not removed and the
- * pointers are not changed.
- *
- * @param shuffle indicates whether we are just shuffling the queue
- * (in which case, the entry table is not modified).
- */
-protected void privateRemoveEntry(LRUCacheEntry entry, boolean shuffle, boolean external) {
- if (!shuffle) {
- if (external) {
- fEntryTable.remove(entry._fKey);
- fCurrentSpace -= entry._fSpace;
- privateNotifyDeletionFromCache(entry);
- } else {
- if (!close(entry)) return;
- // buffer close will recursively call #privateRemoveEntry with external==true
- // thus entry will already be removed if reaching this point.
- if (fEntryTable.get(entry._fKey) == null){
- return;
- } else {
- // basic removal
- fEntryTable.remove(entry._fKey);
+ /**
+ * Removes the entry from the entry queue. If external is true, the
+ * entry is removed without checking if it can be removed. It is assumed
+ * that the client has already closed the element it is trying to remove (or
+ * will close it promptly).
+ *
+ * If external is false, and the entry could not be closed, it is
+ * not removed and the pointers are not changed.
+ *
+ * @param shuffle
+ * indicates whether we are just shuffling the queue (in which
+ * case, the entry table is not modified).
+ */
+ protected void privateRemoveEntry(LRUCacheEntry entry, boolean shuffle,
+ boolean external) {
+
+ if (!shuffle) {
+ if (external) {
+ fEntryTable.remove(entry._fKey);
fCurrentSpace -= entry._fSpace;
privateNotifyDeletionFromCache(entry);
+ } else {
+ if (!close(entry))
+ return;
+ // buffer close will recursively call #privateRemoveEntry with
+ // external==true
+ // thus entry will already be removed if reaching this point.
+ if (fEntryTable.get(entry._fKey) == null) {
+ return;
+ } else {
+ // basic removal
+ fEntryTable.remove(entry._fKey);
+ fCurrentSpace -= entry._fSpace;
+ privateNotifyDeletionFromCache(entry);
+ }
}
}
+ LRUCacheEntry previous = entry._fPrevious;
+ LRUCacheEntry next = entry._fNext;
+
+ /* if this was the first entry */
+ if (previous == null) {
+ fEntryQueue = next;
+ } else {
+ previous._fNext = next;
+ }
+ /* if this was the last entry */
+ if (next == null) {
+ fEntryQueueTail = previous;
+ } else {
+ next._fPrevious = previous;
+ }
}
- LRUCacheEntry previous = entry._fPrevious;
- LRUCacheEntry next = entry._fNext;
-
- /* if this was the first entry */
- if (previous == null) {
- fEntryQueue = next;
- } else {
- previous._fNext = next;
- }
- /* if this was the last entry */
- if (next == null) {
- fEntryQueueTail = previous;
- } else {
- next._fPrevious = previous;
- }
-}
+
/**
* Sets the value in the cache at the given key. Returns the value.
- *
- * @param key Key of object to add.
- * @param value Value of object to add.
+ *
+ * @param key
+ * Key of object to add.
+ * @param value
+ * Value of object to add.
* @return added value.
*/
public Object put(Object key, Object value) {
/* attempt to rid ourselves of the overflow, if there is any */
if (fOverflow > 0)
shrink();
-
+
/* Check whether there's an entry in the cache */
- int newSpace = spaceFor (key, value);
- LRUCacheEntry entry = (LRUCacheEntry) fEntryTable.get (key);
-
+ int newSpace = spaceFor(key, value);
+ LRUCacheEntry entry = (LRUCacheEntry) fEntryTable.get(key);
+
if (entry != null) {
-
+
/**
- * Replace the entry in the cache if it would not overflow
- * the cache. Otherwise flush the entry and re-add it so as
- * to keep cache within budget
+ * Replace the entry in the cache if it would not overflow the
+ * cache. Otherwise flush the entry and re-add it so as to keep
+ * cache within budget
*/
int oldSpace = entry._fSpace;
int newTotal = fCurrentSpace - oldSpace + newSpace;
if (newTotal <= fSpaceLimit) {
- updateTimestamp (entry);
+ updateTimestamp(entry);
entry._fValue = value;
entry._fSpace = newSpace;
fCurrentSpace = newTotal;
fOverflow = 0;
return value;
} else {
- privateRemoveEntry (entry, false, false);
+ privateRemoveEntry(entry, false, false);
}
}
-
+
// attempt to make new space
makeSpace(newSpace);
-
+
// add without worring about space, it will
// be handled later in a makeSpace call
- privateAdd (key, value, newSpace);
-
+ privateAdd(key, value, newSpace);
+
return value;
}
+
/**
- * Removes and returns the value in the cache for the given key.
- * If the key is not in the cache, returns null.
- *
- * @param key Key of object to remove from cache.
+ * Removes and returns the value in the cache for the given key. If the key
+ * is not in the cache, returns null.
+ *
+ * @param key
+ * Key of object to remove from cache.
* @return Value removed from cache.
*/
public Object remove(Object key) {
return removeKey(key);
}
-/**
- * Sets the load factor for the cache. The load factor determines how
- * much space is reclaimed when the cache exceeds its space limit.
- * @param newLoadFactor double
- * @throws IllegalArgumentException when the new load factor is not in (0.0, 1.0]
- */
-public void setLoadFactor(double newLoadFactor) throws IllegalArgumentException {
- if(newLoadFactor <= 1.0 && newLoadFactor > 0.0)
- fLoadFactor = newLoadFactor;
- else
- throw new IllegalArgumentException(Util.bind("cache.invalidLoadFactor")); //$NON-NLS-1$
-}
+
+ /**
+ * Sets the load factor for the cache. The load factor determines how much
+ * space is reclaimed when the cache exceeds its space limit.
+ *
+ * @param newLoadFactor
+ * double
+ * @throws IllegalArgumentException
+ * when the new load factor is not in (0.0, 1.0]
+ */
+ public void setLoadFactor(double newLoadFactor)
+ throws IllegalArgumentException {
+ if (newLoadFactor <= 1.0 && newLoadFactor > 0.0)
+ fLoadFactor = newLoadFactor;
+ else
+ throw new IllegalArgumentException(Util
+ .bind("cache.invalidLoadFactor")); //$NON-NLS-1$
+ }
+
/**
* Sets the maximum amount of space that the cache can store
- *
- * @param limit Number of units of cache space
+ *
+ * @param limit
+ * Number of units of cache space
*/
public void setSpaceLimit(int limit) {
if (limit < fSpaceLimit) {
@@ -391,37 +448,40 @@ public void setLoadFactor(double newLoadFactor) throws IllegalArgumentException
}
fSpaceLimit = limit;
}
+
/**
- * Attempts to shrink the cache if it has overflown.
- * Returns true if the cache shrinks to less than or equal to fSpaceLimit.
+ * Attempts to shrink the cache if it has overflown. Returns true if the
+ * cache shrinks to less than or equal to fSpaceLimit.
*/
public boolean shrink() {
if (fOverflow > 0)
return makeSpace(0);
return true;
}
-/**
- * Returns a String that represents the value of this object. This method
- * is for debugging purposes only.
- */
-public String toString() {
- return
- "OverflowingLRUCache " + this.fillingRatio() + "% full\n" + //$NON-NLS-1$ //$NON-NLS-2$
- this.toStringContents();
-}
-/**
- * Updates the timestamp for the given entry, ensuring that the queue is
- * kept in correct order. The entry must exist.
- *
- *
This method will do nothing if timestamps have been disabled. - */ -protected void updateTimestamp(LRUCacheEntry entry) { - if (fTimestampsOn) { - entry._fTimestamp = fTimestampCounter++; - if (fEntryQueue != entry) { - this.privateRemoveEntry(entry, true); - this.privateAddEntry(entry, true); + + /** + * Returns a String that represents the value of this object. This method is + * for debugging purposes only. + */ + public String toString() { + return "OverflowingLRUCache " + this.fillingRatio() + "% full\n" + //$NON-NLS-1$ //$NON-NLS-2$ + this.toStringContents(); + } + + /** + * Updates the timestamp for the given entry, ensuring that the queue is + * kept in correct order. The entry must exist. + * + *
+ * This method will do nothing if timestamps have been disabled. + */ + protected void updateTimestamp(LRUCacheEntry entry) { + if (fTimestampsOn) { + entry._fTimestamp = fTimestampCounter++; + if (fEntryQueue != entry) { + this.privateRemoveEntry(entry, true); + this.privateAddEntry(entry, true); + } } } } -}