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