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 import net.sourceforge.phpdt.internal.core.util.Util;
  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) {
 165                         /* if space is already available */
 166                         if (fCurrentSpace + space <= limit) {
 167                                 return true;
 168                         }
 169                 }
 170
 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;
 175
 176                 while (fCurrentSpace + spaceNeeded > limit && entry != null) {
 177                         this.privateRemoveEntry(entry, false, false);
 178                         entry = entry._fPrevious;
 179                 }
 180
 181                 /* check again, since we may have aquired enough space */
 182                 if (fCurrentSpace + space <= limit) {
 183                         fOverflow = 0;
 184                         return true;
 185                 }
 186
 187                 /* update fOverflow */
 188                 fOverflow = fCurrentSpace + space - limit;
 189                 return false;
 190         }
 191         /**
 192          * Returns a new instance of the reciever.
 193          */
 194         protected abstract LRUCache newInstance(int size, int overflow);
 195         /**
 196          * Answers the value in the cache at the given key.
 197          * If the value is not in the cache, returns null
 198          *
 199          * This function does not modify timestamps.
 200          */
 201         public Object peek(Object key) {
 202
 203                 LRUCacheEntry entry = (LRUCacheEntry) fEntryTable.get(key);
 204                 if (entry == null) {
 205                         return null;
 206                 }
 207                 return entry._fValue;
 208         }
 209 /**
 210  * For testing purposes only
 211  */
 212 public void printStats() {
 213         int forwardListLength = 0;
 214         LRUCacheEntry entry = fEntryQueue;
 215         while(entry != null) {
 216                 forwardListLength++;
 217                 entry = entry._fNext;
 218         }
 219         System.out.println("Forward length: " + forwardListLength); //$NON-NLS-1$
 220
 221         int backwardListLength = 0;
 222         entry = fEntryQueueTail;
 223         while(entry != null) {
 224                 backwardListLength++;
 225                 entry = entry._fPrevious;
 226         }
 227         System.out.println("Backward length: " + backwardListLength); //$NON-NLS-1$
 228
 229         Enumeration keys = fEntryTable.keys();
 230         class Temp {
 231                 public Class fClass;
 232                 public int fCount;
 233                 public Temp(Class aClass) {
 234                         fClass = aClass;
 235                         fCount = 1;
 236                 }
 237                 public String toString() {
 238                         return "Class: " + fClass + " has " + fCount + " entries."; //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-1$
 239                 }
 240         }
 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);
 246                 if (t == null) {
 247                         h.put(key, new Temp(key));
 248                 } else {
 249                         t.fCount++;
 250                 }
 251         }
 252
 253         for (Iterator iter = h.keySet().iterator(); iter.hasNext();){
 254                 System.out.println(h.get(iter.next()));
 255         }
 256 }
 257         /**
 258          *      Removes the entry from the entry queue.
 259          *      Calls <code>privateRemoveEntry</code> with the external functionality enabled.
 260          *
 261          * @param shuffle indicates whether we are just shuffling the queue
 262          * (in which case, the entry table is not modified).
 263          */
 264         protected void privateRemoveEntry (LRUCacheEntry entry, boolean shuffle) {
 265                 privateRemoveEntry(entry, shuffle, true);
 266         }
 267 /**
 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).
 271  *
 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.
 274  *
 275  *      @param shuffle indicates whether we are just shuffling the queue
 276  *      (in which case, the entry table is not modified).
 277  */
 278 protected void privateRemoveEntry(LRUCacheEntry entry, boolean shuffle, boolean external) {
 279
 280         if (!shuffle) {
 281                 if (external) {
 282                         fEntryTable.remove(entry._fKey);
 283                         fCurrentSpace -= entry._fSpace;
 284                         privateNotifyDeletionFromCache(entry);
 285                 } else {
 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){
 290                                 return;
 291                         } else {
 292                                 // basic removal
 293                                 fEntryTable.remove(entry._fKey);
 294                                 fCurrentSpace -= entry._fSpace;
 295                                 privateNotifyDeletionFromCache(entry);
 296                         }
 297                 }
 298         }
 299         LRUCacheEntry previous = entry._fPrevious;
 300         LRUCacheEntry next = entry._fNext;
 301
 302         /* if this was the first entry */
 303         if (previous == null) {
 304                 fEntryQueue = next;
 305         } else {
 306                 previous._fNext = next;
 307         }
 308         /* if this was the last entry */
 309         if (next == null) {
 310                 fEntryQueueTail = previous;
 311         } else {
 312                 next._fPrevious = previous;
 313         }
 314 }
 315         /**
 316          * Sets the value in the cache at the given key. Returns the value.
 317          *
 318          * @param key Key of object to add.
 319          * @param value Value of object to add.
 320          * @return added value.
 321          */
 322         public Object put(Object key, Object value) {
 323                 /* attempt to rid ourselves of the overflow, if there is any */
 324                 if (fOverflow > 0)
 325                         shrink();
 326
 327                 /* Check whether there's an entry in the cache */
 328                 int newSpace = spaceFor (key, value);
 329                 LRUCacheEntry entry = (LRUCacheEntry) fEntryTable.get (key);
 330
 331                 if (entry != null) {
 332
 333                         /**
 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
 337                          */
 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;
 345                                 fOverflow = 0;
 346                                 return value;
 347                         } else {
 348                                 privateRemoveEntry (entry, false, false);
 349                         }
 350                 }
 351
 352                 // attempt to make new space
 353                 makeSpace(newSpace);
 354
 355                 // add without worring about space, it will
 356                 // be handled later in a makeSpace call
 357                 privateAdd (key, value, newSpace);
 358
 359                 return value;
 360         }
 361         /**
 362          * Removes and returns the value in the cache for the given key.
 363          * If the key is not in the cache, returns null.
 364          *
 365          * @param key Key of object to remove from cache.
 366          * @return Value removed from cache.
 367          */
 368         public Object remove(Object key) {
 369                 return removeKey(key);
 370         }
 371 /**
 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]
 376  */
 377 public void setLoadFactor(double newLoadFactor) throws IllegalArgumentException {
 378         if(newLoadFactor <= 1.0 && newLoadFactor > 0.0)
 379                 fLoadFactor = newLoadFactor;
 380         else
 381                 throw new IllegalArgumentException(Util.bind("cache.invalidLoadFactor")); //$NON-NLS-1$
 382 }
 383         /**
 384          * Sets the maximum amount of space that the cache can store
 385          *
 386          * @param limit Number of units of cache space
 387          */
 388         public void setSpaceLimit(int limit) {
 389                 if (limit < fSpaceLimit) {
 390                         makeSpace(fSpaceLimit - limit);
 391                 }
 392                 fSpaceLimit = limit;
 393         }
 394         /**
 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>.
 397          */
 398         public boolean shrink() {
 399                 if (fOverflow > 0)
 400                         return makeSpace(0);
 401                 return true;
 402         }
 403 /**
 404  * Returns a String that represents the value of this object.  This method
 405  * is for debugging purposes only.
 406  */
 407 public String toString() {
 408         return
 409                 "OverflowingLRUCache " + this.fillingRatio() + "% full\n" + //$NON-NLS-1$ //$NON-NLS-2$
 410                 this.toStringContents();
 411 }
 412 /**
 413  * Updates the timestamp for the given entry, ensuring that the queue is
 414  * kept in correct order.  The entry must exist.
 415  *
 416  * <p>This method will do nothing if timestamps have been disabled.
 417  */
 418 protected void updateTimestamp(LRUCacheEntry entry) {
 419         if (fTimestampsOn) {
 420                 entry._fTimestamp = fTimestampCounter++;
 421                 if (fEntryQueue != entry) {
 422                         this.privateRemoveEntry(entry, true);
 423                         this.privateAddEntry(entry, true);
 424                 }
 425         }
 426 }
 427 }