net.sourceforge.phpeclipse/src/net/sourceforge/phpdt/internal/core/util/LRUCache.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.util;
  12
  13 import java.util.Enumeration;
  14 import java.util.Hashtable;
  15
  16 /**
  17  * The <code>LRUCache</code> is a hashtable that stores a finite number of elements.
  18  * When an attempt is made to add values to a full cache, the least recently used values
  19  * in the cache are discarded to make room for the new values as necessary.
  20  *
  21  * <p>The data structure is based on the LRU virtual memory paging scheme.
  22  *
  23  * <p>Objects can take up a variable amount of cache space by implementing
  24  * the <code>ILRUCacheable</code> interface.
  25  *
  26  * <p>This implementation is NOT thread-safe.  Synchronization wrappers would
  27  * have to be added to ensure atomic insertions and deletions from the cache.
  28  *
  29  * @see org.eclipse.jdt.internal.core.util.ILRUCacheable
  30  */
  31 public class LRUCache implements Cloneable {
  32
  33         /**
  34          * This type is used internally by the LRUCache to represent entries
  35          * stored in the cache.
  36          * It is static because it does not require a pointer to the cache
  37          * which contains it.
  38          *
  39          * @see LRUCache
  40          */
  41         protected static class LRUCacheEntry {
  42
  43                 /**
  44                  * Hash table key
  45                  */
  46                 public Object _fKey;
  47
  48                 /**
  49                  * Hash table value (an LRUCacheEntry object)
  50                  */
  51                 public Object _fValue;
  52
  53                 /**
  54                  * Time value for queue sorting
  55                  */
  56                 public int _fTimestamp;
  57
  58                 /**
  59                  * Cache footprint of this entry
  60                  */
  61                 public int _fSpace;
  62
  63                 /**
  64                  * Previous entry in queue
  65                  */
  66                 public LRUCacheEntry _fPrevious;
  67
  68                 /**
  69                  * Next entry in queue
  70                  */
  71                 public LRUCacheEntry _fNext;
  72
  73                 /**
  74                  * Creates a new instance of the receiver with the provided values
  75                  * for key, value, and space.
  76                  */
  77                 public LRUCacheEntry (Object key, Object value, int space) {
  78                         _fKey = key;
  79                         _fValue = value;
  80                         _fSpace = space;
  81                 }
  82
  83                 /**
  84                  * Returns a String that represents the value of this object.
  85                  */
  86                 public String toString() {
  87
  88                         return "LRUCacheEntry [" + _fKey + "-->" + _fValue + "]"; //$NON-NLS-3$ //$NON-NLS-1$ //$NON-NLS-2$
  89                 }
  90         }
  91
  92         /**
  93          * Amount of cache space used so far
  94          */
  95         protected int fCurrentSpace;
  96
  97         /**
  98          * Maximum space allowed in cache
  99          */
 100         protected int fSpaceLimit;
 101
 102         /**
 103          * Counter for handing out sequential timestamps
 104          */
 105         protected int   fTimestampCounter;
 106
 107         /**
 108          * Hash table for fast random access to cache entries
 109          */
 110         protected Hashtable fEntryTable;
 111
 112         /**
 113          * Start of queue (most recently used entry)
 114          */
 115         protected LRUCacheEntry fEntryQueue;
 116
 117         /**
 118          * End of queue (least recently used entry)
 119          */
 120         protected LRUCacheEntry fEntryQueueTail;
 121
 122         /**
 123          * Default amount of space in the cache
 124          */
 125         protected static final int DEFAULT_SPACELIMIT = 100;
 126         /**
 127          * Creates a new cache.  Size of cache is defined by
 128          * <code>DEFAULT_SPACELIMIT</code>.
 129          */
 130         public LRUCache() {
 131
 132                 this(DEFAULT_SPACELIMIT);
 133         }
 134         /**
 135          * Creates a new cache.
 136          * @param size Size of Cache
 137          */
 138         public LRUCache(int size) {
 139
 140                 fTimestampCounter = fCurrentSpace = 0;
 141                 fEntryQueue = fEntryQueueTail = null;
 142                 fEntryTable = new Hashtable(size);
 143                 fSpaceLimit = size;
 144         }
 145         /**
 146          * Returns a new cache containing the same contents.
 147          *
 148          * @return New copy of object.
 149          */
 150         public Object clone() {
 151
 152                 LRUCache newCache = newInstance(fSpaceLimit);
 153                 LRUCacheEntry qEntry;
 154
 155                 /* Preserve order of entries by copying from oldest to newest */
 156                 qEntry = this.fEntryQueueTail;
 157                 while (qEntry != null) {
 158                         newCache.privateAdd (qEntry._fKey, qEntry._fValue, qEntry._fSpace);
 159                         qEntry = qEntry._fPrevious;
 160                 }
 161                 return newCache;
 162         }
 163         /**
 164          * Flushes all entries from the cache.
 165          */
 166         public void flush() {
 167
 168                 fCurrentSpace = 0;
 169                 LRUCacheEntry entry = fEntryQueueTail; // Remember last entry
 170                 fEntryTable = new Hashtable();  // Clear it out
 171                 fEntryQueue = fEntryQueueTail = null;
 172                 while (entry != null) {  // send deletion notifications in LRU order
 173                         privateNotifyDeletionFromCache(entry);
 174                         entry = entry._fPrevious;
 175                 }
 176         }
 177         /**
 178          * Flushes the given entry from the cache.  Does nothing if entry does not
 179          * exist in cache.
 180          *
 181          * @param key Key of object to flush
 182          */
 183         public void flush (Object key) {
 184
 185                 LRUCacheEntry entry;
 186
 187                 entry = (LRUCacheEntry) fEntryTable.get(key);
 188
 189                 /* If entry does not exist, return */
 190                 if (entry == null) return;
 191
 192                 this.privateRemoveEntry (entry, false);
 193         }
 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          * @param key Hash table key of object to retrieve
 199          * @return Retreived object, or null if object does not exist
 200          */
 201         public Object get(Object key) {
 202
 203                 LRUCacheEntry entry = (LRUCacheEntry) fEntryTable.get(key);
 204                 if (entry == null) {
 205                         return null;
 206                 }
 207
 208                 this.updateTimestamp (entry);
 209                 return entry._fValue;
 210         }
 211         /**
 212          * Returns the amount of space that is current used in the cache.
 213          */
 214         public int getCurrentSpace() {
 215                 return fCurrentSpace;
 216         }
 217         /**
 218          * Returns the maximum amount of space available in the cache.
 219          */
 220         public int getSpaceLimit() {
 221                 return fSpaceLimit;
 222         }
 223         /**
 224          * Returns an Enumeration of the keys currently in the cache.
 225          */
 226         public Enumeration keys() {
 227
 228                 return fEntryTable.keys();
 229         }
 230         /**
 231          * Returns an enumeration that iterates over all the keys and values
 232          * currently in the cache.
 233          */
 234         public ICacheEnumeration keysAndValues() {
 235                 return new ICacheEnumeration() {
 236
 237                         Enumeration fValues = fEntryTable.elements();
 238                         LRUCacheEntry fEntry;
 239
 240                         public boolean hasMoreElements() {
 241                                 return fValues.hasMoreElements();
 242                         }
 243
 244                         public Object nextElement() {
 245                                 fEntry = (LRUCacheEntry) fValues.nextElement();
 246                                 return fEntry._fKey;
 247                         }
 248
 249                         public Object getValue() {
 250                                 if (fEntry == null) {
 251                                         throw new java.util.NoSuchElementException();
 252                                 }
 253                                 return fEntry._fValue;
 254                         }
 255                 };
 256         }
 257         /**
 258          * Ensures there is the specified amount of free space in the receiver,
 259          * by removing old entries if necessary.  Returns true if the requested space was
 260          * made available, false otherwise.
 261          *
 262          * @param space Amount of space to free up
 263          */
 264         protected boolean makeSpace (int space) {
 265
 266                 int limit;
 267
 268                 limit = this.getSpaceLimit();
 269
 270                 /* if space is already available */
 271                 if (fCurrentSpace + space <= limit) {
 272                         return true;
 273                 }
 274
 275                 /* if entry is too big for cache */
 276                 if (space > limit) {
 277                         return false;
 278                 }
 279
 280                 /* Free up space by removing oldest entries */
 281                 while (fCurrentSpace + space > limit && fEntryQueueTail != null) {
 282                         this.privateRemoveEntry (fEntryQueueTail, false);
 283                 }
 284                 return true;
 285         }
 286         /**
 287          * Returns a new LRUCache instance
 288          */
 289         protected LRUCache newInstance(int size) {
 290                 return new LRUCache(size);
 291         }
 292         /**
 293          * Adds an entry for the given key/value/space.
 294          */
 295         protected void privateAdd (Object key, Object value, int space) {
 296
 297                 LRUCacheEntry entry;
 298
 299                 entry = new LRUCacheEntry(key, value, space);
 300                 this.privateAddEntry (entry, false);
 301         }
 302         /**
 303          * Adds the given entry from the receiver.
 304          * @param shuffle Indicates whether we are just shuffling the queue
 305          * (in which case, the entry table is not modified).
 306          */
 307         protected void privateAddEntry (LRUCacheEntry entry, boolean shuffle) {
 308
 309                 if (!shuffle) {
 310                         fEntryTable.put (entry._fKey, entry);
 311                         fCurrentSpace += entry._fSpace;
 312                 }
 313
 314                 entry._fTimestamp = fTimestampCounter++;
 315                 entry._fNext = this.fEntryQueue;
 316                 entry._fPrevious = null;
 317
 318                 if (fEntryQueue == null) {
 319                         /* this is the first and last entry */
 320                         fEntryQueueTail = entry;
 321                 } else {
 322                         fEntryQueue._fPrevious = entry;
 323                 }
 324
 325                 fEntryQueue = entry;
 326         }
 327         /**
 328          * An entry has been removed from the cache, for example because it has
 329          * fallen off the bottom of the LRU queue.
 330          * Subclasses could over-ride this to implement a persistent cache below the LRU cache.
 331          */
 332         protected void privateNotifyDeletionFromCache(LRUCacheEntry entry) {
 333                 // Default is NOP.
 334         }
 335         /**
 336          * Removes the entry from the entry queue.
 337          * @param shuffle indicates whether we are just shuffling the queue
 338          * (in which case, the entry table is not modified).
 339          */
 340         protected void privateRemoveEntry (LRUCacheEntry entry, boolean shuffle) {
 341
 342                 LRUCacheEntry previous, next;
 343
 344                 previous = entry._fPrevious;
 345                 next = entry._fNext;
 346
 347                 if (!shuffle) {
 348                         fEntryTable.remove(entry._fKey);
 349                         fCurrentSpace -= entry._fSpace;
 350                         privateNotifyDeletionFromCache(entry);
 351                 }
 352
 353                 /* if this was the first entry */
 354                 if (previous == null) {
 355                         fEntryQueue = next;
 356                 } else {
 357                         previous._fNext = next;
 358                 }
 359
 360                 /* if this was the last entry */
 361                 if (next == null) {
 362                         fEntryQueueTail = previous;
 363                 } else {
 364                         next._fPrevious = previous;
 365                 }
 366         }
 367         /**
 368          * Sets the value in the cache at the given key. Returns the value.
 369          *
 370          * @param key Key of object to add.
 371          * @param value Value of object to add.
 372          * @return added value.
 373          */
 374         public Object put(Object key, Object value) {
 375
 376                 int newSpace, oldSpace, newTotal;
 377                 LRUCacheEntry entry;
 378
 379                 /* Check whether there's an entry in the cache */
 380                 newSpace = spaceFor (key, value);
 381                 entry = (LRUCacheEntry) fEntryTable.get (key);
 382
 383                 if (entry != null) {
 384
 385                         /**
 386                          * Replace the entry in the cache if it would not overflow
 387                          * the cache.  Otherwise flush the entry and re-add it so as
 388                          * to keep cache within budget
 389                          */
 390                         oldSpace = entry._fSpace;
 391                         newTotal = getCurrentSpace() - oldSpace + newSpace;
 392                         if (newTotal <= getSpaceLimit()) {
 393                                 updateTimestamp (entry);
 394                                 entry._fValue = value;
 395                                 entry._fSpace = newSpace;
 396                                 this.fCurrentSpace = newTotal;
 397                                 return value;
 398                         } else {
 399                                 privateRemoveEntry (entry, false);
 400                         }
 401                 }
 402                 if (makeSpace(newSpace)) {
 403                         privateAdd (key, value, newSpace);
 404                 }
 405                 return value;
 406         }
 407         /**
 408          * Removes and returns the value in the cache for the given key.
 409          * If the key is not in the cache, returns null.
 410          *
 411          * @param key Key of object to remove from cache.
 412          * @return Value removed from cache.
 413          */
 414         public Object removeKey (Object key) {
 415
 416                 LRUCacheEntry entry = (LRUCacheEntry) fEntryTable.get(key);
 417                 if (entry == null) {
 418                         return null;
 419                 }
 420                 Object value = entry._fValue;
 421                 this.privateRemoveEntry (entry, false);
 422                 return value;
 423         }
 424         /**
 425          * Sets the maximum amount of space that the cache can store
 426          *
 427          * @param limit Number of units of cache space
 428          */
 429         public void setSpaceLimit(int limit) {
 430                 if (limit < fSpaceLimit) {
 431                         makeSpace(fSpaceLimit - limit);
 432                 }
 433                 fSpaceLimit = limit;
 434         }
 435         /**
 436          * Returns the space taken by the given key and value.
 437          */
 438         protected int spaceFor (Object key, Object value) {
 439
 440                 if (value instanceof ILRUCacheable) {
 441                         return ((ILRUCacheable) value).getCacheFootprint();
 442                 } else {
 443                         return 1;
 444                 }
 445         }
 446 /**
 447  * Returns a String that represents the value of this object.  This method
 448  * is for debugging purposes only.
 449  */
 450 public String toString() {
 451         return
 452                 "LRUCache " + (fCurrentSpace * 100.0 / fSpaceLimit) + "% full\n" + //$NON-NLS-1$ //$NON-NLS-2$
 453                 this.toStringContents();
 454 }
 455 /**
 456  * Returns a String that represents the contents of this object.  This method
 457  * is for debugging purposes only.
 458  */
 459 protected String toStringContents() {
 460         StringBuffer result = new StringBuffer();
 461         int length = fEntryTable.size();
 462         Object[] unsortedKeys = new Object[length];
 463         String[] unsortedToStrings = new String[length];
 464         Enumeration e = this.keys();
 465         for (int i = 0; i < length; i++) {
 466                 Object key = e.nextElement();
 467                 unsortedKeys[i] = key;
 468                 unsortedToStrings[i] =
 469                         (key instanceof net.sourceforge.phpdt.internal.core.JavaElement) ?
 470                                 ((net.sourceforge.phpdt.internal.core.JavaElement)key).getElementName() :
 471                                 key.toString();
 472         }
 473         ToStringSorter sorter = new ToStringSorter();
 474         sorter.sort(unsortedKeys, unsortedToStrings);
 475         for (int i = 0; i < length; i++) {
 476                 String toString = sorter.sortedStrings[i];
 477                 Object value = this.get(sorter.sortedObjects[i]);
 478                 result.append(toString);
 479                 result.append(" -> "); //$NON-NLS-1$
 480                 result.append(value);
 481                 result.append("\n"); //$NON-NLS-1$
 482         }
 483         return result.toString();
 484 }
 485         /**
 486          * Updates the timestamp for the given entry, ensuring that the queue is
 487          * kept in correct order.  The entry must exist
 488          */
 489         protected void updateTimestamp (LRUCacheEntry entry) {
 490
 491                 entry._fTimestamp = fTimestampCounter++;
 492                 if (fEntryQueue != entry) {
 493                         this.privateRemoveEntry (entry, true);
 494                         this.privateAddEntry (entry, true);
 495                 }
 496                 return;
 497         }
 498 }