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