1/** 2 * $Revision: 1456 $ 3 * $Date: 2005-06-01 22:04:54 -0700 (Wed, 01 Jun 2005) $ 4 * 5 * Copyright 2003-2005 Jive Software. 6 * 7 * All rights reserved. Licensed under the Apache License, Version 2.0 (the "License"); 8 * you may not use this file except in compliance with the License. 9 * You may obtain a copy of the License at 10 * 11 * http://www.apache.org/licenses/LICENSE-2.0 12 * 13 * Unless required by applicable law or agreed to in writing, software 14 * distributed under the License is distributed on an "AS IS" BASIS, 15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 16 * See the License for the specific language governing permissions and 17 * limitations under the License. 18 */ 19 20package org.jivesoftware.smack.util; 21 22import org.jivesoftware.smack.util.collections.AbstractMapEntry; 23 24import java.util.*; 25 26/** 27 * A specialized Map that is size-limited (using an LRU algorithm) and 28 * has an optional expiration time for cache items. The Map is thread-safe.<p> 29 * 30 * The algorithm for cache is as follows: a HashMap is maintained for fast 31 * object lookup. Two linked lists are maintained: one keeps objects in the 32 * order they are accessed from cache, the other keeps objects in the order 33 * they were originally added to cache. When objects are added to cache, they 34 * are first wrapped by a CacheObject which maintains the following pieces 35 * of information:<ul> 36 * <li> A pointer to the node in the linked list that maintains accessed 37 * order for the object. Keeping a reference to the node lets us avoid 38 * linear scans of the linked list. 39 * <li> A pointer to the node in the linked list that maintains the age 40 * of the object in cache. Keeping a reference to the node lets us avoid 41 * linear scans of the linked list.</ul> 42 * <p/> 43 * To get an object from cache, a hash lookup is performed to get a reference 44 * to the CacheObject that wraps the real object we are looking for. 45 * The object is subsequently moved to the front of the accessed linked list 46 * and any necessary cache cleanups are performed. Cache deletion and expiration 47 * is performed as needed. 48 * 49 * @author Matt Tucker 50 */ 51public class Cache<K, V> implements Map<K, V> { 52 53 /** 54 * The map the keys and values are stored in. 55 */ 56 protected Map<K, CacheObject<V>> map; 57 58 /** 59 * Linked list to maintain order that cache objects are accessed 60 * in, most used to least used. 61 */ 62 protected LinkedList lastAccessedList; 63 64 /** 65 * Linked list to maintain time that cache objects were initially added 66 * to the cache, most recently added to oldest added. 67 */ 68 protected LinkedList ageList; 69 70 /** 71 * Maximum number of items the cache will hold. 72 */ 73 protected int maxCacheSize; 74 75 /** 76 * Maximum length of time objects can exist in cache before expiring. 77 */ 78 protected long maxLifetime; 79 80 /** 81 * Maintain the number of cache hits and misses. A cache hit occurs every 82 * time the get method is called and the cache contains the requested 83 * object. A cache miss represents the opposite occurence.<p> 84 * 85 * Keeping track of cache hits and misses lets one measure how efficient 86 * the cache is; the higher the percentage of hits, the more efficient. 87 */ 88 protected long cacheHits, cacheMisses = 0L; 89 90 /** 91 * Create a new cache and specify the maximum size of for the cache in 92 * bytes, and the maximum lifetime of objects. 93 * 94 * @param maxSize the maximum number of objects the cache will hold. -1 95 * means the cache has no max size. 96 * @param maxLifetime the maximum amount of time (in ms) objects can exist in 97 * cache before being deleted. -1 means objects never expire. 98 */ 99 public Cache(int maxSize, long maxLifetime) { 100 if (maxSize == 0) { 101 throw new IllegalArgumentException("Max cache size cannot be 0."); 102 } 103 this.maxCacheSize = maxSize; 104 this.maxLifetime = maxLifetime; 105 106 // Our primary data structure is a hash map. The default capacity of 11 107 // is too small in almost all cases, so we set it bigger. 108 map = new HashMap<K, CacheObject<V>>(103); 109 110 lastAccessedList = new LinkedList(); 111 ageList = new LinkedList(); 112 } 113 114 public synchronized V put(K key, V value) { 115 V oldValue = null; 116 // Delete an old entry if it exists. 117 if (map.containsKey(key)) { 118 oldValue = remove(key, true); 119 } 120 121 CacheObject<V> cacheObject = new CacheObject<V>(value); 122 map.put(key, cacheObject); 123 // Make an entry into the cache order list. 124 // Store the cache order list entry so that we can get back to it 125 // during later lookups. 126 cacheObject.lastAccessedListNode = lastAccessedList.addFirst(key); 127 // Add the object to the age list 128 LinkedListNode ageNode = ageList.addFirst(key); 129 ageNode.timestamp = System.currentTimeMillis(); 130 cacheObject.ageListNode = ageNode; 131 132 // If cache is too full, remove least used cache entries until it is not too full. 133 cullCache(); 134 135 return oldValue; 136 } 137 138 public synchronized V get(Object key) { 139 // First, clear all entries that have been in cache longer than the 140 // maximum defined age. 141 deleteExpiredEntries(); 142 143 CacheObject<V> cacheObject = map.get(key); 144 if (cacheObject == null) { 145 // The object didn't exist in cache, so increment cache misses. 146 cacheMisses++; 147 return null; 148 } 149 // Remove the object from it's current place in the cache order list, 150 // and re-insert it at the front of the list. 151 cacheObject.lastAccessedListNode.remove(); 152 lastAccessedList.addFirst(cacheObject.lastAccessedListNode); 153 154 // The object exists in cache, so increment cache hits. Also, increment 155 // the object's read count. 156 cacheHits++; 157 cacheObject.readCount++; 158 159 return cacheObject.object; 160 } 161 162 public synchronized V remove(Object key) { 163 return remove(key, false); 164 } 165 166 /* 167 * Remove operation with a flag so we can tell coherence if the remove was 168 * caused by cache internal processing such as eviction or loading 169 */ 170 public synchronized V remove(Object key, boolean internal) { 171 //noinspection SuspiciousMethodCalls 172 CacheObject<V> cacheObject = map.remove(key); 173 // If the object is not in cache, stop trying to remove it. 174 if (cacheObject == null) { 175 return null; 176 } 177 // Remove from the cache order list 178 cacheObject.lastAccessedListNode.remove(); 179 cacheObject.ageListNode.remove(); 180 // Remove references to linked list nodes 181 cacheObject.ageListNode = null; 182 cacheObject.lastAccessedListNode = null; 183 184 return cacheObject.object; 185 } 186 187 public synchronized void clear() { 188 Object[] keys = map.keySet().toArray(); 189 for (Object key : keys) { 190 remove(key); 191 } 192 193 // Now, reset all containers. 194 map.clear(); 195 lastAccessedList.clear(); 196 ageList.clear(); 197 198 cacheHits = 0; 199 cacheMisses = 0; 200 } 201 202 public synchronized int size() { 203 // First, clear all entries that have been in cache longer than the 204 // maximum defined age. 205 deleteExpiredEntries(); 206 207 return map.size(); 208 } 209 210 public synchronized boolean isEmpty() { 211 // First, clear all entries that have been in cache longer than the 212 // maximum defined age. 213 deleteExpiredEntries(); 214 215 return map.isEmpty(); 216 } 217 218 public synchronized Collection<V> values() { 219 // First, clear all entries that have been in cache longer than the 220 // maximum defined age. 221 deleteExpiredEntries(); 222 223 return Collections.unmodifiableCollection(new AbstractCollection<V>() { 224 Collection<CacheObject<V>> values = map.values(); 225 public Iterator<V> iterator() { 226 return new Iterator<V>() { 227 Iterator<CacheObject<V>> it = values.iterator(); 228 229 public boolean hasNext() { 230 return it.hasNext(); 231 } 232 233 public V next() { 234 return it.next().object; 235 } 236 237 public void remove() { 238 it.remove(); 239 } 240 }; 241 } 242 243 public int size() { 244 return values.size(); 245 } 246 }); 247 } 248 249 public synchronized boolean containsKey(Object key) { 250 // First, clear all entries that have been in cache longer than the 251 // maximum defined age. 252 deleteExpiredEntries(); 253 254 return map.containsKey(key); 255 } 256 257 public void putAll(Map<? extends K, ? extends V> map) { 258 for (Entry<? extends K, ? extends V> entry : map.entrySet()) { 259 V value = entry.getValue(); 260 // If the map is another DefaultCache instance than the 261 // entry values will be CacheObject instances that need 262 // to be converted to the normal object form. 263 if (value instanceof CacheObject) { 264 //noinspection unchecked 265 value = ((CacheObject<V>) value).object; 266 } 267 put(entry.getKey(), value); 268 } 269 } 270 271 public synchronized boolean containsValue(Object value) { 272 // First, clear all entries that have been in cache longer than the 273 // maximum defined age. 274 deleteExpiredEntries(); 275 276 //noinspection unchecked 277 CacheObject<V> cacheObject = new CacheObject<V>((V) value); 278 279 return map.containsValue(cacheObject); 280 } 281 282 public synchronized Set<Map.Entry<K, V>> entrySet() { 283 // Warning -- this method returns CacheObject instances and not Objects 284 // in the same form they were put into cache. 285 286 // First, clear all entries that have been in cache longer than the 287 // maximum defined age. 288 deleteExpiredEntries(); 289 290 return new AbstractSet<Map.Entry<K, V>>() { 291 private final Set<Map.Entry<K, CacheObject<V>>> set = map.entrySet(); 292 293 public Iterator<Entry<K, V>> iterator() { 294 return new Iterator<Entry<K, V>>() { 295 private final Iterator<Entry<K, CacheObject<V>>> it = set.iterator(); 296 public boolean hasNext() { 297 return it.hasNext(); 298 } 299 300 public Entry<K, V> next() { 301 Map.Entry<K, CacheObject<V>> entry = it.next(); 302 return new AbstractMapEntry<K, V>(entry.getKey(), entry.getValue().object) { 303 @Override 304 public V setValue(V value) { 305 throw new UnsupportedOperationException("Cannot set"); 306 } 307 }; 308 } 309 310 public void remove() { 311 it.remove(); 312 } 313 }; 314 315 } 316 317 public int size() { 318 return set.size(); 319 } 320 }; 321 } 322 323 public synchronized Set<K> keySet() { 324 // First, clear all entries that have been in cache longer than the 325 // maximum defined age. 326 deleteExpiredEntries(); 327 328 return Collections.unmodifiableSet(map.keySet()); 329 } 330 331 public long getCacheHits() { 332 return cacheHits; 333 } 334 335 public long getCacheMisses() { 336 return cacheMisses; 337 } 338 339 public int getMaxCacheSize() { 340 return maxCacheSize; 341 } 342 343 public synchronized void setMaxCacheSize(int maxCacheSize) { 344 this.maxCacheSize = maxCacheSize; 345 // It's possible that the new max size is smaller than our current cache 346 // size. If so, we need to delete infrequently used items. 347 cullCache(); 348 } 349 350 public long getMaxLifetime() { 351 return maxLifetime; 352 } 353 354 public void setMaxLifetime(long maxLifetime) { 355 this.maxLifetime = maxLifetime; 356 } 357 358 /** 359 * Clears all entries out of cache where the entries are older than the 360 * maximum defined age. 361 */ 362 protected synchronized void deleteExpiredEntries() { 363 // Check if expiration is turned on. 364 if (maxLifetime <= 0) { 365 return; 366 } 367 368 // Remove all old entries. To do this, we remove objects from the end 369 // of the linked list until they are no longer too old. We get to avoid 370 // any hash lookups or looking at any more objects than is strictly 371 // neccessary. 372 LinkedListNode node = ageList.getLast(); 373 // If there are no entries in the age list, return. 374 if (node == null) { 375 return; 376 } 377 378 // Determine the expireTime, which is the moment in time that elements 379 // should expire from cache. Then, we can do an easy check to see 380 // if the expire time is greater than the expire time. 381 long expireTime = System.currentTimeMillis() - maxLifetime; 382 383 while (expireTime > node.timestamp) { 384 if (remove(node.object, true) == null) { 385 System.err.println("Error attempting to remove(" + node.object.toString() + 386 ") - cacheObject not found in cache!"); 387 // remove from the ageList 388 node.remove(); 389 } 390 391 // Get the next node. 392 node = ageList.getLast(); 393 // If there are no more entries in the age list, return. 394 if (node == null) { 395 return; 396 } 397 } 398 } 399 400 /** 401 * Removes the least recently used elements if the cache size is greater than 402 * or equal to the maximum allowed size until the cache is at least 10% empty. 403 */ 404 protected synchronized void cullCache() { 405 // Check if a max cache size is defined. 406 if (maxCacheSize < 0) { 407 return; 408 } 409 410 // See if the cache is too big. If so, clean out cache until it's 10% free. 411 if (map.size() > maxCacheSize) { 412 // First, delete any old entries to see how much memory that frees. 413 deleteExpiredEntries(); 414 // Next, delete the least recently used elements until 10% of the cache 415 // has been freed. 416 int desiredSize = (int) (maxCacheSize * .90); 417 for (int i=map.size(); i>desiredSize; i--) { 418 // Get the key and invoke the remove method on it. 419 if (remove(lastAccessedList.getLast().object, true) == null) { 420 System.err.println("Error attempting to cullCache with remove(" + 421 lastAccessedList.getLast().object.toString() + ") - " + 422 "cacheObject not found in cache!"); 423 lastAccessedList.getLast().remove(); 424 } 425 } 426 } 427 } 428 429 /** 430 * Wrapper for all objects put into cache. It's primary purpose is to maintain 431 * references to the linked lists that maintain the creation time of the object 432 * and the ordering of the most used objects. 433 * 434 * This class is optimized for speed rather than strictly correct encapsulation. 435 */ 436 private static class CacheObject<V> { 437 438 /** 439 * Underlying object wrapped by the CacheObject. 440 */ 441 public V object; 442 443 /** 444 * A reference to the node in the cache order list. We keep the reference 445 * here to avoid linear scans of the list. Every time the object is 446 * accessed, the node is removed from its current spot in the list and 447 * moved to the front. 448 */ 449 public LinkedListNode lastAccessedListNode; 450 451 /** 452 * A reference to the node in the age order list. We keep the reference 453 * here to avoid linear scans of the list. The reference is used if the 454 * object has to be deleted from the list. 455 */ 456 public LinkedListNode ageListNode; 457 458 /** 459 * A count of the number of times the object has been read from cache. 460 */ 461 public int readCount = 0; 462 463 /** 464 * Creates a new cache object wrapper. 465 * 466 * @param object the underlying Object to wrap. 467 */ 468 public CacheObject(V object) { 469 this.object = object; 470 } 471 472 public boolean equals(Object o) { 473 if (this == o) { 474 return true; 475 } 476 if (!(o instanceof CacheObject)) { 477 return false; 478 } 479 480 final CacheObject<?> cacheObject = (CacheObject<?>) o; 481 482 return object.equals(cacheObject.object); 483 484 } 485 486 public int hashCode() { 487 return object.hashCode(); 488 } 489 } 490 491 /** 492 * Simple LinkedList implementation. The main feature is that list nodes 493 * are public, which allows very fast delete operations when one has a 494 * reference to the node that is to be deleted.<p> 495 */ 496 private static class LinkedList { 497 498 /** 499 * The root of the list keeps a reference to both the first and last 500 * elements of the list. 501 */ 502 private LinkedListNode head = new LinkedListNode("head", null, null); 503 504 /** 505 * Creates a new linked list. 506 */ 507 public LinkedList() { 508 head.next = head.previous = head; 509 } 510 511 /** 512 * Returns the first linked list node in the list. 513 * 514 * @return the first element of the list. 515 */ 516 public LinkedListNode getFirst() { 517 LinkedListNode node = head.next; 518 if (node == head) { 519 return null; 520 } 521 return node; 522 } 523 524 /** 525 * Returns the last linked list node in the list. 526 * 527 * @return the last element of the list. 528 */ 529 public LinkedListNode getLast() { 530 LinkedListNode node = head.previous; 531 if (node == head) { 532 return null; 533 } 534 return node; 535 } 536 537 /** 538 * Adds a node to the beginning of the list. 539 * 540 * @param node the node to add to the beginning of the list. 541 * @return the node 542 */ 543 public LinkedListNode addFirst(LinkedListNode node) { 544 node.next = head.next; 545 node.previous = head; 546 node.previous.next = node; 547 node.next.previous = node; 548 return node; 549 } 550 551 /** 552 * Adds an object to the beginning of the list by automatically creating a 553 * a new node and adding it to the beginning of the list. 554 * 555 * @param object the object to add to the beginning of the list. 556 * @return the node created to wrap the object. 557 */ 558 public LinkedListNode addFirst(Object object) { 559 LinkedListNode node = new LinkedListNode(object, head.next, head); 560 node.previous.next = node; 561 node.next.previous = node; 562 return node; 563 } 564 565 /** 566 * Adds an object to the end of the list by automatically creating a 567 * a new node and adding it to the end of the list. 568 * 569 * @param object the object to add to the end of the list. 570 * @return the node created to wrap the object. 571 */ 572 public LinkedListNode addLast(Object object) { 573 LinkedListNode node = new LinkedListNode(object, head, head.previous); 574 node.previous.next = node; 575 node.next.previous = node; 576 return node; 577 } 578 579 /** 580 * Erases all elements in the list and re-initializes it. 581 */ 582 public void clear() { 583 //Remove all references in the list. 584 LinkedListNode node = getLast(); 585 while (node != null) { 586 node.remove(); 587 node = getLast(); 588 } 589 590 //Re-initialize. 591 head.next = head.previous = head; 592 } 593 594 /** 595 * Returns a String representation of the linked list with a comma 596 * delimited list of all the elements in the list. 597 * 598 * @return a String representation of the LinkedList. 599 */ 600 public String toString() { 601 LinkedListNode node = head.next; 602 StringBuilder buf = new StringBuilder(); 603 while (node != head) { 604 buf.append(node.toString()).append(", "); 605 node = node.next; 606 } 607 return buf.toString(); 608 } 609 } 610 611 /** 612 * Doubly linked node in a LinkedList. Most LinkedList implementations keep the 613 * equivalent of this class private. We make it public so that references 614 * to each node in the list can be maintained externally. 615 * 616 * Exposing this class lets us make remove operations very fast. Remove is 617 * built into this class and only requires two reference reassignments. If 618 * remove existed in the main LinkedList class, a linear scan would have to 619 * be performed to find the correct node to delete. 620 * 621 * The linked list implementation was specifically written for the Jive 622 * cache system. While it can be used as a general purpose linked list, for 623 * most applications, it is more suitable to use the linked list that is part 624 * of the Java Collections package. 625 */ 626 private static class LinkedListNode { 627 628 public LinkedListNode previous; 629 public LinkedListNode next; 630 public Object object; 631 632 /** 633 * This class is further customized for the Jive cache system. It 634 * maintains a timestamp of when a Cacheable object was first added to 635 * cache. Timestamps are stored as long values and represent the number 636 * of milliseconds passed since January 1, 1970 00:00:00.000 GMT.<p> 637 * 638 * The creation timestamp is used in the case that the cache has a 639 * maximum lifetime set. In that case, when 640 * [current time] - [creation time] > [max lifetime], the object will be 641 * deleted from cache. 642 */ 643 public long timestamp; 644 645 /** 646 * Constructs a new linked list node. 647 * 648 * @param object the Object that the node represents. 649 * @param next a reference to the next LinkedListNode in the list. 650 * @param previous a reference to the previous LinkedListNode in the list. 651 */ 652 public LinkedListNode(Object object, LinkedListNode next, 653 LinkedListNode previous) 654 { 655 this.object = object; 656 this.next = next; 657 this.previous = previous; 658 } 659 660 /** 661 * Removes this node from the linked list that it is a part of. 662 */ 663 public void remove() { 664 previous.next = next; 665 next.previous = previous; 666 } 667 668 /** 669 * Returns a String representation of the linked list node by calling the 670 * toString method of the node's object. 671 * 672 * @return a String representation of the LinkedListNode. 673 */ 674 public String toString() { 675 return object.toString(); 676 } 677 } 678}