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
*/
protected boolean fTimestampsOn = true;
/**
* 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;
}
/**
* Returns a new cache containing the same contents.
*
* @return New copy of this object.
*/
public Object clone() {
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);
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 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);
LRUCacheEntry currentEntry = fEntryQueue._fNext;
LRUCacheEnumerator.LRUEnumeratorElement currentElement = head;
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!
*
* @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.
*/
// 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
* since some elements cannot be removed until they are saved.
*
* @param space
* Amount of space to free up
*/
protected boolean makeSpace(int space) {
int limit = fSpaceLimit;
if (fOverflow == 0) {
/* if space is already available */
if (fCurrentSpace + space <= limit) {
return true;
}
}
/* Free up space by removing oldest entries */
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
*
* 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;
}
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()));
}
}
/**
* 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) {
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);
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;
}
}
/**
* 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.
* @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);
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
*/
int oldSpace = entry._fSpace;
int newTotal = fCurrentSpace - oldSpace + newSpace;
if (newTotal <= fSpaceLimit) {
updateTimestamp(entry);
entry._fValue = value;
entry._fSpace = newSpace;
fCurrentSpace = newTotal;
fOverflow = 0;
return value;
} else {
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);
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.
* @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 maximum amount of space that the cache can store
*
* @param limit
* Number of units of cache space
*/
public void setSpaceLimit(int limit) {
if (limit < fSpaceLimit) {
makeSpace(fSpaceLimit - limit);
}
fSpaceLimit = limit;
}
/**
* 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); } } } }