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