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